Pontifícia Universidade Católica do Paraná
Curso de Especialização em Inteligência Computacional
2004/2005
Computação Evolutiva:
Estratégias Evolutivas
Luiz Eduardo S. Oliveira, Ph.D.
[email protected]
http://www.ppgia.pucpr.br/~soares
Objetivos
Introduzir os principais conceitos da
estratégia evolutiva (EE).
 Entender como e por que EE funcionam.
 Vislumbrar possíveis aplicações de
otimização usando EE.

Introdução

Desenvolvidas inicialmente na Alemanha,
na década de 60
 Resolução
de problemas contínuos de
otimização paramétrica.
 Recentemente estendida ao uso de
problemas discretos.

Baseadas na evolução da evolução.
Representação
Se dá geralmente por um vetor de
números reais.
 Assim como nos AGs, cada posição
corresponde a uma característica do
problema.
 Operações:

 Mutação,
recombinação e seleção.
Mutação

Objetivo:
 Similar
a PE na EE a mutação é responsável
por gerar uma nova população de indivíduos.
 Diferente do objetivo da mutação nos AGs.

Adicionar números aleatórios (extraídos
de uma distribuição normal) às
coordenadas dos pais.
Mutação

Exemplo:
 Considere
um indivíduo X = x1, x2, x3, ...., xn
 O filho do indivíduo X é dado pela seguinte
equação:
 X´= X + N(0,σ)

O filho será composto pelas informações do seus
pais mais os parâmetros da distribuição

Desvio padrão tem um papel importante.
Mutação

Desvio padrão alto:
 Aumenta
a variabilidade dos filhos
 Mais diferentes dos seus pais.
 Exploração global (Exploration)

Desvio padrão baixo:
 Indivíduos
mais similares aos seus pais.
 Exploração local (Exploitation)
Mutação
+ N(0,)
+ N(0,)

+ N(0,)
Como definir qual o valor do desvio
padrão a ser utilizado?
 Teorema

da Convergência
Regra de sucesso de 1/5
Mutação



Se a taxa de sucesso (filho melhor que o pai) >
1/5 então aumenta-se o desvio padrão.
Caso contrário, o desvio é reduzido.
Razão intuitiva da regra de 1/5:
 Aumento
da eficiência na busca
 Se bem sucedida, a busca continua a passos
maiores, caso contrário o passo deve ser reduzido.
Recombinação
Existem dois métodos de recombinação
em EE.
 Local

 Formar
um indivíduo com base em dois pais
selecionados aleatoriamente.

Global
 Os
valores do indivíduo podem vir de vários
pais e não somente de dois.
Recombinação

Recombinação discreta:
 Seleciona
o valor que o indivíduo filho irá
receber de um dos pais.


Similar ao cruzamento realizado nos AGs.
Recombinação intermediária:
 Seleciona
um ponto médio dos valores dos
pais, o qual deverá ser atribuído ao filho.
Recombinação

Recombinação intermediária:
 na
qual C é uma constante (normalmente
igual a 0.5) – para produzir o ponto médio.
(c) é o resultado de uma combinação
Intermediário com C = 0.5
Recombinação
Como podemos notar, a EE contem um
componente de representação sexual de
características.
 Intermediária

 Média

entre os pais.
Discreta
O
filho pode sair intacto somente com
informações de um pai ou de outro.
Seleção

Assim como em outras técnicas
evolutivas, EE também determina a
probabilidade de reprodução de um
indivíduo através de sua fitness.
 Ranking
 Roleta

Russa.
Mais utilizada por ser um processo estocástico
Seleção
Versões mais comuns da EE são (μ, λ) e
(μ + λ)-EE
 Em ambas versões, o número de filhos
gerados a partir de μ pais é λ, e λ > μ.
 Normalmente a proporção é de 7 filhos para
cada pai

Seleção

Na versão original do algoritmo (1+1)-EE um pai
produz um filho. O que tiver a melhor fitness,
sobrevive.
 Essa

versão já não é muito utilizada.
Na versão (μ, λ), os μ indivíduos com as melhores
fitness são escolhidos entre os λ filhos.
 Pais
não participam da seleção
 Estratégia não elitista (Uma boa solução pode ser perdida)
Seleção

Na versão (μ + λ)-EE os melhores μ
indivíduos são selecionados entre um grupo de
candidatos que incluem os μ pais e λ filhos.
Algoritmo Clássico
1.
2.
3.
4.
5.
6.
Inicializar população
Realizar recombinação utilizando μ pais para formar λ
filhos.
Realizar a mutação em todos os filhos
Avaliar a fitness de μ ou μ + λ indivíduos (de acordo com a
estratégia envolvida)
Selecionar μ indivíduos para compor a nova população.
Se o critério de parada não for alcançado, volte ao item 2,
caso contrário, fim.
Exercício

Utilizar a EE para
encontrar o ponto ótimo na
esfera (De Jong’s Sphere)



População = 5
Cada pais gera 5 filhos
Recombinação intermediária



C = 0.5
Roleta russa na seleção
Regra do 1/5
n
f ( x) 
x
i 1
2
i