What is the ICE Applet?
The applet above executes what is called a genetic algorithm (GA). To
facilitate understanding, every step in the GA is animated. This particular GA
evolves solutions to a simple board game I created just for this purpose. This
program also detects and reports if any irreducibly complex (IC) solutions arise
during the evolution of its population of solutions to the board game.
Click here
for more information on the concept of irreducible complexity.
Click here
for more information on Genetic Algorithms.
The Control Bar
After clicking anywhere on the title screen, the applet will display the
following control bar.
The seven controls are, from left to right, the Play/Pause button, the Slow
Speed button, the Medium Speed button, the Fast Speed button, the IC button, the
Threshold button, and the Exit button.
Play/Pause Button
Clicking the Play/Pause button starts and stops the GA animation, as the name
implies. Initially the animation is stopped and this button must be clicked to
begin the GA.
Slow, Medium, and Fast Buttons
These three buttons control the speed of the animation. Slow and medium
speeds are for observing the details of the GA in operation. Fast speed is
considerably quicker than both the slow and medium speed. When set to fast speed, entire
generations tick by in fractions of a second. Use slow and medium speed to learn
how the GA functions and how the board game works; use fast speed to rush ahead
many generations.
IC Button
The IC button toggles the GA between two modes. In the first mode ("IC" in
black text) the GA will check every individual it produces to see if it is
irreducibly complex (IC). An individual will be considered IC if the following
three conditions hold:
- It has non-zero fitness (see below for an explanation of fitness)
- It has at least five "parts".
- Removal of any of its parts results in fitness dropping to zero.
If an IC individual is discovered, the animation will pause, and the message
"INDIVIDUAL IS I.C." will be displayed.
In the second mode ("IC" in gray text) the GA will not bother checking for IC.
Threshold Button
The Threshold button (the circle with the letter "T") toggles the GA between
another two modes. In the first mode (letter "T" in black text) the initial
value of the game ball will drop by one point whenever an individual evolves with
fitness greater than a particular threshold (50). See below for an explanation
of the game ball, and how its initial value affects fitness. A lower initial
value for the game ball makes the game more difficult, so when it drops all
individuals in the population must have their fitness recalculated. Keep the GA
in threshold mode to produce an IC individual (doesn't always happen, of course).
Exit Button
Clicking the Exit button (the circle with the letter "X") takes you back to
the title screen, and the program resets.
The Board Game
The GA evolves a population of solutions to a board game I made up. Here is a
snapshot of the game in play.
The game board consists of 100 boxes in ten rows and ten columns. The game
ball (a circle with a number in it) falls downward through the game board until
it reaches the bottom and falls off. Along the way it can move down, left, or
right, but never up. The number written in the ball indicates its point value.
The value of the ball can change as it falls through the board, and its initial
value (15 points) can change from generation to generation (see "Threshold
Button" above). The ball enters in column four, which is marked at the top of
the board by a purple rectangle. The ball will continue moving straight down
until it encounters one of the following four types of boxes, indicated with the
letters S, A, L, and R:
S ("Split" box)
When a game ball passes through a Split box, it gets split into two balls,
each having the same value as the original. If the original ball enters from
above, the two balls emerge headed left and right. If the original ball enters
from the right, one emerges headed left, the other down. If the original
ball enters from the left, one emerges headed right, the other down. The only
exceptions are Split boxes at the far left/right of the board (columns 0 and 9)
which don't split game balls at all since the extra ball would have nowhere to
go.
A ("Add" box)
When a game ball passes through an Add box, its value increases by one point.
Also, it continues moving in the same direction it was headed when it entered
the box.
L ("Left" box)
When a game ball encounters a Left box, it attempts to make a left turn (from
the ball's point of view). When entering from the left, a left turn would point
the ball upward, which is not allowed, and in such a case the ball exits the box headed
down.
R ("Right" box)
When a game ball encounters a Right box, it attempts to make a right turn
(from the ball's point of view). Just as with Left boxes, upward motion is not
allowed, and a ball entering from the right will be pointed downward instead.
Representation
The Split, Add, Left and Right boxes on the game board come from the
"genetic" material of an individual in the population. The individual (or
solution) is shown as three strings of digits and letters below the game board.
The first string indicates which columns the Split, Add, Left and Right boxes go
in, the second line indicates which rows, and the third indicates which types of
boxes. In the snapshot above, for example, the first letters of each line
indicate that in column 3, row 5 there should be a Left box (L). The individual
is "decoded" from left to right, so that if more than one box is specified for
the same location on the board, the one furthest right in the "genetic" material
ends up on the final game board.
Keeping Score
At the bottom of the game board, in red text, is the number of points
collected ("0 pts" in the snapshot image above). Only balls that fall off the
board in column five (marked at the bottom by a purple rectangle) get their
points added to the total. Once all game balls have fallen off the board, the
fitness of the solution is calculated as: total points subtract length of
"genetic" material. Subtracting the length of the "genetic" material can be
thought of as a kind of selection pressure put on the population to coax
individuals to get more points with fewer boxes. A fitness value less than or
equal to zero is considered a non-solution, and such individuals are "dead".
Since fitness values below zero are just as good as zero, negative fitness
values are changed to be zero. Unless the entire population has fitness zero,
such "dead" individuals are not available as parents for the next generation.
Generations
A single generation in the GA has three steps:
- Fitness evaluation. Each individual whose fitness is not known gets to play the board game in order to determine its fitness.
- Selection. The population is sorted based on fitness and the worst ten individuals in the population are wiped out. Any of the ten remaining, if they have zero fitness, are also wiped out.
- Reproduction. Those individuals remaining after selection become the parents of the next generation. The individuals wiped out by selection are replaced by mutated copies of the remaining individuals, or by crossover of two of the remaining individuals.
The current generation number is shown in small text below the game board.
Population
The 20 individuals making up the GA population are shown to either side of
the game board. They will move about on screen as they take part in various GA
operations such as fitness evaluation, mutation, and crossover.
Population Initialization
The initial random individuals in the population have been generated in
such a way as to boost their chances of being viable (attaining fitness
higher than zero). Without this boost, many initial populations would be
composed entirely of nonviable individuals. Their boxes are placed on the
board only in a restricted rectangular area. Also, each is the best of six
such randomly generated individuals. This could have been avoided by using
a larger population size, but a population of 20 was chosen in order to
make it easier to place all individuals on the screen at once.
Download
Click here
to download a zip archive of all the files needed to run this applet on your home computer.
Click here
to download a zip archive of the source code (in Java).
Folks Linking to the ICE Applet
The following websites have linked to this applet.
