The Schema Theorem and Price's Theorem

Lee Altenberg

In Foundations of Genetic Algorithms 3, ed. Darrell Whitley and Michael Vose. pp. 23-49. Morgan Kaufmann, San Francisco, 1995.

Measurement functions, F(x, . ), and the population properties measured by their mean in the population, F^bar.}

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.