3 Issues in Genetic Programming

The genetic programming literature often cites the importance of maintaining diversity to avoid premature convergence toward local optima [Ekárt and Németh, 2000,McKay, 2000,McPhee and Hopper, 1999,Rosca, 1995a,Ryan, 1994]. What does diversity mean to a population-based search algorithm? Certainly, variation is required in the principles of biological evolution. While genetic programming is not the same process that occurs in Nature, there are many different types and possible levels of diversity.

At the center of this thesis are three questions that are related to diversity. By exploring these issues, a clearer understanding of genetic programming and diversity will be achieved. Each of these three questions motivates the research that follows. The questions are:

1. How can diversity be measured and controlled, and are there ideal levels of diversity?

   The numerous references to the culpability of `the loss of diversity' for poor results, e.g. as suggested by the several methods designed to increase diversity discussed in Chapter 4, suggests that the prevention of this loss will somehow improve results. However, it will be shown later that diversity has been measured and used in a variety of ways that are often conflicting.

2. Genetic programming is a population search method, thus, what effect does population diversity have on other aspects of the search process?

   One challenging problem in genetic programming is the increase of solution size that is not accompanied by an increase in solution quality. While the literature describes the mechanics that cause growth, e.g. [Langdon and Poli, 1998a,Luke, 2003,Soule and Heckendorn, 2002], few have argued as done in this thesis that the varied rate of growth is an artifact of population diversity.

3. What specific role does diversity play in the evolutionary process, i.e. do dissimilar individuals contribute offspring differently than the rest of the population?

   The population provides the main reservoir of genetic material from which to produce new solutions. The population is expected, to a degree, to simultaneously occupy different parts of the search space. However, to provide good solutions, it is accepted that the population converges toward one optimum. These two possibly conflicting functions of the population are important to understand, particularly in context of diversity.

The purpose of this chapter is to examine these issues in more detail.