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.