The problem of programming an artificial ant to follow the Santa Fe trail has been repeatedly used as a benchmark problem. 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 may be 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. 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.
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. This is expected 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 we use to evolve solutions to it are briefly described in Section 2, our results are given and discussed in Section 3, and in Section 4 we give our conclusions.