Abstract
Genetic Programming (GP) homologous crossovers are a
group of operators, including GP one-point crossover
and GP uniform crossover, where the offspring are
created preserving the position of the genetic material
taken from the parents. We present an exact schema
theory for GP and variable-length Genetic Algorithms
(GAs) which is applicable to this class of operators.
The theory is based on the concepts of GP crossover
masks and GP recombination distributions that are
generalisations of the corresponding notions used in GA
theory and in population genetics, as well as the
notions of hyperschema and node reference systems,
which are specifically required when dealing with
variable size representations.
We also present a Markov chain model for GP and
variable-length GAs with homologous crossover. We
obtain this result by using the core of Vose's model
for GAs in conjunction with the GP schema theory. The
model is then specialised for the case of GP operating
on 0/1 trees: a tree-like generalisation of the concept
of binary string. For these, symmetries exist that can
be exploited to obtain further simplifications.
In the absence of mutation, the Markov chain model
presented here generalises Vose's GA model to GP and
variable-length GAs. Likewise, our schema theory
generalises and refines a variety of previous results
in GP and GA theory.
Users
Please
log in to take part in the discussion (add own reviews or comments).