Hyperschema Theory for GP with One-Point Crossover, Building Blocks, and Some New Results in GA Theory

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

  author =       "R. Poli",
  title =        "Hyperschema Theory for GP with One-Point Crossover,
                 Building Blocks, and Some New Results in GA Theory",
  booktitle =    "Genetic Programming, Proceedings of EuroGP'2000",
  year =         "2000",
  editor =       "Riccardo Poli and Wolfgang Banzhaf and 
                 William B. Langdon and Julian F. Miller and Peter Nordin and 
                 Terence C. Fogarty",
  volume =       "1802",
  series =       "LNCS",
  pages =        "163--180",
  address =      "Edinburgh",
  publisher_address = "Berlin",
  month =        "15-16 " # apr,
  organisation = "EvoNet",
  publisher =    "Springer-Verlag",
  keywords =     "genetic algorithms, genetic programming",
  ISBN =         "3-540-67339-3",
  URL =          "http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1802&spage=163",
  DOI =          "doi:10.1007/978-3-540-46239-2_12",
  abstract =     "Two main weaknesses of GA and GP schema theorems are
                 that they provide only information on the expected
                 value of the number of instances of a given schema at
                 the next generation E[m(H,t+1)], and they can
                 only give a lower bound for such a quantity. This paper
                 presents new theoretical results on GP and GA schemata
                 which largely overcome these weaknesses. Firstly,
                 unlike previous results which concentrated on schema
                 survival and disruption, our results extend to GP
                 recent work on GA theory by Stephens and Waelbroeck,
                 and make the effects and the mechanisms of schema
                 creation explicit. This allows us to give an exact
                 formulation (rather than a lower bound) for the
                 expected number of instances of a schema at the next
                 generation. Thanks to this formulation we are then able
                 to provide in improved version for an earlier GP schema
                 theorem in which some schema creation events are
                 accounted for, thus obtaining a tighter bound for
                 E[m(H,t+1)]. This bound is a function of the
                 selection probabilities of the schema itself and of a
                 set of lower-order schemata which one-point crossover
                 uses to build instances of the schema. This result
                 supports the existence of building blocks in GP which,
                 however, are not necessarily all short, low-order or
                 highly fit. Building on earlier work, we show how
                 Stephens and Waelbroeck's GA results and the new GP
                 results described in the paper can be used to evaluate
                 schema variance, signal-to-noise ratio and, in general,
                 the probability distribution of m(H,t+1). In
                 addition, we show how the expectation operator can be
                 removed from the schema theorem so as to predict with a
                 known probability whether m(H,t+1) (rather than
                 E[m(H,t+1)]) is going to be above a given
  notes =        "EuroGP'2000, part of \cite{poli:2000:GP}",

Genetic Programming entries for Riccardo Poli