21 Genetic Programming
Control Parameters |
Value |
Description |
|
|
|
|
|
|
Initial population |
500 |
generated with ramp half-and-half |
|
|
method |
|
|
|
Number of generations |
50 |
[0..49] |
|
|
|
Probability of crossover |
90% |
crossover operation is performed |
|
|
on 90% of selected individuals |
|
|
|
Probability of reproduc- |
10% |
copy operation is performed on |
tion |
|
10% of the selected individual |
|
|
|
Probability of mutation |
0% |
mutation is not used here |
|
|
|
Probability of crossover |
10% |
possibly extending program depth |
point being a leaf node |
|
|
|
|
|
Probability of crossover |
90% |
possibly reducing program depth |
point being internal node |
|
|
|
|
|
Maximum tree height |
5 |
maximum allowed program depth |
|
|
|
Number of evaluations |
4 |
starting individual from different |
per individual |
|
positions in the field |
|
|
|
Maximum simulation |
180 |
time limit for each individual to |
time steps per trial |
|
reach the ball |
|
|
|
Table 21.3: Parameter settings
Genetic Programming |
|
|
Lisp |
Lisp |
|
|
Program |
|
|
Engine |
|
|
|
|
Parser |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Population
Eyesim
Simulator
Figure 21.7: Evaluation and simulation procedure
Fitness function In order to determine the fitness for an individual program, we let each program run a number of times from different starting positions. Potentially more robust solutions can be achieved by choosing the starting positions and orientations at random. However, it is important to ensure that all individuals in a generation get the same starting distances for a run, otherwise, the fitness val-
Evolution of Tracking Behavior
ues will not be fair. In a second step, the ball position should also be made random.
Therefore, we run each individual in four trials with a random starting position and orientation, but with a trial-specific ball distance, i.e. the starting positions for all robots for a certain trial are located on a circle around the ball (Figure 21.8).
Figure 21.8: Robot starting positions
The fitness function is the difference between the initial and the final distance between robot and ball, added over four trials with different starting positions (the higher the fitness value, the better the performance):
|
4 |
|
|
f |
¦ disti 0 |
|
disti N |
|
i |
1 |
|
|
Programs with a shorter execution time (fewer Lisp steps) are given a bonus, while all programs are stopped at the maximum number of time steps. Also, a bonus for programs with a lower tree height can be given.
1.6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1.4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1.2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0.8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0.6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0.4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0.2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 12 13 14 15 |
16 17 18 19 |
20 21 22 23 |
24 25 |
Figure 21.9: Maximum fitness over generations
321
21 Genetic Programming
Evaluation results The initial fitness diversity was quite large, which signifies a large search domain for the optimal solution. Figure 21.9 displays the maximum fitness of the population over 25 generations. Although we are retaining the best individuals of each generation unchanged as well as for recombination, the fitness function is not continuously increasing. This is due to the random robot starting positions in the experimental setup. A certain Lisp program may perform well “by accident”, because of a certain starting position. Running the evolution over many generations and using more than four randomly selected starting positions per evaluation for each individual will improve this behavior.
The evolved Lisp programs and corresponding fitness values are shown in Program 21.4 for a number of generations.
Program 21.4: Optimal Lisp programs and fitness values
Generation 1, fitness 0.24
( IF_LESS obj-size obj-size turn-left move-forw )
Generation 6, fitness 0.82
( WHILE_LESS low obj-pos move-forw )
Generation 16, firness 0.95
( WHILE_LESS low high ( IF_LESS high low turn-left ( PROGN2 ( IF_LESS low low move-back turn-left ) move-forw ) ) )
Generation 22, fitness 1.46
( PROGN2 ( IF_LESS low low turn-left ( PROGN2 |
( PROGN2 |
( |
) turn- |
WHILE_LESS low obj-pos move-forw ) move-forw ) |
move-forw |
) |
left ) |
|
|
|
Generation 25, fitness 1.49
( IF_LESS low obj-pos move-forw ( PROGN2 move-back ( WHILE_LESS low high ( PROGN2 turn-right ( PROGN2 ( IF_LESS low obj-pos move-forw ( PROGN2 turn-right ( IF_LESS obj-size obj-size ( PROGN2 turn-right move-back ) move-back ) ) ) move-forw ) ) ) ) )
Speedup through parallelization
The driving results of the evolved program can be seen in Figure 21.10, top. As a comparison, Figure 21.10, bottom, shows the driving results of the handcoded program. The evolved program detects the ball and drives directly toward it in less than the allotted 180 time steps, while the robot does not exhibit any random movement. The evolved solution shows a similar performance to the hand-coded solution, while the hand-coded version still drives along a smoother path.
The enormous computational time required by genetic programming is an inherent problem of this approach. However, evolution time can be significantly reduced by using parallel processing. For each generation, the population can be split into sub-populations, each of which evaluated in parallel on a workstation. After all sub-populations have finished their evaluation, the fitness results can be distributed among them, in order to perform a global selection operation for the next generation.
References
|
|
1400 |
|
mm)
|
1200 |
|
1000 |
|
(1525
|
|
800 |
|
field
|
|
600 |
|
of
|
|
|
|
lengthY,
|
400 |
|
|
|
|
200 |
|
|
0 |
0
|
|
1400 |
|
mm)
|
1200 |
|
1000 |
|
(1525
|
|
800 |
|
of field
|
|
600 |
|
lengthY,
|
400 |
|
|
|
|
200 |
|
|
0 |
0
Evolved
X, width of field (2740 mm)
Hand-coded
X, width of field (2740 mm)
Figure 21.10: Evolved driving results versus hand-coded driving results
21.7 References
BLICKLE, T., THIELE, L. A Comparison of Selection Schemes used in Genetic Algorithms, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology/ETH Zürich, Report no. 11, 1995
BROOKS, R. A Robust Layered Control System for a Mobile Robot, IEEE Journal of Robotics and Automation, vol. 2, no. 1, March 1986, pp. 14-23 (10)
323
