Programming a Simple Robot
with a GA
Target: solve Program a robot with the moves north, south,
east, and west to find the exit of a given maze in the most efficient way.
By: Aviv Ron (ronav@cs.bgu.ac.il)
(www.cs.bgu.ac.il/~ronav)
Genome: an array of Integers in the range [0,3] that represent the directions N,E,S,W respectively.
I chose a length of 30 for the
genome to encourage versatility. A longer genome is just a waste of time and
shorter can lead to early convergence.
Fitness Value: for each step in the maze the fitness grows by 1. this includes a step into a wall which leaves the robot in
the same room.
The count stops upon exiting
the maze or reaching the end of the genome.
So a genome which reached the
exit in less steps will have a smaller fitness. We are
looking to minimize the fitness.
I also gave a bonus for
genomes which manage to exit the maze and subtracted 5 from their fitness, so
if the robot managed to exit in 9 steps, his fitness would be 5, this is the best fitness an individual can have.
Selection: Tournament Selection with tournament size 2. I
found this size to be most efficient because it improved the versatility of the
individuals and lead to better results.
Crossover: choose two random points in the genomes size range
and swap the parents values between these two points.
Mutation: Select one random point in the genome and assign a
random direction to it.
The Application: written
in Java 1.5. Source code and an executable jar can be downloaded here.
(to run the jar application in Windows just double
click the run.bat file after unzipping).
The Results: see below for plots.
All Runs were made with:
population size 250
400 generations
Cross P 0.7
Mutation P 0.15
Tournament size 2
|
Run no. |
Best Fitness |
Avg. Fitness |
Generation of Best individual |
|
1 |
5 |
5 |
38 |
|
2 |
5 |
5 |
260 |
|
3 |
6 |
6 |
20 |
|
4 |
6 |
6 |
19 |
|
5 |
5 |
6 |
45 |
|
6 |
5 |
7 |
220 |
|
7 |
6 |
5 |
66 |
|
8 |
7 |
7 |
26 |
|
9 |
5 |
5 |
366 |
|
10 |
6 |
6 |
59 |
|
Average |
5.6 |
5.8 |
111.9 |
(yellow
rows indicate an optimal solution found)
Conclusions: half of the runs managed to find the shortest path (10
steps) out of the maze, which is a good result. The rest had one or two
redundant steps in their route. The generation of the best individual is very
versatile and spans from 19 (earliest) to 366 (latest).
We can see most runs started
with an average fitness around 28 and managed to reach an average fitness of
5-7 by the end of the run which shows a very nice improvement from the routes
in the beginning, demonstrating nice performance by the GA in this matter.
Run 1 found the shortest
route:
This found the next route:
Run 2 found the shortest path:
Which found the next route:
Run 3 missed the shortest path by 1 step
The route:
|
|
We can see that it has a “redundant” south move (painted blue) |
Run 4 missed the shortest route by 1 step:
The route:
Run 5 sound the shortest path:
The route: 
Run 6:
Run 7:
Run 8:
started with a bad south step and made another later on
Run 9:
Run 10:
