next up previous contents
Next: 1 Lineage Selection Up: 5 Genetic Lineages and Previous: 3 Relevance to the   Contents

2 Experimental Study using Lineage Selection

To better understand the effects diversity has on search, a simple method is used based on genetic lineages to increase the genetic diversity of populations. No elitism, size, shape or content bias is added. Three problem domains are investigated and compared with previous research to understand why increasing diversity is beneficial in some domains but not others.

The definition of genetic lineages, described in the previous section, is combined with tournament selection to redirect selection pressure from the fit to the fit and diverse. As lineages provide an approximation of diversity in canonical genetic programming, this technique does not require a measure of diversity, but it significantly changes populations during the evolutionary process. The goal of this study and technique is to demonstrate that increasing diversity can lead to dramatic changes in the search ability of genetic programming. Population convergence and increased selection pressure of similar individuals creates a `hill-climbing' atmosphere which, when disturbed, can improve or worsen fitness, depending on the problem. Neither method, genetic programming or hill-climbing, is proposed to be better than the other. Instead, the similarities and differences between the methods are used to explain the effects of changing diversity.

One of the main challenges of search in general is preventing the system from getting stuck in local optima. As highlighted in earlier chapters, convergence is often associated with the inability of the run to improve, but it is also related to the exploitation phase during the evolutionary process. Many problem and representation specific methods have been used to improve diversity. While some methods of diversity show improvement of fitness, they typically add elitism, suffer from additional computation and address a problem which is not clearly defined or understood. How does one know what type of diversity is needed and how much of it is necessary for different problems? As stated by Ryan (1994), ``...what is needed is a method which does not attempt to explicitly measure genetic differences, for this leads to much difficulty when defining exactly what constitutes difference''. Also, it can be difficult to understand why a problem would benefit from different types and levels of diversity.

Figure 5.2: An example of lineage selection. An individual (ind) is randomly chosen from a randomly selected lineage to compete against $T$ others in a tournament.
\begin{figure}\centerline{\psfig{figure=chapters/ch6figs/lineage-selection.eps,width=12cm}}\end{figure}



Subsections
next up previous contents
Next: 1 Lineage Selection Up: 5 Genetic Lineages and Previous: 3 Relevance to the   Contents
S Gustafson 2004-05-20