Exact GP Schema Theory for Headless Chicken
Crossover and Subtree Mutation
CSRP-00-23. University of Birmingham, School of Computer Science, (December 2000)Abstract
In this paper a new general GP schema theory for
headless chicken crossover and subtree mutation is
presented. The theory gives an exact formulation for
the expected number of instances of a schema at the
next generation. The theory includes four main results:
microscopic schema theorems for both headless chicken
crossover and subtree mutation, and two corresponding
macroscopic theorems. The microscopic versions are
applicable to headless chicken crossovers and subtree
mutation operators. The macroscopic versions are valid
for slightly more restricted sets of headless chicken
and mutation operators in which the probability of
selecting the crossover/mutation point(s) depends only
on the size and shape of the parent program(s). In the
paper we provide examples which show how the theory can
be specialised to specific operators.