Fundamentos Matemáticos
Como e porque Algoritmos
Genéticos funcionam?
Teoria de Schema (John Holland 1975)
“Schema é um padrão genético que descreve um
conjunto de cromossomas do espaço de busca
com similaridades em certas posições”
1
Representação de um
Schema

Utiliza-se um símbolo adicional:
 = don’t care

Exemplo:
H= 1 1 
H é um padrão que descreve todos os cromossomas do espaço
23 , cujos os dois primeiros bits são iguais a ‘1’, não importando
os demais.
2
Interpretação





Considere f(x) = x2 , x  23
Seja o schema:
H= 1 1 
H refere-se a conjectura que a razão pela qual 111 e 110
são bons cromossomas (ou não), são os dois bits mais
significativos iguais a ‘1’, não importando os demais.
Para esta conjectura “podem” existir numa determinada
população dois representantes: 110 e 111.
110 e 111 “pertencem” a H= 1 1 
3
Schema






Número de Schemata
Ordem de um Schema
Comprimento de um Schema
Indivíduos pertencentes a um Schema
Schemata representados por um indivíduo
Teorema Fundamental
4
Número de Schemata

Seja o espaço de busca KL onde:
K  número de elementos do alfabeto de representação
L  comprimento do cromossoma
 Total de Schemata = (K+1) L

Exemplo: K=2; L=3
23 = 8 pontos
Total de Schemata = 27
5
Ordem de um Schema
Ordem ou Especificidade O(H)
O(H)  número de posições fixas (diferentes de *)
presentes no schema

H= 0 1 1  1  
O(H) =4
H= 0      
O(H) =1
6
Comprimento de um Schema

(H)  distância entre a primeira e a última posições
específicas (diferentes de *) no schema.
H= 0 1 1  1  
(H) =4
H= 0      
(H) =0
7
Representação Geométrica
Schemata de Ordem 3: Pontos
110
111
010
011
100
000
101
001
8
Representação Geométrica
Schemata de Ordem 2: Linhas
11
110
10
111
11
01
010
011
10
11
00
01
10
100
101
00
000
01
00
001
9
Representação Geométrica
Schemata de Ordem 1: Planos
110
111
1 
010
011
1
0
 1
0 
100
101
0 
000
001
10
Representação Geométrica
Schemata de Ordem 0: Cubo
110
111
010
011

100
000
101
001
11
Indivíduos Pertencentes ao
um Schema

Um indivíduo pertence a um schema se para todas as
L posições o símbolo do indivíduo é igual ao símbolo
do schema, exceto nas posições onde o símbolo do
schema é don’t care ().

Um schema possui 2L-O(H) indivíduos.

Exemplo:

1  possui 23-1 indivíduos
010
011
110
111
12
Indivíduos Pertencentes ao
Schema
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Schema
000
001
00*
010
011
01*
0*0
0*1
0**
100
101
10*
110
111
11*
1*0
1*1
1**
*00
*01
*0*
*10
*11
*1*
**0
**1
***
Indivíduos
000
001
000
010
011
010
000
001
000
100
101
100
110
111
110
100
101
100
000
001
000
010
011
010
000
001
000
001
011
010
011
001
010
011
110
111
100
101
110
100
101
010
111
110
111
011
101
111
110
111
101
100
101
001
110
111
011
010
011
001
13
100
101
110
111
Schemata representados por
um indivíduo



Um indivíduo representa 2L schemata.
Para cada uma das L posições de um indivíduo, define-se
um schema diferente, usando o símbolo presente no
indivíduo ou o símbolo ‘  ’.
Exemplo: 0 1 0 representa os seguintes schemata:
010
10
00
01
0
1
 0

14
Porque utilizar schema?

Porque considerar (K+1) L schemata ao invés de considerar apenas KL
indivíduos?

John Holland procurou mostrar com schema, o paralelismo da busca
através do espaço de soluções.

Há mais informações nos schemata para guiar a busca do que
simplesmente nos indivíduos.

Numa população de n indivíduos, onde cada indivíduo representa 2L
schemata, há entre 2L e n.2L schemata, dependendo da diversidade da
população.

J. Holland mostrou que o número de schemata processados de maneira útil
(não destruídos pelo crossover) a cada geração é proporcional a n3

Paralelismo Implícito  um GA processa n3 schemata em paralelo,
enquanto avalia apenas n indivíduos.
15
Teorema Fundamental de GA
Schemata permitem analisar o efeito global da reprodução e
dos operadores genéticos.

Efeito da Seleção

Efeito do Crossover

Efeito da Mutação
16
Efeito da Seleção

Qual o indicador de que uma determinada espécie ou padrão
apresenta evolução dentro de uma população diversa?

# representantes depois > # representantes antes

Seja m(H,t) o número de representantes do schema H na
população no ciclo t.


Sabemos que, pi = fi /  fj é a probabilidade do cromossoma i
ser escolhido.
Para uma população de tamanho n, então, o número
esperado de representantes de H no ciclo seguinte (t+1) é:
m(H, t+1) = n . (
iH
n
fi /  fj )
17
m(H, t+1) = n . ( 

iH
n
fi /  fj )
Definindo a aptidão média do schema H, como
f(H) = 
iH
fi / m(H,t)
então, 
iH
fi = m(H,t).f(H)
n
m(H, t+1) = n. m(H, t) . f(H) /  fj
n

Como fmédio =  fj / n então,
m(H, t+1) = (m(H, t) . f(H)) / fmédio
Analisando podemos dizer que:
1- Schemata com aptidão acima da média proliferam;
2- Schemata com aptidão abaixo da média tendem a desaparecer.
18
Taxa de Evolução

Supondo H acima da média de um fator constante C
estacionário, a partir de t=0:
m(H, t+1) = m(H, t) . (fmédio + C.fmédio) / fmédio
m(H, t+1) = m(H, t) . (1+C)

Assim,para qualquer t temos:
m(H, t+1) = m(H, 0) . (1+C)t
O número ocorrências nas gerações sucessivas de bons
(maus) schemata, cresce (decresce) exponencialmente.
19
Efeito do Crossover

Ex: A vai cruzar com outro genitor; o que acontece a H1 e H2?
Ponto de crossover
A
0
1
1
1
0
0
0
H1
*
1
*
*
*
*
0
H2
*
*
*
1
0
*
*
H1
será destruído e padrão não será transmitido aos descendentes a
não ser que par genitor de A possa recuperar padrão.
H2
sobreviverá e será transmitido a um dos descendentes.
20
Probabilidade de Destruição
pd = (H)  (L-1)

A probabilidade de sobrevivência de H é,
ps = 1 – ((H)  (L-1))

Então, considerando a probabilidade do crossover e a
recuperação de H após o crossover temos,
ps  1 – (pc .(H)  (L-1))

Portanto,
m(H, t+1)  [m(H, t) . f(H)  fmédio].[1 – (pc .(H)  (L-1))]
21
Efeito da Mutação




Seja, pm a probabilidade de uma posição sofrer
mutação.
1- pm é a probabilidade de sobrevivência.
H tem O(H) posições fixas
Assim, a probabilidade de sobrevivência do schema é:
(1- pm)O(H)

Sabendo que pm  1, então
(1- pm)O(H)  1 - O(H) . pm
22
Teorema Fundamental de GA
m(H, t+1)  [m(H, t).f(H)  fmédio].[1- (pc .(H)  (L-1))].[1 - O(H).pm]
“Schemata curtos, de baixa ordem e com alta aptidão tendem
a proliferar nas gerações sucessivas, a uma taxa
exponencial.”
23
Hipótese dos Blocos
Construtores
Assim como uma criança cria grandes castelos
empilhando pequenos blocos, um algoritmo genético
busca desempenho próximo do ótimo através da
justaposição de schemata curtos, de baixa ordem e
de alta aptidão, ou blocos construtores.
24
Planilha Fundamentos de GA
NúmeroPopulação Inicial
1
1 1 1 0 0
2
1 1 1 0 0
3
1 1 1 1 0
4
1 1 1 0 1
5
1 1 1 1 0
6
1 1 1 1 0
7
1 1 1 1 0
8
1 1 1 1 0
9
1 0 1 1 1
10 1 1 1 0 0
10
Soma
Média
Máximo
x inteiro f(x) =
28
28
30
29
30
30
30
30
23
28
286
28,6
30
Nova Geração
Evoluir Gerações
1
*
1
Schemata
*
*
*
1 0 *
*
*
*
Prob.
Seleção
0,0953539
0,0953539
0,1094624
0,1022865
0,1094624
0,1094624
0,1094624
0,1094624
0,0643396
0,0953539
comp(H)
*
*
0
O(H)
0
1
4
4
4
Núm.
Execução
Descende Automática
0,953539
Seleção
0,953539
1,094624
Crossover
1,022865
1,094624
Mutação
1,094624
1,094624
1,094624
Executar
0,643396
0,953539
8222
1
10
822,2
0,1
1
900 0,1094624 1,094624
Configurações
População
10 (até 10)
Crossover
0,6 (0 a 1)
Mutação
0,08 (0 a 1)
Gerações
20
Gerar População
H1
H2
H3
H4
H5
x^2
784
784
900
841
900
900
900
900
529
784
1
2
2
0
0
Result. Pares de Genitores
Roleta
Pontos de Corte
2 1 1 1 0
0 1 1 1 0
3 1 1 1 1
3 1 1 1 0
1 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
1 1 1 1 1
0 1 1 1 0
10
10
1
3
e
0
0
0
0
0
0
0
0
0
0
5
5
2
2
1
1
5
5
5
5
Processamento de Schemata
Após Seleção
Real
Representantes
f(H)
m(H,t+1)
Representantes
10 {1,2,3,4,5,6,7,8,9,10}
822,2 10,0000001 10 {1,2,3,4,5,6,7,8,9,10}
0 {}
0
0 0 {}
8 {1,2,3,5,6,7,8,10}
856,5 8,33373875 10 {1,2,3,4,5,6,7,8,9,10}
0 {}
0
0 0 {}
0 {}
0
0 0 {}
25
Efeito da Cardinalidade
x
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Espaço
Cardinalidade
Schemata
Binário
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
16
2
81
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
Não Binário
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Aptidão
0
1
4
9
16
25
36
49
64
81
100
121
144
169
196
225
16
16
17
26
Conclusões

GA explora similaridades em codificações
arbitrárias através de schema.

A codificação binária é simples e eficiente,
oferecendo o número máximo de schemata,
porém nem sempre é adequada.

A representação de cromossomas é
fundamental para o desempenho de um GA.
27
Princípios de Escolha da
Representação

Representatividade
– deve representar todo o espaço de busca relevante ao
problema

Schemata
– deve prestigiar a formação de schemata curtos e de baixa
ordem

Alfabeto
– deve utilizar um alfabeto mínimo que permita a expressão
natural do problema
28