next up previous contents
Next: 5 Summary Up: 4 Analysis of Diversity Previous: 3 Scatter Plots of   Contents

4 Discussion of Diversity Measures

The measures studied here are in a sense related hierarchically with respect to the amount of information they contain about the population. The edit distance measures provide a fine grain description of population structure and content differences, pseudo-isomorphs give an aggregated view of the population and the genotype diversity measure simply describes the number of unique genotypes. Entropy and phenotype diversity are similarly related. Entropy not only describes the number of unique phenotypes, but also how the population is distributed over the existing phenotypes. Also, the experimental study shows the most consistent correlation between edit distance and fitness and between entropy and fitness, suggesting that these measures capture an important element in the genetic programming search process. The pseudo-isomorph diversity measure was used to capture a level of information that is more specific than genotype diversity, but less expensive than edit distance. Pseudo-isomorph diversity expressed stronger correlations than genotype diversity and is generally more correlated to edit distance measures.

The experiments used different measures of diversity and have enabled the analysis of not only the measures and how they correlate with fitness, but also the behaviour of standard genetic programming on commonly used problems. Results showed additional evidence that the roots of trees become fixed very early on in the genetic programming evolutionary process and are unlikely to change. This has been demonstrated by previous research [Igel and Chellapilla, 1999,McPhee and Hopper, 1999,Soule and Foster, 1998] and is supported here by the edit distance diversity measures.

Phenotypic diversity and entropy are important due to the ability of selection to distinguish between individuals better and maintain a constant pressure. Depending on the problem and behaviour of the current run, the increase and decrease of phenotype and entropy diversity is likely to be crucial at different stages of evolution. This change of selection pressure could be beneficial in helping to avoid local-optima for some problems. The constantly fluctuating values of phenotype diversity in Fig. 3 could be demonstrating this behaviour. However, based on the experiments and analysis, it is not clear if this is necessarily the case.

The Spearman correlation coefficient showed a positive correlation between fitness-based diversity and fitness, and a negative correlation between edit distance diversity and fitness. A hypothesis to explain this behaviour is that more structurally similar populations create a neighbourhood in which crossover is likely to find better neighbours. Crossover initially works with very unlike structures until a significantly good one is found. Then, combined with the selection pressure, the population begins to resemble this good individual as crossover repeatedly combines more and more similar individuals. Success at this point suggests that crossover is able to work within this population structure to find better solutions. The results have shown how quickly edit distance diversity is lost. It appears that this crossover-friendly neighborhood occurs early in the evolutionary process, but might also be responsible for leading the search toward inescapable local-optima rather quickly. The point here is not to argue that crossover is (or is not) a sufficient operator for search in tree-based genetic programming, but to show (in cases where genetic programming is solving problems) how populations and recombination operators may be working together.

However, just as the correlation coefficient suggests associations between diversity and performance, it should not be used to infer causation between variants, i.e. higher diversity does not necessarily cause better performance but better performance is seen with higher diversity (phenotype diversity here). Caution should also be taken considering that the search mechanism's recombination and selection methods play an extremely important role in shaping individuals and populations. Very simple implementation differences can drastically increase or decrease diversity measures. Models of causation based on diversity results should be defined carefully. Later in Chapter 6, lengths are taken to validate a causal relationship, relying on experimental evidence, previous literature and further experimental evidence on a specially constructed model of genetic programming behaviour.

Standard genetic programming is often compared to a random search or a hill-climber, due to the loss of diversity and the attraction to local optima [Gathercole and Ross, 1996,McPhee and Hopper, 1999,Poli and Langdon, 1998a]. The results on diversity presented here also support the hypothesis of uneven exploration and exploitation phases. After an initial period of adjustment to different problem representations and selection, the populations appeared to converge toward less edit distance diversity. These initial few generations of each run appear to represent the exploration phase, while the latter part of the run exploited the better individuals. Adaptive controls of diversity, selection pressure or mutations could be used to extend the exploration phase to allow more global search. However, they should also consider the initial settling behaviour observed here, which is likely due to the ease of which initial good solutions can be found.

Based on the results presented here, it is hypothesised that strong convergence and exploitation of a common structure occurs in almost all runs, but not all runs exploit a good structure. Thus, genetic programming may be converging to structures which are not amenable to further improvements with respect to the existing population. If the algorithm backtracked upon finding a bad structure, or made a concentrated effort to find a good structure, it could be argued that it is more likely to exploit better structures. In essence, by either increasing the length of exploration or adaptively exploring in later phases, local-optima may be avoided more effectively. Increased population sizes, higher levels of mutation, weaker selection pressure and models which prevent the overall convergence of populations (such as islands, demes or distributed models) could achieve this effect.


next up previous contents
Next: 5 Summary Up: 4 Analysis of Diversity Previous: 3 Scatter Plots of   Contents
S Gustafson 2004-05-20