An Overview of Schema Theory <s> The Schema Theorem for Genetic Algorithms <s> This paper is the second part of a two-part paper which introduces a general schema theory for genetic programming (GP) with subtree-swapping crossover (Part I (Poli and McPhee, 2003)). Like other recent GP schema theory results, the theory gives an exact formulation (rather than a lower bound) for the expected number of instances of a schema at the next generation. The theory is based on a Cartesian node reference system, introduced in Part I, and on the notion of a variable-arity hyperschema, introduced here, which generalises previous definitions of a schema. The theory includes two main theorems describing the propagation of GP schemata: a microscopic and a macroscopic schema theorem. The microscopic version is applicable to crossover operators which replace a subtree in one parent with a subtree from the other parent to produce the offspring. Therefore, this theorem is applicable to Koza's GP crossover with and without uniform selection of the crossover points, as well as one-point crossover, size-fair crossover, strongly-typed GP crossover, context-preserving crossover and many others. The macroscopic version is applicable to crossover operators in which the probability of selecting any two crossover points in the parents depends only on the parents' size and shape. In the paper we provide examples, we show how the theory can be specialised to specific crossover operators and we illustrate how it can be used to derive other general results. These include an exact definition of effective fitness and a size-evolution equation for GP with subtree-swapping crossover. <s> BIB001 </s> An Overview of Schema Theory <s> The Schema Theorem for Genetic Algorithms <s> A few schema theorems for genetic programming (GP) have been proposed in the literature in the last few years. Since they consider schema survival and disruption only, they can only provide a lower bound for the expected value of the number of instances of a given schema at the next generation rather than an exact value. This paper presents theoretical results for GP with one-point crossover which overcome this problem. First, we give an exact formulation for the expected number of instances of a schema at the next generation in terms of microscopic quantities. Due to this formulation we are then able to provide an improved version of an earlier GP schema theorem in which some (but not all) schema creation events are accounted for. Then, we extend this result to obtain an exact formulation in terms of macroscopic quantities which makes all the mechanisms of schema creation explicit. This theorem allows the exact formulation of the notion of effective fitness in GP and opens the way to future work on GP convergence, population sizing, operator biases, and bloat, to mention only some of the possibilities. <s> BIB002
There are a number of important functions related to a schema, and we list here the standard notation which will be used throughout the paper: Notation 1. For a fixed schema H: • The order o(H) is the number of fixed positions in the string. • The defining length d(H) is the distance between the first and last fixed positions, i.e. the number of places where crossover can disrupt the schema. • The fragility of the schema is the number ℓ−1 , i.e. the proportion of places where the schema can be disrupted. • The fitness f (H, t) of a schema is the average fitness of all strings in the population matching schema H at generation t. Let f (t) denote the average of the f (−, t) values. Let f denote the average fitness of the whole population at time t. Compact schema are those with small defining length. These are the schema which are less likely to be disrupted by crossover. The maximum number of compact schema is 2 ℓ−o(H) . Note that not every subset of the search space can be described as a schema since there are 3 ℓ possible schemata but 2 2 ℓ possible subsets of the search space. A population of n strings has instances of between 2 ℓ and n · 2 ℓ different schemata. A string of length ℓ can match up to 2 ℓ schemata. In the language of schema theory, Holland's implicit parallelism is a statement about the number of hyperplanes sampled by a single string. In this way, evaluating the fitness of a string gives information on all the schemata which the string matches. Proposition 1 (Implicit Parallelism). A population of size n can process O(n 3 ) schemata per generation, i.e. these schemata will not be disrupted by crossover or mutation. This result holds when 64 ≤ n ≤ 2 20 and ℓ ≥ 64. Let φ be the number of instances of H in the population needed to say we've "sampled" H. This is a parameter which a statistician would set based on the certainty level desired in the statistical analysis. Let θ be the highest order of hyperplane which is represented by H in the population. Then θ = log 2 (n/φ) and some basic combinatorics shows that the number of schemata of order θ in the population is 2 θ · ℓ θ ≥ n 3 . These types of consideration demonstrate that the language of schema theory allows for the methods of statistics to be used in the analysis of genetic algorithms. We can see that it is valuable to be able to count instances of a given schema in the population. Assume now that the genetic algorithm is using one-point crossover and bit mutation with probability p c and p m respectively (i.e. these are the probabilities with which the operator is used in a given generation). The first attempt to count the number of instances of a fixed schema in a genetic program led to the Schema Theorem. The version stated below is slightly more general than Holland's original version because it factors in mutation fully rather than assuming p m is approximately zero. Theorem 1 (Schema Theorem). Let m(H, t) is the number of instances of H in the population in generation t, and let f denote the fitness as in Notation 1. Then The proof is an exercise in elementary probability. The result is an inequality because Holland only factored in the destructive effects of crossover and assumed that every time crossover occurred within the defining length it destroyed the schema. In Section 3 we will state the Exact Schema Theorem, which obtains an equality by factoring constructive effects as well. The Schema Theorem can be interpreted to mean that building blocks will have exponentially many instances evaluated. This does not directly support the building block hypothesis because there is no mention of crossover or how these building blocks are used in the creation of a final solution. There are many applications of schema theory to both the theoretical study of genetic algorithm and the practical use of genetic algorithm. One of the first was Holland's principle of minimal alphabets, which gave an argument based on the Schema Theorem for why a binary encoding is optimal. Unfortunately, this was an informal argument, and it led to some criticism of the emerging field of schema theory as a whole. 1.1. History of Schema Theory. After Holland's work was republished in 1992, there was a strong interest in schema theory from the computer science community. The principle of minimal alphabets was hotly debated and detractors produced convincing arguments for why larger alphabets are optimal for certain problems. Various computer scientists created versions of the Schema Theorem which held with different crossover, mutation, and selection. Riccardo Poli and others took up the challenge of generalizing the Schema Theorem for genetic programming and this brought the debate over the usefulness of the Schema Theorem to the fore. The following quote nicely sums up the world of schema theory as it existed in the mid 1990s: "Some researchers have overinterpreted these approximate schema models, leading to the formulation of hypotheses on how genetic algorithms work, first highly celebrated and later disproved or shown to be only first order approximations. Other researchers have just incorrectly interpreted such models, while still others have understood and correctly criticized them for their limitations. All this has led to the perception that schema theories are intrinsically inferior to other models and that they are basically only a thing of the past to be either criticized to death or just be swept under the carpet." BIB002 Poli first published on the Schema Theorem in 1997  and subsequently published numerous papers on schema theory every year until 2001. During this time comparatively few others were publishing in the field. Poli successfully defended the Schema Theorem against every attack this author has found, and he deserves a great deal of credit for the existence of the field today. Poli last published in schema theory in 2004, and that work is summarized in Section 6. 1.2. Criticisms of Schema Theory. When Poli began, schema theory was a fairly unpopular field. The most common criticisms of the Schema Theorem (e.g. Whitley, 1993) follow. First, the Schema Theorem is only useful to look one generation into the future rather than many due to its reliance on the expectation operator and the fact that it is an inequality. Too much information is lost by not considering the constructive effects of crossover. Second, because selection becomes biased as the population evolves, the observed fitness of schema changes radically. Thus, the average fitness of a schema is only relevant in the first few generations of a run. Thus, the Schema Theorem cannot be used recursively. Third, schema have no useful applications. One response to the first criticism is to let the population size approach infinity so that we can remove the expectation operator via the Law of Large Numbers. Although arbitrarily large population sizes are impractical, letting n → ∞ has become a common response in theoretical computer science and especially in the asymptotic analysis of algorithms. If Whitley's criticism of schema theory is accepted then it extends to a criticism of much of modern computer science. A different approach is to use Chebychev's inequality from probability theory to remove the need for the expectation operator. For more on this see Section 4. However, as is the case with classical probability theory, using Chebychev's inequality involves a loss of information. For this reason, the author prefers the other responses to the first criticism. The second criticism was resolved in  and BIB001 in the more general setting of genetic programming. A particularly strong version of the Schema Theorem is the Recursive Conditional Schema Theorem, and this resolves the second criticism very completely. The goal of reaching this theorem serves as motivation for our introduction of this language in Section 2. This work requires the use of more tools from probability theory than the Schema Theorem above. At several points during the development of schema theory, new ideas from probability theory propelled the field forward. Examples can be found in Sections 3, 5, and 6. These developments required studying genetic programs microscopically rather than macroscopically, the use of conditional probability, and the use of methods from the theory of Markov chains. For future development in this vein, the author suggests looking to the theory of dynamical systems for more tools which may be used here. The third criticism can again be taken as a criticism of all of theoretical computer science. As is often the case, applications of schema theory did eventually arise, and these are cataloged in Section 7. One of the nicest applications of the ideas in this section came not from the schema theory of genetic algorithms, but rather from the version for genetic programs. We address this version in the next section.