Algoritmo II

Prévia do material em texto

11
Algoritmos Genéticos HíbridosAlgoritmos Genéticos Híbridos
� Consiste na construção de um GA inspirado no 
“algoritmo de otimização em uso” em determinado 
problema (se houver).
AlgAlg. Híbrido = . Híbrido = AlgAlg. Em Uso + . Em Uso + AlgAlg. Genético. Genético
� Hibridizar:
– Adotar REPRESENTAÇÃO em uso
– Adaptar OPERADORES
– Adotar HEURÍSTICAS de otimização
VantagensVantagens
� 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
– Crossover: recombinação de sub-partes de indivíduos
– Mutação: variações globais ou locais para manter 
agitada a variedade genética
22
Representação Representação por por Números Números 
ReaisReais
Cromossomas são estruturas contendo números reais.Cromossomas são estruturas contendo números reais.
� 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 Gera x e y ∈∈∈∈∈∈∈∈ ℜℜℜℜℜℜℜℜ aleatoriamente;aleatoriamente;
••Calcula f6 para o par (x,y);Calcula f6 para o par (x,y);
••Salva (x,y) e f6(x,y);Salva (x,y) e f6(x,y);
••Retorna a melhor avaliaRetorna a melhor avaliaçãção se tempo esgotado;o se tempo esgotado;
••Retorna ao primeiro passo;Retorna ao primeiro passo;
HibridizaçãoHibridização
� Representação:
Lista de Reais : (x,y)
� Avaliação:
f6(x,y) real
� Inicialização:
Números reais aleatórios
� Operadores Genéticos:
Crossover e Mutação e 
Operadores inspirados no problema
33
CrossoverCrossover
� Cromossoma é uma lista de reais: (x,y)(x,y)
� Crossover de 1 ou 2 pontos ou Uniforme sobre lista:
� Exemplo: Crossover Uniforme Problema com 4 variáveis
PP1 1 ≡≡≡≡≡≡≡≡ (x(x11, y, y11, t, t11, z, z11)) FF1 1 ≡≡≡≡≡≡≡≡ (x(x22,, yy11, t, t11, z, z22))
➨➨➨➨➨➨➨➨
PP2 2 ≡≡≡≡≡≡≡≡ (x(x22, y, y22, t, t22, z, z22)) FF2 2 ≡≡≡≡≡≡≡≡ ((xx11, y, y22, t, t22,, zz11))
PadrPadrããoo≡≡≡≡≡≡≡≡ 0 1 1 00 1 1 0
Crossover Crossover de Médiade Média
�� Cruzamento específico para o problemaCruzamento específico para o problema
�� Se dois cromossomas são promissores, a média de Se dois cromossomas são promissores, a média de 
seus valores reais pode levar a uma melhor soluçãoseus valores reais pode levar a uma melhor solução
PP1 1 ≡≡≡≡≡≡≡≡ (x(x11, y, y11))
➨➨➨➨➨➨➨➨ FF1 1 ≡≡≡≡≡≡≡≡ ( (( (xx11++xx22)/2, ()/2, (yy11++ yy22)/2))/2)
PP2 2 ≡≡≡≡≡≡≡≡ (x(x22, y, y22))
� A média entre dois valores pode resultar em valores 
mais próximos do valor desejado.
44
CrossoverCrossover de Médiade Média
� Crossover aritmético é uma combinação linear de 
dois vetores (genitores) PP1 1 e PP22 na geração t:
FF11 = a . P= a . P11 + (1+ (1--a) Pa) P22
FF22 = a . P= a . P22 + (1+ (1--a) Pa) P11
�� a =a =ctecte : crossover uniforme
�� a =f(t)a =f(t) : crossover não-uniforme (a depende 
da idade da população)
MutaçãoMutação
�� Mutação de realMutação de real
– substitui cada número real em um cromossoma por um 
número real aleatório (se teste probabilidade=TRUE)
(x(x11, y, y11)) ➨➨➨➨➨➨➨➨ (x(x11, , yyrandrand))
�� CreepCreep
– busca uma solução próxima através de ajustes 
aleatórios em ambas as direções (+ e -)
(x(x11, y, y11)) ➨➨➨➨➨➨➨➨ (x(x1 1 ±±±±±±±± ∆∆∆∆∆∆∆∆x, yx, y11±±±±±±±± ∆∆∆∆∆∆∆∆y)y)
∆∆∆∆∆∆∆∆ ≡≡≡≡≡≡≡≡ pequeno ou grandepequeno ou grande
55
CreepCreep -- Método de Ajuste 1Método de Ajuste 1
XXt t + + ∆∆∆∆∆∆∆∆ ((mmááxx -- XXtt)) se bit sorteado =0
�� XXtt+1 +1 ==
XXtt -- ∆∆∆∆∆∆∆∆ ((XXtt -- mmíínn) ) se bit sorteado =1
máx e mín = limites do domínio de x
�� ∆∆∆∆∆∆∆∆ (s) = s . (s) = s . randrand
rand = número aleatório ∈ [0, p], p≤≤≤≤ 1
�� O ajuste varia com o valor de O ajuste varia com o valor de pp::
se p = pequeno ➨ ajuste menor
se p = grande ➨ ajuste maior
CreepCreep -- Método de Ajuste 2Método de Ajuste 2
XXt t + + ∆∆∆∆∆∆∆∆ (t, (t, mmááxx-- XXtt)) se bit sorteado =0
�� XXtt+1 +1 ==
XXt t -- ∆∆∆∆∆∆∆∆ (t, (t, XXtt --mmíínn) ) se bit sorteado =1
t= geração; máx e mín = limites do domínio de x.
�� ∆∆∆∆∆∆∆∆ (t, s) = s . ( 1 (t, s) = s . ( 1 -- randrand (1 (1 -- tt////////T)T) b b ))
rand = número aleatório ∈ [0,1]
T = número máximo de gerações
b = grau de dependência com o número da geração
�� A probabilidade de A probabilidade de ∆∆∆∆∆∆∆∆ (t, s) ser pr(t, s) ser próóximo de zero ximo de zero 
aumenta com o naumenta com o núúmero de geramero de geraçõções.es.
66
CreepCreep -- Método de Ajuste 2 Método de Ajuste 2 
randrand
�� O operador busca uniformemente no espaço no O operador busca uniformemente no espaço no 
início da evolução (t=pequeno), e mais localmente no início da evolução (t=pequeno), e mais localmente no 
final da evolução (t=grande)final da evolução (t=grande)
ss
∆∆∆∆∆∆∆∆ (t, s)(t, s)
11
tt////////T=0,50; b=2T=0,50; b=2
ss
∆∆∆∆∆∆∆∆ (t, s)(t, s)
tt////////T=0,90; b=2T=0,90; b=2
11 randrand
� Módulo de Av aliação
➩ Função de Avaliação: Função F6 real
� 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
� 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
77
Binária x ReaisBinária x Reais
� Representação dos genes por números reais (ponto flutuante) é mais 
adequada em problemas de otimização de parâmetros com v ariáveis sobre 
domínio contínuo;
� Especialmente em grandes domínios onde a representação binária requer um 
longo cromossoma:
Ex: 100 v ariáveis, [-500,500], 4 casas decimais ➨➨➨➨➨➨➨➨ 2400 bits2400 bits
� Representação por reais é mais rápida na execução;
� Representação por reais of erece maior precisão (depende do computador);
� Desempenho pode ser melhorado com operadores específicos ao problema;
� 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;
� Representação por reais evita Hamming Cliffs.
88
Distância de Distância de HammingHamming
� Rep. Binário Valor Real
CC11 = 0 1 1 1 1 1= 0 1 1 1 1 1 31 31 
CC22 = 1 0 0 0 0 0= 1 0 0 0 0 0 3232
➨➨➨➨➨➨➨➨ distância = 6distância = 6
� Rep. Real Valor Real
CC11 = 31= 31 3131
CC22 = 32= 32 3232
➨➨➨➨➨➨➨➨ distância = 1distância = 1