*
*
* Cadeias formadas por três símbolos: 0, 1, e *
* O símbolo * (um curinga) significa 0 ou 1.
*
* O número esperado de esquemas H na geração seguinte
(sem levar em conta a destruição causada pelo crossover
e mutação) é dado por:
* onde:
* m é o número de cromossomos da população atual que
contém o esquema H
* b é a média das aptidões de toda população
* a é a média das aptidões dos cromossomos que contém
o esquema H
*
É esperado que esquema H1 esteja presente em 1,8
indivíduos na geração seguinte.
*
*
* H3 (acima da aptidão média) aumenta na
geração seguinte.
* H1 (abaixo da aptidão média) diminui na
geração seguinte.
*
* O tamanho do esquema H , denotado por δ(H), é a
diferença entre a última posição ocupada por 1 ou 0
e a primeira posição ocupada por 1 ou 0.
* Exemplos,
* H1 = 1****, δ(H1) = 0
* H2 = **10*, δ(H2) = 1
* H3 = *0*01, δ(H3) = 3
* δ(H) representa o número de possíveis pontos de
corte que destroi H.
*
* A ordem do esquema H , denotado por O(H), é o
número de posições em H que não tem o símbolo *.
* Exemplos,
* H1 = 1****, O(H1) = 1
* H2 = **10*, O(H2) = 2
* H3 = *0*01, O(H3) = 3
* O(H) representa o número de posições em que a
mutação pode destruir H.
*
* Um grande esquema em pai1
* Um pequeno esquema em pai2
(01*|**10)
(***|*101)
* filho
(01*|*101)
* O primeiro esquema está presente filho, mas o segundo
esquema foi destruído pelo crossover.
* Conclusão: pequenos esquemas possuem maior
probabilidade de sobrevivência.
*
* Esquemas de baixa ordem possuem maior
probabilidade de sobrevivência ao operador
de mutação.
* Mesmo considerando os efeitos destrutivos do
crossover e mutação, este teorema afirma que:
* Esquemas pequenos e de baixa ordem contidos em
bons cromossomos aumentam exponencialmente
nas gerações seguintes, ao passo que esquemas
contidos em cromossomos ruins tendem a
desaparecer nas gerações seguintes.
*
* Blocos de construção são os esquemas
pequenos e de baixa ordem.
* A hipótese: bons blocos de construção são
passados de uma geração para outra e
recombinados para formar cromossomos cada
vez melhores.
*
* AG manipula uma população de apenas N
cadeias de bits, mas processa em paralelo
grande número de esquemas (na ordem de
O(N3) esquemas).
*