Holland's schema theorem

Holland's schema theorem, also called the fundamental theorem of genetic algorithms, is widely taken to be the foundation for explanations of the power of genetic algorithms. It says that short, low-order schemata with above-average fitness increase exponentially in successive generations. The theorem was proposed by John Holland in the 1970s.

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.

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 ${\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:

...
Wikipedia