| Authors: |
Riccardo Poli
and Nicholas Freitag McPhee
and Jonathan E. Rowe
|
| URL: |
http://cswww.essex.ac.uk/staff/rpoli/papers/GPEM2004.pdf |
| Tags: |
Markov
Vose
algorithms,
chain,
genetic
matrices
mixing
model,
programming,
schema
theory,
variable-length
|
| 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. |
@article{poli:2004:GPEM,
title = {Exact Schema Theory and Markov Chain Models for
Genetic Programming and Variable-length Genetic
Algorithms with Homologous Crossover},
author = {Riccardo Poli and Nicholas Freitag McPhee and Jonathan E. Rowe},
journal = {Genetic Programming and Evolvable Machines},
month = {March},
number = {1},
pages = {31--70},
url = {http://cswww.essex.ac.uk/staff/rpoli/papers/GPEM2004.pdf},
volume = {5},
year = {2004},
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.},
issn = {1389-2576}, size = {40 pages}, notes = {Article ID: 5264734}, doi = {doi:10.1023/B:GENP.0000017010.41337.a7},
keywords = {Markov Vose algorithms, chain, genetic matrices mixing model, programming, schema theory, variable-length }
}
::