In our previous work [Langdon and Poli1998] we suggested reasons why the original Santa Fe ant problem is difficult for Genetic Algorithms. However we hoped that the improved training techniques above would have rendered the search space less deceptive. In this section we investigate using one point crossover [Poli and Langdon1997] and point mutation. Performance of one point crossover with point mutation was found to be similar to standard crossover.
The parameters we used were the same as for standard GP crossover (as given in Table 1) except those shown given in Table 3. The principal difference, apart from replacing the crossover operator, is to use point mutation on the children produced by crossover. Normally point mutation is applied with a low probablity for each terminal or function (program node) in the program. When the probablity comes up, point mutation replaces the node with a randomly chosen terminal or function which takes the same number of arguments. Thus point mutation does not change either the mutated program size or shape. Usually there is no check the replacement is different and so there is a finite chance of selecting the same function or terminal, in which case the mutation makes no change. In the case of the ant problem both the terminal and function sets are small and in practice the chance of each point mutation making no change is about 50%. Rather than simply doubling the mutation rate, we provided a difference check. Using this we ensure point mutation is guaranteed to make exactly one change to mutated programs. This avoids doubling the mutation rate, which can lead to many programs suffering multiple changes while still leaving an appreciable fraction unchanged.
The results of one point mutation using both the improved training regime and the original are given in Table 2. From these it is clear that one point crossover with point mutation has a similar performance to standard GP on the Santa Fe problem and the mechanisms limiting initial amount of food or energy (described in the previous sections) have not been demonstrated to be beneficial with one point crossover and point mutation. Other experiments indicate that point mutation on its own is not sufficient and some crossover is needed (albeit at a low rate).
Table 3:
One Point Parameters (as Table 1 unless stated)