TY - JOUR

T1 - General schema theory for genetic programming with subtree-swapping crossover

T2 - Part II

AU - Poli, Riccardo

AU - McPhee, Nicholas Freitag

PY - 2003/6

Y1 - 2003/6

N2 - This paper is the second part of a two-part paper which introduces a general schema theory for generic 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.

AB - This paper is the second part of a two-part paper which introduces a general schema theory for generic 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.

KW - Genetic Programming

KW - Schema Theory

KW - Standard Crossover

UR - http://www.scopus.com/inward/record.url?scp=0042378952&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0042378952&partnerID=8YFLogxK

U2 - 10.1162/106365603766646825

DO - 10.1162/106365603766646825

M3 - Article

C2 - 12875668

AN - SCOPUS:0042378952

SN - 1063-6560

VL - 11

SP - 169

EP - 206

JO - Evolutionary Computation

JF - Evolutionary Computation

IS - 2

ER -