An Overview of Schema Theory <s> Schema Theory for Genetic Programming <s> Background on genetic algorithms, LISP, and genetic programming hierarchical problem-solving introduction to automatically-defined functions - the two-boxes problem problems that straddle the breakeven point for computational effort Boolean parity functions determining the architecture of the program the lawnmower problem the bumblebee problem the increasing benefits of ADFs as problems are scaled up finding an impulse response function artificial ant on the San Mateo trail obstacle-avoiding robot the minesweeper problem automatic discovery of detectors for letter recognition flushes and four-of-a-kinds in a pinochle deck introduction to biochemistry and molecular biology prediction of transmembrane domains in proteins prediction of omega loops in proteins lookahead version of the transmembrane problem evolutionary selection of the architecture of the program evolution of primitives and sufficiency evolutionary selection of terminals evolution of closure simultaneous evolution of architecture, primitive functions, terminals, sufficiency, and closure the role of representation and the lens effect. Appendices: list of special symbols list of special functions list of type fonts default parameters computer implementation annotated bibliography of genetic programming electronic mailing list and public repository. <s> BIB001 </s> An Overview of Schema Theory <s> Schema Theory for Genetic Programming <s> Evolutionary computation systems exhibit various emergent phenomena, primary of which is adaptation. In genetic programming, because of the indeterminate nature of the representation, the evolution of both recombination distributions and representations can emerge from the population dynamics. A review of ideas on these phenomena is presented, including theory on the evolution of evolvability through differential proliferation of subexpressions within programs. An analysis is given of a model of genetic programming dynamics that is supportive of the “Soft Brood Selection” conjecture, which was proposed as a means to counteract the emergence of highly conservative code, and instead favor highly evolvable code. <s> BIB002 </s> An Overview of Schema Theory <s> Schema Theory for Genetic Programming <s> In this paper we rigorously formulate the Schema Theorem for Genetic Programming (GP). This involves defining a schema, schema order, and defining length and accounting for the variable length and the non-homologous nature of GP'S representation. The GP Schema Theorem and the related notion of a GP Building Block are used to construct a testable hypothetical account of how GP searches by hierarchically combining building blocks. Since building blocks need to have consistent above average fitness and compactness, and since the term in the GP Schema Theorem that expresses compactness is a random variable, the proposed account of GP search behavior is based on empirically questionable statistical assumptions. In particular, low variance in schema fitness is questionable because the performance of a schema depends in a highly sensitive manner on the context provided by the programs in which it is found. GP crossover is likely to change this context from one generation to the next which results in high variance in observed schema fitness. Low variance in compactness seems fortuitous rather than assured in GP because schema-containing programs change their sizes essentially at random. <s> BIB003 </s> An Overview of Schema Theory <s> Schema Theory for Genetic Programming <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> BIB004 </s> An Overview of Schema Theory <s> Schema Theory for Genetic Programming <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> BIB005
A genetic program is a special type of genetic algorithm in which each individual in the population is now a computer program. An optimal solution is therefore an optimal algorithm for completing a predetermined task, and so the theory of genetic programming falls under the umbrella of machine learning. The types of considerations which go into genetic programming are related to those of genetic algorithms, but more complicated because individuals are now more naturally represented as parse trees rather than strings. For this reason, crossover and mutation are now operations on trees and there are numerous ways to define these operations, each with their own advantages and disadvantages. Unlike genetic algorithms, the size of individuals in genetic programming cannot be restricted. Trees are therefore allowed to grow arbitrarily large as the number of generations grows, and this phenomenon (called bloat) is common. The interested reader is encouraged to consult (Koza, 1992) for further details. Because genetic programming is a generalization of genetic algorithm, all schema theorems for the former apply to the latter. Indeed, in BIB005 it was shown that these theorems in fact apply to genetic algorithm with variable length bit-string representation. Much of Poli's work is phrased in terms of genetic programs, and that is our motivation for introducing them. The notion of a schema for genetic programming was studied by several authors in the 1990s, and numerous non-equivalent definitions arose BIB001 BIB002 BIB003 Whigham, 1995) . These papers all used representations for genetic programs which did not include positional information and which thus allowed numerous instances of a schema in one program. By way of analogy, the genetic algorithm schema could be defined as a set of pairs {(c 1 , i 1 ), (c 2 , i 2 ), . . . } where the c j are blocks of bit-strings with no breaks and the i j are positions for the c j . Thus, the position of a schema instance is implicit in the genetic algorithm situation. Removing this positional information can lead to the number of strings belonging to a given schema not being equal to the number of instantiations of the schema in the population. Without positional information, counting the number of schema and dealing with even the simplest quantities in the genetic algorithm schema theorem becomes much harder. In  , the authors considered all existing definitions of genetic program schema and then created their own. Their definition simplified the calculations and allowed for the first non-trivial genetic programming schema theorem. This is why Poli and Langdon created their own definition. As motivation for Poli-Langdon schema, we will record the historical definitions here. 2.1. Koza's Definition. Koza defined a schema as a subspace of trees containing a predefined set of subtrees. O'Reilly and Oppacher's definition was a formalization of Koza's with "tree fragments" which are trees with at least one leaf that is a "don't care" symbol, represented by #. These symbols could be matched by any subtree. With this definition, one schema can appear multiple times in the same program. It's clear how to define the order and defining length for one instance, but because it depends on which instance is chosen these quantities are not well-defined for the schema. Still, O'Reilly and Oppacher were able to craft a schema theorem for genetic programming using this definition when fitness proportional selection is used. Before stating this theorem, we record our notation for the section Notation 2. For a fixed genetic programming schema H: is the number of instances of H at generation t. (2) 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. (3) The notation for f and f is the same as in Notation 1. We now state O'Reilly and Oppacher's theorem, using the notation above O'Reilly and Oppacher state the genetic programming building block hypothesis as: "genetic programs combine building blocks, the low order, compact highly fit partial solutions of past samplings, to compose individuals which, over generations, improve in fitness." They observe that a schema instance can change in a generation even when the schema instance is not disrupted. They use this to question the existence of building blocks in genetic programming. They also attack the usefulness of schema theory with the same arguments used in  . They gave two criticisms of schema theory: first, that it could never be correctly applied to genetic programming because genetic programs exhibit time dependent behavior similar to a stochastic processes. Second, that genetic programming exerts no control over program size but program size matters quite a bit to performance. These issues were not resolved until  and BIB004 .