The Schema Theorem and Price's Theorem

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

  author =       "Lee Altenberg",
  year =         "1994",
  title =        "The {Schema} {Theorem} and {Price}'s {Theorem}",
  booktitle =    "Foundations of Genetic Algorithms 3",
  editor =       "L. Darrell Whitley and Michael D. Vose",
  publisher =    "Morgan Kaufmann",
  publisher_address = "San Francisco, CA, USA",
  address =      "Estes Park, Colorado, USA",
  pages =        "23--49",
  month =        "31 " # jul # "--2 " # aug,
  organisation = "International Society for Genetic Algorithms",
  note =         "Published 1995",
  keywords =     "genetic algorithms, genetic programming",
  ISBN =         "1-55860-356-5",
  URL =          "",
  URL =          "",
  abstract =     "Holland's Schema Theorem is widely taken to be the
                 foundation for explanations of the power of genetic
                 algorithms (GAs). Yet some dissent has been expressed
                 as to its implications. Here, dissenting arguments are
                 reviewed and elaborated upon, explaining why the Schema
                 Theorem has no implications for how well a GA is
                 performing. Interpretations of the Schema Theorem have
                 implicitly assumed that a correlation exists between
                 parent and offspring fitnesses, and this assumption is
                 made explicit in results based on Price's Covariance
                 and Selection Theorem. Schemata do not play a part in
                 the performance theorems derived for representations
                 and operators in general. However, schemata re-emerge
                 when recombination operators are used. Using
                 Geiringer's recombination distribution representation
                 of recombination operators, a ``missing'' schema
                 theorem is derived which makes explicit the intuition
                 for when a GA should perform well. Finally, the method
                 of ``adaptive landscape'' analysis is examined and
                 counterexamples offered to the commonly used
                 correlation statistic. Instead, an alternative
                 statistic---the transmission function in the fitness
                 domain--- is proposed as the optimal statistic for
                 estimating GA performance from limited

                 Copyright 1996 Lee Altenberg",
  notes =        "FOGA-3

                 Deals with GAs as a whole, not specifically GP.",

Genetic Programming entries for Lee Altenberg