next up previous contents
Next: 2 Search, Evolutionary Algorithms Up: 1 An Analysis of Previous: 3 Contributions   Contents

4 Overview

Chapter 2 introduces search, heuristics, evolutionary algorithms and genetic programming. An in-depth examination of genetic programming follows. The algorithm, representation and operators are described before an introduction is given to common benchmark problem domains. Two important research issues and a metaphor of genetic programming search are then discussed.

Chapter 3 discusses three major issues which are evaluated in this thesis. First, the representation and possible definitions of diversity are examined to highlight the complexity of diversity measures and methods. Secondly, the effects of diversity on other aspects of the search process is emphasised to demonstrate the wide-reaching issue of population diversity. The chapter concludes by discussing the role the population plays in producing new solutions to guide search is discussed.

Chapter 4 begins the first of four chapters which represent the original contributions in this thesis. Measures and methods of diversity are surveyed from the literature. Common measures are used, along with novel population diversity measures, in an experimental study to assess the correlation between diversity and fitness at different stages of evolution. The results emphasise the contrasting behaviour between the common measures of diversity. Also, the most important diversity measures appear to be the ones that capture information relevant to other processes, such as selection and recombination.

Chapter 5 develops a diversity method based on genetic lineages. This method, lineage selection, is used to demonstrate how and why increasing the diversity of populations may be beneficial for some problems and not for others. Results suggest that many problems benefit or suffer from a hill-climbing type search. When hill-climbing is interrupted by lineage selection, performance is sometimes improved, sometimes worsened. To further investigate the type of search genetic programming performs, the sampling of unique behaviours and structures is analysed. Results provide a clearer characterisation of search on several problem domains.

Chapter 6 explores the effects diversity has on other aspects of the search process. A causal relationship is found between difficulty, diversity and code growth. Initially these results are reinforced by examining related literature, and then verified with a simplified model of genetic programming. The results indicate that increased difficulty leads to both non-decreased selection pressure and less structurally diverse populations, both of which contribute to an increased rate of code growth.

Chapter 7 explores the role of dissimilar individuals in the population and the effectiveness of migrant individuals in distributed models. Several definitions of genetic difference are used to probe these relationships on a new, constructed problem. The study looks at the ability of different subpopulations to produce offspring with high survivability. A survey of previous methods used to encourage distributed evolution is presented. A model is then proposed that explicitly identifies dissimilar solutions and places them into an environment where they will be most effective.

Chapter 8 states the conclusions, lists the contributions and summarises the problem-specific results obtained throughout the thesis. Recommendations for future research then follow.


next up previous contents
Next: 2 Search, Evolutionary Algorithms Up: 1 An Analysis of Previous: 3 Contributions   Contents
S Gustafson 2004-05-20