New Results in the Schema Theory for GP with One-Point Crossover which Account for Schema Creation, Survival and Disruption

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

  author =       "Riccardo Poli",
  title =        "New Results in the Schema Theory for {GP} with
                 One-Point Crossover which Account for Schema Creation,
                 Survival and Disruption",
  institution =  "University of Birmingham, School of Computer Science",
  number =       "CSRP-99-18",
  month =        dec,
  year =         "1999",
  file =         "/1999/",
  URL =          "",
  ftpaddress =   "",
  reportfilename = "pub/tech-reports/1999/",
  keywords =     "genetic algorithms, genetic programming",
  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. We present
                 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 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 threshold.",

Genetic Programming entries for Riccardo Poli