Genetic Algorithm Experiment


alt="Your browser understands the &ltAPPLET> tag but isn't running the applet, for some reason." Your browser is completely ignoring the &ltAPPLET> tag!
Source Code

Overview

This applet demostrates a continuous value genetic algorithm on a variety of problem spaces with a variety of reproduction methods. The problem spaces were adapted from Ackley(1). The Restart button reinitializes the population with random individuals. The Run/Pause button starts and stops the simulation. The Population Count field specifies how many individuals are initialized during a restart. You must press Enter in the field to set this value. The Reproduction Method choice changes how the next generation is created from the current generation. The Fitness Function choice changes the fitness landscape. The first time you go to a function, it will take a while to generate a picture of the landscape. Reproduction Divergence specifies how close child points are to the parent points during crossover. You must press in this field for the value to take effect. Random Divergence adds a random element to the reproduction divergence.

This program is meant to help visualize the processes in a genetic algorithm. The 2D space being searched is simple and easy to understand, but may not be generate behavior representative of higher dimension spaces. The result of crossing two points is the missing corner of an isosceles trianges that can be generated by adding a point to the two points. The divergence factor determines the angles of this triangle and thus the distance of the new point from the old points.

Descriptions of Problem Spaces

    Function 1: A mostly maximal surface. Most searches do well here.

    Function 2: A sloped plane with no local maximum. Hillclimbing is very effective here.

    Function 3: A hill. Again there is no local maximum. Hillclimbing is very effective here too.

    Function 4: Two hills, one slightly higher than the other. Helps demostrate the dangers to converging too quickly.

    Function 5: A sloped plane with a local maximum.

    Function 6: A space with many local minium. A global function still specifies the global maximum. A search method needs to be able to jump between peaks.

    Function 7: The same space as function 6, but the local maximums are more pronounced. It is more difficult to jump between peaks.

    Function 8: A space with large local maximum surrounding the global maximum. It is difficult to get to the global maximum without finding a local maximum.

    Function 9: A space with a small area with value 1.0 and everything else zero. There is nothing to learn from here. All seaches have difficulty with this type of space.

Descriptions of Reproduction Methods

    Fitness Roulette: The probability of an individual being selected in the population is equal to the fitness value normalized with respect to the total fitness of the population. This method takes advantage of individuals that make large jumps in improvement by giving them a much greater chance of reproducing. The problem is that if the slope of the problem space in the area being explored can cause this preference to be either far to great or far too small. Watch this on Function 2. The population will generally converge about halfway up the slope. At this point, the fitness values of the individuals are very close and none of them has a distinct advantage to be selected for reproduction.

    Sorted Roulette: Sorted roulette attempts to solve the problems of fitness roulette by sorting the population by fitness, and then selecting for reproduction with some bias toward the front of the list. This applet takes a random number between 1 and 0, squares it, and multiplies it by the size of the population to get the index of the reproducing individual. This technique does not take advantage of differences between fitness values, but it makes the fitness function much easier to evaluate.

    Fitness Generational: I wrote this applet to experiment with an idea I had. It is based on the idea that individuals should be mated with individuals that are "close" to them. In many cases "close" does not have an obvious meaning. I am guessing that individuals with similar parents are close to each other. The GA maintains a tree of parents. One individual is selecting using fitness roulette, but the mate is found by travelling up the family tree a random distance and then randomly travelling back down to the current generation. This results in sub-populations that explore local areas of the fitness space. This technique tends to ignore global tendencies however since it converges on several local maximums very quickly. The basic idea is to preserve diversity in the population.

    Sorted Generational: This is the same as fitness generational, but it uses a sorted roulette method to select the first individual.

    Hillclimb Best Individual: This select the best individual in the population and generates random points around that individual.

    Elitist Random Search: This moves the best individual to the next population and generates random values for the remainder.


References:
(1) Ackley, David. "A Connectionist Machine for Genetic Hillclimbing." Kluwer Academic Publishers, Norwell, Massachusetts, 1987.

Backlinks:
D2/362 Part II: Lisp materials

Back