Componentes de um Algoritmo Genético 1. Problema 2. Representação 3. Decodificação 4. Avaliação 5. Operadores 6. Técnicas 7. Parâmetros
1. PROBLEMA
GAs são indicados em problemas complexos de otimização- onde se busca uma solução melhor:: ® muitos parâmetros e variáveis; ® mal estruturados: com condições e restrições, difíceis de serem modeladas matematicamente; ® grandes espaços de busca onde não é possível a busca exaustiva.
2. REPRESENTAÇÃO
Representação é fundamental na modelagem de um GA e deve:
® descrever o espaço de busca relevante ao problema; ® codificar geneticamente a “essência” do problema: evolução do “código”
evolução da solução
® ser compatível com os operadores (crossover e mutação) representação adequada
sucesso, evolução
2. REPRESENTAÇÃO Método de Solução – Numérico – Ordem – Grupo – Inteiro – Misto
↔ Representação – Binário, Real – Lista – Vetor – Inteiro – Ex Ex:: Real e Lista
BINÁRIO CODIFICANDO REAL O binário é um contador de unidades de precisão
Aspectos importantes: ¬variáveis do problema (x1 , x2 , ... , xt ) ¬domínio de valores: xi ∈ (míni, máxi) em R ¬precisão: p casas decimais (máxi-míni)x10p diferentes soluções domínio de xi míni Precisão è 1/10p
máxi
Representação: k1 bits
k2 bits
x1
x2
...
kt bits xt
onde,
2k i ≥ (máxi-míni)x10p
Precisão = (máxi-míni) 2k i - 1
Decodificação para Real: i-míni) + mín xi real = xi bin .(máx ________ i 2k i - 1 se xibin=(0 0 ... 0) se xibin=(1 1 ... 1)
xi real = míni xi real = máxi
REPRESENTAÇÃO BINÁRIA ® simples de criar e manipular ® produz bons resultados ® facilita aplicações de operadores ® fácil decodificação numérica ( inteiro,real ) ® facilita a demonstração de teoremas ® porém, nem sempre é adequada
3. DECODIFICAÇÃO Construir a solução para o problema a partir de um cromossoma: Cromossomas “representam” soluções. Cromossoma
Transformação
Solução
0011011
bin
x=27
0011011
x=27 x 10/27 -1
ADBCE
3Km
D
inteiro
A
1Km 4Km
B
cidades 7Km
E 3Km
C
x=2,1 x ∈[0,10] 1 casa decimal
A→D→B→C→E (Σ dist.=18)
4. AVALIAÇÃO Elo entre o algoritmo genético e o problema . f(cromossoma) = medida numérica de aptidão Chances de seleção são proporcionais à aptidão. f(i) n
∑ f(j) j= 1
5. OPERADORES Atuam no processo de criação de novos indivíduos (descendentes): 1. Crossover 2. Mutação 3. Inversão 4. Operadores específicos ao problema
6. TÉCNICAS - Técnicas de Representação - Técnicas de Inicialização da População - Técnicas de Eliminação da População Antiga - Técnicas de Reprodução - Técnicas de Seleção de Genitores - Técnicas de Aptidão - Técnicas de Parametrização - Técnicas de Elitismo - Técnicas de Seleção de Operadores
7. PARÂMETROS
- TAMANHO_POPULAÇÃO - TOTAL_INDIVÍDUOS - NÚMERO_GERAÇÕES - TAXA_CROSSOVER - TAXA_MUTAÇÃO - APTIDÃO_OPERADORES - ETC.
Desenvolvimento de um Algoritmo Genético procedure algoritmo_genético begin t=0 ; primeira geração inicializa P(t) ; população inicial aleatória avalia P(t) ; calcula f(i) p/ cada indivíduo while (not condição_parada) do begin t=t+1 ; próxima geração seleciona P(t) de P(t-1) altera P(t) ; crossover e mutação avalia P(t)
; calcula f(i) p/ cada indivíduo
end end
Sistemas de Desenvolvimento
l l l l l l l l l
ICADEMO Genesis, Genesys WinGenesis GENOCOP GeneHunter Evolver 4.0 Escapade Sugal Bibliotecas específicas (C, Pascal, etc) – TNA/C++,
Algoritmos Genéticos Exemplos GA1-1 a GA6-1 l Especificação de técnicas e parâmetros por módulos: l
– Módulo de Avaliação – Módulo de População – Módulo de Representação
l
Módulo de Avaliação Função de Avaliação:
l
l
Função binária F 6
Módulo de População Técnica de Representação:
Binária 44 bits
Técnica Inicialização da População:
Aleatória
Técnica Eliminação da População:
Elimina todos
Técnica de Reprodução:
Troca da geração
Técnica de Seleção de Genitores:
Roleta
Técnica de Aptidão:
Aptidão é a avaliação
Técnica de Parametrização:
Nenhuma
Técnica de Elitismo:
Nenhuma
Population Size:
100
Total de Indivíduos:
4000
Módulo de Reprodução Técnica de Seleção de Operadores:
Use todos
Operadores:
Crossover 1 ponto & Mutação
Taxa Mutação:
0,008
Taxa Crossover:
0,65
Técnica de Parametrização:
nenhuma
GA1-1
Função F6
Função F6(x,y) F6(x,0)
1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0
-100
- 50
0
50
100
x
Características da F6
F6(x,y) = 0,5 - (sen √ x2 + y2 )2 - 0,5 (1,0 + 0,001 (x2 + y2 ))2
Objetivo: Maximizar F6 l Uma única solução ótima: F6(0,0)=1 l Difícil de otimizar: vários mínimos locais l
Representação l
Binária codificando real
2 Variáveis: x, y l Domínio: x,y ∈ [-100, +100] l Precisão: 4 a 5 casas decimais 6 7 l log2 2x10 ó Ki ó log2 2x10 l
l
Ki=22 Ô total de 44 bits
Exemplo l
Cromossoma: 00001010000110000000011000101010001110111011
l
Dividido em x e y: 0000101000011000000001 1000101010001110111011
l
Convertidos para base 10: 165377 e 2270139
l
Multiplicados por: 200/222-1 7,885791751335085 e 108,24868875710696
l
Subtraídos de mín: x=-92,11420824866492 e y=8,248688757106959
l
Aplicados a F6(x,y): F6(x,y)=0,5050708
Módulo de População l
Técnica Inicialização da População:
Aleatória
Ü Geração aleatória de palavras de 44 bits l
Técnica Eliminação da População:
Elimina todos
Ü Elimina pop_size indivíduos da população anterior l
Técnica de Reprodução:
Troca da geração
Ü Reproduz pop_size indivíduos para a nova população l
Técnica de Aptidão:
Aptidão é a avaliação
Ü Aptidão é numericamente igual à avaliação l
Técnica de Seleção de Genitores:
Roleta
Parâmetros l
Tamanho da População: pop_size
l
100
Número de Gerações: num_ger
l
Exemplo
40
Total de Indivíduos: total_ind = pop_size x num_ger
4000
Parâmetros l
Tamanho da População: pop_size
l
1000
Número de Gerações: num_ger
l
Exemplo
4
Total de Indivíduos: total_ind = pop_size x num_ger
4000
Parâmetros l
Tamanho da População: pop_size
l
10
Número de Gerações: num_ger
l
Exemplo
400
Total de Indivíduos: total_ind = pop_size x num_ger
4000
Seleção pela Roleta Objetivo: Selecionar indivíduos aleatoriamente, proporcionando maiores chances de reprodução aos mais aptos. Método por Computador l
l l
Encontre a soma da aptidão de todos os membros da população AT= ∑ Ai (0 ó i ó pop_size-1) Gere um número aleatório 0 ó rand ó AT Pegue o primeiro membro da população Ik cuja aptidão somada às aptidões dos membros precedentes é maior ou igual a rand. ∑ Ai ò rand (i < k)
Exemplo da Roleta Cromossoma
1 8 8
Aptidão
∑ Ai
2 2 10
Número Aleatório
3 17 27
23 3
Selecionado
4 7 34
5 2 36
49 7
76 10
6 12 48
7 11 59
13 3
8 7 66
1 1
9 3 69
27 3
2
3
4 5
6
7
8
9
10
8
2
17
7 2
12
11
7
3
7
27
34 36
48
59
66 69
Módulo de Reprodução Técnica de Seleção de Operadores:
Use todos
Ü Use o primeiro operador da lista de operadores l
l
57 7
1
8 10
l
10 7 76
Operadores:
Crossover & Mutação
–
Taxa Mutação:
0,008
–
Taxa Crossover:
0,65
Valores ideais das taxas são obtidos experimentalmente
76
Mutação l l
Troca cada gene de um cromossoma se o teste de probabilidade for verdadeiro Taxa Mutação: 0,8% (0,008) – Teste Verdadeiro Ô troca bit – Teste Falso Ô mantém
Cromossoma
1 1 0
0 1 0
1 0 1
Número Aleatório
Novo Cromossoma
0 0,801 0,102 0,266 0,373 1 0 0,128 0,96 0,005 0,84 1 0 0,768 0,473 0,894 0,001 0
0 1 0
1 1 1
Crossover l l
Partes de dois cromossomas genitores são trocadas a partir de uma posição escolhida aleatoriamente Taxa de Crossover : 65% – Teste Verdadeiro Ô Efetua Cruzamento – Teste Falso Ô Copia os Genitores
P1 P2 F1 F2
1 0
0 0
1 1
1 1
0 0
1 0
1 0
0 0
1 1
1 1
0 0
0 1
ponto de corte aleatórioÚ
0 0 1
Evolução X Convergência l
Crossover: – acelerador do processo de busca – tira proveito das soluções mais promissoras
l
Mutação – operador exploratório – dispersa a população pelo espaço de busca Convergência (causas): – população com indivíduos muito similares – não há mais evolução:
l
• ótimo encontrado ou convergência prematura (mínimo local)
– para continuar a evoluir é preciso introduzir mais diversidade na população
Análise de Desempenho l l l
Melhor de um Experimento (valor) Curva dos Melhores por Geração Curva da Média de Melhores de Vários Experimentos
Média de Experimentos l
l l
Calcula a média dos melhores indivíduos por geração em vários experimentos. Mede o desempenho do GA em encontrar uma solução melhor na geração seguinte GAs são estocásticos: desempenho varia a cada experimento São necessários muitos experimentos para se conhecer o desempenho médio do modelo de GA. e
A(t) =
∑ Ae (t) #_Experimentos
1 ó e ó #_Experimentos
t: geração Ae(t): aptidão do melhor indivíduo em t no experimento e A(t): média em #_Experimentos das aptidões dos melhores indivíduos a cada geração t
Média de Experimentos
ger ger ger ger
Experimentos Melhores nas gerações 1a. 2a. 3a. 4a. Média 1 0,6 0,5 0,8 0,5 0,60 2 0,7 0,5 0,8 0,7 0,68 3 0,7 0,6 0,9 0,7 0,73 4 0,8 0,6 0,9 0,8 0,78 Média de Experimentos Avaliação
l
1,00 0,50 0,00 1
2
3
4
5
Experimentos
Característica da Curva de Desempenho •bom desempenho no início da evolução •pouco ou nenhum desempenho no final
Aptidão A(t)
Curva da Média de Experimentos
30000 25000 20000 15000 10000 5000 49
45
41
37
33
29
25
21
17
9
13
5
1
0 Gerações
Curva Média de Experimentos para F6(x,y) l
l
Usamos o número de dígitos 9 após o ponto decimal para distinguir avaliações muito próximas de 1,00 . Exemplo: Avaliação
0,99873578 0,82435787 0,99995432
dígitos 9
2 0 4
ICADEMO
l
Módulo de Avaliação Função de Avaliação:
l
l
Função binária F 6
GA1-1
Módulo de População Técnica de Representação:
Binária 44 bits
Técnica Inicialização da População:
Aleatória
Técnica Eliminação da População:
Elimina todos
Técnica de Reprodução:
Troca da geração
Técnica de Seleção de Genitores:
Roleta
Técnica de Aptidão:
Aptidão é a avaliação
Técnica de Parametrização:
Nenhuma
Técnica de Elitismo:
Nenhuma
Population Size :
100
Total de Indivíduos:
4000
Módulo de Reprodução Técnica de Seleção de Operadores:
Use todos
Operadores:
Crossover 1 ponto & Mutação
Taxa Mutação:
0,008
Taxa Crossover:
0,65
Técnica de Parametrização:
nenhuma
ICADEMO
Novas Técnicas e Parâmetros Técnicas de Aptidão l Elitismo l
Reprodução Steady State l Ajuste dos Parâmetros l
l
Módulo de Avaliação Função de Avaliação:
l
l
Função binária F 6
Módulo de População Técnica de Representação:
Binária 44 bits
Técnica Inicialização da População:
Aleatória
é Técnica Eliminação da População:
Elimina o último
é Técnica de Reprodução:
Steady State s/ duplicados
Técnica de Seleção de Genitores:
Roleta
é Técnica de Aptidão:
Normalização Linear (100 a 1)
Técnica de Parametrização:
Nenhuma
Técnica de Elitismo:
Nenhuma
Population Size :
100
Total de Indivíduos:
4000
Módulo de Reprodução Técnica de Seleção de Operadores:
Use todos
Operadores:
Crossover 1 ponto & Mutação
é
Taxa Mutação:
0,04
é
Taxa Crossover:
0,8
Técnica de Parametrização:
nenhuma
GA2-1 a GA2-5
Medida de Aptidão l
O que ocorre se alterarmos a F6 para: F6 (x,y) = 0,5 - (sen √ x2 + y2 )2 - 0,5 (1,0 + 0,001 (x 2 + y2 ))2
Medida de Aptidão l
O que ocorre se alterarmos a F6 para: F6Elevada(x,y) = 999,5 - (sen √ x2 + y2 )2 - 0,5 (1,0 + 0,001 (x 2 + y2 ))2
l
Formato F6 = formato F6 elevada Melhor cromossoma para F6 = melhor para F6 elevada Avaliação de F6 elevada = avaliação F6 + 999
è
Todavia, GA 1-1 para F6Elevada não apresenta desempenho algum.
è
PORQUE?
l l
Aptidão = Avaliação Ai = fi
: aptidão do indivíduo i
pi = Ai/ AT = fi / ∑ fJ : chances de seleção de I há pop_size sorteios, então Di = pi x pop_size = (fi x pop_size) / ∑ fJ = Di = fi / fAV
: número provável de sorteios de i, ou número de descendentes na próxima geração
l
l l è
F6 avaliação best 0,979 worst 0,066 average 0,514 Dbest = 1,905 Dworst = 0,128 forte pressão seletiva em favor do melhor
l
l l è
F6 Elevada avaliação best 999,979 worst 999,066 average 999,514 Dbest = 1,0005 Dworst = 0,9996 melhor e pior cromossomas vão gerar o mesmo número de descendentes
O efeito da seleção é quase nulo porque as avaliações estão relativamente muito próximas. .
Técnicas de Aptidão l
Aptidão é a Avaliação Ai = fi
l
Exemplo: Ai = 999,979
Windowing – subtrair uma constante dos valores de fi
l
Normalização Linear – atribuir valores a Ai baseados no rank do cromossoma
Windowing l l
l
l
Obtenha a avaliação mínima na população. Atribua a cada cromossoma I uma aptidão igual a: Ai = (f i - Amín) Opcionalmente, atribua uma aptidão mínima de “sobrevivência”, maior que a aptidão mínima calculada, como garantia de reprodução para os cromossomas menos aptos. Exemplo: Ai = (999,979 - 999,066)= 0,913
Normalização Linear l l l
Coloque os pop_size cromossomas em ordem decrescente de avaliação (i=1 é o menos apto). Crie aptidões, partindo de um valor mín e crescendo linearmente até o valor máx. Os valores de máx e mín (ou a constante de incremento) são parâmetros da técnica.
Ai = mín + (máx - mín) pop_size - 1 l
x (i - 1)
Quanto maior a constante de incremento, maior a pressão seletiva sobre os melhores.
Exemplo Comparativo Rank dos cromossomas Avaliação original Aptidão é avaliação Normalização Linear, taxa=10 Normalização Linear, taxa=20 Windowing
6 200 200 60 101 199
5 9 9 50 81 8
4 8 8 40 61 7
3 7 7 30 41 6
2 4 4 20 21 3
1 1 1 10 1 0
• SUPER INDIVÍDUO: cromossoma 6 •poucas chance de recombinação com outros indivíduos; elimina competidores em poucas gerações; rápida convergência.
• COMPETIÇÃO PRÓXIMA: entre cromossomas 3, 4 e 5 •é preciso aumentar a pressão seletiva sobre os melhores
l
Módulo de Avaliação Função de Avaliação:
l
l
GA2-1
Função binária F 6
Módulo de População Técnica de Representação:
Binária 44 bits
Técnica Inicialização da População:
Aleatória
Técnica Eliminação da População:
Elimina todos
Técnica de Reprodução:
Troca da geração
Técnica de Seleção de Genitores:
Roleta
é Técnica de Aptidão:
Normalização Linear (100 a 1)
Técnica de Parametrização:
Nenhuma
Técnica de Elitismo:
Nenhuma
Population Size :
100
Total de Indivíduos:
4000
ICADEMO
Módulo de Reprodução Técnica de Seleção de Operadores:
Use todos
Operadores:
Crossover 1 ponto & Mutação
Taxa Mutação:
0,008
Taxa Crossover:
0,65
Técnica de Parametrização:
nenhuma
Elitismo l
Melhor cromossoma de P(t) é copiado em P(t+1), após o mutação e crossover.
l
Reduz o efeito aleatório do processo seletivo.
l
Garante que o melhor indivíduo da próxima geração é melhor ou igual ao da geração anterior.
l
Módulo de Avaliação Função de Avaliação:
l
l
Função binária F 6
GA2-2
Módulo de População Técnica de Representação:
Binária 44 bits
Técnica Inicialização da População:
Aleatória
Técnica Eliminação da População:
Elimina todos
Técnica de Reprodução:
Troca da geração
Técnica de Seleção de Genitores:
Roleta
é Técnica de Aptidão:
Normalização Linear (100 a 1)
Técnica de Parametrização:
Nenhuma
é Técnica de Elitismo:
Copia o melhor
Population Size :
100
Total de Indivíduos:
4000
ICADEMO
Módulo de Reprodução Técnica de Seleção de Operadores:
Use todos
Operadores:
Crossover 1 ponto & Mutação
Taxa Mutação:
0,008
Taxa Crossover:
0,65
Técnica de Parametrização:
nenhuma
Algoritmo Genético Tradicional l l l l l
Representação Binária Reprodução com substituição da população Elitismo Normalização Linear Crossover de 1 ponto e Mutação – Algoritmo de partida em aplicações – Apresenta bom desempenho em vários problemas
Reprodução Steady State l l l
l l
Substituição parcial de indivíduos a cada geração (mais elitista) Bons indivíduos (material genético) são preservados, garantindo mais chances de reprodução Método: – Crie n filhos (seleção+crossover+mutação) – Elimine os n piores membros da população – Avalie e introduza os filhos na população GAP = fração da população que é trocada valor de GAP determina relação entre exploitation e exploration
Exemplo de Steady State C19 C18 C17 C16 C15 C14 C13 C12 C11 C10 C9 C8 C7 C6 C5 C4 C3 C2 C1
120 110 100 99 95 81 76 67 58 44 42 36 22 20 19 17 10 8 5
avaliações de P(t)
38 6 121 88 58 17
120 110 100 99 95 81 76 67 58 44 42 36 22 38 6 121 88 58 17
crie n novos
substitua os n piores
121 120 110 100 99 95 88 81 76 67 58 58 44 42 38 36 22 17 6
avaliações de P(t+1)
l
Módulo de Avaliação Função de Avaliação:
l
GA2-3
Módulo de População Técnica de Representação:
Binária 44 bits
Técnica Inicialização da População:
Aleatória
é Técnica Eliminação da População:
Elimina o último
é Técnica de Reprodução:
Steady State
Gap
l
Função binária F 6
ICADEMO
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:
Nenhuma
Population Size :
100
Total de Indivíduos:
4000
Módulo de Reprodução Técnica de Seleção de Operadores:
Use todos
Operadores:
Crossover 1 ponto & Mutação
Taxa Mutação:
0,008
Taxa Crossover:
0,65
Técnica de Parametrização:
nenhuma
Steady State sem Duplicados l l l l l
Substituição parcial de indivíduos com exclusão de duplicados Evita os duplicados que são mais frequentes com steady state (populações mais estáticas) Maior eficiência do paralelismo de busca, garantindo pop_size indivíduos diferentes Descendentes duplicados são desprezados Maior overhead para teste de igualdade
Novos Técnicas, Parâmetros e Operadores Crossover de 2 pontos l Crossover Uniforme l
l
l
Operadores Independentes e Seleção de Operadores
l
Interpolação dos Parâmetros
Módulo de Avaliação Função de Avaliação:
l
Módulo de População Técnica de Representação:
Binária 44 bits
Técnica Inicialização da População:
Aleatória
Técnica Eliminação da População:
Elimina o último
Técnica de Reprodução:
Steady State s/ duplicados
Gap
l
Função binária F 6
GA3-1 a GA 3-3
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 (de 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
é
Mutação Taxa Mutação:
0,04
Taxa Crossover:
0,8
é Técnica de Parametrização:
Interpolar Pesos dos Operadores
é
de (70 30) a (50 50)
Crossover de 2 Pontos l
Semelhante ao crossover de 1 ponto
l
2 pontos são escolhidos aleatoriamente Crossover de 1 ponto não consegue combinar todos os padrões de dois genitores
l
P1 P2
1 0
1 0
0 0
1 1
1 0
0 1
0 1
1 0
0 1
1 1
1 1
0 1
1 0
1 0
pontos de corte P1 P2
1 0
1 0
0 0
1 1
1 0
0 1
0 1
1 0
0 1
1 1
1 1
0 1
1 0
1 0
F1 F2
1 0
1 0
0 0
1 1
0 1
1 0
1 0
0 1
1 0
1 1
1 1
0 1
1 0
1 0
Crossover Uniforme l l
P1
A contribuição de cada genitor é decidida aleatoriamente por um padrão Capacidade de combinar quaisquer padrões
P2
1 0
0 1
0 0
1 1
0 1
1 0
1 1
Padrão
1
1
0
1
0
0
1
F1 F2
Operadores Independentes Determinados GAs podem incorporar diversos operadores genéticos. l Operadores não devem ser usados todos, com a mesma intensidade, a cada fase da evolução ( por ex: mais crossover no início e mais mutação no final da evolução ). l Uma roleta sorteia um operador a cada reprodução. l Pesos (chances) dos operadores, iniciais e finais, e taxa de interpolação são parâmetros do algoritmo. l
OP4
OP3 OP2
l
Módulo de Avaliação Função de Avaliação:
l
Função binária F 6
GA3-1
Módulo de População Técnica de Representação:
Binária 44 bits
Técnica Inicialização da População:
Aleatória
Técnica Eliminação da População:
Elimina o último
Técnica de Reprodução:
Steady State s/ duplicados
Gap
l
OP1
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:
Nenhuma
Population Size :
100
Total de Indivíduos:
4000
Módulo de Reprodução é Técnica de Seleção de Operadores:
Roleta
é Operadores:
Crossover 2 pontos
é
Mutação Taxa Mutação:
0,01
Taxa Crossover:
0,7
Técnica de Parametrização:
Nenhuma
é Pesos
(50 50)
ICADEMO
Módulo de Avaliação
l
Função de Avaliação:
GA3-2
Função binária F 6
Módulo de População
l
ICADEMO
Técnica de Representação:
Binária 44 bits
Técnica Inicialização da População:
Aleatória
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:
Nenhuma
Population Size :
100
Total de Indivíduos:
4000
Módulo de Reprodução
l
é Técnica de Seleção de Operadores:
Roleta
é Operadores:
Crossover Uniforme
é
Mutação Taxa Mutação:
0,01
Taxa Crossover:
0,7
Técnica de Parametrização:
Nenhuma
é Pesos
(50 50)
Desempenho l
Aspectos importantes:
l
– convergência do GA – proximidade dos melhores cromossomas a um mínimo local – diversidade da população – valores dos parâmetros do GA Exemplo: variação da aptidão dos operadores durante evolução.
30
30
30
25
25
25
20
20
15
15
10
6 66
6 66
5 0 1
2
3
4
5
6
7
Início: Crossover Mutação
8
6
9 10 11 12 13 14 15
66 6 6 6 6
20
6 66 6 6
10 5
15
6 6
10
6
5
0
0 1
2
3
4
5
6
7
8
Meio: Crossover Mutação
9 10 11 12 13 14 15
1
2
3
4
5
6
7
8
Fim: Crossover Mutação
9 10 11 12 13 14 15
Interpolação de Parâmetros l
l
Consiste na variação dos valores dos parâmetros do GA durante a execução, de modo a alcançar maior desempenho. Parâmetros: – – – –
l
taxa de crossover taxa de mutação taxa incremento da normalização da aptidão aptidão dos operadores
Interpolação define: – valores inicial e final do parâmetro e frequência de ajuste.
l
Módulo de Avaliação Função de Avaliação:
l
Módulo de População Técnica de Representação:
Binária 44 bits
Técnica Inicialização da População:
Aleatória
Técnica Eliminação da População:
Elimina o último
Técnica de Reprodução:
Steady State s/ duplicados
Gap
l
GA3-3
Função binária F 6
ICADEMO
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 (de 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
é
Mutação Taxa Mutação:
0,01
Taxa Crossover:
0,7
é Técnica de Parametrização:
Interpolar Pesos dos Operadores
é
de (70 30) a (50 50)
gráfico
Algoritmos Genéticos Híbridos ●
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
●
Hibridizar: – Adotar REPRESENTAÇÃO em uso – Adaptar OPERADORES – Adotar HEURÍSTICAS de otimização
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 – Crossover: recombinação de sub-partes de indivíduos – Mutação: variações globais ou locais para manter agitada a variedade genética
1
Representação por 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 ∈ ℜ aleatoriamente; •Calcula f6 para o par (x,y); •Salva (x,y) e f6(x,y); •Retorna a melhor avaliaçã avaliaçãoo se tempo esgotado; •Retorna ao primeiro passo;
Hibridizaçã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
2
Crossover ● ● ●
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, t 1, z 2) ➨
P2 ≡ (x2, y2, t 2, z 2) Padrã Padr ão ≡ 0 1 1 0
F2 ≡ ( x1, y2, t 2, z 1)
Crossover de Média ●
Cruzamento específico para o problema
●
Se dois cromossomas são promissores, a média de seus valores reais pode levar a uma melhor solução P1 ≡ (x1, y1) ➨
( x1+x2)/2, (y ( y1+ y2)/2) F1 ≡ ( (x
P2 ≡ (x2, y2) ●
A média entre dois valores pode resultar em valores mais próximos do valor desejado.
3
Crossover de Média ●
Crossover aritmético é uma combinação linear de dois vetores (genitores) P1 e P2 na geração t: F1 = a . P 1 + (1(1-a) P 2 F2 = a . P 2 + (1(1-a) P 1
●
a =cte =cte
: crossover uniforme
●
a =f(t)
: crossover não-uniforme (a depende da idade da população)
Mutação ●
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) 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
4
Creep - Método de Ajuste 1 Xt + ∆ (máx - Xt) se bit sorteado =0 ●
Xt+1 = Xt - ∆ (Xt - mín) se bit sorteado =1
máx e mín = limites do domínio de x ● ∆ (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
Creep - Método de Ajuste 2 ● Xt +1
Xt + ∆ (t, máx- Xt)
se bit sorteado =0
Xt - ∆ (t, Xt -mí n)
se bit sorteado =1
=
t= geração; máx e mín = limites do domínio de x . ●
∆ (t, s) = s . ( 1 - rand
(1 - t/T) 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 ∆ (t, s) ser pró próximo de zero aumenta com o nú número de geraçõ gerações. es.
5
Creep - Método de Ajuste 2 ∆ (t, s)
∆ (t, s)
s
s t/T=0,50; b=2
t/T=0,90; b=2
1 rand ●
● ●
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)
Mód ulo de Av aliação ➩ Função de Avaliação: Mód ulo de População
Função F6 real
➩ 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
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: ●
1
Total de Indivíduos: Mód ulo de Reprodução
100 4000
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)
6
Biná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 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.
7
Distância de Hamming ●
Rep. Binário C1 = 0 1 1 1 1 1
31
C2 = 1 0 0 0 0 0
32
➨ ●
Valor Real
distância = 6
Rep. Real
Valor Real
C1 = 31
31
C2 = 32
32
➨
distância = 1
8
GA em Otimização Combinatorial ●
Problemas onde a busca da solução depende da avaliação de diversas combinações (ORDEM) dos elementos considerados – – – – –
Problem a do Caixeiro Viajante Problem as de Planejamento Problem as de Cronogram as Alocação de Salas Grafos: Colorir, Colorir Particionar, Percorrer
Problema de Colorir o Grafo índice I-P
●
1-5
2-8
3-4
4-9
5-6
6-7
7-13
8-10
9-15
peso
Regras: – Colorir os nós do grafo de modo a maximizar a soma total dos pesos. – Pares de nós conectados por um arco não podem possuir a mesma cor
1
Algoritmo Guloso ●
●
Considera apenas uma das possíveis soluções, colorindo os nós em ordem decrescente de peso. Nós em ordem decrescente de peso:
1-5
2-8
3-4
4-9
5-6
6-7
7-13
8-10
9-15
1-5
2-8
3-4
4-9
5-6
6-7
7-13
8-10
9-15
(9, 7, 8, 4, 2, 6, 5, 1, 3) ●
Solução Ótima p/ 1 cor: (9, 4, 2) ➨ ∑ Pi = 32
Algoritmo Guloso ●
●
Considera apenas uma das possíveis soluções, colorindo os nós em ordem decrescente de peso. Nós em ordem decrescente de peso: (9, 7, 8, 4, 2, 6, 5, 1, 3)
●
Solução Ótima p/ 1 cor: (9, 4, 2) ➨ ∑ Pi = 32
2
Algoritmo Guloso ●
●
Considera apenas uma das possíveis soluções, colorindo os nós em ordem decrescente de peso. Nós em ordem decrescente de peso:
1-5
2-8
3-4
4-9
5-6
6-7
7-13
8-10
9-15
1-5
2-8
3-4
4-9
5-6
6-7
7-13
8-10
9-15
(9, 7, 8, 4, 2, 6, 5, 1, 3) ●
Solução Ótima p/ 1 cor: (9, 4, 2) ➨ ∑ Pi = 32
Algoritmo Guloso ●
●
Considera apenas uma das possíveis soluções, colorindo os nós em ordem decrescente de peso. Nós em ordem decrescente de peso: (9, 7, 8, 4, 2, 6, 5, 1, 3)
●
Solução Ótima p/ 2 cores: (9, 4, 2) e ( 7, 6, 5) ➨ ∑ Pi = 32 + 26
3
Aplicando o Algoritmo Guloso ●
Nós em ordem decrescente de peso:
2-8
1-12
(7, 3, 4, 1, 6, 5, 2)
3-14
6-10
7-15
4-13
5-9
Aplicando o Algoritmo Guloso ●
Nós em ordem decrescente de peso:
2-8
1-12
(7, 3, 4, 1, 6, 5, 2) ●
Algoritmo Guloso começa e para no nó 7
3-14
6-10
7-15
4-13
5-9
4
Aplicando o Algoritmo Guloso ●
Nós em ordem decrescente de peso:
2-8
1-12
(7, 3, 4, 1, 6, 5, 2) ●
Soluções Ótimas:
3-14
6-10
7-15
– 1 cor: (1, 5, 3) – 2 cores: (2, 4, 6) 4-13
5-9
Características do Problema ●
● ●
●
A modificação dos pesos, número de cores e arcos, altera radicalmente a solução do problema. Estratégias como o algoritmo guloso não funcionam bem para todos os problemas de colorir o grafo. Heurísticas (Ex: a valiar número de arcos ou pesos de nós vizinhos antes colorir um nó) podem não ser eficientes para grandes espaços de busca. Algoritmos Genéticos oferecem uma solução (subótima ou ótima) para qualquer problema de colorir o grafo.
5
Componentes de um Algoritmo Genético 1. Problema 2. Representação 3. Decodificação 4. Avaliação 5. Operadores 6. Técnicas 7. Parâmetros
Tentando a Representação Binária ●
Cada nó do grafo é representado por um campo (gene) no cromossoma: Símbolo do Campo ≡ Cor do nó
●
Podemos usar a representação binária. Para apenas 1 cor : 0 ≡ não colorido
1 ≡ colorido
1-5
2-8
3-4
4-9
5-6
6-7
7-13
8-10
9-15
Cromossoma ≡ 0 1 0 1 1 0 0 0 1 Nó
1 2 3 4 5 6 7 8 9
6
Avaliando Representação Binária ● ●
● ●
C é um cromossoma ILEGAL ILEGAL. Inicialização, crossover e mutação vão gerar soluções ilegais. Seria necessário um módulo reparador de cromossomas Representação binária permite soluções sub-ótimas: 1-5 3-4 2-8 C≡ 010100000 Nó
●
1 2 3 4 5 6 7 8 9
C ainda poderia ter o nó 6, ou 8 ou 9 colorido e ser legal.
4-9
5-6
6-7
7-13
8-10
9-15
Representação Baseada em Ordem ● ●
GA Híbrido ≡ Técnicas de GA + Algoritmo Guloso Algoritmo Guloso: – Cria uma lista de nós (ordem decrescente de peso) – Constrói a solução: atribui ao próximo nó da lista uma cor legal
●
Algoritmo Genético – Cria uma lista (nós em ordem qualquer) – Constrói a solução: atribui ao próximo nó da lista uma cor legal
7
Exemplo ●
Cromossoma = lista C1 ≡(9, 7, 8, 4, 2, 6, 5, 1, 3) C2 ≡(2, 3, 7, 4, 9, 6, 5, 1, 8) C3 ≡(4, 5, 1, 2, 9, 6, 8, 7, 3)
●
2-8
3-4
4-9
5-6
6-7
7-13
8-10
9-15
C1 C2 C3 resultam na solução ótima p/ 1 cor: (9, 4, 2) ➨ ∑ Pi = 32
●
1-5
Informação codificada é a ordem relativa dos nó n ós
Operadores Genéticos ●
Testando o Crossover de 1 ponto: P1 ≡(9, 7, 8, 4, 2, 6, 5, 1, 3) P2 ≡(2, 6, 7, 4, 9, 3, 5, 1, 8) F1 ≡(9, 7, 8, 4, 2, 3, 5, 1, 8) F2 ≡(2, 6, 7, 4, 9, 6, 5, 1, 3)
● ●
Descendentes são cromossomas ilegais: nós repetidos e ausência de determinados nós. Crossover e mutação devem garantir uma lista válida de todos os nós
8
Modelagem do Algoritmo Genético 1. Problema
• Problema de Colorir o Grafo 2. Representação
• Permutação dos índices dos nós 3. Decodificação
• Da esquerda para direita, atribui uma cor válida ao próximo nó 4. Avaliação • ∑ Pi 5. Operadores • Crossover Uniforme Baseado em Ordem ●
Mutação por Embaralhamento
Crossover Uniforme Baseado em Ordem ● ●
●
● ●
●
Dados dos genitores P1 e P2, , criar descendente F1; Gere um padrão de bits do mesmo comprimento que os genitores; Preencha F1, copiando o genitor P1 nas posições em que o padrão é igual a “1”; Faça uma lista dos elementos de P1 associados com os bits “0” do padrão; Permute estes elementos de modo que eles apareçam na mesma ordem em que aparecem em P2 ; Preencha as lacunas de F1 com os elementos ordenados no passo anterior;
9
Exemplo P2
1 8
2 6
3 4
4 2
5 7
6 5
7 3
8 1
Padrão
0
1
1
0
1
1
0
0
F1
8
2 -
3 -
2
5 -
6 -
3
1
P1
F2
Elementos de P 1 associados a “ 0”: 1, 4, 7, 8.
Ordenados segundo P 2 : 8, 4, 7, 1
Elementos de P 2 associados a “ 1”: 6, 4, 7, 5.
Ordenados segundo P 1 : 4, 5, 6, 7
F1 F2
8 8
2 4
3 5
4 2
5 6
6 7
7 3
1 1
Mutação por Embaralhamento ●
●
Seleciona aleatoriamente uma sub-lista do cromossoma Embaralha sub-lista
1
2
3
4
5
6
7
8
9
1
2
3
6
4
8
7
5
9
10
●
●
Mód ulo de Av aliação ➩ Função de Avaliação:
GA6-1
Mód ulo de População ➩ T écnica de Representação:
Lista de nós
➩ T écnica Inicialização da População:
Permutação aleatória
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: ●
Avaliador do problema de colorir o grafo ∑ Pi
Total de Indivíduos: Mód ulo de Reprodução
100 4000
T écnica de Seleção de Operadores:
Roleta
➩ Operadores:
Crossover Uniforme Baseado em Ordem
➩
Mutação por Embaralhamento
➩ T écnica de Parametrização:
Interpolar Pesos dos Operadores
➩
de (60 40) a (30 70)
Problema de Colorir o Grafo ● ● ●
Grafo com 100 nós ➨ 100! permutações diferentes 3 cores possíveis Listagem descreve o grafo através de: (índice_nó, peso (lista de nós conectados))
(1 62 (20 58 74 82)) (2 183 (6 12 20 28 29 32 51 53 70 79 84 94)) (3 247 (18 24 33 50 88 92)) .................... ........... (99 254 (29 52 53 67 75 80 84 89)) (100 145 (15 20 22 29 34 44 60 87))
11
Busca Aleatória ●
● ●
●
Muitas vezes não temos como comparar os resultados obtidos por um GA. Nestes casos, podemos usar a busca exaustiva como base de comparação. Gera-se uma curva média de desempenho para a busca aleatória com o mesmo número de tentativas que o GA. Um modelo de GA desempenhando abaixo da busca exaustiva deve prova velmente conter erros de modelagem e/ou programação.
Busca Aleatória procedure busca_aleatória begin t=0 ; primeira geração inicializa P(t) ; população inicial aleatória av alia P(t) ; calcula f(i) p/ cada indivíduo salv a_melhor de P(t) ; salva melhor indivíduo while (not total_indivíduos) do begin t =t + 1 ; próxima geração inicializa P(t) ; população aleatória av alia P(t) ; calcula f(i) p/ cada indivíduo compara_melhor P(t) com melhor P(t-1) salv a_melhor end end
12
Resultados do GA 66-1 ●
GA 6-1 é em média 7,4% que a busca aleatória após 4000 tentativas: – média GA 6-1= 10300 10300; média busca aleatória=9600 9600
●
GA 6-1 é em média 7,4% que a Algoritmo Guloso: – máximo do Alg. Guloso= 9590
●
GA 6-2 com pop_size=1200 e total_indivíduos=10000 encontrou avaliação=10594 10594
13
GA em Otimização de Planejamento ●
Planejamento envolve:
Procedimentos Recursos Tarefas Tempo Objetivos Restrições e condições ●
Otimizar: – “Alocar , no tempo, os recursos para a execução das tarefas, respeitando as restrições e condições, de modo a alcançar os objetivos do problema.”
Exemplos – – – – – –
Problema do Caixeiro Viajante Otimização da Distribuição (Rota de veículos) Alocação de Salas; Timetabling Planejamento de Vôos de Cias Aéreas Otimização de Estoque/Produção Otimização da Produção Industrial
1
Variáveis Típicas do Planejamento ●
Restrições de Recursos – número de instâncias de cada recurso/máquina; – diferenças entre as instâncias (velocidade, tempo máximo de operação, capacidade etc). – paradas de manutenção – máquinas com programação especial: laminadores de aço (largura, espessura e dureza)
●
Restrições Temporais – horário de funcionamento preferenciais; – tempo de transporte de material entre máquinas
●
Reajuste das Máquinas – tarefas exigem setup de máquinas (automático ou manual).
Variáveis Típicas do Planejamento (cont.) ●
Prioridade – tarefas possuem prioridades diferentes (prazo de entrega, emergência, manutenção, tipo de cliente etc).
●
Estoque – matéria prima: disponibilidade, ordem de desempilhamento
●
Reprogramação – reprogramação das máquinas em casos de contingências
●
Precedência – certas tarefas não podem ser programadas antes que outras tenham terminado.
2
Características do Planejamento ●
Há muitas condições e restrições que não podem ser ser expressas matematicamente;
●
Métodos de busca podem falhar devido aos requisitos de tempo;
●
Podar o espaço de busca reduz o tempo de execução mas limita desempenho;
●
Heurísticas são úteis para acelerar a busca;
●
GA é um técnica adequada a problemas mal estruturados como os de planejamento.
Problema Simples de Planejamento de Produção ● ●
● ● ● ●
●
90 tarefas: (a, b, c, d, e, f................) cada tarefa possui um peso associado a sua importância (lucro, prioridade, benefício etc) 30 recursos: apenas uma instância de cada recurso tarefas requerem de 1 a 3 horas para execução programação para um total de 40 horas de produção algumas tarefas têm restrições nas primeiras 12 horas do planejamento Objetivo: maximizar a soma dos pesos das tarefas planejadas nas primeiras 40 horas
3
Exemplo de Tarefas:
a..u
Tempo de Execução de cada tarefa:
1, 2 ou 3 horas
Recursos requeridos por cada tarefa: “ . ” = recurso não requerido Tarefas
“ a” = recurso requerido Recursos Utilizados pelas Tarefas
Tempo Execução a b c d e f g h i j k l m n o p q r s t u
3 1 3 3 3 1 3 2 1 1 1 1 3 2 3 1 3 1 3 1
. . . . . . g h . . . l . . . . . r . t
a . . . . f . . . . . . . . o . . . . .
. b c d . . g . . . k . . . o . . . . .
. . . . . c . . . e f f . . . h i . . . k . . l . m . . . . . p q . . . s s . .
. . c . e f . . . . k l . . . . . . . .
a . . d e . . h . . . . m . . . . . . .
a b . . . . g . . . k . . . . . q . . .
. . c . . f . h . . . l . . o . . . s .
. . a b . . . . . d . . e . . . . . . . . . h h . i i . . . . . . . . . . m m . . . . . . . p . . . . . r r s . . . . .
a b . d . . g . i . . l . . . p q . . .
. . c . . . . . . . k . . . . p . r . .
. b . . . . g . . . k . . n o . . . . t
. b . . . . g . . . . l . n . . q . s .
. . c . . . g . . . . . . . . . . . . .
. . c . e . . . . . . l . . o . . . . t
. b . . . . . . i . . l . n o p q . . t
. . c . . . . . . . . . . n . . . r . .
a b . . . f . . . . . . . . . . q . . .
. . c d . . g . i . k . . . o p . . s .
. . c . . f g . . . . l . . . . . . . .
. . . . . . . . . . . . . . . f f . . g g . . . . . . . j . . . . . . l . m . . . . . . . p . . q . q . . . . . . . . .
Exemplo de Planejamento Planejamento parcial das tarefas em ordem alfabética
●
Tempo Hora
1 2 3 4 5 6 7 8 9 10 11
. . . . . g g g . g
a a a . f . . . . . f .
c c c . d d d g g g . g
. . . b f . . . . . f .
c c c . f . . e e e f .
c c c . f . . e e e f .
a a a a a a . . d . d . d . e g e g e g . . . g
c c c b f . . . . . f .
. . . . d d d e e e . .
. . . b . . . . . . . .
a a a . . . . . . . . .
a c a c a c . b d . d . d . g . g . g . . . g .
. . . . . . . g g g . g
. . . b . . . g g g . g
c c c b . . . g g g . g
c c c . . . . e e e . .
. . . . . . . . . . . .
c c c b . . . . . . . .
a a a . f . . . . . f .
c c c b d d d g g g . g
c c c . f . . g g g f g
. . . . f . . . . . f .
. . . . . . . . f . . . . . g g g g g g f . g g
. . . . f . . e e e f .
. . . . . . . . . . . .
. . . . f . . . . . f .
. . . . d d d e e e . .
4
Modelagem do Algoritmo Genético 1. Problema 2. Representação 3. Decodificação 4. Avaliação 5. Operadores 6. Técnicas 7. Parâmetros
Representação ●
Cromossoma ≡ permutação (lista) de tarefas P1 = (a, b, c, d, e, . . . . t) P2 = (d, s, e, h, g, . . . . i)
● ●
cromossoma codifica a ordem e a vez (posição) nas quais as tarefas serão planejadas requer decodificador ≡ construtor de planejamentos legais
5
Decodificador do Cromossoma ●
Constrói soluções LEGAIS
●
Concentra todo o conhecimento no domínio do problema: restrições, recursos, horários, etc.
●
Regra Principal: “Se uma tarefa está planejada na hora t, uma outra tarefa não pode ser planejada em t, exceto se a interseção dos recursos requisitados é vazia”
Decodificador do Cromossoma 1
Pega a primeira tarefa da lista;
2
Coloca a tarefa no planejamento a partir de t=0;
3
Pega próxima tarefa e procura colocá-la no planejamento, considerando as restrições presentes, a partir de t=0 até t=40 horas;
4
Vai para 3 se não terminou a lista.
6
P = (t, c, s, a) Hora
t
.
.
.
.
.
.
.
.
.
.
.
.
.
t
.
.
t
t
.
.
.
.
.
.
.
.
.
.
.
. c c c
. c c c
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
1 2 3 4 5 6 7 8 9 10 11
P = (t, c, s, a) Hora
t . . .
. . . .
. c c c
. . . .
. c c c
. c c c
. . . .
. . . .
. c c c
. . . .
. . . .
. . . .
. . . .
. c c c
t . . .
. . . .
. c c c
t c c c
t . . .
. c c c
. . . .
1 2 3 4 5 6 7 8 9 10 11
7
P = (t, c, s, a) Hora
t . . . .
. . . . .
. c c c . . .
. . . . c c . c c . c c s s . s s . s s .
. . . . . . .
. . . . . . .
. c c c s s s
. . . . s s s
. . . . . . .
. . . . . . .
. . . . . . .
. c c c . . .
t . . . . . .
. . . c . c . c s . s . s .
t c c c . . .
t . . . . . .
. c c c . . .
. . . . . . .
. . c c c c c c s . s . s .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . s s s
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
1 2 3 4 5 6 7 8 9 10 11
P = (t, c, s, a) ➨ 7 horas Hora
t . . . .
a a a . .
. c c c . . .
. . . . c c . c c . c c s s . s s . s s .
a a a . . . .
a a a . . . .
. c c c s s s
. . . . s s s
. . . . . . .
a a a . . . .
a a a . . . .
. c c c . . .
t . . . . . .
. . . c . c . c s . s . s .
t c c c . . .
t . . . . . .
. c c c . . .
a a a . . . .
. . c c c c c c s . s . s .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . s s s
1 2 3 4 5 6 7 8 9 10 11
8
P = (t, a, s, c) Hora
t
.
.
.
.
.
.
.
.
.
.
.
.
.
t
.
.
t
t
.
.
.
.
.
.
.
.
.
.
.
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
1 2 3 4 5 6 7 8 9 10 11
P = (t, a, s, c) Hora
t . .
a a a
. . .
. . .
. . .
. . .
a a a
a a a
. . .
. . .
. . .
a a a
a a a
. . .
t . .
. . .
. . .
t . .
t . .
. . .
a a a
. . .
1 2 3 4 5 6 7 8 9 10 11
9
P = (t, a, s, c) Hora
t . .
a a a
. . .
s s s
s s s
. . .
a a a
a a a
s s s
s s s
. . .
a a a
a a a
. . .
t . .
s s s
. . .
t . .
t . .
. . .
a a a
s s s
. . .
. . .
. . .
. . .
s s s
. . .
. . .
. . .
. . . . . .
. . . . . .
. . . . . .
1 2 3 4 5 6 7 8 9 10 11
P = (t, a, s, c) ➨ 6 horas Hora
t . . . . .
a a a . . .
. . . c c c
s s s . . .
s s s c c c
. . . c c c
a a a . . .
a a a . . .
s s s c c c
s s s . . .
. . . . . .
a a a . . .
a a a . . .
. . . c c c
t . . . . .
s s s . . .
. . . c c c
t . . c c c
t . . . . .
. . . c c c
a a a . . .
s s s c c c
. . . c c c
. . . . . .
. . . . . .
. . . . . .
s s s . . .
1 2 3 4 5 6 7 8 9 10 11
10
Avaliação ●
Uma possível função considera: – pesos das tarefas ➨ maximizar a soma das planejadas – restrições das tarefas ➨ penalizar se violação – período ➨ não planejar se além de t=40 horas
Ai = ∑ pt - ∑ pn + ∑ pp + ∑ pv/2 t
– – – – ●
pt pn pp pv
n
p
v
= pesos de todas as tarefas = pesos das tarefas não planejadas = pesos das tarefas planejadas = pesos das tarefas que violaram restrição
Ai ≥ 0; Ai = 0 ➨ nenhuma planejada; Ai = 2 ∑ pt ➨ todas
Avaliando Operadores ● ● ● ● ● ●
Mutação Baseada em Ordem Mutação Baseada em Posição Mutação por Embaralhamento Crossover Baseado em Ordem Crossover Baseado em Posição Recombinação de Adjacências Aspectos importantes – Ordem Relativa • tarefas anteriores podem impedir o planejamento das tarefas posteriores – Posição da Tarefa • tarefas no início da lista têm maior chance de serem planejadas
11
Avaliação de Desempenho ●
Avaliação dos Operadores isoladamente: – só mutação – só crossover
● ●
Combinando os Melhores Operadores Busca Aleatória para comparar resultados – gera uma lista de tarefas e avalia
● ●
Espaço de Representação = 90! = 10138 Média de 50 Experimentos de 3000 Indivíduos: média dos melhores a cada instante
Busca Aleatória
12
Mutação Baseada em Ordem ●
●
●
duas tarefas são selecionadas aleatoriamente e a segunda é colocada na frente da primeira Exemplo: (a a b c d e f)
(a b c d e f)
⇓ (e e a b c d f)
⇓ (a d b c e f)
operador preserva ordem relativa de parte do cromossoma
Mutação Baseada em Posição ●
●
troca as posições de duas tarefas escolhidas aleatoriamente (a a b c d e f)
(a b c d e f)
⇓ (e e b c d a f)
⇓ (a d c b e f)
operador não preserva a ordem relativa das posições selecionadas em relação as tarefas do meio
13
Mutação por Embaralhamento ●
●
embaralha sub-lista escolhida aleatoriamente (a | b c d | e f)
(a b c | d e f |)
⇓
⇓
(a | c d b | e f)
(a b c | f d e |)
operador tem maior poder de dispersão da população
Resultados da Mutação ● ● ● ● ●
Testes sem crossover e com elitismo Mutação é mais efetiva que busca aleatória Mutação baseada em ordem é mais efetiva Embaralhamento é melhor que busca aleatória Operadores de mutação são heurísticos, por isso são melhores que busca aleatória
14
Resultados da Mutação
Crossover de Ordem ● ●
Posições são selecionadas aleatoriamente Ordem das tarefas nas posições selecionadas em um genitor é imposta nas tarefas correspondentes no outro genitor
P1 = P2 =
a e
b c i b ✶ ✶
posições
d d
e f
f g a j
✶
F1 = F2 =
a _
_ i
c _
d d
e f
_ a
_ h j g
F1 = F2 =
a b
i i
c c
d d
e f
b a
f j
h g ✶
i j c h
_ j _ _
h g g e
j h
15
Crossover de Posição ● ●
Posições são selecionadas aleatoriamente Posições das tarefas em um genitor são impostas nas tarefas correspondentes no outro genitor a b c d e f g h i j P1 = e i b d f a j g c h P2 = posições
✶
✶
✶ _ f _ e
F1 = F2 =
_ _
i b
b c
F1 = F2 =
a i
i b
b c c d
✶ _ _
_ g _ h
_ _ _ _
f d e f
e g a h
h j j g
Recombinação de Adjacências ●
Crossover combina a informação de adjacências entre as tarefas presentes nos genitores P1 = P2 =
a b
P1 ➩ P2 ➩
ab bc cd de ef fa bd dc ca ae ef fb
informação de adjacência informação de adjacência
F = F ➩
b c d e a f bc cd de ea af fb
informação de adjacência
b d
c c
d a
e e
f f
16
Recombinação de Adjacências ●
Operador foi originalmente criado para o problema do Caixeiro Viajante (TSP) 3Km
ADBCE
D 1Km
cidades
A
7Km
B
4Km
E 3Km
C ●
No TSP temos: – informação de adjacência é importante
– direção (ordem) entre 2 cidades não importa (A B = B A)
Resultados do Crossover ●
●
●
Testes sem mutação e com elitismo (rápida evolução no início, nada acontece após 1000 indivíduos) Crossover de ordem apresenta resultado equivalente ao de posição: são de fato o mesmo operador !! Recombinação de Adjacências é equivalente a busca aleatória no problema de planejamento
17
Resultados do Crossover
Combinando Crossover e Mutação 1 Mutação de Ordem (50%) + Crossover de Ordem (50%) 2 Mutação de Ordem (50%) + Crossover de Posição (50%) 3 Mutação de Ordem (50%) + Recomb. de Adjacências (50%) ● ●
Curvas menos inclinadas no início e menos planas no final Variando os pesos do crossover e mutação, pode-se melhorar o desempenho: aumentando-se a mutação e diminuindo-se o crossover, lentamente, durante a evolução.
18
Crossover (50%) + Mutação (50%)
Variando-se os Pesos de Crossover + Mutação
19
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”
Schema ●
Buscando padrões de jogadores de seleção Sexo
Gostam de Futebol Jogadores da Seleção Masculino
Médico
> 30 anos
Feminino
Idade
Gosto
Profissão
Aptidão dos Padrões Sexo
Idade
Gosto
Profissão
Aptidão baixa
Masculino
I>30
X
X
Feminino
X
X
X
baixa
Masculino
I<30
X
X
boa
X
X
Sim
Médico
Gostam de Futebol Médico Jogadores > 30 anos da Seleção Feminino Masculino
baixa
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 2 3 , cujos os dois primeiros bits são iguais a ‘1’, não importando os demais.
Interpretação ● ● ●
●
●
f(x) = x2 , x ∈ 23 Seja o schema 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 ✴
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
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
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
Representação Geométrica Schemata de Ordem 3: Pontos 110
111
010
011
100
101
001
000
Representação Geométrica Schemata de Ordem 2: Linhas 11✶
110
111
✶ 11
✶ 10 01✶
010
011
1✶ 0
1✶ 1
0✶ 0
0✶ 1 10✶
100
101
✶ 00
000
✶ 01 00✶
001
Representação Geométrica Schemata de Ordem 1: Planos 110
111
✶ 1✶ 010
011 1✶ ✶
✶✶ 0
✶ ✶1 0✶ ✶
100
101
✶ 0✶ 001
000
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 0 0 1 1
10 11 10 11
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
Sch ema 0 00 0 01 00 * 0 10 0 11 01 * 0* 0 0* 1 0 ** 1 00 1 01 10 * 1 10 1 11 11 * 1* 0 1* 1 1 ** *0 0 *0 1 * 0* *1 0 *1 1 * 1* * *0 * *1 ***
I ndi ví du os 0 00 0 01 0 00 0 10 0 11 0 10 0 00 0 01 0 00 1 00 1 01 1 00 1 10 1 11 1 10 1 00 1 01 1 00 0 00 0 01 0 00 0 10 0 11 0 10 0 00 0 01 0 00
0 01
0 0 0 0
11 10 11 01
0 10
0 11
1 10
1 11
1 00
1 01
1 1 1 0
1 1 1 0
1 01
1 1 1 1 1 1 0 1 1 0 0 0 0
11 10 11 01 00 01 01 10 11 11 10 11 01
10 00 01 10
11 10 11 11
1 00
10 1
11 0
11 1
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: 0 10 ✴1 0 0✴0 01✴ 0✴✴ ✴1 ✴ ✴ ✴0 ✴✴✴
Porque utilizar schema schema? ? ●
Porque considerar (K+1) L ao invés de considerar apenas K L indivíduos?
●
John Holland procurou mostrar com schemata, 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 2 L schemata, há entre 2 L e n.2 L schemata, dependendo da diversidade da população. J. Holland mostrou que o número de schemata processados a cada geração é proporcional a n3
●
●
●
●
Paralelismo Implícito ➨ um GA processa n3 schemata em paralelo, enquanto avalia n indivíduos.
Teorema Fundamental de GA Schemata permitem analizar o efeito global da reprodução e dos operadores genéticos. ●
Efeito da Seleção
●
Efeito do Crossover
●
Efeito da Mutação
Efeito da Seleção ●
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.
●
Então, o número esperado de representantes de H no ciclo seguinte (t+1) é: i∈ H
m(H, t+1) = n . ∑
i∈ H
m(H, t+1) = n . ∑ ●
n
fi / ∑ fj
n
fi / ∑ fj
Definindo a aptidão média do schema H, como i∈ H
f(H) = ∑
fi / m(H,t)
então, n
m(H, t+1) = m(H, t) . n . 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.
Taxa de Evolução ●
Supondo H acima da média de um fator constante C estacionário, a partir de t=0: C.f médio) / fm édio m(H, t+1) = m(H, t) . (f (fm édio + C.f 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.
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
sobrev iv erá e será transmitido a um dos descendentes.
Probabilidade de Destruição pd = δ(H) / (L (L--1) ●
A probabilidade de sobrevivência de H é, (L--1) ps = 1 - δ(H) / (L
●
Então, considerando a probabilidade do crossover e a recuperação de H após o crossover temos, ps ≥ 1 - p c .δ(H) / (L (L--1)
●
Portanto,
m(H, t+1) ≥ m(H, t) . f(H) / fmédio [1 - pc .δ(H) / (L (L--1)]
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) (1
●
Sabendo que pm « 1, então (1-- pm)O(H) ≈ 1 - O(H) . pm (1
Teorema Fundamental de GA m(H, t+1) ≥ m(H, t).f(H) / fmédio [1 [1-- pc .δ(H) / (L (L--1)].[ 1)].[1 1O(H).p O(H). pm ] “Schemata curtos, de baixa ordem e com alta aptidão tendem a proliferar nas gerações sucessivas, a uma taxa exponencial.”
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.
Processando Schemata Número
1 2 3 4
P opulaç ão I nic ial
0 1 0 1
1 1 1 0
1 0 0 0
0 0 0 1
1 0 0 1
x Inteiro
f(x) x2
13 24 8 19
169 576 64 361
0,14 0,49 0,05 0,31
0, 58 1, 97 0, 22 1, 23
1 2 0 1
1170 293 576
1,00 0,25 0,49
4, 00 1 1, 97
4 1 2
S oma Média Máx imo
P rob. Número Result . Pares de Geni tores e S el eç ão Des cen. Roleta Pont os de Corte
0 1 1 1
1 1 1 0
1 0 | |
0 0 0 0
| | 0 1
1 0 0 1
Nova População
0 1 1 1
1 1 1 0
1 0 0 0
0 0 1 0
0 1 1 0
x Inteiro
f(x ) x2
12 25 27 16
144 625 729 256 1754 439 729
P roc es sament o de Sc hemata Após Seleção c om p(H) O(H) Repres . H1 H2 H3
1 * 1
* 1 *
* 0 *
* * *
* * 0
0 1 4
1 2 2
2, 4 2, 3 2
i∈H
=∑
Após Cros sover
f(H)
m(H,t +1)
real
469 320 576
3,2 2, 18 1, 97
3 2 2
f i / m(H,t)
Repres. m(Ht +1) 2,3,4 2,3 2,3
3, 2 1,64 0
real
Repres.
3 2 1
2,3,4 2,3 4
= m(H, t) . f(H) / f médio[1 -p c .δ(H) / (L1)]
= m(H, t) . f(H)/ f médio
Processando Schemata Número
1 2 3 4
P opulaç ão I nic ial
0 1 0 1
1 1 1 0
1 0 0 0
0 0 0 1
1 0 0 1
x Inteiro
f(x) x2
13 24 8 19
169 576 64 361
0,14 0,49 0,05 0,31
0, 58 1, 97 0, 22 1, 23
1 2 0 1
1170 293 576
1,00 0,25 0,49
4, 00 1 1, 97
4 1 2
S oma Média Máx imo
P rob. Número Result . Pares de Geni tores e S el eç ão Des cen. Roleta Pont os de Corte
0 1 1 1
1 1 1 0
1 0 | |
0 0 0 0
| | 0 1
1 0 0 1
Nova População
0 1 1 1
1 1 1 0
1 0 0 0
0 0 1 0
0 1 1 0
x Inteiro
f(x ) x2
12 25 27 16
144 625 729 256 1754 439 729
P roc es sament o de Sc hemata Após Seleção c om p(H) O(H) Repres . H1 H2 H3
1 * 1
* 1 *
* 0 *
* * *
* * 0
0 1 4
1 2 2
2, 4 2, 3 2
Após Cros sover
f(H)
m(H,t +1)
real
469 320 576
3,2 2, 18 1, 97
3 2 2
i∈H
=∑
fi / m(H,t)
= m(H, t) . f(H)/ fmédio
Repres. m(Ht +1) 2,3,4 2,3 2,3
3, 2 1,64 0
real
Repres.
3 2 1
2,3,4 2,3 4
= m(H, t) . f(H) / fmédio [1 - pc .δ(H) / (L-1)]
Planilha Fundamentos de GA Núm 1 2 3 4 5 6 7 8 9 10
P opulaç ão Ini cial 1 1 1 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 10
S oma Média Máx imo
x i nt eiro f(x ) = 28 28 30 29 30 30 30 30 23 28 286 28,6 30
x^2 784 784 900 841 900 900 900 900 529 784
Prob. Seleç ão 0,0953539 0,0953539 0,1094624 0,1022865 0,1094624 0,1094624 0,1094624 0,1094624 0,0643396 0,0953539
Núm. Ex ecução Desc ende A ut omát ic a 0, 953539 0, 953539 Seleção 1, 094624 1, 022865 Crossover 1, 094624 Mu tação 1, 094624 1, 094624 1, 094624 0, 643396 Exec utar 0, 953539
8222 1 10 822,2 0,1 1 900 0,1094624 1, 094624
Configurações População 10 (até 10) Cros sover 0,6 (0 a 1) Mut ação 0, 08 (0 a 1) Geraç ões 20
Gerar Pop ulação No va Ge ração Evo lu ri Geraç ões
Result . Pares de Genitores Rolet a P ontos de Cort e 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
H1 H2 H3 H4 H5
1 * 1
comp(H) * * 0
O(H) 0 1 4 4 4
1 2 2 0 0
m(H,t +1) Repres ent a f(H) 822,2 10, 0000001 10 {1,2,3,4, 0 {} 0 0 856,5 8,33373875 8 {1,2, 3, 5, 6 0 {} 0 0 0 {} 0 0
Real Representant es 10 {1,2,3, 4, 5, 6, 7,8,9,10} 0 {} 10 {1,2,3, 4, 5, 6, 7,8,9,10} 0 {} 0 {}
Efeito da Cardinalidade x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Espa ço Cardi nalida de Sche mata
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
0 0 0 0 0 0 0 0 0 0
5 5 2 2 1 1 5 5 5 5
P roces sament o de Sc hem
Após S eleç ão S chemat a * * * 1 0 * * * *
e
Nã o Bi ná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 16 16 17
Aptidão 0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225
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.
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
Desempenho de Algoritmos Genéticos ●
Temas relacionados: Convergência – – – –
●
Decepção Epistasia Multimodalidade Ruído
Medidas de Convergência – Medidas de Monitoração – Medidas de Previsão
●
Algoritmos Alternativos – Algoritmos Messy
Convergência Como caracterizar o sucesso ou insucesso de um GA? ● GAs não garantem a convergência para um ponto ótimo em problemas de otimização. ● GAs podem encontrar soluções sub-ótimas em espaço complexos que satisfaçam as expectativas. ● Convergência é fortemente influenciada pela modelagem: representação, decodificação, avaliação, operadores, técnicas e parâmetros. ● Outros fatores que afetam a convergência: – Decepção – Epistasia
Decepção ●
●
● ●
Ocorre quando, em uma função, o ponto ótimo está cercado pelos piores pontos. Os blocos construtores são desorientados, devido à função ou código usados, e há dificuldade de se encontrar boas soluções (longo tempo). Por definição: Decepção ocorre quando os melhores schemata de ordem k não instanciam o ponto ótimo. Problemas artificiais são criados para avaliar o desempenho de GAs.
Problema Mínimo de Decepção (PMD) ●
Problema que viola a hipótese dos blocos contrutores: – existem schemata curtos, de baixa ordem e com alta aptidão que levam a schemata incorretos de mais alta ordem.
●
Two-bit Problem – Criado por Goldberg (1987) para avaliar o desempenho de GAs 11 é o ponto ótimo, então f(11) > f(10) ; f(11) > f(01) e f(11) > f(00)
●
Para não haver decepção em competição de schemata de ordem 1 devemos satisfazer às duas condições: 1) f(1*) ≥ f(0*) e 2) f(*1) ≥ f(*0) isto é, melhores schemata de ordem K=1 instanciam o ótimo
Problema Mínimo de Decepção (PMD) ●
Decepção ocorre se um das relações não se verificar. Exemplo: 1) f(0*) > f(1*) ➨ f(00) + f(01) > f(10) + f(11) 2
2
2) f(*0) > f(*1) ➨ f(00) + f(10) > f(01) + f(11) 2
2
●
As duas expressões não podem se verificar simultaneamente no PMD (senão 11 não será o ponto ótimo).
●
Escolhemos a condição 1)
Problema Mínimo de Decepção (PMD) ●
Considerando todos valores positivos temos: f(00) + f(01) > f(10) + f(11) ➨ f(01) - f(10) > f(11) - f(00)
●
Como f(11) - f(00) > 0
●
➨
f(01) - f(10) > 0
➨
f(01) > f(10)
➨
f(00) > f(10)
Analogamente f(00) - f(10) > f(11) - f(01)
●
Como f(11) - f(01) > 0
●
➨
f(00) - f(10) > 0
Resta saber a relação entre f(00) e f(01): – Tipo I: f(01) > f(00) – Tipo II: f(00) > f(01)
➨ f(11)>f(01)>f(00)>f(10) ➨ f(11)>f(00)>f(01)>f(10)
Representação Gráfica do PMD Tipo II
Aptidão
Aptidão
Tipo I
Atrator Decepcionante
01
01
11 00
11 00
10
10
Num GA, c om a mes ma proporção dos pontos na populaç ão inicial, o GA converge para para 11
Num GA, s e a proporção do ponto 00 é maior na populaç ão inicial, o GA converge para para 00
Epistasia ●
● ● ●
●
Biologia: Interação funcional de genes: quando um gene não responsável por uma característica influencia o resultado desta característica, diz-se que os genes são epistáticos. Em GAs: quando há interdependência entre genes. Desse modo, schemata de menor ordem não contém toda informação significativa. Schema significativo precisa representar também genes dependentes. Construção de blocos deve partir de schemata de maior ordem.
Multimodalidade ●
A e xistência de vários ótimos locais promove a ocorrência de atratores que afastam a convergência do ponto ótimo. Exemplo: F6(x,y) 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0
Ruído ●
Representações Ruidosas: – quando é impossível representar de maneira exata o objeto desejado.
●
Funções Ruidosas: – quando a função de avaliação retorna diferentes avaliações para o mesmo cromossoma.
●
Exemplo: Pcross, Pmut, GAP
GA1 Otimiz a Parâm etros do GA2
GA2 Best, média
Medidas de Convergência ●
Medidas de Monitoração – procuram acompanhar o comportamento da população ao longo da execução do GA. • On-line • Off-line • Best-so-far • Proporção dos Valores dos alelos
●
Medidas de Previsão – estimar o grau esperado de dificuldade de um problema para o GA realizar a convergência a um ponto ótimo . • FDC (Fitness Distance Correlation) – avaliação dos pontos aumenta a medida que estes se aproximam do ponto ótimo.
On-- line e Off On Off--line A medida On-line premia a rápida obtenção de boas soluções ● A medida Off-line premia melhores soluções, independente do tempo necessário para encontrá-las.( De Jong) ●
T
medida (t) = 1 ∑ f * (t) T – On-line: f * e (t) = valor da função dos indivíduos. – Off-line: f * e (t) = valor da função dos melhores indivíduos. ●
Em aplicações executadas “OFF-LINE”, o número total de avaliações do GA não é tão importante quanto para as aplicações que são executadas “ON-LINE”.
Exemplo ●
Sejam 5 indivíduos criados em 5 passos até o momento: {17, 21, 13, 28, 22}
●
A medida On-line(t) é a média das avaliações de todos os indivíduos avaliados até o passo de avaliação t. On-line(t=3) = (17+21+13)/3=17 On-line(t=4) = (17+21+13+28)/4=19,75 On-line(t=5) = (17+21+13+28+22)/5=20,2
●
A medida Off-line(t) é o valor médio das avaliações dos melhores indivíduos encontrados a cada passo de avaliação até o passo t. Off-line(t=3) = (17+21+21)/3=19,66 Off-line(t=4) = (17+21+21+28)/4=21,75 Off-line(t=5) = (17+21+21+28+28)/5=23
Proporção dos Valores dos Alelos ●
Um gene converge quando o seu alelo é o mesmo para, pelo menos, 95% da população. (De Jong)
●
A convergência do GA ocorre quando todos os genes da representação superam a taxa de 95%.
●
A proporção de alelos permite avaliar o grau de convergência de um GA ao longo da execução e ser usada como critério de parada.
FDC (Fitness (Fitness Distance Correlation)) Correlation ●
● ● ● ●
Calcula a correlação entre Aptidão e Distância (ao ponto ótimo global) para os pontos do espaço de busca de um problema. FDC = cov (F,D)/ σ(F) . σ(D) FDC =1/n 1/n [∑ [∑ (fi - fav ) (d (di - d av )] / σ(F) . σ(D) Correlação é a covariância normalizada entre -1 e 1 FDC próximo a -1 indica que a avaliação dos pontos aumenta a medida que estes se aproximam do ponto ótimo.
Algoritmos Alternativos ●
●
Algoritmos que buscam melhor desempenho (convergência) através de métodos não convencionais em algoritmos genéticos. Algoritmo Messy (Goldberg) – Idealizado de modo a relaxar a rigidez posicional da representação tradicional. – Aumenta as chances de aproximar genes interdependentes que estão inicialmente distantes. – Adequado para problemas epistáticos.
Algoritmo Messy ●
Representação: – cada gene é representado por 2 valores: (locus, alelo). Ex: Cromossoma [0 1 0 0 1 1] é representado por [ (1 0) (2 1) (3 0) (4 0) (5 1) (6 1) ]
●
Operadores: – Cut: escolhe o ponto de corte e corta cromossomas [ (1 0) (2 1) (3 0) (4 0) ] [ (5 1) (6 1) ] – Splice: concatena os cromossomas [ (1 0) (2 1) (3 0) (4 0) (5 1) (6 1) ] – A aplicação do Splice não é vinculada a realização do Cut.
Messy ●
Consequências: – Independência posicional dos genes – Sobre-especificação: mais de um gene com o mesmo locus – Sub-especificação: determinado locus não está representado
●
Exemplo:
●
Operador Cut:
●
Operador Slice:
[ (1 0) (4 0) (3 1) (5 0) (2 1) ]
e
[ (2 0) (1 1) (3 0) (5 1) (4 1) ]
[ (1 0) (4 0) (3 1) ] [ (5 0) (2 1) ] e [ (2 0) (1 1) (3 0) (5 1) ] [ (4 1) ] [ (1 0) (4 0) (3 1) (2 0) (1 1) (3 0) (5 1) ] [ (5 0) (2 1) (4 1) ]
➨ sobre-especificado ➨ sub-especificado
Computação Evolucionária em Machine Learning Programas capazes de construir novo conhecimento ou de aperfeiçoar conhecimento existente, usando informação de entrada. Ambiente do Problema Informação Novo Conhecimento
Aprendizado por Computador
•Aplicações: •Jogos •Robótica •Biologia e Medicina •Engenharia •Ciências Sociais
Dilema dos Prisioneiros l
l l
l l
Algoritmo Genético é usado para “aprender” uma estratégia para um jogo. INDIVÍDUO ≡ estratégia de jogo, regra de comportamento APTIDÃO ≡ função da interação com outros jogadores (pontuação) AMBIENTE ≡ interativo entre indivíduos coevolventes Problema é usado para estudar fatores associados com a evolução de cooperação e agressão em comunidades sociais.(Merrill Flood & Melvin Dresher 1950s)
Dilema dos Prisioneiros l
Dois suspeitos de terem cometido um crime estão em celas separadas e a polícia propõe um acordo. O que pode acontecer?
l
Os prisioneiros têm duas opções: – Delatar : fazer um acordo com a polícia e delatar o parceiro – Cooperar : manter silêncio sobre o delito e cooperar com o parceiro O que pode acontecer ?
l
– Nenhum aceita trair – Apenas um trai – Ambos traem
Recompensa = Máximo - Penalidade l
l
l
Nenhum aceita trair: – ambos cooperam e recebem pequena punição (2 anos) por falta de provas; Recompensa intermediária= (5-2) =3 Apenas um trai: – o traidor é libertado (0 anos); o outro é punido (5 anos) ; recompensa por trair é uma Tentação=(5-0) =5; recompensa do ingênuo (Sucker) baixa= (5-5)=0. Ambos traem: – punição intermediária (Punishment) para ambos (4 anos) =(5-4)=1
Tabela de Recompensas Jogador B
C
Jogador B
C
D
(γ1, γ1)
(γ2, γ3)
Jogador A
C
D
C
(3, 3)
(0, 5)
D
(5, 0)
(1, 1)
Jogador A
D
(γ3, γ2)
(γ4, γ4)
D = Delatar
D = Delatar
C = Cooperar
C = Cooperar
Restrições:
γ3> γ1> γ4> γ2 è delatar é mais atraente do que cooperar porém, 2 γ1> γ2
+ γ3 è cooperar aumenta a recompensa de ambos a longo prazo
γ2 + γ3 > 2 γ4 è se ambos sempre delatam o resultado é ainda pior
Características do DP l l l l
jogo não cooperativo para 2 jogadores pode ser disputado em torneio entre vários jogadores Axelrod promoveu 2 torneios mundiais de estratégias p/ DP Estratégia vencedora: Tit_for_Tat (Anatol Rapoport) – coopera na primeira jogada e depois repete a titude do oponente na jogada anterior. – “Coopera no primeiro encontro e a seguir retribui na mesma moeda”
l
Axelrod usou Algoritmos Genéticos para evoluir novas estratégias; as 8 melhores estratégias (humanas) dos torneios serviram para avaliar os indivíduos (ambiente de avaliação estático).
Modelagem do GA l
Indivíduo (Estratégia) – um indivíduo do GA representa uma estratégia de um jogador cuja atitude é função dos 3 últimos resultados (história).
l
Representação – Ao final de cada jogada podemos ter 4 possibilidades: • Os dois jogadores delataram: DD 11 Punishment • Apenas o jogador A delatou: DC 10 Temptation • Apenas o jogador B delatou: CD 01 Sucker • Nenhum jogador delatou: CC 00 Reward – Nas últimas 3 jogadas há: 4 x 4 x 4= 64 histórias diferentes – Cromossoma possui 64 bits: 1 ou 0 (D ou C) – Cada bit define a atitude do jogador para cada uma das 64 histórias – Posição do bit identifica a história
Representação Posição História Base 2 Base 4 String Decisão
l l l
0 CCCCCC 000000 RRR 0 C coopera
1 DCCCCC 100000 TRR 1 D delata
2 CDCCCC 010000 SRR 1 D delata
...... ...... ...... ...... ...... ...... ......
63 6 bits DDDDDD 111111 PPP 1 010000 D delata (SRR)4 = 2
Posição no cromossoma corresponde a uma história. Conteúdo de cada posição corresponde à atitude do jogador. Símbolos da base 4 correspondem às iniciais da tabela de recompensa (Reward, Temptation, Sucker e Punishment). – R=0, T=1, S=2, P=3 – Exemplo: (RST)4= Rx40 + Sx41 + Tx42 = 000110 = 24
Representação l
Para fazer a estratégia funcionar no início do jogo, são adicionados 6 bits correspondentes a 3 partidas hipotéticas.
Posição História Base 2 Base 4 String Decisão
0 CCCCCC 000000 RRR 0 C coopera
1 DCCCCC 100000 TRR 1 D delata
2 CDCCCC 010000 SRR 1 D delata
...... ...... ...... ...... ...... ...... ......
63 6 bits DDDDDD 111111 PPP 1 010000 D delata (SRR)4 = 2
•Atitude na primeira jogada = D. •Na 2ª e 3ª jogadas utiliza-se parte dos 6 bits e os resultados reais.
Modelagem do GA l
Avaliação – cada indivíduo (estratégia) da população joga com cada um dos 8 oponentes um torneio de 151 partidas m Ai = ∑ pi,j / m pi,j : pontos do jogador i na partida j m: total de partidas contra todos oponentes
l
Operadores Genéticos – crossover e mutação sobre binários
l
Seleção – avaliação na média – avaliação acima da média – avaliação abaixo da média
è 1 cruzamento è 2 cruzamentos è 0 cruzamentos
Resultados l
l l l
l
Indivíduos evoluiram regras de comportamento a partir da interação com outros indivíduos. 40 rodadas de 50 gerações de 20 indivíduos. O GA evoluiu estratégias que venceram Tit-for-Tat. Cromossomas de aptidão média eram tão bons quanto as melhores heurísticas. Características das estratégias: – traem no 1° e no 2° movimentos; – sabem pedir desculpas e entrar em cooperação; – têm comportamento diferenciado para indivíduos traidores e nãotraidores
Padrões encontrados l l
Maioria dos indivíduos apresentava os seguintes padrões: C após (CC) (CC) (CC) – “Não deixei o barco virar, continue cooperando”.
l
D após (CC) (CC) (CD) – “Aceite a provocação, traia depois que outro traiu por nada”.
l
C após (CD) (DC) (CC) – “Aceite as desculpas, coopere após cooperação ser restabelecida”.
l
C após (DC) (CC) (CC) – “Coopere quando cooperação mútua é restabelecida depois de uma agressão”.
l
D após (DD) (DD) (DD) – “Aceite a provocação, traia após três agressões”.
Segundo GA l
l
l
l
Axelrod desenvolveu um segundo experimento, permitindo que os indivíduos jogassem uns contra os outros e contra si mesmos (ambiente de avaliação dinâmico). Nas primeiras gerações, estratégias cooperativas não encontravam reciprocidade e tendiam a desaparecer. Após 10 a 20 gerações, o panorama se revertia: GA encontrava estratégias de cooperação recíproca, que puniam traição. Essas estratégias não foram derrotadas pelas menos cooperativas e conseguiram proliferar nas gerações seguintes.