An Overview of Schema Theory <s> Future Directions <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> BIB001 </s> An Overview of Schema Theory <s> Future Directions <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> BIB002 </s> An Overview of Schema Theory <s> Future Directions <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> BIB003
As the huge number of papers listed above demonstrates, schema theory is certainly an interesting and rich field of study. Many early arguments based on schema theory demonstrated a lack of understanding and rigor on the part of those writing the papers, but this led to disapproval among computer scientists of the field as a whole. This disapproval chased away many who could have done work in schema theory, but thanks to the work of Riccardo Poli and his collaborators, schema theory survived this early setback and is becoming a popular field once more. Poli has demonstrated that all criticisms leveled at schema theory are either unfounded or can be fixed. He has created a huge number of schema theorems and related them to Markov models so that other computer scientists can use them effectively. Furthermore, Poli and others have found numerous surprising applications of schema theory. These include applications to the Ant problem, to controlling bloat, to the study of variation operators, to parameter setting, and to population initialization. There are also several extended examples such as linear structures where the insights from schema theory have been invaluable. There are many more directions for development of schema theory. We begin with the easiest first. The next two problems build directly on the considerations discussed in the previous sections: Problem 1. Extend the work discussed at the end of Section 4 and combine the Probabilistic Schema Theorems with the Exact, Microscopic, and Macroscopic Schema Theorems. Problem 2. Update the existing schema theorems to address the effects of mutation. Consider creating a mutation mask analogous to the crossover mask from Section 6 so that all choices of mutation are handled at once. Once this is done, the natural next step would be to specialize the schema theorems for different mutation operators as has been done for different selection and crossover operators. This would likely lead to a better understanding of the role of mutation in genetic algorithms and genetic programming just as the schema theory above led to a better understanding of the role of crossover and selection. (Whitley, 1993) claims that mutation can be used as a hill-climbing mechanism and that genetic algorithms using only mutation can compete with genetic algorithms using crossover and a small mutation probability. Mutation often serves the role of searching locally, while crossover is more of a global search. It would be valuable to understand the relationship between local and global search, and the considerations within schema theory may help in obtaining this understanding. A more difficult but more fruitful collection of problems is based on the considerations in Section 7. Problem 3. Formulate schema theories for developmental genetic programming, Genetic Algorithm for Rule Set Production (GARP), learning classifier systems, and other systems commonly studied. Moving in a different direction, note that the development of schema theory has so far only made use of relatively elementary results from probability theory. Each time more advanced results were introduced they led to significant gains in schema theory. There are more advanced tools from probability theory which have not been used, and this provides a rich and fertile area for future work. For example, to the author's knowledge no one has tried to apply the study of martingales to the recursive conditional schema theorem. There is a well-developed study of conditional stochastic processes and many tools from this could be applied. It is possible that more advanced mathematical approaches would answer the remaining open problems in this field. Perhaps the biggest such problem is that schema theory and Markov models do not contain information about the fitness distribution in the search space, so we cannot hope to fully characterize genetic programming behavior  . Problem 4. Sharpen the inequalities in the various schema theorems by making use of more sophisticated tools from probability theory. Problem 5. Introduce the study of martingales into recursive conditional schema theory, and use this to obtain tighter bounds and to make better predictions for the behavior of evolutionary computation in the presence of conditional effects. Problem 6. Find a way to factor information about the fitness distribution into schema theory. In a related vein, there is still much work to be done towards relating schema theory to Markov models. Problem 7. Fill in the details of the claims in the conclusion of BIB002 ) that exact schema models contain precisely the same information as Markov chain models. A reasonable place to begin working on this problem would be the remark in BIB002 ) that using their exact formulas for the probability that reproduction and recombination will create any specific program, "a GP Markov chain model is then easily obtained by plugging this ingredient into a minor extension of Vose's model for genetic algorithms" BIB002 . Once this has been done, results obtained by Vose and the Markov chain model can be generalized to apply to both genetic programming and variable-length genetic algorithms. For example, as pointed out in BIB001 , Markov chain models have the ability to calculate probability distributions over the space of all possible populations. If there is a version of this for schema theory then it might help to produce better bounds in schema theorems and to produce more accurate long term predictions. Problem 8. Generalize Vose's results on the Markov chain model to apply to both genetic programming and variable-length genetic algorithms. Problem 9. Use schema theory to determine conditions under which the Markov model's transition matrix is ergodic. If Problem 6 can be solved and if the dictionary between schema theory and Markov models can be fleshed out, then this could also provide a way for Markov chain models to factor in information about the fitness distribution. There are also hard foundational left to resolve in this field. The most famous was mentioned in the Introduction: Problem 10. Use the theory of dynamical systems to formulate a precise mathematical statement of the building block hypothesis. Prove or disprove this statement. The next problem goes back to the comparison of definitions in Section ??. (Whigham, 1995) allowed multiple instances of a schema in a given tree and showed that this definition restricts to both the usual genetic programming schema theory and to the genetic algorithm schema theory. In biology, genetic material does not come in packages which corresponding to single "good" templates. Rather, having multiple copies of a "good" block of alleles or a "good" template is rewarded. For artificial evolution to successfully move towards computational evolution it will be necessary to include the possibility of multiple instances of a schema. Problem 11. Generalize the schema theorem so that it holds for genetic algorithm strings which allow multiple copies of a schema to be represented. Learning classifier systems provide one way in which to attack this problem. In particular, the use of numerosity in accuracy-based learning classifier systems like XCS could be adapted to create an initial model which contains the possibility of multiple schema instances. The schema theorem which works for variable-length genetic algorithms is a very nice step in this direction. The solution to these last problems may add another layer of complexity to the schema theorems, but with care the solution could also create a simpler overall theory. Furthermore, this theory would be robust enough to cope with self-modification mechanisms and feedback in artificial evolution. Generalizing schema theory in the direction of computational evolution would likely lead to good suggestions for ways to factor in this added layer of complexity. One crucial way to move towards computational evolution is by generalizing genetic programming schema theorems so they work when we don't restrict the size and shape of the program. Poli has avoided doing this because he believes "simply getting to the point of stating exact models for these algorithms requires a lot of machinery" BIB002 . But because there is so much machinery in probability theory which has not been exploited, it is not unreasonable to hope that generalizing schema theory will one day occur. More sophisticated mathematics should lead to a better grasp of the theory. The application of genetic programming schema theory to genetic algorithm schema theory with a representation of variable-length bit strings BIB003 will be very useful in the move from artificial evolution to computational evolution. This is because in biology the genome is not given by fixed length chromosomes. Rather, genetic material can come in all shapes and sizes. The existence of this genetic algorithm generalization should also give us all hope that it will be possible to generalize genetic programming schema theorems to work when the representation is not of a fixed length size and shape. The other applications of schema theory will also be useful in the move to computational evolution, and their existence suggests that schema theory will continue to give surprising applications in the future. If there is any lesson to be taken from Poli's work it is that schema theory is strong and can adapt to any problem thrown at it. Generalizing schema theory tends to make proofs easier to understand, so it's possible schema theory can lead the way in the move from artificial evolution to computational evolution.