Algoritmos Genéticos
Adriano Joaquim de O Cruz
©2003
NCE/UFRJ
[email protected]
Sumário




Introdução
Aplicações
Operadores
Exemplos
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 2
Algoritmos Genéticos

Nas minhas investigações debaixo do
sol, vi ainda que a corrida não é para
os ágeis, nem a batalha para os
bravos, nem o pão para os prudentes,
nem a riqueza para os inteligentes,
nem o favor para os sábios: todos
estão à mercê das circunstâncias e da
sorte.
Eclesiastes 9,12
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 3
O Problema?




Existem problemas para os quais algoritmos
rápidos de solução não são conhecidos.
Encontrar a solução é buscar em um espaço
onde vivem potenciais soluções a que melhor
resolve o nosso problema.
Quando este espaço é muito grande encontrar
a melhor solução pode levar tempo demais
É possível obter soluções aproximadamente
ótimas usando algoritmos probabilísticos.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 4
Algoritmos Genéticos



Técnica prática e robusta de busca e
otimização
Baseados nos conceitos da seleção
natural
É um método
estocástico de busca
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 5
Exemplos de problemas



Encontrar o máximo (mínimo) de uma
função.
Encontrar um bom conjunto de regras
para um sistema nebuloso.
Encontrar o melhor agente para atuar
como jogador digital.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 6
A Metáfora


A metáfora que está por trás dos AGs é
a da seleção natural.
Na natureza, o problema de cada
espécie é o de encontrar as melhores
adaptações que a façam sobreviver em
um ambiente complicado, muitas vezes
hostil e que está sempre mudando.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 7
Evolução?


Há na natureza evolução no sentido de
melhoria?
Evolução pressupõe caminhar em
direção a um indivíduo ideal.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 8
Adaptação?

Não seria mais apropriado
falar em melhor adaptação
ao ambiente

@2002 Adriano Cruz
Na natureza sobrevivem
não os mais evoluídos e
sim os mais adaptados a
um determinado ambiente.
NCE e IM - UFRJ
Algoritmos Genéticos 9
Adaptação

O conjunto de características de um
indivíduo, que o distingue dos demais,
determina sua capacidade de
sobrevivência.

Estas características são determinadas
pelo seu material genético.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 10
Mecanismos



Na natureza a competição por recursos
escassos faz com que os mais aptos
sobrevivam e consigam se reproduzir.
Através da reprodução com parceiros os
genes destes indivíduos são então
transmitidos aos seus descendentes.
Este processo contínuo de seleção e
reprodução dos mais aptos pode conduzir a
indivíduos cada vez mais adaptados.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 11
Termos e Definições
Cromossomo



Usualmente, cada possível solução é
codificada como uma cadeia de bits, o
cromossomo ou genótipo.
Cada parametro codificado na solução
é chamado de um gene.
F(x,y,z)
Gene x
@2002 Adriano Cruz
Gene y
NCE e IM - UFRJ
Gene z
Algoritmos Genéticos 13
População


AGs mantém um conjunto de indivíduos
formando populações de soluções.
Indivíduos devem ser avaliados
segundo uma função de aptidão.
 Indivíduos
mais aptos
terão mais chances de
propagar sua
informação genética.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 14
Gerações



A cada geração o AG cria uma nova
população.
Esta criação de indivíduos é baseada
em operadores genéticos.
A evolução de uma geração para outra
é feita em três fases: avaliação da
aptidão, seleção dos mais aptos e
reprodução.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 15
Fluxo do AG
Início
Aleatoriamente
Gera
População
Inicial
Geração
Atual
Mutação
Avalia
Seleciona
Pais
Gera
Filhos
Próxima
Geração
Cruzamento
OK?
Não
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 16
Codificação de Soluções




A codificação transforma pontos no
espaço de soluções em cadeias de bits.
Codificações são maneiras de traduzir
o conhecimento sobre o problema para
o ambiente dos AGs.
Considere f(x,y,z) e que x=3, y=1, z=0
O cromossomo de 12 bits com genes
de 4 bits seria 001100010000
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 17
Codificação de Soluções 1




A codificação determina a resolução da
solução.
Considere uma variável codificada em
16 bits.
Considere que esta variável pode
assumir valores entre 0 e 2 inclusive.
A codificação divide o intervalo [0,2] em
216-1 pedaços.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 18
População Inicial



A população inicial é gerada
aleatoriamente.
Em algumas soluções várias
populações são criadas.
Estas populações podem evoluir
paralelamente de forma cooperativa ou
não.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 19
Avaliação da Aptidão


O primeiro passo após gerar uma
população de soluções e calcular a
aptidão de cada solução.
Em um problema de maximização de
funções esta avaliação significa
calcular o valor da função para cada
indivíduo.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 20
Seleção



Após a avaliação deve-se gerar uma
nova população a partir da atual.
A seleção escolhe que indivíduos
participarão deste processo.
A probabilidade de um indivíduo ser
selecionado é proporcional a sua
aptidão (método da roleta).
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 21
Cruzamento


Cruzamento e o operador genético
aplicado a pares selecionados de pais.
Deste cruzamento espera-se que as
boas características de prévias
gerações sejam passadas as próximas.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 22
Cruzamento 1

Cruzamentos em um ponto é o modo
mais comum.

Cruzamentos ocorrem com uma
probabilidade.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 23
Cruzamento 2


Considere os dois indivíduos abaixo,
cada um com 8 bits (7 até 0).
Considere um ponto de corte no bit 5.
Pais
Filhos
10110111
10100010
x
01100010
@2002 Adriano Cruz
x
01110111
NCE e IM - UFRJ
Algoritmos Genéticos 24
Cruzamento 3



Filhos podem ultrapassar seus pais
caso herdem as melhores
características de cada pai.
E se os indivíduos atuais não contém
os genes da solução?
Será que temos os genes para
telepatia?
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 25
Mutação




Mutação é capaz de gerar novos
cromossomos espontaneamente.
A maneira mais comum é trocar o valor de
um bit com uma probabilidade, geralmente,
igual a um valor baixo (taxa de mutação).
Evita que a população entre em estagnação.
Moradores de uma ilha no meio do oceano.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 26
Exemplo







Considere o problema de achar o
máximo da função y = sen(10*x)*sen(x)
Parâmetros:
População = 20
Gerações = 30
Probabilidade de cruzamento=1.0
Probabilidade de mutação = 0.01
Bits para codificação = 8
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 27
Função e o máximo
90
8
7
6
5
4
3
2
1
15
14
13
12
11
20
19
18
17
16
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
0
@2002 Adriano Cruz
0.5
1
1.5
NCE e IM - UFRJ
2
2.5
3
Algoritmos Genéticos 28
Evolução OK
1
Best
Average
Poorest
0.8
0.6
0.4
Fitness
0.2
0
-0.2
-0.4
-0.6
-0.8
-1
0
@2002 Adriano Cruz
5
10
15
Generations
NCE e IM - UFRJ
20
25
30
Algoritmos Genéticos 29
Função e máximo não OK
0.8
20
1
9
8
7
6
5
4
19
18
17
16
15
14
13
12
11
20
3
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
0
@2002 Adriano Cruz
0.5
1
1.5
NCE e IM - UFRJ
2
2.5
3
Algoritmos Genéticos 30
Evolução
0.8
Best
Average
Poorest
0.6
0.4
Fitness
0.2
0
-0.2
-0.4
-0.6
-0.8
-1
0
@2002 Adriano Cruz
5
10
15
Generations
NCE e IM - UFRJ
20
25
30
Algoritmos Genéticos 31
Aprendendo Estratégia




O dilema dos prisioneiros.
Dois prisioneiros em celas diferentes.
Impossível se comunicarem.
Cada um deles pode acusar o outro (A)
ou ficar calado/cooperar (C).
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 32
Punições x Prêmios
Jog 1
Jog 2
P1
P2
Comentário
Acusa
Acusa
1
1
Punição
Acusa
Coopera 5
0
Tentação
Coopera Acusa
0
5
Tentação
Coopera Copera
3
3
Prêmio
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 33
O Dilema

Cada um dos prisioneiros deve decidir
se deve cooperar com o outro
prisioneiro ou trair e procurar uma pena
menor.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 34
Como jogar?




Jogo entre dois jogadores.
Em cada jogada os jogadores decidem
o que fazer.
Pontos são atribuídos de acordo com a
tabela.
Após um certo número de jogadas, o
jogador com mais pontos vence.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 35
Representando as estratégias



Considerar estratégias determinísticas.
Considerar os resultados das três
últimas jogadas para decidir o que
fazer.
Desde que há 4 possibilidades temos
4x4x4=64 histórias diferentes.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 36
Representando as estratégias 1



64 bits indicam o que fazer para cada
uma história possível (acusar ou
cooperar)
Podemos usar seis bits para
representar as três jogadas iniciais
(imaginárias) para a primeira jogada.
Total de 70 bits.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 37
Representando as estratégias 2




Possível cromossomo: AACCA...ACC
Considerando o bit mais à direita
como a estratégia 1 (=C cooperar) e
o mais à esquerda como estratégia
70 (=A acusar).
A estratégia 3 tem como próxima
jogada A=acusar
Esta estratégia pode estar
representando a história: CC; AC; CA
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 38
Algoritmo



Escolha uma população inicial. Cada
jogador recebe uma cadeia aleatória de
bits (As e Cs), representando uma
estratégia.
Teste cada jogador para testar sua
eficácia. O resultado de cada jogador é
a média de todos os jogos.
Selecione os jogadores que irão
reproduzir
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 39
Algoritmo 1



Um jogador mediano recebe um
parceiro; um jogador acima de um
desvio padrão acima da média recebe
dois; um ruim nada.
Os jogadores são casados e usa-se
mutação.
Assim temos uma nova geração.
@2002 Adriano Cruz
NCE e IM - UFRJ
Algoritmos Genéticos 40