General Schema Theory for Genetic Programming with Subtree-Swapping Crossover: Part II
Authors:
- 1 June 2003
- journal article
- research article
- Published by MIT Press in Evolutionary Computation
- Vol. 11 (2) , 169-206
Abstract
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.Keywords
This publication has 15 references indexed in Scilit:
- General Schema Theory for Genetic Programming with Subtree-Swapping Crossover: Part IEvolutionary Computation, 2003
- Grammatical evolutionIEEE Transactions on Evolutionary Computation, 2001
- Schemata Evolution and Building BlocksEvolutionary Computation, 1999
- Schema processing under proportional selection in the presence of random effectsIEEE Transactions on Evolutionary Computation, 1997
- Strongly Typed Genetic ProgrammingEvolutionary Computation, 1995
- Balancing Accuracy and Parsimony in Genetic ProgrammingEvolutionary Computation, 1995
- A genetic algorithm tutorialStatistics and Computing, 1994
- Analysis of genetic algorithms using statistical mechanicsPhysical Review Letters, 1994
- A Markov Chain Framework for the Simple Genetic AlgorithmEvolutionary Computation, 1993
- On the Probability Theory of Linkage in Mendelian HeredityThe Annals of Mathematical Statistics, 1944