An Overview of Schema Theory <s> Applications of Schema Theory <s> In this paper, firstly we specialise the exact GP schema theorem for one-point crossover to the case of linear structures of variable length, for example binary strings or programs with arity-1 primitives only. Secondly, we extend this to an exact schema theorem for GP with standard crossover applicable to the case of linear structures. Then we study, both mathematically and numerically, the schema equations and their fixed points for infinite populations for both a constant and a length-related fitness function. This allows us to characterise the bias induced by standard crossover. This is very peculiar. In the case of a constant fitness function, at the fixed-point, structures of any length are present with non-zero probability. However, shorter structures are sampled exponentially much more frequently than longer ones. <s> BIB001 </s> An Overview of Schema Theory <s> Applications of Schema Theory <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> Applications of Schema Theory <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 </s> An Overview of Schema Theory <s> Applications of Schema Theory <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 </s> An Overview of Schema Theory <s> Applications of Schema Theory <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> BIB005
In general, theorists in this field wish to understand the benefits of schema theory over other theories which attempt to explain the efficacy of genetic algorithms. Over a number of years, Poli laid the groundwork for schema theory and resolved the criticisms which this field faced. Practitioners tend to be more interested in choosing the correct representation of a problem, choice of operators, choice of fitness function, settings of parameters, size of population, number of runs, etc. The problem of combating bloat is also important. There have also been applications to fields other than genetic programming, and these are discussed at the end of the section. 7.1. Applications to Genetic Programs. The considerations in Section 2 provide comparisons between the various ways to represent a problem. Finding a relationship between the choice of representation and schema behavior can help practitioners choose the best representation for their chosen application. Another instance where schema theory helps practitioners was discussed at the end of Section 5. Here schema theory provides a lower bound on population size and thereby helps practitioners determine a good value for the population size parameter. Regarding the problem of bloat, BIB004 shows how to use the macroscopic exact genetic programming schema theorem and its corollary to determine when there is an effective fitness advantage in having a large amount of inactive code. Thus, bloat can at times be necessary for the success of the genetic program. However, because bloat often slows down a genetic program, practitioners can also use the considerations in BIB004 to avoid situations which lead to bloat. Schema theory has motivated new crossover functions (one-point and uniform) and the notion of a smooth operator, and these notions have been useful to practitioners. Furthermore, in BIB002 ) different measurement functions are explored to investigate the behavior and biases of the variation operators and parameters. This led to new initialization strategies for genetic programming to optimize performance using knowledge of the variation operator biases. Finally, BIB004 provides an exact formulation of which problems are hard for a genetic program to solve (see also BIB003 . To discuss other applications, we must first discuss the proof method in the 2003 paper of Poli and McPhee. This proof method relies on the Cartesian node reference system representation of genetic programs as functions over the space N 2 and the process of selection as a probability distribution over N 4 . This reference system consists of laying out the trees on a grid where each node has arity a m . After doing so, there are a n m nodes at depth n. Any node can be recovered from its depth (d) and where it falls (i) in that row. We list the relevant notation: (1) The name function N (d, i, h) returns the node in h at position (d, i). (2) The size function S(d, i, h) returns the number of nodes present in the subtree rooted at (d, i). (7) Define p(d, i|h) as the probability that the (d, i) node is selected in program h. . A symmetric crossover is one for which p(i, j|h 1 , h 2 ) = p(j, i|h 2 , h 1 ). The microscopic and macroscopic schema theorems can be specialized for standard genetic programming crossover using this machinery. A corollary is the size-evolution equation for genetic programming with subtree-swapping crossover: Theorem 13 (Size Evolution Equation). Let µ be the mean size of a program in a genetic program population. If the genetic program uses a symmetric subtree-swapping crossover operator and no mutation then for fixed (d, i) we have The theorem tells us that the mean program size evolves as if selection alone were acting on the population. Thus, bloat is the effect of selective pressure and we can calculate the mean size of individuals at time t in terms of the number N of individuals sampling a schema G k and the proportion Φ of individuals of size and shape . This allows for the prediction and control of bloat, helping to solve a major open problem dating back to Koza's early work in genetic programming. In this application, controlling bloat can be achieved by acting on the selection probabilities to discourage growth, e.g. by creating holes in the fitness landscape which repel the population. Note that this equation was expanded and simplified by  to exactly formalize program size dynamics. Corollary 1. For a flat landscape, we have E(µ(t + 1)) = µ(t) This has also been studied by Poli and McPhee for at landscapes with holes and spikes. This study can also be used to fine tune parameter settings for the variation operators and move towards optimal performance. In the same vein, applied schema theory to look into bistability of a gene pool genetic algorithm with mutation. A bistable landscape is one with two stable fixed points on a single-peak fitness landscape. This paper led to a better overall understanding of mutation and also provided another example of an unexpected application of schema theory. Another corollary of the size-evolution equation is the study of Crossover Bias Theory  . This states that because crossover removes as much material as it adds (on average), crossover is not solely responsible for changes in mean program size. However, crossover does affect the higher moments of the distribution, pushing the population towards a Lagrange Distribution of the Second Kind. In this distribution smaller programs have significantly higher frequency than larger programs. Thus, larger programs have an evolutionary advantage over smaller programs and this forces the mean program size to increase over time. 7.2. Applications to Other Fields. After genetic programming schema theory provided a definition for the notion of a deceptive program (discussed in Section 3), were able to investigate deception in the Ant problem. The Ant problem is a difficult search-space problem in which the goal is to program an artificial ant to follow the Santa Fe trail. A priori, this problem has nothing to do with schema theory, so this is a particularly striking application. Another striking application is the relationship between schema theory and Markov models discussed at the end of Section 6 and in BIB005 . For instance, the authors hint that schema theory can be used to determine conditions under which the Markov model's transition matrix is ergodic. This relationship has the potential for many other future applications as well, some of which are discussed in Section 8. In BIB001 , the authors specialized exact genetic programming schema theory to the case of linear structures of variable length (i.e. where the functions are all unary). For example, binary strings or programs with primitives of arity 1 only are linear structures. The authors then found a version of the theorem for standard crossover in the linear representation case. Finally, they considered fixed points of the schema equations which allowed them to prove that standard crossover has a bias which samples shorter structures exponentially more frequently than longer structures BIB002 . This led to a number of conclusions about linear systems BIB003 . First, genetic programming crossover exerts a strong bias forcing the population towards a Gamma length distribution. This bias is strong enough to overpower the selection bias, so a practical application is to initialize a population so that the lengths begin by matching the Gamma distribution. Second, shorter than average structures are sampled exponentially more than longer ones, so the genetic program wastes time resampling. Thus, time could be saved by setting the mean length of the initial structures so that the sampling will occur where solutions are believed to be. Third, focusing on the distribution of primitives in the representation gives a generalization to Geiringer's Theorem and of the notion of linkage equilibrium to representations with non-fixed length BIB003 . It can be shown that the primitives in each individual tend to be swapped with those of other individuals and also to diffuse across the positions within the individual. This diffusive bias may also interfere with the selection bias and so should be avoided by initializing the population so that primitives are already uniformly distributed in each individual. Fourth, highly fit individuals may fail to transmit their genes, so this should be avoided by moving towards a steady-state model. These four lessons show a very nice application of schema theory to a well-studied problem area. Linear structures enter in the following way. Given a genetic program made up of linear structures with only two functions and only two terminals, the concept of a genetic program schema corresponds exactly to that of a genetic algorithm schema. Similarly, 1-point genetic programming crossover corresponds exactly to 1-point genetic algorithm crossover. This gives yet another link between the theories of genetic programming and genetic algorithms.