General schema theory for genetic programming with subtree-swapping crossover: Part II

Riccardo Poli, Nicholas Freitag McPhee

    Research output: Contribution to journalArticlepeer-review

    54 Scopus citations

    Abstract

    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.

    Original languageEnglish (US)
    Pages (from-to)169-206
    Number of pages38
    JournalEvolutionary Computation
    Volume11
    Issue number2
    DOIs
    StatePublished - Jun 2003

    Keywords

    • Genetic Programming
    • Schema Theory
    • Standard Crossover

    Fingerprint Dive into the research topics of 'General schema theory for genetic programming with subtree-swapping crossover: Part II'. Together they form a unique fingerprint.

    Cite this