Genetic Programming (GP)
GP is an automated programming technique developed by John Koza
at Stanford University
about GP) . In 1994 I designed and built GeneCode
a GP on a 68K Mac solving the "The Santa Fe Ant Trail" as described in
Koza's Genetic Programming I text. The software built in
C was a GP success in that the ants could successfully traverse a 2D
but a software mistake; an example of disadvantage of object
(sub classing) without a compiler support. My program was never
to PPC Mac or other system.
I would like to start another project in Java, and have a particular
stone based game in mind. The first step will be to see what is
available in Java for GP.
Link to John Koza's site
on genetic programming.
Santa Fe Trail
The Santa Fe Trail is a simple problem where you attempt to train
computer through GP to simulate an ant foraging along a broken trail of
The following is output from my GeneCode program. The search for
evolution of) a program was different every run because I would alter
size of the pool of individuals and because GP uses a randomized
set. Each run is different, and no run is guaranteed to score
well. None of these runs exhibit perfect fitness, however
runs exhibit various approaches as you may expected in a living system.
both close and narrow tracking, wide tracking, and more chaotic
- The environment would be the the black pixel trail of sugar.
- The fitness test is percentage of sugar found in a fixed number
- The instruction set is
- turn left 1/4 turn
- turn right 1/4 turn
- move forward
- branch forward
- is food ahead branch, else
- (I don't believe I used these but they would make good
as the ant had no state information)
- was food here branch, else
- have i been here, else
Color Key: Green indicates a space where the
traveled to without finding food, blue a score - food that the ant
and black food that was not discovered. The ant always beginsin
upper left hand corner. The graph in the bottom left is a the
measure of both the best and average of all ants in green and the best
of a generation in red across the horizontal axis the generation
For these runs the individual pool was between 500 and 2000
This run took the wide but non chaotic approach, but it cannot pass a
in the trail of 4 down.
This run depicts a frequent strategy, a very careful ant.
this ant looks in every direction before moving and only travels in the
that last scored it some food. This approach works flawlessly
the end of the maze where it needs to circle around the last found food
widening circles to get the last two morsels. With this program I
no way (outside of a debugger) of reading the "instructions" generated,
strongly suspect that it commonly follows well because it invariably
left at the last food pixel. The poor ant needs some more state
in its instruction set!
More chaotic approaches tended to be succeeded by a "good tracking"
Here's one that scores over 1/3 and has lasted to the 39th generation.