Every program terminal uses one time unit each time it is executed. This gives us a convenient, if crude, way to estimate the amount of code being used within each program. Figure 14 plots the average number of terminals executed each time a program is run. Initially on average 6.8 terminals are used per program execution, this then rises rapidly to 19.1 before falling back to 9.3 (no penalty). Runs with high penalties are similar except they rise to slightly higher peaks, 26.3, and take longer to fall back to similar values (10.7, 100% penalty). The initial rise in the average may simply be due to selection acting to remove those with lower values, however it appears crossover finds better solutions which execute only a small fraction on their terminals each time the programs are run.
If we assume that there are two frequently occurring cases, either the program starts with the ant facing food or facing an empty square, we can estimate the two parts of the program most often used contain between them no more than twice the y ordinate number of terminals. I.e. less than 20 by the end of the run. This is clearly a very small fraction of the whole (on average programs exceed 300 nodes, and so must contain at least 150 terminals, by the end of the run, cf. Fig. 4). It appears evolution promotes the creation of small islands of useful code in large programs since such programs are less liable to disruption by crossover. Figure 14 implies the essential nature of the evolved (partial) solutions is unchanged by the plagiarism penalty. This is surprising because the stability of such programs in the face of crossover means they will suffer the penalty which should prevent them creating children in the next generation. We now turn to the dynamic fitness function results, and will see in this respect GP evolves significantly differently.
Figure 15:
Time used per call of each program in population
on random trails
as plagiarism penalty is increased.
Mean of 50 runs.
Figure 14:
Time used per call of each program in population
on Santa Fe trail
as plagiarism penalty is increased.
Mean of 10 runs.