Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover

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

@Article{poli:2001:GPEM,
  author =       "Riccardo Poli",
  title =        "Exact Schema Theory for Genetic Programming and
                 Variable-Length Genetic Algorithms with One-Point
                 Crossover",
  journal =      "Genetic Programming and Evolvable Machines",
  year =         "2001",
  volume =       "2",
  number =       "2",
  pages =        "123--163",
  month =        jun,
  keywords =     "genetic algorithms, genetic programming, schema
                 theory, one-point crossover, variable-length genetic
                 algorithms",
  ISSN =         "1389-2576",
  URL =          "http://ipsapp009.lwwonline.com/content/getfile/4723/5/4/fulltext.pdf",
  URL =          "http://cswww.essex.ac.uk/staff/poli/papers/postscript/Poli-GPEM2001.ps.gz",
  DOI =          "doi:10.1023/A:1011552313821",
  URL =          "http://citeseer.ist.psu.edu/503095.html",
  abstract =     "A few schema theorems for genetic programming (GP)
                 have been proposed in the literature in the last few
                 years. Since they consider schema survival and
                 disruption only, they can only provide a lower bound
                 for the expected value of the number of instances of a
                 given schema at the next generation rather than an
                 exact value. This paper presents theoretical results
                 for GP with one-point crossover which overcome this
                 problem. First, we give an exact formulation for the
                 expected number of instances of a schema at the next
                 generation in terms of microscopic quantities. Due to
                 this formulation we are then able to provide an
                 improved version of an earlier GP schema theorem in
                 which some (but not all) schema creation events are
                 accounted for. Then, we extend this result to obtain an
                 exact formulation in terms of macroscopic quantities
                 which makes all the mechanisms of schema creation
                 explicit. This theorem allows the exact formulation of
                 the notion of effective fitness in GP and opens the way
                 to future work on GP convergence, population sizing,
                 operator biases, and bloat, to mention only some of the
                 possibilities.",
  notes =        "Article ID: 335712",
}

Genetic Programming entries for Riccardo Poli

Citations