Representação por Números
Reais
l
Cromossomas expressam valores através de
números reais (ponto flutuante) e não em binário
l
Para apresentarmos essa representação vamos
introduzir o conceito de hibridização em Gas.
Algoritmos Genéticos Híbridos
l
Consiste na construção de um GA inspirado no
“algoritmo de otimização em uso” em determinado
problema (se houver).
Alg.. Híbrido = Alg
Alg
Alg.. Em Uso + Alg
Alg.. Genético
l
Hibridizar:
– Adotar REPRESENTAÇÃO em uso
– Adaptar OPERADORES
– Adotar HEURÍSTICAS de otimização
1
Vantagens
Modelo incorpora o conhecimento no domínio do
problema;
Resulta num sistema mais familiar para o usuário;
Algoritmo em uso pode fornecer “sementes” para o
GA, garantindo soluções melhores.
Novos operadores devem estar alinhados com a
filosofia de GAs: recombinação e mutação
l
l
l
l
– Crossover: recombinação de sub-partes de indivíduos
– Mutação: variações globais ou locais para manter
agitada a variedade genética
Representação por Números
Reais
Cromossomas são estruturas contendo números reais.
l
l
Hibridizando com “algoritmo em uso” para a
otimização da função f6 (x,y)
“Algoritmo em uso” ≡ Busca Exaustiva de x e y reais
•Gera x e y ∈ ℜ aleatoriamente;
•Calcula f6 para o par (x,y);
•Salva (x,y) e f6(x,y);
•Retorna a melhor avaliaç
avalia ção se tempo esgotado;
•Retorna ao primeiro passo;
2
Hibridização
l
Representação:
Lista de Reais : (x,y)
l
Avaliação:
f6(x,y) real
l
Inicialização:
Números reais aleatórios
l
Operadores Genéticos:
Crossover e Mutação e
Operadores inspirados no problema
Crossover
l
l
l
Cromossoma é uma lista de reais: (x,y)
Crossover de 1 ou 2 pontos ou Uniforme sobre lista:
Exemplo: Crossover Uniforme Problema com 4 variáveis
P1 ≡ (x1 , y1 , t 1 , z 1 )
F1 ≡ (x2 , y1 , t1 , z 2 )
è
P2 ≡ (x2 , y2 , t 2 , z 2 )
Padrão ≡ 0 1 1 0
F2 ≡ (x1 , y2 , t2 , z 1 )
3
Crossover de Média
l
Cruzamento específico para o problema
l
Se dois cromossomas são promissores, a média de
seus valores reais pode levar a uma melhor solução
P1 ≡ (x1 , y1 )
è
F1 ≡ ( (x
(x1 +x2 )/2, (y
( y1 + y2 )/2)
P2 ≡ (x2 , y2 )
l
A média entre dois valores pode resultar em valores
mais próximos do valor desejado.
Crossover de Média
l
Crossover aritmético é uma combinação linear de dois
vetores (genitores) P1 e P2 na geração t:
F1 = a . P1 + (1(1-a) P2
F2 = a . P2 + (1
(1--a) P1
l
l
a =rand
=rand ∈ [0, 1] : crossover uniforme
a =f(t)
: crossover não-uniforme
(depende da idade da popula ção)
4
Mutação
l
Mutação de real
– substitui cada número real em um cromossoma por um
número real aleatório (se teste probabilidade=TRUE)
l
(x1, y1)
Creep
è
(x1, yrand)
– busca uma solução próxima através de ajustes
aleatórios em ambas as direções (+ e -)
(x1, y1)
è
(x1 ± ∆ x, y1± ∆ y)
∆ ≡ pequeno ou grande
Creep - Método de Ajuste 1
Xt + ∆ (máx - Xt) se bit sorteado =0
l
Xt+1 =
Xt - ∆ (Xt - mín) se bit sorteado =1
máx e m ín = limites do dom ínio de x
l ∆ (s) = s . rand
rand = número aleatório ∈ [0, p], pó 1
l
O ajuste varia com o valor de p:
se p = pequeno
è
ajuste menor
se p = grande
è
ajuste maior
5
Creep - Método de Ajuste 2
l
Xt + ∆ (t, máx- Xt)
se bit sorteado =0
Xt - ∆ (t, Xt -mín)
se bit sorteado =1
Xt+1 =
t= geração; m áx e m ín = limites do dom ínio de x.
(1 - t/ T) b
l
∆ (t, s) = s . ( 1 - rand
l
rand = número aleatório ∈ [0, p], pó 1
l
T = número máximo de gerações
)
b = grau de dependência com o n úmero da geração
l
A probabilidade de ∆ (t, s) ser pr óximo de zero
aumenta com o nú
nú mero de geraç
gerações.
Creep - Método de Ajuste 2
∆ (t, s)
∆ (t, s)
s
s
t/ T=0,50; b=2
1 rand
l
t/ T=0,90; b=2
1
rand
O operador busca uniformemente no espaço no
início da evolução (t=pequeno), e mais localmente no
final da evolução (t=grande)
6
l
l
Módulo de Avaliação
é Função de Avaliação:
Módulo de População
é Técnica de Representação:
Lista de números reais
é Técnica Inicialização da População:
Números reais aleatórios
Técnica Eliminação da População:
Elimina o último
Técnica de Reprodução:
Steady State s/ duplicados
Gap
l
Função F6 real
GA5-1
Testar de 5 em 5
Técnica de Seleção de Genitores:
Roleta
Técnica de Aptidão:
Normalização Linear (100 a 1)
Técnica de Parametrização :
Interpolar taxa de incremento (0,2 a 1,2)
Population Size :
100
Total de Indivíduos:
4000
Módulo de Reprodução
Técnica de Seleção de Operadores:
Roleta
é Operadores:
Crossover Uniforme de Lista
é
Crossover de Média
é
Mutação de Número Real
é
Creep ∆ pequeno
é
Creep∆
∆ grande
é Técnica de Parametrização:
Interpolar Pesos dos Operadores
é
de (10 40 10 30 10) a (10 20 0 40 30)
7
Binária x Reais
l
Representação dos genes por números reais (ponto flutuante) é mais
adequada em problemas de otimização de parâmetros com variáveis sobre
domínio contínuo;
l
Especialmente em grandes domínios onde a representação binária requer um
longo cromossoma:
Ex: 100 variáveis, [-500,500], 4 casas decimais è 2400 bits
l
Representação por reais é mais rápida na execução;
l
Representação por reais oferece maior precisão (depende do computador);
l
Desempenho pode ser melhorado com operadores específicos ao problema;
l
Representação por reais tem a propriedade que dois pontos próximos um ao
outro no espaço de representação, estão também próximos no espaço do
problema;
l
Representação por reais evita Hamming Cliffs.
Distância de Hamming
l
Rep. Binário
Valor Real
C1 = 0 1 1 1 1 1
31
C2 = 1 0 0 0 0 0
32
è distância = 6
l
Rep. Real
Valor Real
C1 = 31
31
C2 = 32
32
è distância = 1
8