INF 1771 – Inteligência Artificial
Aula 04 – Algoritmos Genéticos
Edirlei Soares de Lima
<elima@inf.puc-rio.br>
Introdução
Algoritmos genéticos são bons para abordar
espaços de buscas muito grandes e navegá-
los procurando por soluções que talvez não
fossem encontradas em uma busca convencional
mesmo que ela durasse centenas de anos.
Consiste em um mecanismo de busca direcionada
baseado na evolução dos seres biológicos.
Provêem técnicas eficazes (mas não tão
eficientes) de otimização e de aprendizado de
máquina.
Teoria da Evolução
A teoria da evolução diz que na natureza todos os
indivíduos dentro de um ecossistema competem entre si
por recursos limitados (comida, água...)
Os indivíduos mais fracos de uma mesma espécie
tentem a não se proliferarem.
A descendência reduzida faz com que a probabilidade de
ter seus genes propagados ao longo de sucessivas
gerações seja menor.
A combinação entre os genes dos indivíduos que
sobrevivem pode produzir um novo indivíduo muito
melhor adaptado às características de seu meio
ambiente ao combinar características possivelmente
positivas de cada um dos seus pais.
Introdução
Todo indivíduo biológico é formado
por uma ou mais células.
Dentro de cada célula existe um
conjunto de cromossomos.
Os seres humanos têm 23 pares de
cromossomos por célula.
O número de pares varia de espécie para
espécie.
Introdução
Cada cromossomo consiste em sequências
de DNA (molécula que codifica toda a
informação necessária para o
desenvolvimento e funcionamento de
organismos vivos).
Um cromossomo consiste de genes
(blocos de sequências de DNA).
Cada gene codifica uma ou mais proteínas.
Cada gene tem uma posição própria no
cromossomo chamada locus.
Introdução
O conjunto completo de material genético (todos os
cromossomos) é chamado de genoma.
Um conjunto específico de genes no genoma é
chamado de genótipo.
O genótipo é a base do fenótipo, que é a expressão
das características físicas e mentais codificadas pelos
genes e modificadas pelo ambiente, tais como cor
dos olhos, inteligência...
A qualidade do indivíduo (fitness) é medida pelo
seu sucesso (sobrevivência)
Reprodução
Na natureza existem dois tipos de
reprodução:
Assexuada: típica de organismos inferiores, como
bactérias.
Sexuada: exige a presença de dois organismos, na
maioria das vezes de sexos opostos, que trocam
material genético.
A reprodução sexuada é a base dos
algoritmos genéticos.
Reprodução
Na reprodução sexuada
ocorre a formação de um
novo indivíduo através da
combinação de duas células
gametas.
Na formação destas
gametas, ocorre o processo
de recombinação
genética (crossing-over).
Mutação
O processo de replicação do
DNA é extremamente complexo.
Pequenos erros podem ocorrer
ao longo do tempo, gerando
mutações dentro do código
genético.
Estas mutações podem ser
boas, ruins ou neutras.
Mutação
Alguns fatores externos, como a radiação
ultravioleta, também podem causar pequenas
disrupções no código genético.
Teoria da Evolução
Indivíduos com uma melhor adequação do seu fenótipo
ao meio ambiente (melhor fitness) se reproduzem
mais.
Dessa forma têm mais chances de passar seus genes
para a próxima geração.
Entretanto, graças aos operadores genéticos
(
não são exatamente iguais aos dos pais.
recombinação e mutação) os cromossomos dos filhos
Assim, eles podem evoluir e se adaptar cada vez mais
aos meio ambiente que os cerca.
Algoritmos Evolucionários
Os algoritmos evolucionários, dos quais
os algoritmos genéticos fazem parte,
procuram se inspirar na forma como a
natureza funciona.
Os algoritmos evolucionários funcionam
mantendo uma população de estruturas
que evoluem de forma semelhante à
evolução das espécies.
Algoritmos Evolucionários
Nestas estruturas são aplicados operadores
genéticos, como a recombinação e
mutação.
Cada indivíduo recebe uma avaliação que é
uma quantificação da sua qualidade como
solução do problema em questão
Baseados nesta avaliação são aplicados
operadores genéticos de forma a simular a
sobrevivência do mais apto.
Algoritmos Evolucionários
Algoritmos evolucionários buscam (dentro
da atual população) aquelas soluções que
possuem as melhores características e
tenta combiná-las de forma a gerar soluções
ainda melhores.
O processo é repetido até que tenha se
passado tempo suficiente ou que tenhamos
obtido uma solução satisfatória para nosso
problema.
Algoritmos Evolucionários
Algoritmos evolucionários são extremamente
dependente de fatores estocásticos
(
da população quanto na fase de evolução.
probabilísticos), tanto na fase de inicialização
Isto faz com que os seus resultados raramente
sejam perfeitamente reprodutíveis.
Além disso, claramente os algoritmos
evolucionários são heurísticas que não
garantem a obtenção do melhor resultado
possível em todas as suas execuções.
Algoritmos Evolucionários
Conclusão: se você tem um algoritmo com
tempo de execução razoável para solução de um
problema, então não há nenhuma necessidade de
se usar um algoritmo evolucionário.
Sempre dê prioridade aos algoritmos
exatos.
Os algoritmos evolucionários entram em cena
para resolver aqueles problemas cujos algoritmos
exatos são extremamente lentos ou incapazes de
obter uma solução.
Algoritmos Genéticos
Algoritmos Genéticos são uma sub-área dos
Algoritmos Evolucionários. Logo, são uma metáfora
para a evolução natural.
Os algoritmos genéticos são técnicas heurísticas de
otimização global. Com isto, raramente eles ficam
presos em máximos locais.
Máximo
Global
Máximo
Local
Ponto de início
Algoritmos Genéticos
Nos algoritmos genéticos as populações de indivíduos
são criadas e submetidas a operadores genéticos.
Seleção.
Recombinação.
Mutação.
Estes operadores utilizam uma caracterização da
qualidade de cada indivíduo como solução do
problema em questão chamada de avaliação do
indivíduo (fitness).
É gerado um processo de evolução natural destes
indivíduos.
Algoritmos Genéticos
Definição de um problema em
algoritmos genéticos:
É necessário definir uma maneira de codificar os
indivíduos.
Definir os operadores genéticos que serão
utilizados.
Definir uma função de avaliação para medir a
capacidade de sobrevivência de cada indivíduo.
Algoritmos Genéticos
Processo:
1
2
3
) Inicialize a população de indivíduos.
) Avalie cada indivíduos na população.
) Selecione os melhores pais para gerar novos indivíduos. Aplique os
operadores de recombinação e mutação a estes pais de forma a gerar os
indivíduos da nova geração.
4
5
6
) Apague os velhos membros da população.
) Avalie todos os novos indivíduos e insira-os na população
) Se o tempo acabou, ou o melhor indivíduos satisfaz os requerimentos da
solução do problema, retorne-o, caso contrário volte para o passo 3.
Algoritmos Genéticos
Distribuição dos indivíduos na Geração 0
Distribuição dos indivíduos na Geração N
Algoritmos Genéticos
Para criar um algoritmo genéticos é
necessário:
Definir uma maneira de codificar a população de
indivíduos.
Definir uma função de avaliação.
Definir um método de seleção dos pais.
Definir os operadores genéticos:
Recombinação.
Mutação.
Codificação da População
A representação dos cromossomos é fundamental
para o codificação do algoritmo genético.
Consiste em uma maneira de traduzir a informação do
problema em uma maneira viável de ser tratada pelo
computador.
Cada pedaço indivisível desta representação é
chamado de um gene, por analogia aos genes que
compõem um cromossomo biológico.
Codificação da População
É importante notar que a representação
computacional dos cromossomos é
completamente arbitrária.
Cromossomos podem ser:
Strings de bits (0101 ... 1100)
Números reais (43.2 -33.1 ... 0.0 89.2)
Listas de regras (R1 R2 R3 ... R22 R23)
Qualquer estrutura de dados imaginável!
Exemplo - População
Objetivo: Encontrar o máximo da função f(x)=x2 no
intervalo [0,31].
Os indivíduos da população precisam armazenar o
valor de uma variável inteira.
Podemos codificar cada indivíduo da população
como uma sequência de 5 bits.
1
0
0 1 0 0
x=20
0 0 1 1 x=3
Função de Avaliação
A função de avaliação é a maneira
utilizada pelos algoritmos genéticos para
determinar a qualidade de um indivíduo
como solução do problema em questão.
A função de avaliação deve ser escolhida
cuidadosamente. Ela deve embutir todo o
conhecimento que se possui sobre o
problema a ser resolvido.
Exemplo - Função de Avaliação
Objetivo: Encontrar o máximo da função
2
f(x)=x no intervalo [0,31].
A função de avaliação para este caso
consiste simplesmente em converter o
número de binário para inteiro e depois
elevá-lo ao quadrado.
Indivíduos que tiverem maiores valores na
função de avaliação são os mais aptos.
Seleção dos Pais
O método de seleção de pais deve tentar simular o
mecanismo de seleção natural que atua sobre as
espécies biológicas.
Os pais mais capazes geram mais filhos, mas os menos aptos
também podem gerar descendentes.
Temos que privilegiar os indivíduos com função de
avaliação alta, sem desprezar completamente aqueles
indivíduos com função de avaliação extremamente baixa.
Isto ocorre pois até indivíduos com péssima avaliação
podem ter características genéticas que sejam favoráveis
à criação de um "super indivíduo“.
Seleção dos Pais
Método mais comum de seleção de pais:
Roleta.
Cria-se uma roleta (virtual) na qual cada
cromossomo recebe um pedaço proporcional
à sua avaliação.
Roda-se a roleta para sortear os indivíduo
que serão pais de um novo indivíduo.
Exemplo - Seleção dos Pais
Considerando a seguinte população gerada
aleatoriamente para o problema de
2
maximização de f(x)=x no intervalo [0,31]
Indivíduo Avaliação Pedaço da Pedaço da
roleta (%)
1.61
14.51
25.81
58.07
roleta (º)
5.8
52.2
92.9
209.1
360.0
0
0
0
0
0001
0011
0100
0110
1
9
16
36
62
Total
100.00
Exemplo - Seleção dos Pais
Roleta para População Exemplo
1
9
1
6
3
6
"
00001"
"00011"
"00100"
"00110"
Operadores Genéticos - Recombinação
Operador de recombinação (crossover) de
um ponto.
O processo consiste em:
(
1) Seleciona-se dois pais através processo de seleção
de pais.
(
2) Um ponto de corte (uma posição entre dois genes de
um cromossomo) é selecionado. Este ponto de corte é o
ponto de separação entre cada um dos genes que
compõem o material genético de cada pai.
(
filho e a metade à direita vai para outro.
3) A metade à esquerda do ponto de corte vai para um
Recombinação - Ponto de Corte
Cada indivíduo com n genes possui n-1 pontos de corte.
Em um indivíduo com codificação binária, cada bit é um
gene.
gene
Pontos de Corte: 1
2
3
4
Exemplo - Recombinação
Operadores Genéticos - Mutação
Depois de compostos os filhos, entra em ação o
operador de mutação.
O operador atua com base em uma probabilidade
extremamente baixa (da ordem de 5%) de alteração
aleatória do valor de um gene ou mais genes dos
filhos.
O valor da probabilidade que decide se o operador de
mutação será ou não aplicado é um dos parâmetros
do algoritmo genético que pode alterar o resultado
alcançado pelo algoritmo.
Exemplo – Mutação
Altere-se cada gene de forma independente
com base em uma probabilidade pm
p é denominada taxa de mutação e costuma
m
ser bem baixa.
Outras Técnicas
Interpolação de operadores.
Recombinação de mais pontos.
Recombinação uniforme.
Elitismo.
Operadores Genéticos
É possível aumentar ou diminuir a
incidência de cada um dos operadores
sobre a população e assim ter mais controle
sobre o desenvolvimento dos cromossomos.
Cada operador pode receber uma avaliação.
Normalmente o operador de recombinação
recebe um fitness bem maior que o operador
de mutação.
Operadores Genéticos
As porcentagem de aplicação de cada operador
não precisa ser fixa.
No início queremos executar muita reprodução e
pouca mutação, visto que há muita diversidade
genética e queremos explorar o máximo possível
nosso espaço de soluções.
Depois de um grande número de gerações, há pouca
diversidade genética na população e seria
extremamente interessante que o operador de
mutação fosse escolhido mais frequentemente.
Interpolando Operadores
Fitness
Fitness
Fitness
8
0%
8
2
0%
80%
0%
20%
2
0%
Gerações
Gerações
Gerações
Linear
Quadrática
Descontínua
Recombinação de Dois Pontos
Existem indivíduos que não podem ser gerados com a
recombinação de somente um ponto. Exemplo:
1
******1.
Consequentemente, se não mudarmos o operador de
recombinação, o algoritmo genético fica limitado na
sua capacidade de gerar um certo conjunto de
cromossomos.
Para melhorar essa capacidade é possível introduzir a
recombinação de 2 pontos.
Nele, em vez de sortearmos um só ponto de corte,
sorteamos dois.
Recombinação de n Pontos
Evoluindo a idéia da recombinação de dois
pontos, é possível tonar o operador uma
recombinação de n pontos.
Recombinação Uniforme
Para cada gene é sorteado um número zero ou um.
Se o sorteado for 1, um filho recebe o gene do primeiro pai e o
segundo filho o gene do segundo pai.
Se o sorteado for 0, o primeiro filho recebe o gene do segundo
pai e o segundo filho recebe o gene do primeiro pai.
Elitismo
A idéia básica por trás do elitismo é a
seguinte:
Os n melhores indivíduos de cada geração
não devem "morrer" junto com a sua
geração, mas sim passar para a próxima
geração para garantir que seus genomas
sejam preservado.
É uma forma de garantir que o
algoritmo nunca regrida.
Algoritmos Genéticos - Exemplo
Problema do caixeiro viajante: Deve-se
encontrar o caminho mais curto para
percorrer n cidades sem repetição.
Cada indivíduo pode ser representador por
uma lista ordenada de cidades, que indica a
ordem em que cada uma será visitada.
Exemplo: (3 5 7 2 1 6 4 8)
Algoritmos Genéticos - Exemplo
Cada cromossomo tem que conter todas as
cidades do percurso, apenas uma vez.
Considerando 8 cidades:
Cromossomos válidos: (1 2 3 4 5 6 7 8), (8 7 6
5
4 3 2 1), (1 3 5 7 2 4 6 8)...
Cromossomos inválidos: (1 5 7 8 2 3 6) - Falta a
cidade 4, (1 5 7 8 2 3 6 5) - Falta a cidade 4 e a
cidade 5 está representada 2 vezes...
Algoritmos Genéticos - Exemplo
A função de avaliação consiste em somar todas as
distâncias entre cidades consecutivas.
Exemplo:
3
0
0
1
1
00
5
4
90
8
2
50
6
5
35
2
5
3
1
0
O cromossomo (1 3 5 4 2) tem avaliação igual a 35+
80 + 50 + 65 = 230
Algoritmos Genéticos - Exemplo
Recombinação (uniforme):
Pai1 (3 5 7 2 1 6 4 8)
Pai2 (2 5 7 6 8 4 3 1)
1
) Gera-se uma string de bits aleatória do mesmo tamanho que os
pais:
1
2
0 0 1 0 1 0 1
) Copia-se para o filho 1 os elementos do pai 1 referentes àquelas
posições onde a string de bits possui um 1:
3
_ _ 2 _ 6 _ 8
3
) Elementos não copiados do pai1:
5
7 1 4
3
mesma ordem que no pai 2 e copia-se eles para dentro do Filho1:
) Permuta-se esta lista de forma que os elementos apareçam na
3
5 7 2 4 6 1 8
Algoritmos Genéticos - Exemplo
Mutação:
Individuo (3 5 7 2 1 6 4 8)
Escolhem-se dois elementos aleatórios dentro do
cromossomo e trocam-se as suas posições:
(
3 5 7 2 1 6 4 8)
Novo individuo mutante:
3 1 7 2 5 6 4 8)
(
Algoritmos Genéticos
Questões importantes na definição de
um problema em algoritmos
genéticos:
Representação dos indivíduos.
Parâmetros do sistema (tamanho da população,
taxa de mutação...).
Políticas de seleção e eliminação de indivíduos.
Operadores genéticos (recombinação e mutação)
Critérios de parada.
Função de avaliação (a mais importante e mais
complicada de ser definida).
Vantagens dos Algoritmos Genéticos
Sempre oferece uma resposta que tende a
ser melhor com o tempo.
Conforme ganhamos conhecimento sobre o
problema podemos melhorar a função de
avaliação.
Usado em diversos tipos de aplicações.