Schema theories are among the oldest and the best known models of evolutionary algorithms (Holland, 1992; ?). Schema theories are based on the idea of partitioning the search space into subsets, called schemata. They are concerned with modelling and explaining the dynamics of the distribution of the population over the schemata. Modern genetic algorithm schema theory (Stephens and Waelbroeck, 1997, 1999) provides exact information about the distribution of the population at the next generation in terms of quantities measured at the current generation, without having to actually run the algorithm.
The theory of schemata in GP has had a difficult childhood. Some excellent early efforts led to different worst-case-scenario schema theorems (Altenberg, 1994; Koza, 1992; O'Reilly and Oppacher, 1994b; Poli and Langdon, 1997; Rosca, 1997; ?). Only very recently have the first exact schema theories become available (Poli, 2000a,b, 2001a) which give exact formulations (rather than lower bounds) for the expected number of individuals sampling a schema at the next generation. Initially (Poli, 2000b, 2001a), these exact theories were only applicable to GP with one-point crossover (see Section 5.3 ). However, more recently they have been extended to the class of homologous crossovers (Poli, McPhee, and Rowe, 2004) and to virtually all types of crossovers that swap subtrees (Poli and McPhee, 2003a, b), including standard GP crossover with and without uniform selection of the crossover points (Section 2.4 ), one-point crossover, context-preserving crossover and size-fair crossover (which have been described in Section 5.3 ), as well as more constrained forms of crossover such as strongly-typed GP crossover (see Section 6.2.2 ), and many others.
Other models of evolutionary algorithms include models based on Markov chain theory (e.g. (Davis and Principe, 1993; Nix and Vose, 1992)) and on statistical mechanics (e.g. (Prügel-Bennett and Shapiro, 1994)). Markov models have been applied to GP (Mitavskiy and Rowe, 2006; Poli et al., 2004; Poli, Rowe, and McPhee, 2001), but so far they have not been developed as fully as the schema theory model.
Exact mathematical models of GP are probabilistic descriptions of the operations of selection, reproduction, crossover and mutation. They explicitly represent how these operations determine which areas of the program space will be sampled by GP, and with what probability. These models treat the fitness function as a black box, however. That is, there is no representation of the fact that in GP, unlike in other evolutionary techniques, the fitness function involves the execution of computer programs on a variety of inputs. In other words, schema theories and Markov chains do not tell us how fitness is distributed in the search space. Yet, without this information, we have no way of closing the loop and fully characterising the behaviour of a GP systems which is always the result of the interaction between the fitness function and the search biases of the representation and genetic operations used in the system.