Holland's schema theorem

Description

For example, consider binary strings of length 6. The schema 1*10*1 describes the set of all strings of length 6 with 1's at positions 1, 3 and 6 and a 0 at position 4. The * is a wildcard symbol, which means that positions 2 and 5 can have a value of either 1 or 0. The order of a schema o ( H ) is defined as the number of fixed positions in the template, while the defining length δ ( H ) is the distance between the first and last specific positions. The order of 1*10*1 is 4 and its defining length is 5. The fitness of a schema is the average fitness of all strings matching the schema. The fitness of a string is a measure of the value of the encoded problem solution, as computed by a problem-specific evaluation function. Using the established methods and genetic operators of genetic algorithms, the schema theorem states that short, low-order schemata with above-average fitness increase exponentially in successive generations. Expressed as an equation:

Here m ( H , t ) is the number of strings belonging to schema H at generation t , f ( H ) is the observed average fitness of schema H and a t is the observed average fitness at generation t . The probability of disruption p is the probability that crossover or mutation will destroy the schema H . It can be expressed as:

where o ( H ) is the order of the schema, l is the length of the code, p m is the probability of mutation and p c is the probability of crossover. So a schema with a shorter defining length δ ( H ) is less likely to be disrupted.
An often misunderstood point is why the Schema Theorem is an inequality rather than an equality. The answer is in fact simple: the Theorem neglects the small, yet non-zero, probability that a string belonging to the schema H will be created "from scratch" by mutation of a single string (or recombination of two strings) that did not belong to H in the previous generation.

Limitation

The schema theorem holds under the assumption of a genetic algorithm that maintains an infinitely large population, but does not always carry over to (finite) practice: due to sampling error in the initial population, genetic algorithms may converge on schemata that have no selective advantage. This happens in particular in multimodal optimization, where a function can have multiple peaks: the population may drift to prefer one of the peaks, ignoring the others.