Sub-Tree Swapping Crossover, Allele Diffusion and GP Convergence
Created by W.Langdon from
gp-bibliography.bib Revision:1.7964
- @InProceedings{Dignum:2008:PPSN,
-
author = "Stephen Dignum and Riccardo Poli",
-
title = "Sub-Tree Swapping Crossover, Allele Diffusion and GP
Convergence",
-
booktitle = "Parallel Problem Solving from Nature - PPSN X",
-
year = "2008",
-
editor = "Gunter Rudolph and Thomas Jansen and Simon Lucas and
Carlo Poloni and Nicola Beume",
-
volume = "5199",
-
series = "LNCS",
-
pages = "368--377",
-
address = "Dortmund",
-
month = "13-17 " # sep,
-
publisher = "Springer",
-
keywords = "genetic algorithms, genetic programming, Search,
Crossover Bias, Allele Diffusion, Convergence",
-
ISBN = "3-540-87699-5",
-
DOI = "doi:10.1007/978-3-540-87700-4_37",
-
abstract = "We provide strong evidence that sub-tree swapping
crossover when applied to tree-based representations
will cause alleles (node labels) to diffuse within
length classes. For a-ary trees we provide further
confirmation that all programs are equally likely to be
sampled within any length class when sub-tree swapping
crossover is applied in the absence of selection and
mutation. Therefore, we propose that this form of
search is unbiased - within length classes - for a-ary
trees. Unexpectedly, however, for mixed-arity trees
this is not found and a more complicated form of search
is taking place where certain tree shapes, hence
programs, are more likely to be sampled than others
within each class. We examine the reasons for such
shape bias in mixed arity representations and provide
the practitioner with a thorough examination of
sub-tree swapping crossover bias. The results of this,
when combined with crossover length bias research,
explain Genetic Programming's lack of structural
convergence during later stages of an experimental run.
Several operators are discussed where a broader form of
convergence may be detected in a similar way to that
found in Genetic Algorithm experimentation.",
-
notes = "PPSN X",
- }
Genetic Programming entries for
Stephen Dignum
Riccardo Poli
Citations