Paper Info
Title
General schema theory for genetic programming with subtree-swapping crossover: Part II.
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.
Year
DOI
Venue
2003
10.1162/106365603766646825
Evolutionary Computation
Keywords
DocType
Volume
specific crossover operator,crossover point,space n2,strongly-typed gp crossover,standard crossover,context-preserving crossover,exact schema theory,genetic programming,subtree-swapping crossover,gp crossover,schema theory,part ii,cartesian node reference system,gp schema,one-point crossover,general schema theory,size-fair crossover,two-part paper,probability distribution,lower bound
Journal
11
Issue
ISSN
Citations 
2
1063-6560
63
PageRank 
References 
Authors
3.25
33
2
Name
Order
Citations
PageRank
Riccardo Poli12589308.79
Nicholas Freitag McPhee240432.94