A general GA toolkit implemented in Java, for experimenting with genetic algorithms and handling optimization problems


Contents

The GAA Applet/Application

Examples and Test Problems


 

Overview

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.

 

Browser Requirements and Loading Times

The applet is written in JDK 1.1.5 and uses the new event model. Therefore it requires a browser that supports AWT 1.1. Currently (June 1998) this means MSIE 4.01, Netscape Communicator 4.05 Preview Release (The regular Communicator 4.05 supports only version 1.1.2) or Netscape Communicator 4.0+ with the JDK 1.1 patch. Other options are HotJava 1.1 or using the Java Plugin.

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.

 

General Notes

 

Alphabet


The implementation of the genetic algorithm uses a high alphabet to encode the chromosome's genes. In this implementation, each locus on the chromosome stands for a complete gene or variable. Since Java uses Unicode internally, the available range for the alleles of each gene is 64K, which provides an adequate resolution for most cases.

 

Problem Definition - Definition Files

The input is defined by a Problem Definition file, an Ascii file formatted like a Windows Ini file. Two additional input files are optional: An alleles-definition file and a mapping file. These files are optional since in many cases the input they specify can be created automatically by the program.

 

Problem Definition - Source Modifications

The design of the program is modular, and each module is packaged separately as an easily replaceable (or extendable) class. Of the many classes that make the toolkit, only one should be handled by the user in defining a new problem. This is the GaaFunction class, that contains three methods: getValue, draw and createAllelesMap. The getValue method calculates the individual's fitness, and should obviously be written explicitly for each problem. The draw method is optional, and should be overwritten only if a graphic output is needed. The createAllelesMap is required only when a mapping file is not supplied, and the mapping table should be generated by the program.

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)

 

Special GA Mechanisms

The implementation of the genetic algorithm follows the standard GA structure but it incorporates several less standard mechanisms:

 

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

 

Interactively (on-the-fly) defined functions

The GA Playground supports optimization of functions and expressions defined on-the-fly. The user can enter an expression of arbitrary length and complexity, with up to 20 variables, define range constraints for each variable, and let the program search for an optimized (minimum or maximum) solution. This option is available only in application mode (cannot be run in a browser).

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 (metlov@fzu.cz), and its site is at http://galaxy.fzu.cz/JEL/.

 

Continuous Reporting

The applet user-interface supports three tools for monitoring the evolution process. Each is switchable, the trade off being performance (switched off) versus information (switched on). They are: The text window, where textual information is continuously displayed (when the text window is enabled), the graphic window that supports the draw method of the GaaFunction class when relevant (e.g. in TSP problems), and the Log window, that can gather information in the background and be displayed on request. All these tools can be toggled on or off anytime, including during execution.

 

Graphic Display

The program's Gui provides a graphic window which can optionally be used for displaying graphic representation of the evolutionary process. Problems of geometrical nature, such as TSP or resource allocation problems, are natural candidates for taking use of this option. To use the graphic option it is required to override the "draw" function in the user-modifiable GaaFunction file. The graphic display can be turned on or off at any time, including in the course of the evolution process.

 

User-Initiated Logging

In addition to the switchable continuous reporting, the user can output information to the log file at any time. While the evolutionary process is going on, it is possible to log current chunks of data, such as a list of the current population (list of current chromosome strings), or a description of the current mating process (in the format: Father + Mother => Kid => Mutated Kid). The population list can be printed in several formats, some more suited for short chromosomes, other for longer ones. All logging functions are accessible through the Log menu. Saving the log file to disk is possible only in application mode, while displaying the log file on screen is available in any mode. The log file can be viewed (or saved) either during the calculation process or afterwards, and can be used to analyze what happened during the evolutionary process.

 

File Input/Output

 

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).

 

Online Help

The GA Playground assumes some familiarity with genetic algorithm programs, and the help is relatively concise. There are three help utilities

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.

 

Download and Installation

The GA-Playground can be downloaded to be run from local hard disks. The program can be run either as an applet (from any browser supporting JDK 1.1.5), or as an application (running on a JDK 1.1.5 VM).
Please download the GaPlayground.zip (about 470K) and unzip it to any directory. The same files are used for both applet and application modes.

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:
java GaaApplet [Parameters File].
The Parameter file name is optional: When not given the "All Demos" version (All.par) will be activated by default.

Examples:
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.

Example:
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:
CLASSPATH=.;tabsplitter.jar;ScsGrid.jar;jel.jar;gaa.jar
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
Get the code GA Playground Source Code

 

Limitations and Request for feedback

The GA Playground is currently at a preliminary stage, still under construction. The options for definitions of new problems are not fully implemented yet, and there is no Java documentation, so it is currently limited to playing with the defined problems. When playing with the parameters (or preparing new parameters files in the application mode), please be careful with your input parameters, as there is no protection against illegal entries

I shall be glad to receive any comments or suggestions. Please use my mailbox for any sort of feedback.

 

Examples and Test Problems

Note: If you wish to run the examples in full-screen mode, click the Full-Screen button (in left panel) before selecting an example, then select the item from the links in the page rather than from the menu.

General

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.

Important Notes:


List of Demo Problems

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:
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)
Knapsack:
Single
0/1-Knapsack
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
Bin Packing:
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
Facility Allocation:
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)
Multi-modal Functions:
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
Function Optimization:
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]