UMA INTRODUÇÃO AOS
ALGORITMOS GENETICOS
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Uma visão geral dos GAs
Um algoritmo genético é uma classe de algoritmo de
busca. O algoritmo procura uma solução dentro de um
espaço para um problema de otimização.
A principal característica dos GAs é como esta busca pela
solução ótima é feita:
O algoritmo cria uma “população” de possíveis soluções
para o problema e a deixa “evoluir” por várias gerações
para encontrar melhores e melhores soluções.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Uma visão geral dos GAs
1. Cria uma população aleatória de candidatos a solução (pop).
2. Em quanto as condições de terminação não são satisfeitas: (cada iteração e geração):
(a) Cria uma nova população vazia (new-pop).
(b) Em quanto new-pop não estiver completa:
i. Selecione dois indivíduos aleatoriamente de pop ( dando
preferência na seleção aos indivíduos mais fit) .
ii. Cross-over os dois indivíduos para obter dois novos indivíduos.
(c) Dá a cada membro de new-pop a chance de mutate.
(d) Substitui pop com new-pop.
3. Seleciona o individuo da população com a melhor fitness como a solução do
problema.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Uma visão geral dos GAs
Inicializar
a população
Iniciar
nova geração
Calcular adequação
dos crom osom os
Selecionar pais
usando adecualçao
G erar a
ninhada
M utar a
ninhada
R estaurar o
tam anho da pop.
Solução
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
População
A população é a coleção de candidatos a soluções que se
estão considerando durante o uso do algoritmo. Pelas
gerações do algoritmo, novos membros “nascem” na
população em quanto outros “morrem” (saem da
população).
Uma simple solução na população é referenciada como um
individuo. A adaptação (fitness) de um individuo é uma
medida quam “boa” a solução representada pelo individuo
é. Quanto melhor a solução, maior será a sua adaptação. É
claro que isto depende do problema a ser resolvido.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Seleção
O processo de seleção é análogo à sobrevivência dos
mais adaptados no mundo natural. Indivíduos são
selecionados para “procriação” (cross-over)
baseados no valor da sua adaptação (fitness) –
quanto mais adaptado o individuo, maior será a
chance deste individuo seja escolhido para
reprodução. O cross-over ocorre pela mistura de duas
soluções (indivíduos) para crias dois novos indivíduos.
Durante cada geração, existe uma pequena chance de
que um individuo sofra uma mutação, que vai a
mudar o individuo levemente.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Questões
• Como um indivíduo é representado?
• Como a adaptação de um indivíduo é calculada?
• Como os indivíduos são selecionados para pro-criação?
• Como os indivíduos são “crossed-over”?
• Como os indivíduos são mutados?
• Qual o tamanho da população?
• Quais são as condições de terminar o processo?
A resposta as questões dependem do problema especifico.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Tamanho da População
O tamanho da população é muito variável. Quanto maior
seja a população, temos maior quantidade de soluções
possíveis, que significa maior variação da população.
Variações significa que é mais provável que melhores
soluções sejam criadas.
Então, a população deve ser a maior possível. O limite é o
tempo que vai a demorar o algoritmo em ser executado.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Terminação do Algoritmo
O significado de “Em quanto as condições de terminação
não são satisfeitas” não é obvio no caso dos GAs. O
motivo é que não existe fim para o algoritmo.
• A abordagem mais simples é rodar o algoritmo de
busca por um determinado número de gerações –
mais gerações geralmente é melhor.
• Outra abordagem é terminar o algoritmo se depois
de passadas algumas gerações não se obtém uma
melhora na adaptação do melhor individuo da
população.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Exemplo: Maximização de funções
Uma aplicação comum dos GAs é obter valores para um grupo
de variáveis que maximizem/minimizem funções destas
vadeáveis. Estas variáveis pelas sua vez podem estar sujeitas
as restrições:
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Exemplo: Maximização de funções
Como um indivíduo é representado?
Temos que ter valores para w, x, y e z. Se temos valores (qualquer
valor) para as variáveis, temos um candidato a solução do problema.
O problema é como representar estas 4 valores. Uma forma muito
simples é usar um vetor de 4 valores ( inteiros ou reais).
Sem embargo, para GAs é geralmente melhor ter grandes
indivíduos–de esta forma, as variações podem ser feitas de uma
forma mais suave.
Podemos escolher uma cadeia de bits para cada variável, e
concatenar as 4 cadeias formando uma única cadeia de bits
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Como é calculado a adaptação
Existe uma diferencia entre as funções de adaptação
(fitness) e avaliação (evaluation) .
As funções de avaliação retorna uma medida absoluta do
individuo.
As funções de adaptação mede o valor do individuo relativo
ao resto da população.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Como são selecionados os Pais?
A chave do processo de seleção é que deve ser
probabilisticamente tal de que indivíduos com maior
adaptação (fitness) tenham maior probabilidade de
serem escolhidos.
Uma possibilidade é ordenar os elementos segundo a
ordem decrescente da função de adaptação. Depois
calcular a probabilidade de de seleção dos indivíduos
em função desta ordem: O primeiro individuo tem
por exemplo 70% de chances de ser escolhido, o
segundo 40 etc.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Como os indivíduos são
cruzados?
Uma vez que encolhemos um par de indivíduos, eles são
“procriados” – ou em linguagem de GAs eles são crossed-over.
Tipicamente dois filhos são criados para cada conjunto de pais.
Um método de realizar o cross-over é o seguinte:
Duas locações são escolhidas aleatoriamente dentro dos
indivíduos. Estas definem os correspondentes substrings em
cada individuo. Os substrings são intercambiados entre os dois
indivíduos pais e formam os dos novos filhos.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Como os indivíduos mutados?
Finalmente, temos que permitir que os indivíduos
mutem. Quando os indivíduos são codificados usando
cadeias de bits, a forma mais fácil de implementar a
mutação é permitir que cada um dos bits da cadeia
tenham a chance de mutar. Esta chance deve ser muito
pequena já que não queremos que os indivíduos
cambiem radicalmente devido a mutações. (ver
problemas com o MSB). Colocando uma porcentagem
de 0,1% é razoável..
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Problema do Caixeiro viajante
GAs podem ser usados para resolver o problema do
Caixeiro viajante (traveling salesman problem (TSP)).
Um caixeiro tem que atender várias cidades incluindo a sua.
Tem que viajar partindo da sua, visitando todas as outras
cidades (uma única vez) e retornar a sua. Ele quer realizar a
viajem gastando a menor quantidade possível de
dinheiro/gasolina etc.
Uma proposta mais formal: dado um grafo de N-vertices,
encontrar o caminho de menor custo, partindo de uma
cidade v that visitando as outras cidades exatamente uma
vez e retornado a v.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Representação dos indivíduos e
Fitness
Nosso primeiro passo é decidir como representar cada
individuo candidato a solução, ou tour.
O modelo de cadeia de bits não é muito útil. Os cross-overs
e mutações podem facilmente produzir um tour que é
inválido– Cada cidade dever ser visitada uma vez no
tour(fora a cidade inicial).
A forma prática de de representar os indivíduos é um vetor
de cidades (armazenadas como números inteiros) . O custo
de viajar entre cidades deve ser dado na forma de matriz. O
uso de um vetor de inteiros produz problemas no cross-over
e nas mutações
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Cross-over e Mutação
Cross-over e mutações devem produzir tours válidos.
Então estes processos devem ser modificados em
relação ao caso de procurar extremos de funções.
Mais a idéia básica pode continuar a mesma,.
A mecânica deve ser diferente: Para cross-over, ao in
vez de simplesmente trocar sub-cadeias (que pode
resultar em um tour inválido), manteremos as
mesmas cidades, mais mudaremos a sua ordem,
para ajustar o outro pai de cross-over.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Resumo
GAs são muito úteis. Especialmente quando os
problemas não podem ser resolvidos por métodos
tradicionais.
São interessantes, porque não obvio que eles
funcionem, mais funcionam.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Bibliografia
•Scott M. Thede - Introduction to genetic
algorithms
•J.H. Holland - Adaptation in Natural and
Artificial Systems, MIT Press, 1975.
•Stuart Russell and Peter Norvig - Artificial
Intelligence: A Modern Approach, Second
Edition, Prentice Hall, 2003.
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121
Engenheiros
Computação Evolutiva e Engenharia do
Conhecimento (EGC6011)
Como estou lecionando?
Ligue 0xx48-331-7121