Better Trained Ants
Previous:Better Trained Ants
The problem of programming an artificial ant to follow the Santa Fe trail has been repeatedly used as a benchmark problem [Jefferson et al. 1992, (John Muir trail),], [Koza1992,Lee and Wong1995,Chellapilla1997,Harries and Smith1997,Luke and Spector1997,Ito et al. 1998,Kuscu1998]. Recently we have shown performance of several techniques is not much better than the best performance obtainable using uniform random search [Langdon and Poli1998]. We suggested that this was because the program fitness landscape is difficult for hill climbers and the problem contains multiple levels of deception which also makes it difficult for Genetic Algorithms.
Analysis of high scoring non-optimal programs suggests many reach high rewards even though they exhibit poor trail following behaviour. Typically they achieve high scores by following the trail for a while and then losing it at a corner or gap. They then execute a random search until they stumble into the trail at some later point and recommence following it (see Fig. 1). The random search may give them a better score than a competing program which successfully navigated the same bend or gap but lost the trail later (see Fig. 2). In Figs. 1 and 2 the ant's path is shown by the bending line with arrows, uneaten food pellets by black squares, eaten food by squares with horizontal crosses, shaded squares show gaps in the trail.
Figure 1:
Example program from 
generation, eats 40 pellets
Figure 2:
Example program from 
generation, eats 38 pellets
Here we redefine the problem. The same trail is used but we only place food onto the grid as the ant following along the trail nears it. This makes it difficult for an ant which moves away from the trail to find another part of it by random search. This changes the fitness landscape. We anticipate that almost all optimal points within it will retain their scores and many previously high scoring non-optimal points will be given reduced fitness by the new training regime. (Of the 3916 solutions to the Santa Fe trail problem found by exhaustive search, uniform random and ramped half-and-half random search [Langdon and Poli1998], all but at most 2 completed the trail.
These solutions are available via anonymous ftp from ftp.cs.bham.ac.uk directory pub/authors/W.B.Langdon/gp-code file antsol.tar.gz). We also extend interim results presented in [Langdon1998a] by requiring the ant to find food quickly, by including its speed in the fitness function and by solving the problem using one point crossover. The changes to the fitness function are intended to make the landscape less deceptive and so easier for genetic algorithms. Removal of false peaks may also benefit hill climbing techniques.
The ant problem and the GP system we use to evolve solutions to it are briefly described in Sect. 2, our results are given and discussed in Sect. 3, and in Sect. 4 we give our conclusions.
Better Trained Ants
Previous:Better Trained Ants