|
|
Manna Mouse:
Exploratory Fitness Landscaping
|
A
joint project of
and CapletSecurity
Among interactive artificial
life simulations, Manna Mouse is uniquely simple: a creature's genome
encodes its location on the display area. This simplicity allows
us to see interesting dynamics that are often inaccessible. |
With your mouse you paint manna--the
reward function. By visualizing the fitness landscape, you can quickly
build intuitions about evolution. |
Manna Mouse Applet
You see the evolution of two, separate populations of creatures. A creature's
genotype encodes two values--an x coordinate and a y coordinate. The phenotype
is expressed as a dot on the display area.
For each population, the first generation is determined randomly. Without
a fitness function to selectively steer reproduction, subsequent generations
of creatures appear to be moving randomly through the 2-d space.
Genetic Algorithms were invented by John Holland. See my book
review of John Holland's Hidden Order, appearing in the December
1996 issue of Reason Magazine.
Painting Manna
Click stop.
Mouse down in one of the population areas. Slowly, drag the mouse to paint
manna. Start with something simple, such as a vertical line. The manna
appears in both populations.
Click go.
The distribution of manna is the fitness function; creatures located on
manna are selected for, during reproduction. But manna is consumed, and
eventually, the population returns to random movement.
For GA aficionados, we are using tournaments rather than roulette wheels,
and we do collision avoidance: if a mating would result in creating a
creature in an occupied location, we try again rather than redundantly
search.
Manna Mouse Controls
- go: Start or resume the simulation. You can
change parameters and draw manna while the simulation is running. To
stop it, click stop.
- stop: Stop the simulation. To resume it, click
go.
Manna Mouse Parameters
Note: If you do not see the ui
controls for changing the algorithm's parameters scroll the applet into
view in the browser window.
Set the parameters the same in both populations and watch a few runs;
you will be surprised at the divergence. This is known as sensitivity
to initial conditions: where an evolutionary process ends up depends
not only on the rewards but where it starts.
- population: The population size can be changed.
When increased, the new creatures are placed in randomly-determined
locations.
- mutants: The mutation rate defines the percentage
of the evolving population that has a random bit flipped. These random
mutations can increase the genetic diversity over what is seen with
crossover alone.
- gray: A Gray representation encodes the genotype
in a way that results in adjacent positions differing only by one bit.
Binary representations do not have this property. If a transformation
happens to invoke the hardware's carry operation, adjacent positions
will have very dissimilar genotypes.
Note: Gray representation has not been
implemented yet -- the default is binary.
- uniform: When two creatures mate, how are their
genotypes combined to create their offspring? The two options are uniform
crossover and two-point crossover (seen in bacteria).
In uniform crossover the contribution from each parent is determined
randomly.
In two-point crossover, the two ends of the genotype are joined to form
a ring, removing the significance of the end points. The ring is cut
at two positions, determined randomly. The parents contribute alternate
segments to their offspring. For example, if the rings are cut at positions
A and B, the child's genotype is made up of the segment from
A to B of one parent and the segment from B to A of the
other parent.
- local: Are creatures more likely to mate if
they are closer together?
Note: Spatial locality has not been implemented
yet.
- consumed: Is manna consumed when it is eaten?
The pure notion of a fitness landscape (or function optimization) would
not allow for manna consumption, but it makes for more interesting dynamics.
As the manna is consumed, its color changes from green to red before
finally disappearing.
Javadoc-umentation,
and source code (AWT 1.0):
|
|
|
|