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

Created by W.Langdon from gp-bibliography.bib Revision:1.3872

@Article{poli03:ECJ_gener_schem_part_II,
  author =       "Riccardo Poli and Nicholas Freitag McPhee",
  title =        "General Schema theory for genetic programming with
                 subtree-swapping crossover: {Part II}",
  journal =      "Evolutionary Computation",
  year =         "2003",
  volume =       "11",
  number =       "2",
  month =        jun,
  pages =        "169--206",
  URL =          "http://cswww.essex.ac.uk/staff/rpoli/papers/ecj2003partII.pdf",
  DOI =          "doi:10.1162/106365603766646825",
  keywords =     "genetic algorithms, genetic programming, Node
                 Reference Systems, Models of Crossover, Schema Theory",
  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 \cite{poli03:ECJ_gener_schem_part_I}). 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 onepoint 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.",
  notes =        "see also \cite{poli03:ECJ_gener_schem_part_I}",
}

Genetic Programming entries for Riccardo Poli Nicholas Freitag McPhee

Citations