Algorithms, genetics, and populations: The schemata theorem revisited

Models for the genetic evolution of natural populations have supplied the inspiration for the adaptive computer algorithms known as “genetic algorithms.” In its original form, a genetic algorithm simulates the evolution of a haploid population: Genetic variation is produced by mutation at a number of genetic loci in a chromosome, represented as a string of bits, and the variants in the various chromosomes are reshuffled by genetic recombination. In nature, the ability of a haploid individual to survive and reproduce is expressed as its fitness; in computer science the value of a string is measured by its ability to program a given task. The performance of genetic algorithms is evaluated in the “schemata theorem,” which we present and discuss in the context of the population genetics of multiple loci and propose a generalization of the theorem.