Techreport,
General Schema Theory for Genetic Programming with Subtree-Swapping Crossover
CSRP-00-16. University of Birmingham, School of Computer Science, (November 2000)
Abstract
In this paper a new general schema theory for genetic
programming is presented. 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
which makes it possible to describe programs as
functions over the space N^2 and allows one to model
the process of selection of the crossover points of
subtree-swapping crossovers as a probability
distribution over N^4. The theory is also based on the
notion of variable-arity hyperschema, which generalises
previous definitions of schema or hyperschema
introduced in GP. The theory includes two main theorems
describing the propagation of GP schemata: a
microscopic schema theorem and a macroscopic one. 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 equally applicable to
standard GP crossover with and without uniform
selection of the crossover points, as it is to
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 their size and shape. In
the paper we provide examples which show how the theory
can be specialised to specific crossover operators and
how it can be used to derive other general results such
as an exact definition of effective fitness and a
size-evolution equation for GP with subtree-swapping
crossover.
