The Troubling Aspects of a Building Block Hypothesis for Genetic Programming

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

  author =       "U. M. O'Reilly and F. Oppacher",
  title =        "The Troubling Aspects of a Building Block Hypothesis
                 for Genetic Programming",
  institution =  "Santa Fe Institute",
  year =         "1992",
  type =         "Working Paper",
  number =       "94-02-001",
  address =      "1399 Hyde Park Road Santa Fe, New Mexico 87501-8943

  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  size =         "12 pages",
  abstract =     "n this paper we rigorously formulate the Schema
                 Theorem for Genetic Programming (GP). This involves
                 defining a schema, schema order, and defining length
                 and accounting for the variable length and the
                 non-homologous nature of GP'S representation. The GP
                 Schema Theorem and the related notion of a GP Building
                 Block are used to construct a testable hypothetical
                 account of how GP searches by hierarchically combining
                 building blocks. Since building blocks need to have
                 consistent above average fitness and compactness, and
                 since the term in the GP Schema Theorem that expresses
                 compactness is a random variable, the proposed account
                 of GP search behavior is based on empirically
                 questionable statistical assumptions. In particular,
                 low variance in schema fitness is questionable because
                 the performance of a schema depends in a highly
                 sensitive manner on the context provided by the
                 programs in which it is found. GP crossover is likely
                 to change this context from one generation to the next
                 which results in high variance in observed schema
                 fitness. Low variance in compactness seems fortuitous
                 rather than assured in GP because schema-containing
                 programs change their sizes essentially at random.",
  notes =        "A version of this paper will be published in
                 Foundations of Genetic Algorithms (FOGA), See

Genetic Programming entries for Una-May O'Reilly Franz Oppacher