Sub-Tree Swapping Crossover, Allele Diffusion and GP Convergence

Created by W.Langdon from gp-bibliography.bib Revision:1.4216

  author =       "Stephen Dignum and Riccardo Poli",
  title =        "Sub-Tree Swapping Crossover, Allele Diffusion and GP
  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