Holland's Schema Theorem

Holland's schema theorem gives a lower bound on the expected value of the number of strings matching a genetic algorithm schema after one generation of a simple genetic algorithm. Let be the number of strings matching schema at generation , let be their average fitness, and let be the population average fitness. For fitness-proportionate selection, one-point crossover with probability , and independent bit mutation with probability ,

where is the string length, is the number of fixed positions in , and is the distance between its first and last fixed positions. Thus short, low-order schemata with above-average fitness receive a favorable one-generation bound. The theorem does not by itself guarantee convergence of a genetic algorithm.