Evolutionary
algorithms Assignment 3
In this question we where asked to solve
the
The code was all written in java so we
had to create an interpreter of our own. The advantage in using java was that we
could easly make a GUI for debugging purposes. Here's the code: src.zip
All the genetic operators and programs
variable where done as described in Coza's paper.
The parameters we used for the algorithm
are:
· Population size – 500
· Generation count – 51
· Genome representation – The genome was
represented as a tree. Each node in the tree represents an expression, the
inner nodes represent the functions and the leaves represent the terminals.
· Fitness calculation function – the
fitness was calculated as described in Coza's paper.
The sum of the product between the sand grain distance from the y axis and the
sand grain value. Sand grins values are (1, 2 and 3).
· Crossover method – Cross over was by
picking a random tree node from each parent and switching between them
(switching a node switches also the node's sub tree).
· Crossover rate – 0.67.
· Mutation method – Mutation was done by
picking a random tree node and growing a new tree instead of him.
· Mutation rate – 0.045.
· Selection method – tournament selection
with K = 7.
First Run results:
It took several runs to get a run that
give us an optimal result, the described run gave us the best individual after
24 generations.
The individual code is:
(IFLTZ (IFDROP (IFLTE
(CARRYING ) (COLOR ) (X ) (GO_W ) ) (IFLTE (GO_N ) (Y ) (GO_W ) (GO_N ) ) )
(IFLTZ (IFLTZ (PICK_UP ) (MOVE_RANDOM ) (GO_E ) ) (IFLTE (GO_W ) (IFLTZ (IFLTE
(GO_E ) (GO_S ) (PICK_UP ) (PICK_UP ) ) (IFLTZ (CARRYING ) (GO_E ) (PICK_UP ) )
(IFLTZ (CARRYING ) (GO_E ) (MOVE_RANDOM ) ) ) (CARRYING ) (COLOR ) ) (IFLTE
(GO_S ) (GO_W ) (CARRYING ) (GO_W ) ) ) (IFLTE (IFLTE (X ) (COLOR ) (PICK_UP )
(Y ) ) (IFDROP (GO_S ) (PICK_UP ) ) (IFLTE (Y ) (GO_N ) (X ) (GO_E ) ) (IFLTZ
(COLOR ) (GO_W ) (MOVE_RANDOM ) ) ) )
As you can clearly see the above code
take grains from somewhere and put them somewhere else. J
Yet after looking at runs from this ant
we saw that the program we got wasn't that good. The program we got know to put
the black grains in place but it might put the green and blue ones (gray and
striped) in the blacks place. So the program succeeded only if it gets very
lucky.
This behavior was caused because
according to the fitness function it is the blue and green grains add less to
the fitness if they are located at the black grains locations.
So we made a change to the fitness
function to give a fine to sand grains that take the place of other sand
grains. We added 4 to the score for each green grain located at a black grain
location, 4 for a blue grain standing at green grain location and 8 for blue
grain standing at a black grain location. Another change we made is to raise
the maximal number of generations to 100.
Second run results
This time we got this little buddy after
74 generations. It the more time to find that program but it gives better
results.
(IFLTE (IFDROP (Y ) (IFLTE (GO_S ) (MOVE_RANDOM
) (GO_E ) (CARRYING ) ) ) (IFLTZ (IFLTE (X ) (GO_N ) (GO_E ) (PICK_UP ) ) (IFLTE
(X ) (GO_N ) (GO_N ) (PICK_UP ) ) (IFLTZ (GO_N ) (CARRYING ) (Y ) ) ) (IFLTE (IFLTZ
(CARRYING ) (GO_E ) (GO_W ) ) (CARRYING ) (IFLTE (PICK_UP ) (Y ) (X ) (COLOR )
) (GO_W ) ) (IFLTE (IFLTE (GO_S ) (CARRYING ) (GO_S ) (GO_W ) ) (IFLTZ (X ) (CARRYING
) (X ) ) (IFDROP (COLOR ) (MOVE_RANDOM ) ) (IFLTE (IFLTZ (IFLTZ (COLOR ) (PICK_UP
) (PICK_UP ) ) (IFLTZ (GO_E ) (GO_E ) (COLOR ) ) (CARRYING ) ) (X ) (IFDROP (IFDROP
(GO_W ) (CARRYING ) ) (CARRYING ) ) (CARRYING ) ) ) )
The best we got from this run gave us
better result in average and it tries to remove grains that are in incorrect
locations.
Code for best of generations 0,5,20,40,72:
Best of generation 0, fitness 177:
(IFLTE (IFDROP (IFLTZ (GO_E ) (GO_E ) (MOVE_RANDOM
) ) (IFLTE (GO_S ) (MOVE_RANDOM ) (GO_E ) (CARRYING ) ) ) (IFLTZ (IFLTE (X ) (GO_N
) (MOVE_RANDOM ) (COLOR ) ) (IFLTE (X ) (GO_N ) (GO_N ) (PICK_UP ) ) (IFLTZ (GO_N
) (CARRYING ) (Y ) ) ) (IFLTE (IFLTZ (MOVE_RANDOM ) (PICK_UP ) (GO_N ) ) (IFLTZ
(GO_W ) (GO_S ) (MOVE_RANDOM ) ) (IFLTE (Y ) (CARRYING ) (Y ) (MOVE_RANDOM ) )
(IFDROP (GO_S ) (CARRYING ) ) ) (IFLTE (IFLTE (GO_S ) (CARRYING ) (GO_S ) (GO_W
) ) (IFLTZ (X ) (CARRYING ) (X ) ) (IFDROP (COLOR ) (MOVE_RANDOM ) ) (IFLTE (MOVE_RANDOM
) (X ) (Y ) (CARRYING ) ) ) )
Best of generation 5, fitness 147:
(IFLTE (IFDROP (IFLTZ (GO_E ) (GO_E ) (MOVE_RANDOM
) ) (IFLTE (GO_S ) (MOVE_RANDOM ) (GO_E ) (CARRYING ) ) ) (IFLTZ (IFLTE (X ) (GO_N
) (MOVE_RANDOM ) (COLOR ) ) (IFLTE (X ) (GO_N ) (GO_N ) (PICK_UP ) ) (IFLTZ (GO_N
) (CARRYING ) (Y ) ) ) (IFLTE (IFLTZ (CARRYING ) (GO_E ) (GO_W ) ) (CARRYING )
(IFLTE (PICK_UP ) (Y ) (X ) (COLOR ) ) (GO_W ) ) (IFLTE (IFLTE (GO_S ) (CARRYING
) (GO_S ) (GO_W ) ) (IFLTZ (X ) (CARRYING ) (X ) ) (IFDROP (COLOR ) (MOVE_RANDOM
) ) (IFLTE (MOVE_RANDOM ) (X ) (Y ) (CARRYING ) ) ) )
Best of generation 20, fitness 132:
(IFLTE (IFDROP (IFLTZ (GO_E ) (GO_E ) (MOVE_RANDOM
) ) (IFLTE (GO_S ) (MOVE_RANDOM ) (GO_E ) (CARRYING ) ) ) (IFLTZ (IFLTE (X ) (GO_N
) (MOVE_RANDOM ) (COLOR ) ) (IFLTE (X ) (GO_N ) (GO_N ) (PICK_UP ) ) (IFLTZ (GO_N
) (CARRYING ) (Y ) ) ) (IFLTE (IFLTZ (CARRYING ) (GO_E ) (GO_W ) ) (CARRYING )
(IFLTE (PICK_UP ) (IFLTE (GO_S ) (IFDROP (GO_W ) (GO_S ) ) (IFLTZ (Y ) (IFLTE (COLOR
) (CARRYING ) (COLOR ) (GO_S ) ) (IFLTZ (COLOR ) (X ) (GO_S ) ) ) (IFLTE (COLOR
) (Y ) (Y ) (PICK_UP ) ) ) (X ) (COLOR ) ) (GO_W ) ) (IFLTE (IFLTE (GO_S ) (CARRYING
) (GO_S ) (GO_W ) ) (IFLTZ (X ) (CARRYING ) (X ) ) (IFDROP (COLOR ) (MOVE_RANDOM
) ) (IFLTE (MOVE_RANDOM ) (X ) (Y ) (CARRYING ) ) ) )
Best of generation 40, fitness 126:
(IFLTZ (CARRYING )
(GO_E ) (GO_W ) ) (CARRYING ) (IFLTE (PICK_UP ) (Y ) (X ) (COLOR ) ) (GO_W ) )
(IFLTE (IFLTE (GO_S ) (CARRYING ) (GO_S ) (GO_W ) ) (IFLTZ (X ) (CARRYING ) (X )
) (IFDROP (COLOR ) (MOVE_RANDOM ) ) (IFLTE (IFLTZ (IFLTZ (COLOR ) (PICK_UP ) (PICK_UP
) ) (IFLTZ (GO_E ) (GO_E ) (COLOR ) ) (CARRYING ) ) (X ) (IFDROP (IFDROP (GO_W )
(CARRYING ) ) (CARRYING ) ) (CARRYING ) ) ) )
Best of generation 74, fitness 100 :
(IFLTE (IFDROP (Y ) (IFLTE (GO_S ) (MOVE_RANDOM
) (GO_E ) (CARRYING ) ) ) (IFLTZ (IFLTE (X ) (GO_N ) (GO_E ) (PICK_UP ) ) (IFLTE
(X ) (GO_N ) (GO_N ) (PICK_UP ) ) (IFLTZ (GO_N ) (CARRYING ) (Y ) ) ) (IFLTE (IFLTZ
(CARRYING ) (GO_E ) (GO_W ) ) (CARRYING ) (IFLTE (PICK_UP ) (Y ) (X ) (COLOR )
) (GO_W ) ) (IFLTE (IFLTE (GO_S ) (CARRYING ) (GO_S ) (GO_W ) ) (IFLTZ (X ) (CARRYING
) (X ) ) (IFDROP (COLOR ) (MOVE_RANDOM ) ) (IFLTE (IFLTZ (IFLTZ (COLOR ) (PICK_UP
) (PICK_UP ) ) (IFLTZ (GO_E ) (GO_E ) (COLOR ) ) (CARRYING ) ) (X ) (IFDROP (IFDROP
(GO_W ) (CARRYING ) ) (CARRYING ) ) (CARRYING ) ) ) )
The following applet shows sample runs
of the programs we got. You can pick the generation you want to see the best of
and the display speed.
In order to view the applet you need to
have JRE 1.5 installed on your computer:
Conclusions:
The