Hyperschema Theory for GP with OnePoint Crossover, Building Blocks, and Some New Results in GA Theory
Created by W.Langdon from
gpbibliography.bib Revision:1.7706
 @InProceedings{poli:2000:htGP1xbb,

author = "R. Poli",

title = "Hyperschema Theory for GP with OnePoint 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 = "163180",

address = "Edinburgh",

publisher_address = "Berlin",

month = "1516 " # apr,

organisation = "EvoNet",

publisher = "SpringerVerlag",

keywords = "genetic algorithms, genetic programming",

ISBN = "3540673393",

DOI = "doi:10.1007/9783540462392_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 lowerorder schemata which onepoint 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, loworder 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, signaltonoise 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.",

notes = "EuroGP'2000, part of \cite{poli:2000:GP}",
 }
Genetic Programming entries for
Riccardo Poli
Citations