next up previous contents
Next: 2 Experimental Study using Up: 1 Genetic Lineages Previous: 2 Variation of Loss   Contents

3 Relevance to the Fitness Landscape

If the fitness landscape is smooth with our representation, operator and fitness function, then an application of an operator should cause a relatively small change in fitness. If the landscape is rough, then small changes to an individual by the operator may cause large or small changes in fitness. With a smooth landscape, genetic lineages should be lost quicker. More random changes in fitness between root-parents and offspring occurring with a rough landscape will preserve the most lineages. As it is generally more preferable to have a correlated or smooth landscape, the quicker loss of lineages would be a sign of good search.

However, the loss of lineages also implies genetic convergence and the inability to escape local optima. In canonical genetic programming, using subtree crossover, genetic lineages will begin to share more and more genetic material, from the root downward, during successive generations. As individuals become larger, the size of subtrees inserted into the root parent becomes relatively smaller and at lower points, respectively [Luke, 2003]. Quicker genetic lineage loss leads to quicker genetic diversity loss. The evolutionary process then becomes a sort of local search over the converged population's tree shape(s) and contents.

If the operator, representation and fitness function create a rough landscape, genetic lineages will be lost more slowly, more genetic diversity will be preserved longer and more varied tree shapes and tree contents will remain in the population longer. However, this later convergence time and increased diversity is the consequence of a more uncorrelated landscape, which is generally undesirable. Thus, a paradox exists with respect to loss of lineages and ability of improvement. If the operator works `well', genetic lineages and diversity should be lost rather quickly, getting the algorithm stuck in local optima. If the operator and representation do not work well together and induce a rough landscape, genetic diversity is maintained longer, whereby a more global search may be performed. The loss of genetic lineages is a desirable property as it signifies the correlated landscape in our representation and operator, but it also signifies a loss of diversity which will eventually prevent runs from improving.

Results in Chapter 4 showed that lower genetic diversity was more often correlated with better fitness, supporting the idea that better fitness was achieved when lineages were lost quickly due to a more correlated landscape. The following experimental study serves to further highlight these conclusions about diversity and to provide an analysis of the effects of increased diversity.


next up previous contents
Next: 2 Experimental Study using Up: 1 Genetic Lineages Previous: 2 Variation of Loss   Contents
S Gustafson 2004-05-20