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.8010

@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