Microscopic and Macroscopic Schema Theories for Genetic Programming and Variable-length Genetic Algorithms with One-Point Crossover, their Use and their Relations with Earlier GP and GA Schema Theories
Created by W.Langdon from
gp-bibliography.bib Revision:1.7964
- @TechReport{Poli00b,
-
author = "Riccardo Poli",
-
title = "Microscopic and Macroscopic Schema Theories for
Genetic Programming and Variable-length Genetic
Algorithms with One-Point Crossover, their Use and
their Relations with Earlier GP and GA Schema
Theories",
-
institution = "University of Birmingham, School of Computer Science",
-
number = "CSRP-00-15",
-
month = oct,
-
year = "2000",
-
keywords = "genetic algorithms, genetic programming",
-
email = "R.Poli@cs.bham.ac.uk",
-
file = "/2000/CSRP-00-15.ps.gz",
-
URL = "ftp://ftp.cs.bham.ac.uk/pub/tech-reports/2000/CSRP-00-15.ps.gz",
-
abstract = "A few schema theorems for GP have been proposed in the
literature in the last few years. One of their main
weaknesses is that they provide only a lower bound for
the expected value of the number of instances of a
given schema H at the next generation, E[m(H,t+1)],
rather than an exact value. This paper presents new
theoretical results for GP with one-point crossover
which overcome this problem. Firstly, we give an exact
formulation (rather than a lower bound) for the
expected number of instances of a schema at the next
generation in terms of microscopic quantities. Thanks
to this formulation we are then able to provide in
improved version for an earlier GP schema theorem in
which some (but not all) schema creation events are
accounted for, thus obtaining a tighter bound for
E[m(H,t+1)]. Then, we extend the microscopic schema
theorem to obtain an exact formulation of E[m(H,t+1)]
in terms of macroscopic quantities. In this formulation
E[m(H,t+1)] 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 makes the
effects and the mechanisms of schema creation explicit,
unlike previous work which concentrated on schema
survival and disruption. This supports the existence of
building blocks in GP which, however, are not
necessarily all short, low-order or highly fit. Also,
the macroscopic schema 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, only to
mention some possibilities.",
- }
Genetic Programming entries for
Riccardo Poli
Citations