General Schema theory for genetic programming with subtree-swapping crossover: Part II
Created by W.Langdon from
gp-bibliography.bib Revision:1.7954
- @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