O teorema do esquema holandês

O teorema do esquema holandês, também chamado de teorema fundamental dos algoritmos genéticos, é uma desigualdade que resulta da formação de uma equação para a dinâmica evolucionária. O Teorema do Esquema diz que os esquemas curtos e de baixa ordem com aptidão acima da média aumentam exponencialmente de freqüência em gerações sucessivas. O teorema foi proposto por John Holland nos anos 70. Inicialmente foi considerado como sendo a base para explicações sobre o poder dos algoritmos genéticos. Entretanto, esta interpretação de suas implicações tem sido criticada em várias publicações revisadas em , onde o Teorema do Esquema é mostrado como um caso especial da equação de Preço com a função do indicador do esquema como a medida macroscópica.

Um esquema é um modelo que identifica um subconjunto de cordas com semelhanças em certas posições de cordas. Os esquemas são um caso especial de conjuntos de cilindros e, portanto, formam um espaço topológico.

Descrição

Considere cordas binárias de comprimento 6. O esquema 1*10*1 descreve o conjunto de todas as cordas de comprimento 6 com 1's nas posições 1, 3 e 6 e um 0 na posição 4. O * é um símbolo curinga, o que significa que as posições 2 e 5 podem ter um valor 1 ou 0. A ordem de um esquema o ( H ) {\displaystyle o(H)} $o(H)$ é definida como o número de posições fixas no modelo, enquanto que o comprimento definido δ ( H ) {\displaystyle \delta (H)} $\delta (H)$ é a distância entre a primeira e a última posição específica. A ordem de 1*10*1 é 4 e seu comprimento definidor é 5. A adequação de um esquema é a adequação média de todas as cordas que correspondem ao esquema. A adequação de uma corda é uma medida do valor da solução do problema codificado, como computado por uma função de avaliação específica do problema. Usando os métodos estabelecidos e operadores genéticos de algoritmos genéticos, o teorema do esquema afirma que esquemas curtos e de baixa ordem com aptidão acima da média aumentam exponencialmente em gerações sucessivas. Expresso como uma equação:

E ( m ( H , t + 1 ) ) ≥ m ( H , t ) f ( H ) a t [ 1 - p ] . estilo de jogo do operador (m(H,t+1))geq {m(H,t)f(H) {t}[1-p]. } $\operatorname {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p].$

Aqui m ( H , t ) $m(H,t)$ é o número de cordas pertencentes ao esquema H ( H , t ) $H$ na geração t ( H , t ) $t$ f ( H ) f(H ) $f(H)$ é a aptidão média observada no esquema H ( H ) $H$ e um t ( H ) t $a_{t}$ é a aptidão média observada na geração t ( H ) t $t$ é a aptidão média observada na geração t ( H ) f(H ) f(H ) f(H ) f(H ) é a aptidão média observada no esquema H ( H ) t é a aptidão média observada na geração t A probabilidade de perturbação p estilo de exibição p $p$ é a probabilidade de que o cruzamento ou mutação destrua o esquema H estilo de exibição H $H$ . Ela pode ser expressa como:

p = δ ( H ) l - 1 p c + o ( H ) p m {\displaystyle p={\delta (H) {\delta (H) }over l-1}p_{c}+o(H)p_{m}}} $p={\delta (H) \over l-1}p_{c}+o(H)p_{m}$

onde o ( H ) $o(H)$ é a ordem do esquema, l ( ) $l$ é o comprimento do código, p m ( ) $p_{m}$ é a probabilidade de mutação e p c ( ) $p_{c}$ é a probabilidade de crossover. Portanto, um esquema com um comprimento de definição mais curto δ ( H ) {\i1}displaystyle {\i}delta (H)} $\delta (H)$ é menos provável que seja interrompido.
Um ponto muitas vezes mal compreendido é a razão pela qual o Teorema do Esquema é uma desigualdade e não uma igualdade. A resposta é de fato simples: o Teorema negligencia a pequena, porém não nula, probabilidade de que uma corda pertencente ao esquema H $H$ seja criada "do zero" pela mutação de uma única corda (ou recombinação de duas cordas) que não pertencia ao esquema H $H$ na geração anterior.

Limitação

O teorema do esquema se mantém sob a suposição de um algoritmo genético que mantém uma população infinitamente grande, mas nem sempre transita para a prática (finita): devido ao erro de amostragem na população inicial, os algoritmos genéticos podem convergir em esquemas que não têm nenhuma vantagem seletiva. Isto acontece em particular na otimização multimodal, onde uma função pode ter picos múltiplos: a população pode se desviar para preferir um dos picos, ignorando os outros.

A razão pela qual o Teorema do Esquema não pode explicar o poder dos algoritmos genéticos é que ele é válido para todos os casos de problemas e não pode distinguir entre problemas nos quais os algoritmos genéticos têm mau desempenho e problemas nos quais os algoritmos genéticos têm bom desempenho.

Lote de uma função multimodal em duas variáveis.

Perguntas e Respostas

P: O que é o teorema do esquema de Holland?

R: O teorema do esquema de Holland é um teorema relacionado a algoritmos genéticos que diz que indivíduos com aptidão superior à média têm maior probabilidade de prevalecer.

P: Quem propôs o teorema do esquema de Holland e quando?

R: John Holland propôs o teorema do esquema de Holland na década de 1970.

P: O que é um esquema no contexto dos algoritmos genéticos?

R: No contexto dos algoritmos genéticos, um esquema é um modelo que identifica um subconjunto de cadeias de caracteres com semelhanças em determinadas posições de cadeia.

P: Qual é a interpretação do teorema do esquema de Holland que foi usado como base para explicações sobre o poder dos algoritmos genéticos?

R: A interpretação do teorema do esquema de Holland que foi usado como base para as explicações sobre o poder dos algoritmos genéticos é que os indivíduos com aptidão superior à média têm maior probabilidade de prevalecer.

P: O que as críticas ao teorema do esquema de Holland demonstraram ser?

R: As críticas ao teorema do esquema de Holland mostraram que ele é um caso especial da equação de Price com a função indicadora do esquema como medida macroscópica.

P: O que é um caso especial de conjuntos de cilindros?

R: Os esquemas são um caso especial de conjuntos de cilindros.

P: Que tipo de espaço os esquemas formam?

R: Os esquemas formam um espaço topológico.