Holland's schema theorem

Holland's schema theorem Holland's schema theorem, also called the fundamental theorem of genetic algorithms,[1] is an inequality that results from coarse-graining an equation for evolutionary dynamics. The Schema Theorem says that short, low-order schemata with above-average fitness increase exponentially in frequency in successive generations. The theorem was proposed by John Holland in the 1970s. It was initially widely taken to be the foundation for explanations of the power of genetic algorithms. No entanto, this interpretation of its implications has been criticized in several publications reviewed in,[2] where the Schema Theorem is shown to be a special case of the Price equation with the schema indicator function as the macroscopic measurement.

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 e 6 e um 0 at position 4. o * is a wildcard symbol, which means that positions 2 e 5 can have a value of either 1 ou 0. The order of a schema {estilo de exibição o(H)} is defined as the number of fixed positions in the template, while the defining length {delta de estilo de exibição (H)} is the distance between the first and last specific positions. The order of 1*10*1 é 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: {nome do operador de estilo de exibição {E} (m(H,t+1))geq {m(H,t)f(H) over a_{t}}[1-p].} Aqui {estilo de exibição m(H,t)} is the number of strings belonging to schema {estilo de exibição H} at generation {estilo de exibição t} , {estilo de exibição f(H)} is the observed average fitness of schema {estilo de exibição H} e {estilo de exibição a_{t}} is the observed average fitness at generation {estilo de exibição t} . The probability of disruption {estilo de exibição p} is the probability that crossover or mutation will destroy the schema {estilo de exibição H} . Under the assumption that {estilo de exibição p_{m}ll 1} , it can be expressed as: {displaystyle p={delta (H) over l-1}p_{c}+o(H)p_{m}} Onde {estilo de exibição o(H)} is the order of the schema, {estilo de exibição l} is the length of the code, {estilo de exibição p_{m}} is the probability of mutation and {estilo de exibição p_{c}} is the probability of crossover. So a schema with a shorter defining length {delta de estilo de exibição (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 {estilo de exibição H} will be created "from scratch" by mutation of a single string (or recombination of two strings) that did not belong to {estilo de exibição H} in the previous generation. Além disso, the expression for {estilo de exibição 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 {estilo de exibição H} .

Limitation Plot of a multimodal function in two variables.

The schema theorem holds under the assumption of a genetic algorithm that maintains an infinitely large population, but does not always carry over to (finito) 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.[3] The reason that the Schema Theorem cannot explain the power of genetic algorithms is that it holds for all problem instances, and cannot distinguish between problems in which genetic algorithms perform poorly, and problems for which genetic algorithms perform well.

References ^ Bridges, Clayton L.; Goldberg, David E. (1987). An analysis of reproduction and crossover in a binary-coded genetic algorithm. 2nd Int'l Conf. on Genetic Algorithms and their applications. ISBN 9781134989737. ^ Altenberg, eu. (1995). The Schema Theorem and Price’s Theorem. Foundations of genetic algorithms, 3, 23-49. ^ David E., Goldberg; Richardson, Jon (1987). Genetic algorithms with sharing for multimodal function optimization. 2nd Int'l Conf. on Genetic Algorithms and their applications. ISBN 9781134989737. J. Holanda, Adaptation in Natural and Artificial Systems, The MIT Press; Reprint edition 1992 (originally published in 1975). J. Holanda, Hidden Order: How Adaptation Builds Complexity, Helix Books; 1996. Categorias: Genetic algorithmsTheorems in discrete mathematics

Se você quiser conhecer outros artigos semelhantes a Holland's schema theorem você pode visitar a categoria Genetic algorithms.

Deixe uma resposta

seu endereço de e-mail não será publicado.

Ir para cima

Usamos cookies próprios e de terceiros para melhorar a experiência do usuário Mais informação