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.7975
- @TechReport{poli:CSRP-99-18,
-
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/CSRP-99-18.ps.gz",
-
URL = "ftp://ftp.cs.bham.ac.uk/pub/tech-reports/1999/CSRP-99-18.ps.gz",
-
reportfilename = "pub/tech-reports/1999/CSRP-99-18.ps.gz",
-
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
Citations