GA02_Representação_Números_Reais_2019-2

Prévia do material em texto

1 
l Cromossomas expressam valores através de 
números reais (ponto flutuante) e não em 
binário 
 
l Para apresentar essa representação deve 
introduzir o conceito de hibridização em GAs. 
Problemas Numéricos com 
Representação por Números 
Reais 
2 
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. Em Uso + Alg. Genético 
 
l Hibridizar: 
– Adotar REPRESENTAÇÃO em uso 
– Adaptar OPERADORES 
– Adotar HEURÍSTICAS de otimização 
3 
Vantagens 
l Incorpora o conhecimento no domínio do problema; 
l Resulta num sistema mais familiar para o usuário; 
l Algoritmo em uso pode fornecer “sementes” para o 
GA, garantindo soluções melhores. 
l Novos operadores devem estar alinhados com a 
filosofia de GAs: recombinação e mutação 
– Crossover: recombinação de sub-partes de 
indivíduos 
– Mutação: variações globais ou locais para manter 
agitada a variedade genética 
4 
Representação por Números 
Reais 
Cromossomas são estruturas contendo números reais. 
 
l Hibridizando com “algoritmo em uso” para a 
otimização da função f6 (x,y) 
l “Algoritmo em uso”  Busca Aleatória 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ção se tempo esgotado; 
•Retorna ao primeiro passo; 
5 
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 
6 
Crossover 
l Cromossoma é uma lista de reais: (x,y) 
l Crossover de 1 ou 2 pontos ou Uniforme sobre lista: 
l Exemplo: Crossover Uniforme Problema com 4 variáveis 
 
 P1  (x1, y1, t1, z1) F1  (x2, y1, t1, z2) 
 
 P2  (x2, y2, t2, z2) F2  (x1, y2, t2, z1) 
 
Padrão  0 1 1 0 
7 
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  ( (x1+x2)/2, (y1+ y2)/2) 
P2  (x2, y2) 
 
l A média entre dois valores pode resultar em valores 
mais próximos do valor desejado. 
8 
Crossover Aritmético 
l Crossover aritmético é uma combinação linear de dois 
vetores (genitores) P1 e P2 na geração t: 
 
F1
 
 = a . P1
 
 + (1-a) P2
 
 
F2
 
 = a . P2
 
 + (1-a) P1 
l a =rand  [0, 1] : crossover uniforme 
l a =f(t) : crossover não-uniforme 
 (depende da idade da população) 
9 
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) 
 
(x1, y1) (x1, yrand) 
 
• Alto poder de dispersão 
10 
Mutação CREEP 
l Implementa uma BUSCA LOCAL 
– busca uma solução próxima através de ajustes 
aleatórios em ambas as direções (+ e -) 
– (x1, y1) (x1  x, y1 y) 
  pode ser pequeno ou grande 
 
 
X 
f() 
x 
11 
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 
O ajuste varia com o valor de p: 
se p = pequeno ajuste menor 
se p = grande ajuste maior 
12 
Creep - Método de Ajuste 2 
 Xt +  (t, máx- Xt) se bit sorteado =0 
l Xt+1 = 
 Xt -  (t, Xt -mín) se bit sorteado =1 
 
máx e mín = limites do domínio de x. 
l  (t, s) = s . ( 1 - rand 
(1 - t T) 
b 
) 
– rand = número aleatório  [0, p], p 1; 
– t= geração; 
– 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úmero de gerações. 
13 
Creep - Método de Ajuste 2 
rand 
l 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) 
s 
 (t, s) 
1 
t T=0,50; b=2 
s 
 (t, s) 
t T=0,90; b=2 
1 rand 
14 
l Módulo de Avaliação 
 Função de Avaliação: Função F6 real 
l 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 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 
l 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) 
GA5-1 
15 
16 
Binária x Reais 
l Representação por números reais (ponto flutuante) é mais adequada em 
problemas de otimização com variáveis sobre domínio contínuo; 
l Em particular 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 (não há decodificaçã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 Na representação por reais, dois pontos próximos um ao outro no espaço de 
representação, estão também próximos no espaço do problema (evita 
Hamming Cliffs). 
17 
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