Source Code

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.

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

**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