Examples and Test Problems
The GA Playground is a general purpose genetic algorithm toolkit where the user can define and run his own optimization problems. The toolkit is implemented in the Java language, and requires (when used as an application, in its full mode), a Java compiler and a very basic programming knowledge (just enough for coding a fitness function). Defining a problem consists of creating an Ascii definition file in a format similar to Windows Ini files, and modifying the fitness function in the GaaFunction source file. In addition, other methods can (optionally) be overwritten (e.g. the drawing method), other classes can be extended or replaced, and additional input can be supplied through Ascii files.
The GA Playground is primarily designed to be used as an application and not as an applet, since it requires re-compiling of at least one class and use of local file I/O. In addition, it is a little heavy as an applet, taking a relatively long loading time over the net. However, although its use as an applet does not enable defining new problems with new fitness functions, it enables extensive playing with many variations of an already existing problem type, by opening every aspect of the problem definition to the user. For example, any TSP test problem can be loaded through the 'Parameters' module. Used as an applet, the toolkit takes advantage of the Java cross-platform nature and the cross-world nature of the Internet, to bring a GA Playground to anyone interested in experimenting with genetic algorithms.
Updated info (2003): The program requires JDK between 1.1.5 and 1.4 (it will not run under JDK 1.4 or higher). Therefore, the applet will not run in a browser using version 1.4 (or higher) plugin. The application can be run using an appropriate java version (all past versions are downloadable from the Sun Archive.The applet is large and takes a relatively long time to load. It uses four jar files, the first is about 100K and the other three about 50K each. Please be patient until the loading process is finished. When the GA Playground is used as an application (the program's natural mode), and loaded locally and not from the Internet, the loading time is obviously very short.
Besides these, any class can be extended or re-written to create a different genetic algorithm (e.g. the GaaMutation class or the GaaCrossover class)
1. An automatic 'Kick': A sensor in the program monitors the evolutionary process, and when it finds that there has not been any advance in the recent N generations (N is user definable), it gives the population a 'Kick' and scrambles it a little (in a user defined manner). This mechanism helps against the GA tendency to get stuck at a mediocre local optimum.
2. A kin-competition compensating factor: If a population contains identical individuals, only one of them receives the nominally calculated fitness. The others are assigned decreased fitness values. This helps to maintain diversity in the population, and reduces the danger of the whole population being taken by a single, relatively superior, individual. The evolutionary justification for this mechanism (a justification is not really needed, but anyway), is that identical individuals compete over the same niche, so that although each might possess good genes, the very existence of the others makes it more difficult for him.
3. Memory: Each individual in a population owns both a chromosome (a solution string) and a memory string, where history data can be recorded. The use of the memory string is optional. If required, the memory maintenance code can be included in the fitness function.
4. Pre & Post Breed Functions: These two functions (empty by default) are activated just before and just after breeding takes place (correspondingly). This enables to add any extra processing to the old population (preBreed) or to the new population (postBreed) during the process of creating a new generation
The interactive function optimization code is based on the Java Expressions Library (JEL), an amazing library that enables fast evaluation of dynamic string expressions. The library was written by Konstantin Metlov (firstname.lastname@example.org), and its site is at http://galaxy.fzu.cz/JEL/.
1. Application Mode IO: Both input and output files can be saved to and loaded from disk. Parameters that were modified interactively can be saved to a file, and loaded later as a new problem definition. Parameter files (as well as all other Ascii files) can be edited in a text editor, saved (optionally under different names) and later used to define different problems
Population of strings can be saved, together with the their function and fitness values, to be studied and analyzed. Saved population files can be loaded (completely or partially) into the program, to define a specific population with known individuals. The population file can be edited in order to modify strings (chromosomes) or create new ones.
Finally, the log screen that optionally stores information about the evolutionary process, can also be saved to disk for subsequent examination.
2. Applet Mode IO: When used as an applet, the GA Playground cannot access user's local disk. Therefore input can only be modified through the multi-tabbed Parameters module. This module supports editing of any aspect of the problem definition, as long as it uses the same fitness function. Output is limited to screen, but it can be copied and pasted to another application through the clipboard (I am talking Windows here).
1. Online Help Screens: Two basic help screens (General Help and Input Files Help) are accessible from within the program (Help menu).
In addition there are two compact context-sensitive help mechanisms, which are particularly relevant to the parameters (input) panels:
2. Automatic Tool-Tip: A short help string is automatically displayed in the status bar when the cursor is over a particular component (Textfield, label or button). This automatic mechanism can be toggled on or off through the Options menu.
3. Right-Mouse-Button click: An additional short help string can be displayed in the status bar by clicking the right mouse button when the cursor is over a particular component. This second help tip complements the automatic help tip described above.
Documentation: Currently there is only an empty, skeleton Javadoc documentation. While I have all the good intentions of filling it with real documentation, it might take some time. Meanwhile it can be used, with some intuition and possible trial-and-error, as a basis for extending and subclassing GA Playground classes. The classes can be retrieved by expanding the gaa.jar file.
For defining new problems, a new fitness function and possibly other methods must be defined. All these methods are contained in GaaFunction.class. You can replace the original GaaFunction of GA Playground with your own class. The jar file (gaa.jar) should be expanded in order to access the class file. The file GaaFunctionExample.java can be used as a template for building a new class with a different problem (or problems). This source file is freely downloadable in zipped version too. Use it in conjunction with corresponding .par and .gmp files to define any optimization problem.
Applet Mode: Just load any of the Html problem files into your (JDK 1.1.5 capable) browser. The file gaa.html (this file) contains an index of all the demo problems, and can be used to load any of them. However, any specific problem can be loaded directly into the browser (e.g. TspDemo.html). In any case, once the applet is loaded, any of the demo problems can be loaded through the Ga/Entry Screen menu.
Application Mode: The application is activated by the command:
To run the "All Demos" version: java GaaApplet
To run the TSP demo of Bavarian cities: java GaaApplet bayg29.par
Classpath (Application mode): When used as application the three jar files of the GA Playground should be defined in the CLASSPATH variable. Each one should be entered separately.
If you unzipped the GaPlayground.zip file into C:\GAPL directory, your Classpath assignment should be similar to the following:
set CLASSPATH=.;C:\GAPL\gaa.jar;C:\GAPL\ScsGrid.jar;C:\GAPL\tabsplitter.jar; C:\jel.jar
Application Batch File: On Windows you can create an icon that activates a batch file for running GA Playground as an application.
The batch file should be similar to the following:
java GaaApplet %1
Assuming the batch file is named RunGaa.bat, entering "RunGaa" at the command prompt will activate GA Playground with the default (problem selection) mode, while entering e.g. "RunGaa TspDemo.par" will run the specific TspDemo problem.
Javadoc files: The "skeleton" Javadoc files set is packaged as a zip file and can be downloaded It is a little thin, but it might be useful.
Source Code Download: All the source code can now be downloaded and used freely. Please give appropriate credit where the code is used, and let me know about interesting enhancements or code evolution
I shall be glad to receive any comments or suggestions. Please use my mailbox for any sort of feedback.
If you will look at the source of any of the following Demo Html pages (by the View Source function in your browser), you will see that each activates the same Java class file (GaaApplet.class), the only difference is the ascii definition file that is given as a parameter to the applet. In each case, all the class files used are the same. The only exception is the GaaFunction.class, which either should be specific for each problem definition, or contain several alternative functions that are activated according to the specific problem code.
Once you load a specific example, you can change the problem definition (by modifying problem attributes, variables ranges and variables mapped values) and also experiment with the genetic algorithm by playing with any of the GA parameters.
|Multiple Problems Applets|
|All Demos||All the demo problems: In this configuration you can select any of the examples listed below, and switch between them. Selection is done from the applet's 'Entry Screen' (GA menu)|
|TSP on circle||A Tsp where all cities are located on a circle. The number of cities is user definable.|
|TSP Bayg29||TSP of 29 Cities in Bavaria (Groetschel,Juenger,Reinelt)|
|TSP Att48||TSP of 48 capitals of the US (Padberg/Rinaldi)|
|A single knapsack problem with 50 objects|
|Weing1: multiple 0/1-Knapsack||A multiple knapsack problem with 2 knapsacks and 28 objects|
|Weish01: multiple 0/1-Knapsack||A multiple knapsack problem with 5 knapsacks and 30 objects|
|Binpack1 u120_00||120 objects uniformly distributed in (20,100), bins of size 150|
|Binpack5 t60_19||60 objects in 'triplets' of items from (25,50), bins of size 100|
|Steiner on circle||A facility allocating problem (where all cities are on a circle)|
|Steiner by file||A facility allocating problem (where city coordinates are read from a file)|
|Ackley's Function||A multi-modal test function:
Minimize f(x) = 20+e-20*exp(-0.2*(sqrt((1/n)*sum(x(i)^2))-exp((1/n)*sum(cos(2*Pi*x(i)))
|Rosenbrock's Function||A multi-modal test function:
Minimize f(x) = sum(100*(x(i)-x(i-1)^2)^2 + (1-x(i-1))^2
|Schwefel's Function||A multi-modal test function:
Minimize f(x) = 418.9829*n + sum(-x(i)*sin(sqrt(abs(x(i))))
|Rastrigin's Function||A multi-modal test function:
Minimize f(x) = 10.0*n + sum(x(i)^2 - 10.0*cos(2*Pi*x(i)))
|Griewank's Function||A multi-modal test function:
Minimize f(x) = 1/4000*sum(x(i)-100)^2 - prod((x(i)-100)/sqrt(i)) + 1
|Sphere Model||A well known test function:
Minimize f(x) = sum((x(i)-1)^2)
|Single Variable Minimization||Minimize f(x) = x^4 - 12*x^3 + 15*x^2 + 56*x - 60|
|Multi Variable Minimization||Minimize f(x1,x2,x3,x4,x5) = x1*sin(x1) + 1.7*x2*sin(x1) - 1.5*x3 - 0.1*x4*cos(x4+x5-x1) + (0.2*x5^2-x2) - 1|
|Simpleton||A Trivial 10 Variables Maximization Problem:
Maximize: (x1*x2*x3*x4*x5)/(x6*x7*x8*x9*x10) where (x1..x10)=[1..10]