Exact Schema Theory and Markov Chain Models for Genetic Programming and Variable-length Genetic Algorithms with Homologous Crossover

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

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

Genetic Programming entries for Riccardo Poli Nicholas Freitag McPhee Jonathan E Rowe

Citations