An Overview of Schema Theory <s> 2.2. <s> Two main weaknesses of GA and GP schema theorems are that they provide only information on the expected value of the number of instances of a given schema at the next generation E[m(H,t + 1)], and they can only give a lower bound for such a quantity. This paper presents new theoretical results on GP and GA schemata which largely overcome these weaknesses. Firstly, unlike previous results which concentrated on schema survival and disruption, our results extend to GP recent work on GA theory by Stephens and Waelbroeck, and make the effects and the mechanisms of schema creation explicit. This allows us to give an exact formulation (rather than a lower bound) for the expected number of instances of a schema at the next generation. Thanks to this formulation we are then able to provide in improved version for an earlier GP schema theorem in which some schema creation events are accounted for, thus obtaining a tighter bound for E[m(H, t + 1)]. This bound is a function of the selection probabilities of the schema itself and of a set of lower-order schemata which one-point crossover uses to build instances of the schema. This result supports the existence of building blocks in GP which, however, are not necessarily all short, low-order or highly fit. Building on earlier work, we show how Stephens and Waelbroeck’s GA results and the new GP results described in the paper can be used to evaluate schema variance, signal-to-noise ratio and, in general, the probability distribution of m(H, t + 1). In addition, we show how the expectation operator can be removed from the schema theorem so as to predict with a known probability whether m(H, t + 1) (rather than E[m(H, t + 1)]) is going to be above a given threshold. <s> BIB001 </s> An Overview of Schema Theory <s> 2.2. <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 indudes 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> BIB002 </s> An Overview of Schema Theory <s> 2.2. <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> BIB003
Whigham's Definition. Whigham's paper addresses context free grammars, which are generalizations of genetic programs. Context free grammars may be thought of as derivation trees which explicitly tell how to apply rewrite rules coming from a pre-defined grammar Σ to a starting symbol S. The result of this application is the program. The derivation tree has internal nodes which may be thought of as rewrite rules and terminals which may be thought of as the functions and terminals used in the program. Whigham's schema are partial derivation trees rooted in some non-terminal node. Formally, a schema is a derivation tree x ⇒ α where x is in the set of nonterminals N and α ∈ {N ∪Σ} * . Thus, one schema represents all programs which can be obtained by adding rules to the leaves of the schema until only terminal symbols are present. As with O'Reilly and Koza, one schema can occur multiple times in the derivation tree of the same program, but Whigham also is able to obtain a schema theorem in the presence of fitness proportionate reproduction. We state this theorem, again using Notation 2 and our usual notation regarding probabilities p c and p m of crossover and mutation: The definitions for mutation are similar. Whigham also has an equivalent statement of the theorem using only probabilistic quantities. He uses his theorem as a possible explanation for the well-known problem of bloat in genetic programming, but does not rigorously show anything to this effect. He does show, however, that his notion of schema and his schema theorem applies to fixed-length binary genetic algorithms under one-point crossover and to genetic programming under standard crossover. 2.3. Altenberg's Definition. Altenberg focused on emergent phenomena, meaning "behaviors that are not described in the specification of the system, but which become evident in its dynamics." An example of such behavior is bloat. Altenberg defines soft-brood selection in order to avoid producing offspring of low fitness. This selection method is very similar to tournament selection but there is no probability that the tournament winner will be selected randomly and there is a probability that no recombination will occur. Let x i be the frequency of program i in the population, P be the space of programs, S be the space of subexpressions which recombination can obtain from programs in P , C(s ← k) be the probability that recombination obtains s from program k, and P (i ← j, s) be the probability that recombination on subexpression s and program j produces program i. Then without soft-brood selection, Altenberg uses this to create a schema theorem for genetic programming in the situation of an infinite population. Suppose v s is the marginal fitness of subexpression s obtained from averaging weighted sums of C(s ← i). Suppose u s (t) is the weighted sum i∈P C(s ← i)x i in generation t. Then Altenberg then factors in soft-brood selection and analyzes how it changes the situation. His schemata are the subexpressions s and as with the definitions above, each schema lacks positional data and so can appear multiple times in a given program i. One of Altenberg's models is an exact microscopic model (i.e. the constructive effects of crossover are taken into account), but it fails to be a theorem about schemata as sets. Such a model did not exist in Poli's work until 2001. 2.4. Rosca's Definition. Justinian Rosca  ) published a new definition of genetic program schema at the same time as Poli and Langdon. Rosca's definition of a schema is a rooted contiguous tree fragment. These schemata divide the space of programs into subspaces containing programs of different sizes and shapes. The order o(H) is the number of defining symbols (non-# nodes) H contains. This definition uses positional information and does not allow multiple copies of one schema in a given program. This makes the calculations needed for a schema theorem much nicer but also restricts what is meant by a "good" block of genetic material. The pros and cons will be discussed more in the conclusion. His work yields this schema theorem: Here N (h) is the size of a program h matching H. 2.5. Poli and Langdon's Definition. Poli and Langdon similarly defined schema using positional data to avoid the problem of multiple instances of a schema appearing in the same individual. We highlight their definition, as it will be the one used for the remainder of the paper: Definition 3. A genetic program schema is a rooted tree composed of nodes from the set F ∪T ∪{=} where F and T are the function and terminal sets, and = is a "don't care" symbol which can be any arity needed. With this definition, schemata partition the program space into subspaces of programs of fixed size and shape. Furthermore, the effect of genetic operators on schemata are now much easier to evaluate. Notation 3. For a fixed genetic programming schema H: is the number of instances of H at generation t. (2) The order o(H) is the number of non-= symbols. (3) The length N (H) is the total number of nodes in the schema (4) The defining length L(H) is the number of links in the minimum tree fragment containing all non-= symbols (5) N (H) is the number of nodes of the individual (6) p d (t) is the fragility of H in generation t (7) G(H) be the zeroth order schema with the same structure as H but all nodes being = symbols (8) P dc (H, h, t) is the probability of disruption due to crossover of schema H in program h in generation t. Taking the average over all h yields P dc (H, t). Analogously we obtain P dm for mutation. (9) The notation for f and f is the same as in Notation 1. These quantities are independent of the shape and size of the programs. This definition is lower level than Rosca's definition above in that a smaller number of trees can be represented by schemata. Still, the trees represented by other schema can be represented by collections of genetic programming schemata and the converse is not true. Using this notation, we obtain: Theorem 2 (Genetic Programming Schema Theorem). In a generational genetic program with fitness proportional selection, one-point crossover, and point mutation, Point mutation works by substituting a function node with another of the same arity or a terminal with another terminal. One-point crossover is defined as follows. First, identify the parts of both trees with the same topology (i.e. same arity nodes in the same places). Call this set of nodes the common region. Then select a random crossover point and create the offspring with the part of parent 2 from below the crossover point and the rest from parent 1 above the crossover point. For the purposes of schema theory this crossover is better than standard genetic programming crossover (where a point is chosen randomly in each parent and crossover does not worry about the topology). Note that one-point crossover yields children whose depth is no greater than that of the parents. This has the potential to help prevent bloat, though the author does not know whether this idea was ever explored. In ) the authors also defined uniform crossover where "the offspring is created by independently swapping the nodes in the common region with a uniform probability." For function nodes on the boundary of the common region, the nodes below them are also swapped. These two crossovers were motivated completely by schema theory but have become popular in their own right to practitioners since their creation. The problem of genetic programming for standard crossover was too hard to solve at this time, and was not solved till BIB002 and BIB003 , which gave a Genetic Programming Schema Theorem for all homologous crossovers. The notion of a common region was not truly formalized until BIB002 ). The Genetic Programming Schema Theorem is proven using basic probability theory applied to the four cases depending on whether the parents are both in G(H), both not in G(H), or only one is in G(H). Analysis of the Genetic Programming Schema Theorem shows that the probability of schema disruption is very high at the beginning of a run. Furthermore, diversity of shapes and sizes will decrease over time and so a schema H with above average fitness and short defining length will tend to survive better than other schemata. If all programs have the same structure then a genetic program with one-point crossover is nothing more than a genetic algorithm. In this situation, the theory of genetic programming limits to the theory of genetic algorithms as t → ∞. Perhaps most important is the observation that two competitions are occurring in genetic programming. First, there is competition among programs with different G(H). Then once only a few such hyperspaces are left there is competition within those hyperspaces on the basis of defining length. It is in the second phase that a genetic program acts like a genetic algorithm. The definition of a genetic program schema was generalized twice more. The first generalization occurred in BIB001 with the notion of a hyperschema. Definition 4. A hyperschema is a rooted tree composed of nodes from the set F ∪ T ∪ {=, #} where F and T are the function and terminal sets, the symbol = means "don't care" for exactly one node, and # means any valid subtree. The special symbols can take any arity needed. This definition generalizes both the definition of a genetic program schema and Rosca's definition. Using this definition, Poli generalized all his versions of the schema theorem (addressed below) and obtained cleaner statements, tighter bounds, and better proofs. Additionally, Poli used these results to argue for the existence of building blocks in genetic programming. The final generalization was in BIB003 with the notion of a variable arity hyperschema. There are also versions of schema theory in this context, and we leave it to the interested reader to investigate. Definition 5. A variable arity hyperschema is a rooted tree composed of internal nodes from the set F ∪ {=, #} and leaves from T ∪ {=, #} where the symbol = means "don't care" for exactly one node, the leaf # stands for any valid subtree, and the function # stands for a function with unspecified arguments which can be any valid subtree and arity ≥ the number of subtrees connected to it. In extensive experiments were performed on a genetic program to record all schema in the population, their average fitnesses, the population average fitness, the number of programs sampling a schema, the length, order, and defining length of schema, and schema diversity. The results confirmed a several conjectures. First, schema disruption is frequent at the beginning of a run before crossover counteracts the effects of selection. If selection only is acting, then schema with below average fitness disappear. Second, without mutation the population will start converging quickly and short schemata with above average fitness will have low disruption probability. Third, the average deviation in fitness of high-order schemata is larger than that for low-order schemata. More surprisingly, this experiment points to the conclusion that building blocks do not grow exponentially. Rather, the growth function was not at all monotonic. The authors suggest that genetic drift and a small population size may have led to this conclusion. They suggested that to obtain achieve a better understanding of the genetic programming building blocks it may be necessary to study the propogation of structures which are functionally equivalent as programs but which are structurally different (now called "phenotypical schemata"). It was found that initially, one-point crossover is as disruptive as standard genetic programming crossover, but as the run progresses it becomes much less disruptive. The disruption probability varies greatly from one generation to the next and therefore should be considered as a random variable (necessitating the conditional schema theorems of Section 5). Finally, the genetic program does indeed asymptotically tend to a genetic algorithm, so nothing is lost by working in the setting of genetic programs for the rest of the paper.