The Exact Schema Theorem

posted 7/12/99, paper revised 9/30/99

The Exact Schema Theorem

Alden H. Wright
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
wright@cs.umt.edu
(406) 243-4790
http://www.cs.umt.edu/u/wright/wright.htm


Abstract

A schema is a naturally defined subset of the space of fixed-length
binary strings.  The Holland Schema Theorem \cite{Holland} gives a 
lower bound on the expected fraction of a population in a schema after
one generation of a simple genetic algorithm.  
This paper gives formulas for the exact expected fraction of 
a population in a schema after one generation of the simple genetic 
algorithm.  

Holland's schema theorem has three parts, one for selection, one
for crossover, and one for mutation.  The selection part is exact,
whereas the crossover and mutation parts are approximations.
This paper shows how the crossover and mutation parts can be made
exact.  Holland's schema theorem follows naturally as a corollary.

There is a close relationship between schemata and the representation
of the population in the Walsh basis.  This relationship is used
in the derivation of the results, and can also make computation
of the schema averages more efficient.

This paper gives a version of the Vose infinite population model
where crossover and mutation are separated into two functions
rather than a single ``mixing'' function.