1 Artificial Ant

Langdon and Poli (2002) described the Ant problem to be highly deceptive for genetic programming. The problem contains numerous solutions with a lot of symmetry and there is no `guiding' force to encourage the Ant to travel any particular path. The authors also showed that the Ant problem is solved better using genetic programming than simulated annealing and hill-climbing techniques. Only population based, mutation-only search performed considerably better, as did a variant of strict hill-climbing, which allowed for trees that were smaller and larger than those that would be typically produced by subtree crossover. As population search only uses mutation, it should maintain a high amount of diversity and be similar to performing several hill-climbing searches in parallel. This search method should deal with deception better and not get stuck in local optima as frequently, which explains better performance.

Figure 5.6: The generation in the Ant problem where the best fitness of the run was found is plotted against the best fitness of the run. Single standard deviation bars are plotted for both means in all directions.

Lineage selection also adds a similar component of parallel search to the Ant problem. High edit distance diversity is maintained and selection pressure is reduced, creating a parallel hill-climbing effect that escapes local-optima better. When an individual becomes stuck in local optima because of deception, a diverse population is likely to contain another individual which is significantly different and allows the run to continue. Lineage selection increases or maintains higher entropy longer with more fitness values or more uniform distributions. In the control experiments, entropy quickly rises and then declines, suggesting a short period of exploration and a higher likelihood of being stuck in local optima. Also, note that in Figure 5.5 the weighted edit distance between best of generation individuals is considerably higher with lineage selection between generations 10-30, the same generations where the entropy values between experiments diverge. The difference between the best individuals in this phase is found closer to the root with lineage selection. A more explorative search phase appears to be taking place with lineage selection.