Our GP system was set up to be the same as given in [16, pages 147--155,] except the populations were allowed to continue to evolve even after an ant succeeded in traversing the whole trail, each crossover produces one child rather than two, tournament selection was used and the ants were allowed 600 operations (Move, Left, Right) to complete the trail. The details are given in Table 1, parameters not shown are as [17, page 655,]. On each version of the problem 50 independent runs were conducted.
Since bloating is widespread in GP it is common to impose a limit on the size of programs. Commonly this is in the region of 50, although Koza imposed a maximum depth restriction of 17 on his evolved programs. As we are studying program size the relatively large limit of 500 was used. As we shall see, this allows three separate stages of evolution to be studied: the initial population, bloat and bloat constrained by an upper bound.
Note a limit of 500 allows the evolved programs to be far bigger than required to solve the problem. For example the 100% correct solution given in [16, page 154,] takes about 543 time steps to traverse the Santa Fe trail but has a length of only 18 nodes and this is not the most compact solution possible.
