An Overview of Schema Theory <s> Introduction <s> Abstract Holland's Schema Theorem is widely taken to be the foundation for explanations of the power of genetic algorithms (GAs). Yet some dissent has been expressed as to its implications. Here, dissenting arguments are reviewed and elaborated upon, explaining why the Schema Theorem has no implications for how well a GA is performing. Interpretations of the Schema Theorem have implicitly assumed that a correlation exists between parent and offspring fitnesses, and this assumption is made explicit in results based on Price's Covariance and Selection Theorem. Schemata do not play a part in the performance theorems derived for representations and operators in general. However, schemata re-emerge when recombination operators are used. Using Geiringer's recombination distribution representation of recombination operators, a “missing” schema theorem is derived which makes explicit the intuition for when a GA should perform well. Finally, the method of “adaptive landscape” analysis is examined and counterexamples offered to the commonly used correlation statistic. Instead, an alternative statistic — the transmission function in the fitness domain — is proposed as the optimal statistic for estimating GA performance from limited samples. <s> BIB001 </s> An Overview of Schema Theory <s> Introduction <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> BIB002 </s> An Overview of Schema Theory <s> Introduction <s> The basic Schema Theorem for genetic algorithms is modified for a grammatically-based learning system. A context-free grammar is used to define a language in which each sentence is mapped to a fitness value. The derivation trees associated with these sentences are used to define the structure of schemata. The effect of crossover and mutation on schemata is described. A schema theorem is developed which describes how sentences of a language are propagated during evolution. <s> BIB003
Evolutionary computation began in the 1950s as an attempt to apply the theory of evolution to optimization problems. The goal of an evolutionary program is to begin with a population of candidate solutions for a given problem and then evolve an optimal solution. In order for evolution to occur one needs external pressure, a method by which genetic material is passed to offspring, and time. Genetic algorithms are one way to implement evolutionary computation. A genetic algorithm uses a counter to mimic the passage of time, uses a fitness function to mimic external pressure, and uses reproduction operators to mimic reproduction. A genetic algorithm begins with a randomly generated population at time zero. Each iteration of the time counter yields a new generation. During any generation, the population is referred to as the search space. External pressure is modeled by a fitness function f that assigns (positive) numerical values to candidate solutions. A random process called selection determines which solutions survive to the next generation, but solutions with low fitness values have a lower probability of survival. Reproduction is mimicked via operations by which existing solutions produce new solutions. Examples include the crossover operator and the mutation operator. Once a solution evolves whose fitness surpasses some predetermined level, or once a predetermined number of generations pass, the algorithm halts and returns the best solution. Throughout this paper we will assume that each individual is represented by a string of length ℓ taken from the alphabet {0, 1} (a.k.a. bit-strings). These bits are also referred to as alleles, in analogy with evolutionary biology. For an individual A let A[i] denote the bit at position i, where the first bit is at A [0] . The fitness function is therefore a function from the set of bit-strings to the Date: December 30, 2009. set of real numbers. The reproduction operations use such strings as input and output. Mutation changes some number of bits at random. Crossover selects two strings uniformly at random, breaks them into pieces, and rearranges the pieces to form two new strings. There are many types of mutation and crossover. An example of mutation is bit mutation, which selects a single bit uniformly at random and swaps its value from 0 to 1 or from 1 to 0. An example of crossover is one-point crossover, which takes two strings A and B, selects a random number k between 1 and ℓ − 2, and produces new strings A ′ = A[0, k]B[k + 1, ℓ − 1] and B ′ = B[0, k]A[k + 1, ℓ − 1]. So it simply splits the two strings at index k and then glues their pieces together. An example of selection is fitness proportional selection, where the probability of selecting an individual A to survive to the next generation is f (A)/ p f (p) where p runs through the population. Another example is tournament selection, where a predetermined number of individuals are randomly selected and then divided into a tournament and compared in pairs. A biased coin is flipped, and depending on the outcome the individual which emerges from the pair is either the more fit or less fit of the two. This process continues until only one individual is left. To select k individuals requires k tournaments. In this example, selection pressure can be modified by changing the parameter which represents tournament size or by changing the parameter which represents the coin's bias. The success of a genetic algorithm often depends on choices made by the programmer. The programmer selects the probability with which crossover or mutation take place in each generation. For example, a selection procedure which is too random may destroy good solutions (i.e. solutions of high fitness) and allow bad solutions to percolate. A selection procedure which is not random enough may encourage the algorithm to evolve an overly naive solution to the optimization problem, i.e. to take the easy way out. Most search heuristics which employ randomness face similar trade-offs, since randomization can always lead to better or worse answers. A more subtle question is to determine how different choices for the fitness function, crossover, and mutation affect the success of the algorithm. To address such questions, and to create more effective genetic algorithms, it is instructive to consider how evolution works from generation to generation rather than as a process spread over thousands of generations. A first attempt to explain the phenomenon of evolution is the Building Block Hypothesis, which states that crossover combines building blocks (blocks of nearby alleles which endow high fitness) hierarchically into a final solution. Formalizing this statement was the starting point for schema theory. Schema theory was developed in 1975 by John Henry Holland and his work was republished in 1992  . Holland realized that when the genetic algorithm evaluates the fitness of a string in the population it is actually evaluating the fitness of many strings in an implicitly parallel fashion. As one of the slowest parts of a genetic algorithm is evaluating fitnesses in the search space, Holland's idea that this could be done in parallel has the potential to speed up genetic algorithms substantially. Definition 1. A schema is a string of length ℓ from the alphabet {0, 1, * }. The * is taken to be a symbol for "don't care" so that one schema corresponds to multiple strings in the search space. The indices where the schema has a 0 or 1 are called the fixed positions. The number of fixed positions is the order of the schema. When a string matches the schema on the fixed positions it is called an instance of the schema, and we say the string matches the schema. Thus, a schema is equivalent to a hyperplane in the search space, and we will sometimes use these terms interchangeably. Crossover and mutation can disrupt the schema if they result in a change to one of the fixed positions. A change to one of the other indices results in a different individual in the same schema. We will use the word schema for an individual schema, i.e. a single hyperplane. We will use the word schemata for the plural. Schema theory studies how schema percolate in the population and how they relate to the process by which high fitness solutions are evolved over time. The framework of schema theory allows for a definition of a building block and a formal statement of the building block hypothesis: Definition 2. A building block is a short, low order schema with above average fitness. Hypothesis 1 (Building Block Hypothesis). Good genetic algorithms combine building blocks to form better solutions. There is a much stronger version of the building block hypothesis which has at times been called the building block hypothesis in the literature, especially literature which is critical of the building block hypothesis. We state it now under a different name to avoid confusion. Hypothesis 2 (Static Building Block Hypothesis). Given any schema partition, a genetic algorithm is expected to converge to the class with the best static average fitness. Readers with a background in biology will recognize that this hypothesis is far too strong. Evolution is far too random of a process for a statement like this to be possible, and indeed empirical studies have demonstrated that the static building block hypothesis is unlikely to be true. See, for instance,  BIB003 BIB001 BIB002 . The building block hypothesis, on the other hand, is sufficiently vague that it has potentially true interpretations. The author believes that the best way to resolve this debate would be to study a genetic algorithm as a dynamical system. Then the building block hypothesis can be given a mathematical interpretation and proven or disproven conclusively. The controversial nature of the building block hypothesis has led to some unjust criticism of schema theory as a whole. In this paper we hope to convince the reader that schema theory is a useful and interesting study. Towards this end we highlight several open problems and suggested solutions. The author believes that an interested mathematician can make serious headway in this field and in so doing can help to develop the theory behind genetic algorithms and behind evolution in general. In the next several sections we will summarize the work which has been done in schema theory, beginning in Section 1. In this section we also discuss the criticisms of schema theory. The resolution of these criticisms leads into the following sections. The main result of Section 1 is the Schema Theorem for genetic algorithms. This theorem gives a lower bound on the expect number of instances of a schema. The bound can be turned into an equality, and this is the subject of Section 3. The generalizations and strengthenings of the Schema Theorem are phrased in the language of genetic programs and contain the genetic algorithm Schema Theorem as a special case. We choose to begin with the simplest version first so that the reader can become accustomed to the definitions. In Section 2 we introduce Genetic Programming, a specialization of genetic algorithms. We discuss how to define schema in this setting, and we give a Schema Theorem regarding the expected number of instances of a given schema. In Section 3 we state the various Exact Schema Theorems which improve the inequality to an equality. These sections form the heart of the paper, and afterwards the reader could safely skip to the final section, which includes a list of open problems. The development of schema theory saw a large number of definitions and varied approaches, some of which are cataloged in Section 2. Most approaches faced stiff criticism and needed to be tweaked over subsequent years. For this reason it may be hard for an outsider to determine the current status of the field. This paper is meant to provide a unified treatment of the development and current state of the field, to clearly state the definitions which appear to have been most successful, to list a number of applications of the field which have been spread across several papers, and to highlight directions for future work. Readers interested in developing more advanced applications of probability theory to schema theory may be interested in Sections 4, 5, and 6, as these will help the reader find the boundaries of the field. In Section 7 we discuss applications of the schema theory developed in the earlier sections. Finally, a large list of open problems can be found in Section 8, and the author hopes this will lead to more development of this beautiful field.