The Trouble Aspects of a Building Block Hypothesis for Genetic Programming

Una-May O'Reilly

Working Papers from Santa Fe Institute

Abstract: In 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.

Date: 1994-02
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:94-02-001

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().