Foundations of Genetic Programming

The idea of fitness landscapes, firstly proposed in genetics by Sewall Wright [Wright, 1932], is well established in artificial evolution. They are a metaphor used to help visualise problems. In the metaphor landscapes are viewed as being like an area of countryside. Looking vertically down from a great height the countryside appears like a map. This corresponds to the area to be searched. That is, the plan view is the search space.

Since John Holland’s work in the mid-1970s and his well known schema theorem [Holland, 1975, Goldberg, 1989b], schemata are often used to explain why genetic algorithms work. Schemata are similarity templates representing entire groups of chromosomes. The schema theorem describes how schemata are expected to propagate generation after generation under the effects of selection, crossover and mutation. The usefulness of schemata has been recently criticised (see for example [Altenberg, 1995, Macready and Wolpert, 1996, Kargupta, 1995, Kargupta and Goldberg, 1994]) and many researchers nowadays believe that Holland’s schema theorem is nothing more than a trivial tautology of no use whatsoever (see for example [Vose, 1999, preface]). However, as stated in [Radcliffe, 1997], the problem with Holland’s schema theorem is not the theorem itself, rather its over-interpretation.

In Chapter 4 we introduced pessimistic schema theories for genetic programming in which schemata are treated as subsets of the search space. These two theories (Rosca’s and ours) do not take schema creation into account and consider only the worst-case scenario for schema disruption. As a result they only provide lower bounds for the expected number of members of the population matching a given schema at the next generation.

This chapter considers different ways in which we can use the schema theory described in the previous chapters to better understand the dynamics of genetic programming populations. We will also illustrate the possible uses of the schema theory to clarify concepts such as effective fitness (next section), biases in GP (Section 6.2), building blocks (Section 6.3), problem hardness and deception (Section 6.5). We also discuss new ideas inspired by schema theories (Section 6.4).

We shall investigate how the space of all possible programs, i e the space which genetic programming searches, scales. Particularly how it changes with respect to the size of programs We will show, in general, that above some problem dependent threshold, considering all programs, their fitness shows little variation with their size. The distribution of fitness levels, particularly the distribution of solutions, gives us directly the performance of random search. We can use this as a benchmark against which to compare GP and other techniques. These results are demonstrated in this chapter using a combination of enumeration and Monte Carlo sampling. For the interested reader, formal proofs are given in Chapter 8. Informal; arguments are presented in Section 7.5 to extend our results to modular GP, memory and Turing complete GP. Section 7.6 considers the relationship between tree size and depth for various types of program. We finish this chapter with a discussion of these results and their implications.

We start this chapter by formally proving results given in Chapter 7 for linear and tree based GP. The rest of the chapter gives proofs for other properties of program search spaces. The implications of these results have been previously discussed in Section 7.7. For the reader who does not wish to study the proofs in detail, the main results are summarised next.

In genetic algorithms, deception (i.e. false peaks in the fitness landscape) has long been recognised as an important barrier to performance however in genetic programming it has not received the recognition it deserves. In this and the next chapter we study two benchmark problems using the techniques described in the previous chapters. These show that deception is one of the reasons why these problems appear to be hard.

In this second chapter on the application of our analysis techniques, we consider a second GP benchmark problem: the “Max Problem”. Briefly, this problem is to find a program, subject to a size or depth bound, which produces the largest value [Gathercole, 1998]. This problem is unusual in several respects: we know in advance what the solution is, what value it returns and and exactly how many solutions there are. Also, the size or depth limit is fundamental to the problem. MAX is hard for GP because of the way deception interacts with size and depth bounds to make it difficult to evolve solutions.

While genetic programming with one-point crossover behaves like a genetic algorithm (see Sections 4.4.6–4.4.8), the question of convergence in genetic programming, with standard subtree crossover has a mixed history. Using experimental evidence, we will suggest that bloat in GP is a manifestation of convergence.

The role of this concluding chapter is twofold: to summarise the major contributions but also to draw lessons.