As the applications of GP have expanded it has become more urgent that we understand how and why the process works when it does, and how and why it fails when it fails. Only on the basis of a solid theoretical understanding of these issues can we intelligently apply or enhance the technique. Early theoretical approaches, based for example on the schema theorem from traditional genetic algorithms, made little progress because of several factors including GP's richer representations, variable length genotypes, and execution semantics for individuals. Neither have attempts to avoid theory, relying for example on blind faith in the power of recombination and natural selection, produced sufficiently satisfying answers to questions about how and why GP works or doesn't work.
Chapter 8, ``The Evolution of Size and Shape'' by W. B. Langdon, Terry Soule, Riccardo Poli and James A. Foster investigates the phenomenon of growth in program size in GP populations. This has been known for some time but previous explanations have not been completely satisfactory. The authors start from the basics -- What is the nature of the search space upon which GP operates? That is, what are program search spaces like? How big are they, i.e. how many possible programs are there? What shapes can they have? How are program shapes (particularly tree shapes) distributed in the search space? How is program performance (i.e. fitness) distributed in the space? They present a maximum likelihood (maximal entropy) model of bloat, which simply suggests programs evolve towards the part of the search space containing the most programs of the current best fitness level. This not only explains the evolution of program length but also program shape (which had not previously been considered). The chapter also considers various GP specific mechanisms in bloat and proposes two new genetic operators which considerably reduce bloat. The keenly interested reader should also read Chapter 11 where Rosca and Ballard also propose a bloat-reducing genetic operator which is derived from an analysis with a different perspective. As well, in Chapter 16, Ito, Iba and Sato propose new genetic operators that foster the protection and growth of building blocks. Their evaluation shows that their self-tuning mechanism also can address bloat.
Chapter 9, ``Fitness Distributions: Tools for Designing Efficient Evolutionary Computations'' by Christian Igel and Kumar Chellapilla, is an important landmark in the theoretical analysis of subtree mutation operators. Recently there has been impressive experimental work on mutation-only GP [Chellapilla, 1997], and in this chapter the authors start to lay theoretical ground work for this work by analysing the effectiveness of a total of 11 different subtree operators within evolving populations on a total of four benchmark problems. Their analysis yields important conclusions about these operators and recommendations for their future use.
Chapter 10, ``Analysis of Single-Node (Building) Blocks in Genetic Programming'' by Jason M. Daida, Robert R. Bertram, John A. Polito 2, and Stephen A. Stanhope, addresses the crux of the crossover versus mutation debate in automatic program generation (cf. Chapter 9). That is the question of ``building blocks''. Do they exist in program parse trees? If so, are the current mechanisms effective in finding them and building complete solutions from them? If not, can more effective mechanisms be devised? The authors empirically analyze the evolutionary process as it combines and exploits the most primitive potential building block in GP -- terminals which are ephemeral random constants. Their investigation provides qualified support for the notion of simple building blocks within the current GP framework, but they warn that GP dynamics are complex. They further suggest that the notions of genotype and phenotype need careful rethinking when used in the context of GP.
Chapter 11, ``Rooted-Tree Schemata in Genetic Programming'' by Justinian P. Rosca and Dana H. Ballard, turns GP on its head. Instead of viewing the GP process as forming solutions in a ``bottom up'' fashion it suggests GP solutions evolve from the root down in a ``top down'' fashion. They present detailed quantitative analysis of several important aspects of the dynamics of GP. Following a review of work on Genetic Algorithms (GAs) population dynamics in terms of the schema theorem and Price's Theorem they present a GP schema theorem based on rooted-tree schema. They then extend this to consider the phenomenon of increase in program size in GP and a common response to it, adding a parsimony bias to the fitness function. Their theoretical analysis suggests values for the strength of the parsimony bias which they experimentally verify using the parity and Pac-Man problems. In addition, further analysis indicates that schema growth needs to be controlled so that the size of a program does not influence the likelihood of a tree-schema's survival during crossover. Two methods of exercising this control are delineated and one, which adapts the probability of disruption of a tree as a function of its size, is shown to be effective on the parity and Pac-Man problems.