Genetic Algorithms in Squeak

http://www.ConsultAr.com/Squeak/GA

Description

We have developed a Genetic Algorithm Framework based on the classic ideas described in Goldberg 1989 and Mitchell 1997.

The framework implements the operation of selection, mutation ans crossing-over. We added memetic-algorithm capabilities through an implementation of a local search based on hill climbing and dynamic hill climbing. Mutation operations are based on random gaussian-like distribution, so small adjustments are more likely than drastic ones (Numerical Recipes). Selection is implemented with Tournament or with Roulette Wheel and Elite, in Roulette Wheel you can chose Sigma Fitness Scaling or Linear Fitness Scaling.

We exploited the modelling capabilities of Smalltalk and the visualization an development capabilities of Squeak. We priorized these things in spite of the apparently low performance of Smalltalk and Squeak. We think that our decision:

allowed us to have an interesting framework up and running very quickly,
allows us to easily find and improve the framework and adapt it to new areas,
and wil allow you to use our framework to learn about Genetic Algorithms and apply it to your own optimization problem.

Samples

We included some samples, the classical OnesCountIndividual and some De Jong's Function (1 to 4). Each class contains a test method where you can explore how to use the framework. Some extra description is available in the classes comments

OnesCount: The goal is to obtain an Indivual of all 1, the fitness is the number of 1 in the Individual.
DeJongFunction: The goal is to maximize/minimize these functions. In the Goldberg book exists a graph and a description for each function.

Visualization

These graphs show some information about the run of the algorithm (click to see bigger images)

The first plot shows the Fitness evolution, the blue line shows the maximun fitness, the red shows the average and the green one show the minimal fitness in each generation.
The second graph plot a point each time a better individual was found. These graph can help to see if the algorithm is converged.
The third graph shows the fitness evolution but in diferent way: each generation has a line, in the line each pixel represent an Individual, the color of the pixel is proportional to the fitness, so you can see that the algorithm get 'colored'.
Optionaly you can graph similar plots but on Scaled Fitness.

References

Goldberg, David E. 1989. Genetic Algorithms in search, optimization, and machine learning. Addison-Wesley.
Mitchell, Melanie. 1996. An introduction to Genetic Algorithms. MIT Press. Cambridge, Massachusetts. London, England.
Teukolsky and W. T. Vetterling. 1996. Numerical Recipes. The Art of Scientific Computing. Cambridge University Press. Cambridge, London.

Download

Genetic_Algorithms.2.cs.gz (January 15, 2000): These changeset will work in a 2.8 image.

Testing and Quick View

For an quick overview of the framework open an morphic project, leaves the Transcrip open and evaluate some of these expressions:

OnesCountIndividual test.
DeJongF1ParameterIndividual test.
DeJongF2ParameterIndividual test.
DeJongF3ParameterIndividual test.
DeJongF4ParameterIndividual test.