3 Analysis of Results

Fifty independently random runs, with one graph for each problem and diversity measure are shown in Figures 4.4 to 4.12.

Figure 4.4: Ant, Parity, Quartic and Rastrigin best fitness in population, plotted against the generation number. 50 independently random runs of each problem are shown.

Figure 4.4 shows the best fitness of each generation during the evolutionary process and Figure 4.5 shows the evolution of size, while depth is shown in Figure 4.6. Many runs stop improving after 15-20 generations, with the exception of the Parity problem which continues to make improvements. Previous research by Luke (2001) showed that it is better to carry out short runs (above a critical point) than fewer long runs for the Ant and Quartic problem. Luke also found that with the Parity problem (Even-10), one long run was actually better. This was due to the difficulty of the problem and the ability of genetic programming to consistently make improvements. This critical point was around generation 8 for the Quartic problem and slightly higher for the Ant problem.

Figure 4.5: Average number of nodes vs. generation for the Ant, Parity, Quartic and Rastrigin experiments.

Figure 4.6: Average depth vs. generation for the Ant, Parity, Quartic and Rastrigin experiments.

An early period of higher activity in the runs also exists with respect to diversity measures. There is typically a lot of activity in the early generations and not too much after generation 30.

For the Quartic and Rastrigin experiments, the phenotype diversity in Figures 4.7 shows an initial decrease followed by a sharp increase. This behaviour was also seen with genotype diversity and entropy: an initial sharp decrease was followed by an increase within the Quartic and Rastrigin experiments and in all experiments with genotype diversity. Intuitively, the cause of this initial fluctuation is due to the ease with which improvements can be found in the initial solutions. This initial phase highlights the differences between the experiments. Also, note that phenotype diversity for the Parity experiments continues to increase until the final generation.

Figure 4.7: Ant, Parity, Quartic and Rastrigin phenotype diversity, plotted against the generation number.

Figure 4.8: Average entropy vs. generation for the Ant, Parity, Quartic and Rastrigin experiments.

Figure 4.9: Ant, Parity, Quartic and Rastrigin edit distance One diversity plotted against the generation number.

Figure 4.10: Edit distance Two diversity vs. generation for the Ant, Parity, Quartic and Rastrigin experiments.

Figure 4.11: Genotype diversity vs. generation for the Ant, Parity, Quartic and Rastrigin experiments.

Figure 4.12: Pseudo-isomorph diversity vs. generation for the Ant, Parity, Quartic and Rastrigin experiments.

For all experiments, the edit distance One in Figure 4.9 generally decreases after the initial generation. Also, in Figure 4.10, the populations measured with edit distance Two behave similarly. With this in mind, and because the edit distance Two measure places more importance on the root and higher portions of trees, one can conclude the following: While trees are changing (according to edit distance One) to be more like the best fit tree in each population, the differences between the roots and top portions of the tree also become more similar (according to the edit distance Two measure). This supports previous conclusions [Igel and Chellapilla, 1999,McPhee and Hopper, 1999,Soule and Foster, 1998] that roots become fixed early on in the evolutionary process. Structural convergence is important when considering using a method to control diversity. If structural convergence is beneficial to genetic programming search, then encouraging or forcing structural diversity (edit distance in this case) could have negative consequences. However, the loss of edit distance diversity does not necessarily mean a loss of phenotype diversity or the worsening of fitness, as seen in Figure 4.7 and 4.4.

Lastly, the figures show the behaviour that in some runs fitness continues to increase until the final generation. Identifying the dynamics and properties that allowed for this continued increase is critical for genetic programming practitioners. This is a goal of this research: understanding how to make populations more amenable to improvement. Given the wide range of fitness and diversity, one would like to know if these measures correlate with fitness in any way. Addressing this question is key to understanding if controlling diversity is likely to be effective and how it should be applied to different problem domains.