Genetic Algorithms and Genetic Programming
Genetic algorithms are fast becoming a hot area of
computer science research. Propelled into popularity
by the pioneering work of John Holland at the
University of Michigan in the 1970's, genetic
algorithms have been successfully utilized in problem
areas previously thought intractable.
The concept of genetic algorithms is very simple.
A problem is mapped into a chromosome expression and
the principals of fitness proportionate selection and
crossover mating are implemented to successively evolve
populations of proposed solutions that over time evolve
to an acceptable solution to a problem.
Genetic programming takes the genetic algorithm one
step further, by mapping the problem such that we are
looking for an algorithm. The desired algorithm is then
evolved by generating random algorithms and successively
reproducing them using the genetic principles of fitness
proportionate selection and crossover mating.
The advantage of evolving logo algorithms is that the
results are visual and can show inheritance is a striking
way. This allows a student of genetic algorithms to get
a visual sense of how the algorithms evolve over time,
and in what ways they evolve.
Logo Expressions and Programming
Logo is a graphical programming language. It has been
around for many years, and is currently popular for
teaching simple programming principles to students.
It is exceptionally good for this task, since the
concept of the turtle is much easier to grasp than
that of a CPU, and the results of the programs are
visual, providing good feedback and motivation.
Logo Life takes the logo language and reduces it to
an extremely simple subset. The reasons for this are
many, but the primary reason is that the reduction is
required to make the genetic algorithm feasible.
LogoLife Turtle Language
The following description attempts to convey
the syntax of the Evolved Turtle Logo programming
language:
algorithm => expr
expr => ( terminal )
or
( function expr_list )
expr_list => expr ...
terminal => One of the following:
FWD_1, FWD_2, FWD_3, FWD_5, FWD_10, FWD_50, FWD_100
These commands move the turtle the number of
specified steps forward from its current position
in the direction it is facing. If its stick is down,
drawing occurs as the turtle moves.
LEFT_1, LEFT_2, LEFT_3, LEFT_5, LEFT_10, LEFT_15, LEFT_45, LEFT_90
These commands turn the turtle the specified number
of degrees to the left from its current direction.
RIGHT_1, RIGHT_2, RIGHT_3, RIGHT_5, RIGHT_10, RIGHT_15, RIGHT_45, RIGHT_90
These commands turn the turtle the specified number
of degrees to the right from its current direction.
function => One of the following:
BLOCK
This command executes the expressions in its expression list.
REPEAT_2, REPEAT_3, REPEAT_5, REPEAT_10, REPEAT_50, REPEAT_100
These commands repeat the expressions in their expression
list the specified number of times.
IF_PEN_UP, IF_PEN_DOWN
These two commands execute the first expression in their
expression list if true, otherwise they execute the second
expression.
Creating Your Own Turtles
You can use any text editor to create a turtle
logo expression and paste the expression into a
population to help with its evolution, or to
explore new evolutionary paths. Furthermore, if
you copy a turtle to the clipboard, you will then
be able to paste the turtle's program into a text
editor. This way, you can evolve a turtle, edit the
program to change the turtle, paste it back into the
population to evolve it further and mate it with other
turtles.
For example, you might type in the following program
and paste it into a turtle's square that you select
in a population window:
( REPEAT_2 ( REPEAT_2 ( FWD_100 ) (RIGHT_90 ) ) )
The logo expression above would draw a square with sides 100 steps long. You might also try this expression:
( REPEAT_5
( FWD_100 )
( RIGHT_45 )
( RIGHT_5 )
( RIGHT_10 )
( RIGHT_10 )
( RIGHT_2 )
)
Or you might try this one:
( REPEAT_100
( FWD_100 )
( RIGHT_90 )
( RIGHT_10 )
( RIGHT_10 )
( RIGHT_5 )
( RIGHT_3 )
)