An Overview of Schema Theory <s> Relationship between Schema Theory and Markov Models <s> In this paper we present a Markov chain model for GP and variable-length GAs with homologous crossover: a set of GP operators where the offspring are created preserving the position of the genetic material taken from the parents. We obtain this result by using the core of Vose's model for GAs in conjunction with a specialisation of recent GP schema theory for such operators. The model is then specialised for the case of GP operating on 0/1 trees: a tree-like generalisation of the concept of binary string. For these symmetries exist that can be exploited to obtain further simplifications. In the absence of mutation, the theory presented here generalises Vose's GA model to GP and variable-length GAs. <s> BIB001 </s> An Overview of Schema Theory <s> Relationship between Schema Theory and Markov Models <s> This paper presents a simple method to control bloat which is based on the idea of strategically and dynamically creating fitness "holes" in the fitness landscape which repel the population. In particular we create holes by zeroing the fitness of a certain proportion of the offspring that have above average length. Unlike other methods where all individuals are penalised when length constraints are violated, here we randomly penalise only a fixed proportion of all the constraint-violating offspring. The paper describes the theoretical foundation for this method and reports the results of its empirical validation with two relatively hard test problems, which has confirmed the effectiveness of the approach. <s> BIB002 </s> An Overview of Schema Theory <s> Relationship between Schema Theory and Markov Models <s> Genetic Programming (GP) homologous crossovers are a group of operators, including GP one-point crossover and GP uniform crossover, where the offspring are created preserving the position of the genetic material taken from the parents. In this paper we present an exact schema theory for GP and variable-length Genetic Algorithms (GAs) which is applicable to this class of operators. The theory is based on the concepts of GP crossover masks and GP recombination distributions that are generalisations of the corresponding notions used in GA theory and in population genetics, as well as the notions of hyperschema and node reference systems, which are specifically required when dealing with variable size representations. ::: ::: In this paper we also present a Markov chain model for GP and variable-length GAs with homologous crossover. We obtain this result by using the core of Vose's model for GAs in conjunction with the GP schema theory just described. The model is then specialised for the case of GP operating on 0/1 trees: a tree-like generalisation of the concept of binary string. For these, symmetries exist that can be exploited to obtain further simplifications. ::: ::: In the absence of mutation, the Markov chain model presented here generalises Vose's GA model to GP and variable-length GAs. Likewise, our schema theory generalises and refines a variety of previous results in GP and GA theory. <s> BIB003 </s> An Overview of Schema Theory <s> Relationship between Schema Theory and Markov Models <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> BIB004
Schema theories up until 2001 were purely macroscopic models of genetic algorithms. In her 1996 textbook, Mitchell claims that models based on Markov chains and statistical mechanics will be necessary to formalize the theory of genetic algorithms. Markov chain models are generally exact and fully microscopic, so they hold more appeal for computer scientists looking for accuracy. The cost is that Markov models have many degrees of freedom and are difficult to derive and use. For examples of such models, see  . Statistical mechanics models are macroscopic so they are simpler but also less accurate. For examples of such models see  . Markov models have also been applied to genetic programming  BIB003 BIB001 ). For most of the 1990s macroscopic models dominated the field of genetic algorithm modeling. BIB004 helped combat this by providing an exact microscopic model, but there are still many more macroscopic models than microscopic. Aggregation of states in Markov chain models provide another way to move from the microscopic to the macroscopic. Again, the benefit of such a move is in simpler equations, but the downside is a loss of accuracy. Very few of these models explicitly factor in the fitness function, so the fitness landscape cannot be seen even if we get a the program space is well understood. This is one reason why genetic programming schema theory is useful: it provides a new point of view regarding this failure of Markov chain models. Exact genetic programming models are designed to explicitly determine how selection and the variation operators affect sample program space. While the 1990s saw a competition between Markov models and schema theory, both have provided useful applications and theory, and the two now seem to coexist as alternative approaches. These two approaches are linked in BIB003 . In this paper, the authors successfully applied schema theory to determine the biases of the variation operators (see also BIB002 and helped get a better hold on the program space. Furthermore, the authors create a new Markov chain model and use it to analyze in detail 0/1 trees. This work required the use of crossover masks, which generalize all possible choices of crossover operator. For fixed-length binary strings, a crossover mask is a binary string which tells how crossover is done. In this string, a 1 is an instruction to choose the allele at this position from parent A while a 0 is an instruction to take the allele from parent B. For each mask i, let p i be the probability this mask is selected. The distribution of the p i is the recombination distribution. Crossover masks can also be generalized to genetic programming via trees with the same size and shape as the common region. Similarly, there is a generalized recombination distribution and a building block generating function for genetic programs. Denote this function by Γ(H, i). It returns the empty set if i contains a node not in H and otherwise it returns the hyperschema with size and shape matching H but with = nodes everywhere. Letting i be the tree complementary to i, it turns out that Γ(H, i) and Γ(H, i) generalize L(H, i) and U (H, i) from Notation 4. The following lemma is used to prove both microscopic and macroscopic exact theorems stating the total transmission probability for a genetic program schema using homologous crossover. This is the heart of the 2004 paper. Lemma 1. If P 1 ∈ Γ(H, i) and P 2 ∈ Γ(H, i) then crossing P 1 and P 2 using mask i gives an offspring matching H. Conversely, if crossover according to i yields an individual matching H then one of the parents must have come from Γ(H, i) and the other from Γ(H, i). Both Markov chain models and schema theory are attempts to look carefully at the generation-togeneration behavior of a genetic algorithm or genetic program. In the conclusion of (Poli-McPheeRowe, 2004) , the authors claim that exact schema models are simply different representations of Markov chain models. If this is true then these two fields are equivalent, and there are many areas where results from one may be applied to the other. The authors support this claim by noting the use of dynamic building blocks in the formulation of exact schema theory. The authors leave open the details of making this connection precise, so we have included this as an open problem in Section 8.