An Overview of Schema Theory
---
paper_title: The Schema Theorem and Price's Theorem

paper_content:

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.
---
paper_title: A Schema Theorem for context-free grammars

paper_content:

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.
---
paper_title: The Troubling Aspects of a Building Block Hypothesis for Genetic Programming

paper_content:

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.
---
paper_title: General Schema Theory for Genetic Programming with Subtree-Swapping Crossover: Part II

paper_content:

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.
---
paper_title: Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover

paper_content:

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.
---
paper_title: General Schema Theory for Genetic Programming with Subtree-Swapping Crossover: Part II

paper_content:

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.
---
paper_title: Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover

paper_content:

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.
---
paper_title: Genetic Programming: On the Programming of Computers by Means of Natural Selection

paper_content:

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.
---
paper_title: The Troubling Aspects of a Building Block Hypothesis for Genetic Programming

paper_content:

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.
---
paper_title: Emergent Phenomena In Genetic Programming

paper_content:

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.
---
paper_title: Hyperschema Theory for GP with One-Point Crossover, Building Blocks, and Some New Results in GA Theory

paper_content:

Two main weaknesses of GA and GP schema theorems are that they provide only information on the expected value of the number of instances of a given schema at the next generation E[m(H,t + 1)], and they can only give a lower bound for such a quantity. This paper presents new theoretical results on GP and GA schemata which largely overcome these weaknesses. Firstly, unlike previous results which concentrated on schema survival and disruption, our results extend to GP recent work on GA theory by Stephens and Waelbroeck, and make the effects and the mechanisms of schema creation explicit. This allows us to give an exact formulation (rather than a lower bound) for the expected number of instances of a schema at the next generation. Thanks to this formulation we are then able to provide in improved version for an earlier GP schema theorem in which some schema creation events are accounted for, thus obtaining a tighter bound for E[m(H, t + 1)]. This bound is a function of the selection probabilities of the schema itself and of a set of lower-order schemata which one-point crossover uses to build instances of the schema. This result supports the existence of building blocks in GP which, however, are not necessarily all short, low-order or highly fit. Building on earlier work, we show how Stephens and Waelbroeck’s GA results and the new GP results described in the paper can be used to evaluate schema variance, signal-to-noise ratio and, in general, the probability distribution of m(H, t + 1). In addition, we show how the expectation operator can be removed from the schema theorem so as to predict with a known probability whether m(H, t + 1) (rather than E[m(H, t + 1)]) is going to be above a given threshold.
---
paper_title: General Schema Theory for Genetic Programming with Subtree-Swapping Crossover: Part II

paper_content:

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.
---
paper_title: General Schema Theory for Genetic Programming with Subtree-Swapping Crossover: Part I

paper_content:

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 indudes 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.
---
paper_title: Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover

paper_content:

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.
---
paper_title: Exact GP schema theory for headless chicken crossover and subtree mutation

paper_content:

A new general genetic programming (GP) schema theory for headless chicken crossover and subtree mutation is presented. The theory gives an exact formulation for the expected number of instances of a schema at the next generation, either in terms of microscopic quantities or in terms of macroscopic ones. This paper gives examples which show how the theory can be specialised to specific operators.
---
paper_title: General Schema Theory for Genetic Programming with Subtree-Swapping Crossover: Part II

paper_content:

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.
---
paper_title: Schema Theorems without Expectations

paper_content:

This paper presents two new schema theorems in which expectations are absent. The first theorem provides confidence intervals for the number of instances of a schema at the next generation. The second gives a lower bound for the same quantity.
---
paper_title: Hyperschema Theory for GP with One-Point Crossover, Building Blocks, and Some New Results in GA Theory

paper_content:

Two main weaknesses of GA and GP schema theorems are that they provide only information on the expected value of the number of instances of a given schema at the next generation E[m(H,t + 1)], and they can only give a lower bound for such a quantity. This paper presents new theoretical results on GP and GA schemata which largely overcome these weaknesses. Firstly, unlike previous results which concentrated on schema survival and disruption, our results extend to GP recent work on GA theory by Stephens and Waelbroeck, and make the effects and the mechanisms of schema creation explicit. This allows us to give an exact formulation (rather than a lower bound) for the expected number of instances of a schema at the next generation. Thanks to this formulation we are then able to provide in improved version for an earlier GP schema theorem in which some schema creation events are accounted for, thus obtaining a tighter bound for E[m(H, t + 1)]. This bound is a function of the selection probabilities of the schema itself and of a set of lower-order schemata which one-point crossover uses to build instances of the schema. This result supports the existence of building blocks in GP which, however, are not necessarily all short, low-order or highly fit. Building on earlier work, we show how Stephens and Waelbroeck’s GA results and the new GP results described in the paper can be used to evaluate schema variance, signal-to-noise ratio and, in general, the probability distribution of m(H, t + 1). In addition, we show how the expectation operator can be removed from the schema theorem so as to predict with a known probability whether m(H, t + 1) (rather than E[m(H, t + 1)]) is going to be above a given threshold.
---
paper_title: Analysis of Schema Variance and Short Term Extinction Likelihoods

paper_content:

This paper first analyses the impact of variance on schema transmission. Working from an exact derivation of the expected variance in schema transmission, it derives and analyses the signal-to-noise ratio for schemata. The paper then presents short term schema transmission probability results that focus on newly created schemata in the population. The analysis reveals the relative dependencies between schema transmission, population size, schema measured fitness, schema fragility and schema creation.
---
paper_title: Schema Theorems without Expectations

paper_content:

This paper presents two new schema theorems in which expectations are absent. The first theorem provides confidence intervals for the number of instances of a schema at the next generation. The second gives a lower bound for the same quantity.
---
paper_title: Analysis of Schema Variance and Short Term Extinction Likelihoods

paper_content:

This paper first analyses the impact of variance on schema transmission. Working from an exact derivation of the expected variance in schema transmission, it derives and analyses the signal-to-noise ratio for schemata. The paper then presents short term schema transmission probability results that focus on newly created schemata in the population. The analysis reveals the relative dependencies between schema transmission, population size, schema measured fitness, schema fragility and schema creation.
---
paper_title: Hyperschema Theory for GP with One-Point Crossover, Building Blocks, and Some New Results in GA Theory

paper_content:

Two main weaknesses of GA and GP schema theorems are that they provide only information on the expected value of the number of instances of a given schema at the next generation E[m(H,t + 1)], and they can only give a lower bound for such a quantity. This paper presents new theoretical results on GP and GA schemata which largely overcome these weaknesses. Firstly, unlike previous results which concentrated on schema survival and disruption, our results extend to GP recent work on GA theory by Stephens and Waelbroeck, and make the effects and the mechanisms of schema creation explicit. This allows us to give an exact formulation (rather than a lower bound) for the expected number of instances of a schema at the next generation. Thanks to this formulation we are then able to provide in improved version for an earlier GP schema theorem in which some schema creation events are accounted for, thus obtaining a tighter bound for E[m(H, t + 1)]. This bound is a function of the selection probabilities of the schema itself and of a set of lower-order schemata which one-point crossover uses to build instances of the schema. This result supports the existence of building blocks in GP which, however, are not necessarily all short, low-order or highly fit. Building on earlier work, we show how Stephens and Waelbroeck’s GA results and the new GP results described in the paper can be used to evaluate schema variance, signal-to-noise ratio and, in general, the probability distribution of m(H, t + 1). In addition, we show how the expectation operator can be removed from the schema theorem so as to predict with a known probability whether m(H, t + 1) (rather than E[m(H, t + 1)]) is going to be above a given threshold.
---
paper_title: A simple but theoretically-motivated method to control bloat in genetic programming

paper_content:

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.
---
paper_title: Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover

paper_content:

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.
---
paper_title: Markov Chain Models for GP and Variable-length GAs with Homologous Crossover

paper_content:

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.
---
paper_title: Exact Schema Theory and Markov Chain Models for Genetic Programming and Variable-length Genetic Algorithms with Homologous Crossover

paper_content:

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.
---
paper_title: General Schema Theory for Genetic Programming with Subtree-Swapping Crossover: Part II

paper_content:

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.
---
paper_title: A simple but theoretically-motivated method to control bloat in genetic programming

paper_content:

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.
---
paper_title: Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover

paper_content:

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.
---
paper_title: Exact Schema Theorems for GP with One-Point and Standard Crossover Operating on Linear Structures and their Application to the Study of the Evolution of Size

paper_content:

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.
---
paper_title: Exact Schema Theory and Markov Chain Models for Genetic Programming and Variable-length Genetic Algorithms with Homologous Crossover

paper_content:

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.
---
paper_title: General Schema Theory for Genetic Programming with Subtree-Swapping Crossover: Part II

paper_content:

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.
---
paper_title: Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover

paper_content:

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.
---
paper_title: Exact Schema Theory and Markov Chain Models for Genetic Programming and Variable-length Genetic Algorithms with Homologous Crossover

paper_content:

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.
---

Title: An Overview of Schema Theory

Section 1: Introduction
Description 1: Provide an overview of evolutionary computation, genetic algorithms, and introduce schema theory.

Section 2: The Schema Theorem for Genetic Algorithms
Description 2: Discuss the Schema Theorem and its significance in genetic algorithms.

Section 3: History of Schema Theory
Description 3: Review the historical development of schema theory and early debates within the field.

Section 4: Criticisms of Schema Theory
Description 4: Address various criticisms of schema theory and responses to these criticisms.

Section 5: Schema Theory for Genetic Programming
Description 5: Introduce genetic programming, its relationship to genetic algorithms, and different schema definitions for genetic programming.

Section 6: Exact Schema Theory
Description 6: Explore the development of exact schema theory and its implications for genetic algorithms and genetic programming.

Section 7: Schema Theorems without the Expectation Operator
Description 7: Discuss schema theorems that do not rely on the expectation operator and their significance.

Section 8: Conditional Schema Theorems
Description 8: Examine conditional schema theorems and their response to stochastic fitness functions.

Section 9: Relationship between Schema Theory and Markov Models
Description 9: Analyze the connection between schema theories and Markov models.

Section 10: Applications of Schema Theory
Description 10: Highlight applications of schema theory in genetic programming and other fields.

Section 11: Future Directions
Description 11: Suggest various avenues for future research and development in schema theory.