Holland's schema theorem

A schema is a template that identifies a subset of strings with similarities at certain string positions. Schemata are a special case of cylinder sets, and hence form a topological space.

Description

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 ${\displaystyle o(H)}$ is defined as the number of fixed positions in the template, while the defining length ${\displaystyle \delta (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:

${\displaystyle \mathrm{E}(m(H,t+1))\ge \frac{m(H,t)f(H)}{a_t}[1-p].}$

Here ${\displaystyle m(H,t)}$ is the number of strings belonging to schema ${\displaystyle H}$ at generation ${\displaystyle t}$, ${\displaystyle f(H)}$ is the observed average fitness of schema ${\displaystyle H}$ and ${\displaystyle a_t}$ is the observed average fitness at generation ${\displaystyle t}$. The probability of disruption ${\displaystyle p}$ is the probability that crossover or mutation will destroy the schema ${\displaystyle H}$. Under the assumption that ${\displaystyle p_m\ll 1}$, it can be expressed as:

${\displaystyle p=\frac{\delta (H)}{l-1}{p}_c+o(H)p_m}$

where ${\displaystyle o(H)}$ is the order of the schema, ${\displaystyle l}$ is the length of the code, ${\displaystyle p_m}$ is the probability of mutation and ${\displaystyle p_c}$ is the probability of crossover. So a schema with a shorter defining length ${\displaystyle \delta (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 ${\displaystyle H}$ will be created "from scratch" by mutation of a single string (or recombination of two strings) that did not belong to ${\displaystyle H}$ in the previous generation. Moreover, the expression for ${\displaystyle p}$ is clearly pessimistic: depending on the mating partner, recombination may not disrupt the scheme even when a cross point is selected between the first and the last fixed position of ${\displaystyle H}$.