The Schema Theorem and Price's Theorem   [ST]

by

Altenberg, L.

Literature search on Evolutionary ComputationBBase ©1999-2013, Rasmus K. Ursem
     Home · Search · Adv. search · Authors · Login · Add entries   Webmaster
Note to authors: Please submit your bibliography and contact information - online papers are more frequently cited.

Info: Foundations of Genetic Algorithms 3 (Conference proceedings), 1995, p. 23-49
Keywords:genetic algorithms, genetic programming
Abstract:
Holland's Schema Theorem [ST] is widely taken to be the foundation for explanations of the power of genetic algorithms (GAs). [GA] [GAG] Yet some dissent has been expressed as to its implications. Here, dissenting arguments are reviewed and elaborated upon, explaining why the Schema Theorem [ST] has no implications for how well a GA is performing. Interpretations of the Schema Theorem [ST] 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 [ST] is derived which makes explicit the intuition for when a GA should perform well. Finally, the method of ``adaptive landscape'' analysis [LA] 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 samples. Copyright 1996 Lee Altenberg
Notes:
FOGA-3 Deals with GAs as a whole, not specifically GP.
URL(s):(G)zipped postscript
HTML

Review item:

Mark as doublet (will be reviewed)

Print entry




BibTex:
@InProceedings{Altenberg:1995STPT,
  author =       "Lee Altenberg",
  year =         "1995",
  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 # " 1994",
  organisation = "International Society for Genetic Algorithms",
  keywords =     "genetic algorithms, genetic programming",
  ISBN =         "1-55860-356-5",
  URL =          "ftp://ftp.mhpcc.edu/pub/incoming/altenberg/LeeSTPT.ps.Z",
  url_2 =        "http://pueo.mhpcc.edu/~altenber/PAPERS/LeeSTPT.html",
  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
                 samples.

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

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