As expected limiting the amount of uneaten food in front of the ant along the trail made the task of evolving suitable programs easier for GP. This can be seen in Fig. 3 which plots the estimated minimum number of individuals that GP with a population size of 500 needs to create in order to have a probability of at least 99% of finding at least one solution. (This is known as ``effort'' required, cf. [Koza1992, page 194,], see also Table 2). We estimate of the variability of the effort data by calculating the minimum effort assuming the proportion of successful runs at each generation is increased or decreased by one standard deviation. These are given as the (max) and (min) values in Table 2 and by error bars in Figs. 3 and 4.
Figure 3:
Effort v. no. food pellets ahead the ant can see and eat.
Error bars indicate estimates given by one standard deviation above
and below minimum measured figure.
Original Santa Fe trail always allows all 89 food pellets to be seen.
Figure 4 plots effort with various restrictions on the maximum program size. Data points are calculated from at least 50 runs using the original Santa Fe trail, only placing five food pellets ahead of the ant (i.e. x=5) and allowing the energy available to the ant to increase as it moves along the Santa Fe trail (see next section). No run found any of the very smallest solutions (of length 11).
Considering first the original problem (crosses and long dashed line in Fig. 4). The minimium estimate for the effort is 189,000 which occurs with a size limit of 100. Values for 25--100 are similar at about two thirds of the effort required when no size limit is imposed. Also effort values for size limits of 200--500 appear to be much the same as when there is no size limit. The error bars are large as most data points are based on about 10 runs (out of 50) which quickly found a solution.
Now consider the case where food is only placed on the grid as the ant approaches it in along the trail (i.e. x=5, dimonds and solid line in Fig. 4). The minimium estimate for the effort is 104,000 and occurs with a size limit of 50. Values for 25--100 are similar at about 80% of the effort required when no size limit is imposed. Again effort values for size limits of 200--500 appear to be much the same as with no size limit. The effort bars are smaller as data are estimated from more succesful runs. Fig. 4 also gives data from [Chellapilla1997].
Figure 4:
Effort v. maximium program size
for original Santa Fe trail and ant restricted to look
ahead of 5.
Points offset slightly to improve presentation.
Table 2: Effort (in 1,000s) to solve Santa Fe Trail
(no program size restriction)