TÓPICOS DE I.A.
ALGORÍTMOS GENÉTICOS
Prof. Mário Dantas
A IA USA SEMPRE ALGUMAS METÁFORAS...

Cérebro e sistema nervoso
 conexionismo

Linguagem + processos cognitivos
 IA simbólica

Teoria da evolução
 computação evolutiva (algoritmos genéticos)
2
INDAGAÇÕES DE ALGUNS SÉCULOS
ATRÁS...
Como explicar a diversidade de animais?
 Como explicar sua evolução?

Qual é a influência do dos antepassados?
 Qual é a influência do meio ambiente?

3
HISTÓRIA DA TEORIA DA EVOLUÇÃO
Teoria da evolução: de Lamarck a De Vries

1809: Jean-Baptiste Lamarck

Lei do uso e do desuso


pelo uso e desuso de suas aptidões, a natureza
força os seres a se adaptarem para
sobreviverem.
Lei dos caracteres adquiridos.

Os serem mais fortes são mais capazes de
“trasmitir” suas aptidões às novas gerações
4
HISTÓRIA DA TEORIA DA EVOLUÇÃO

1859: Charles Darwin

Existe uma diversidade de seres devido aos
contingentes da natureza (comida, clima, ...)
e é pela lei da Seleção Natural que os seres
mais adaptados ao seus ambientes
sobrevivem


Os caracteres adquiridos são herdados pelas
gerações seguintes


contra lei do uso de desuso
o homem vem do macaco...
Na época, que isto tudo foi polêmico...
5
HISTÓRIA DA TEORIA DA EVOLUÇÃO

1865: Gregor Mendel


Formalizou a “herança de características”, com a
teoria do DNA (ervilhas)
1901: Hugo De Vries
Só a seleção natural não é responsável pela produção
de novas (mais adaptadas) espécies. Tem de haver
uma mudança genética!
 Formalizou o processo de geração de diversidade:
Teoria da Mutação

6
COMPUTAÇÃO EVOLUTIVA

A Computação Evolucionária foi introduzida em
1960 por Ingo Rechenberg com seu trabalho
"Estratégias de Evolução" (Evolutions strategie
no original). Sua idéia foi então desenvolvida por
outros pesquisadores.
7
COMPUTAÇÃO EVOLUTIVA

1975: Jonh Holland: Idealizou os algoritmos
genéticos


Adaptation in Natural & Artificial Systems
MIT Press, 1975 (2nd ed. 1992)
Porque a evolução é uma boa metáfora?

Muitos problemas computacionais
envolvem busca através de um grande número de possíveis
soluções
 requerem que o programa seja adaptativo, apto a agir em um
ambiente dinâmico


A evolução biológica é
é uma busca massivamente paralela em um enorme espaço de
8
problema
 soluções desejadas = organismos mais adaptados

1. INTRODUÇÃO

1.1 O que são Algoritmos Genéticos?
São algoritmos de busca baseados no mecanismo de
seleção natural e genética.
 Utilizam a representação das soluções através de
cadeias de bits (strings), que são modeladas à maneira
das cadeias de DNA dos seres vivos orgânicos.
 Foram desenvolvidos por John Holland na Universidade
de Michigan.

9
1. INTRODUÇÃO

1.2 Objetivos do algoritmo original proposto por
Holland:
Criar uma abstração para explicar rigorosamente o
processo adaptativo dos sistemas naturais;
 Projetar sistemas de software artificial que
conservassem os mecanismos mais importantes dos
sistemas naturais.

10
FUNDAMENTOS BIOLÓGICOS

Cromossomos





Em cada célula há um mesmo conjunto de
cromossomos.
cromossomos são cadeias de DNA e servem como
modelo para todo o organismo. O cromossomo é
constituído de genes, que são blocos de DNA.
Cada gene codifica uma determinada proteína.
Basicamente, podemos dizer que cada gene codifica
uma determinada feição, por exemplo cor dos olhos.
Conjunto de genes relacionados com determinada
feição são chamados alelos.
Cada gene tem sua posição própria dentro do
cromossomo. Essa posição é chamada local.
11
FUNDAMENTOS BIOLÓGICOS

Um conjunto completo de material genético
(todos os cromossomos) é chamado genoma. Um
conjunto particular de genes de um genoma é
chamado genótipo. O genótipo mais o
desenvolvimento que ocorre após o nascimento é
a base para o fenótipo do organismo, que são
suas características físicas e mentais, tais como:
cor dos olhos, inteligência, etc.
12
FUNDAMENTOS BIOLÓGICOS

Reprodução



Durante a reprodução, ocorre inicialmente
recombinação (ou cruzamento).
Os genes dos pais são combinados para formar um
novo cromossomo.
Essa descendência recém criada pode sofrer uma
mutação.
Mutação significa que os elementos do DNA são
ligeiramente modificados. Essas mudanças são
causadas principalmente por erros na cópia dos
genes dos pais.
 A adaptação de um organismo é medida pelo
sucesso do organismo na vida (sobrevivência).

13
ESPAÇO DE SOLUÇÕES
O espaço de todas as soluções possíveis (que é um
conjunto entre as quais a solução procurada está)
é chamado Espaço das Soluções (ou Espaço de
Estados).
 Cada ponto desse estado representa uma solução
possível.
 Cada uma das possíveis soluções pode ser
"marcada" pelo seu valor (ou adequação) para o
problema.
 Com os Algoritmos Genéticos nós procuramos
pela melhor solução dentre um número de
possíveis soluções.

14
ESPAÇO DE SOLUÇÕES

Procurar por uma solução se resume então em
procurar por algum valor extremo (um mínimo ou
máximo) no espaço de soluções.
15
ALGORITMOS GENÉTICOS
Solução de um problema através de algoritmos
genéticos utiliza um processo evolucionário (a
solução é desenvolvida).
 O algoritmo começa com um conjunto de
soluções (representadas por cromossomos)
chamada população.
 Soluções de uma população são utilizadas para
formar uma nova população.
 Isto é motivado pela esperança que a nova
população será melhor do que a primeira.
 Soluções que são selecionadas para formar novas
gerações de soluções são selecionadas de acordo
com sua adequação.

16
ESBOÇO BÁSICO DO ALGORITMO
GENÉTICO



[Início] Gere uma população aleatória de n cromossomos
(soluções adequadas para o problema)
[Adequação] Avalie a adequação f(x) de cada cromossomo x
da população
[Nova população] Crie uma nova população repetindo os
passos seguintes até que a nova população esteja completa
[Seleção] Selecione de acordo com sua adequação (melhor adequação,
mais chances de ser selecionado) dois cromossomos para serem os pais
 [Cruzamento] Com a probabilidade de cruzamento cruze os pais
para formar a nova geração. Se não realizar cruzamento, a nova
geração será uma cópia exata dos pais.
 [Mutação] Com a probabilidade de mutação, altere os cromossomos
da nova geração nos locus (posição nos cromossomos).
 [Aceitação] Coloque a nova descendência na nova população




[Substitua] Utilize a nova população gerada para a próxima
rodada do algoritmo
[Teste] Se a condição final foi atingida, pare, e retorne a
melhor solução da população atual
[Repita] Vá para o passo 2
17
OPERADORES DOS ALGORITMOS
GENÉTICOS
O cruzamento e a mutação são as partes mais
importantes do algoritmo genético.
 O desempenho é influenciado principalmente por
esses dois operadores.

18
A CODIFICAÇÃO DE UM CROMOSSOMO

Um cromossomo deve de alguma maneira conter
a informação da solução que ele representa. A
forma mais comum de codificar é uma série
(string) binária. Um cromossomo pode então se
parecer como isto:
Cromossomo 1: 1101100100110110
Cromossomo 2: 1101111000011110

Cada bit da série representa alguma
característica da solução
19
CRUZAMENTO
O cruzamento opera em determinados genes dos
cromossomos dos pais e cria novas descendências.
 A maneira mais simples de fazer isso é escolher
aleatoriamente alguns pontos de cruzamento e
copiar tudo o que vem antes desse ponto de um
dos pais e então copiar tudo o que vem depois
desse ponto do outro pai.

20
CRUZAMENTO
0
1
1
1
1
0
0
0
1
0
21
A=
B=
Pai
Mãe
Indice de
corte = 3
Filho 1
A1 =
B1 =
0
1
1
1
1
0
0
0
0
1
Filho 2
Cruzamento (Cross Over)
MUTAÇÕES

Implementação do Mecanismo de Mutação
(Mutation)

Após o cruzamento, os filhos podem sofrer alterações no
seu código genético, chamadas de mutações.

Estas podem ocorrer em um ou mais alelos (bits), de
acordo com uma probabilidade pré-estabelecida.

Em virtude da probabilidade de mutação ser, geralmente baixa
nos seres vivos, ela desempenha um papel secundário na
evolução das espécies.
22
MUTAÇÕES
A1 =
0
1
1
0
0
Cromossom
o Original
0
0
0
Após
Mutação
Prob. de mutação <= 1% =
0,01
A1 =
0
1
I = 1,
M = rand() =
0,45
Sem mutação
I = 1,
M = rand()
=0,3
Sem mutação
I = 1,
M = rand() =
0,5
Sem mutação
I = 1,
M = rand() =
0,002
Mutação
I = 1,
M = rand() =
0,2
Sem mutação
23
PARÂMETROS DOS ALGORÍTMOS
GENÉTICOS

Probabilidade de Cruzamento:
 Com qual freqüência o cruzamento é
realizado.
 Se a probabilidade de cruzamento é 100%,
então toda a descendência é produzida por
cruzamento.
 Se a probabilidade é 0%, toda a nova geração é
formada por cópia exata dos cromossomos da
população antiga (mas isso não significa que a
nova geração é a mesma!).
24
PARÂMETROS DOS ALGORÍTMOS
GENÉTICOS

Probabilidade de Mutação:
 Com qual freqüência as partes dos
cromossomos sofrerão mutação.
 Se a probabilidade de mutação é 100%, todos
os cromossomos são alterados, se é 0%,
nenhum é alterado.
 A mutação em geral evita que o AG caia num
extremo (mínimo ou máximo) local.
 A mutação não deve ocorrer com muita
freqüência porque senão o AG tornar-se-á de
fato uma busca aleatória.
25
PARÂMETROS DOS ALGORÍTMOS
GENÉTICOS

Tamanho da População:
Quantos cromossomos existem na população (em uma
geração).
 Se houver poucos cromossomos, o AG terá poucas
possibilidade de realizar cruzamentos e somente uma
parte pequena do espaço de soluções será explorada.
 Por outro lado, se houver muitos cromossomos, os
AG’s se tornarão lentos.
 Pesquisas mostram que após determinado limite (que
depende principalmente da codificação e do
problema), não é conveniente aumentar a população
porque isso não resolve o problema mais rapidamente
do que com tamanhos moderados de população.

26
SELEÇÃO
Os cromossomos são selecionados de uma
população para serem pais de um cruzamento.
 O problema é como selecionar esses cromossomos.
 De acordo com a teoria da evolução de Darwin, o
melhor sobrevive para criar a descendência.
 Há muitos métodos para selecionar o melhor
cromossomo.
 Exemplos são: seleção por roleta, seleção
Boltzman, seleção por campeonato, seleção por
classificação, seleção por estado estacionário, e
outras.

27
SELEÇÃO POR ROLETA

Os pais são selecionados de acordo com sua
adequação. O lado de cada seção da roleta é
proporcional ao valor da adequação de cada
cromossomo: quanto maior for esse valor, mais
larga a secção.
28
SELEÇÃO POR CLASSIFICAÇÃO


O método anterior de seleção tem problemas
quando há grandes diferenças entre os valores de
adequação. Por exemplo, se a melhor adequação
dos cromossomos é 90% da soma de todas as
adequações, então haverá cromossomos com
chances muito baixas de serem selecionados.
A Seleção por Classificação primeiro classifica a
população e então atribui a cada cromossomo um
valor de adequação determinado pela sua
classificação. O pior terá adequação igual a 1, o
segundo pior 2 etc. de forma que o melhor terá
adequação igual a N (número de cromossomos na
população).
29
SELEÇÃO POR CLASSIFICAÇÃO
Agora todos os cromossomos tem uma chance de serem selecionados.
Entretanto, este método pode resultar em menor convergência, porque
Situação
antes da Classificação
(gráfico muito
da
os melhores
cromossomos
não se distinguem
dos outros.
adequação)
Situação depois da Classificação (gráfico dos números de
ordem)
30
SELEÇÃO POR ESTADO ESTACIONÁRIO
Este não é um método particular de seleção de
pais. A idéia principal deste tipo de seleção é que
a nova população deve ter uma grande parte de
cromossomos que sobreviverão para a próxima
geração.
 A seleção tipo Estado Estacionário dos AG’s
funciona do seguinte modo:


Em cada nova geração uns poucos bons cromossomos
(com alta adequação) são selecionados para a criação
da descendência. A seguir alguns maus cromossomos
(com baixa adequação) são removidos e novos
descendentes são colocados em seus lugares. Todo o
resto da população sobrevive para as próximas
gerações.
31
ELITISMO
Quando criamos uma nova população por
cruzamento e mutação, nós temos uma grande
chance de perder os melhores cromossomos.
 Elitismo é o nome do método que primeiro copia
os melhores cromossomos (ou os poucos melhores
cromossomos) para a nova população.
 O resto da população é construída das formas
descritas acima.
 Elitismo pode aumentar rapidamente o
desempenho do AG, porque previne a perda da
melhor solução já encontrada.

32
CODIFICAÇÃO
A codificação dos cromossomos é a primeira
questão a ser feita quando começamos a resolver
um problema utilizando AG.
 A codificação depende muito do problema.

33
CODIFICAÇÃO BINÁRIA
Codificação Binária é a mais comum
principalmente porque foi a que os primeiros
pesquisadores de AG usaram e devido à sua
relativa simplicidade.
 Na Codificação Binária, cada cromossomo é
uma série de bits - 0 or 1.
 Codificação Binária permite muitos possíveis
cromossomos, mesmo com pequenos número de
alelos.
 Por outro lado, esta codificação não é natural
para muitos problemas e algumas vezes é
necessário fazer correções antes dos cruzamentos
e/ou mutações.

34
CODIFICAÇÃO BINÁRIA



Exemplo de Problema: Problema da Mochila
O problema: É dada uma lista de coisas com
preços e tamanhos. É fornecido o valor da
capacidade da mochila. Escolha as coisas de
forma a maximizar o valor das coisas que cabem
dentro da mochila, sem ultrapassar sua
capacidade.
Codificação: Cada bit é usado para dizer se a
coisa correspondente está ou não na mochila.
35
CODIFICAÇÃO POR PERMUTAÇÃO
A Codificação por Permutação pode ser usada em
problemas que envolvem ordenação como o
"Problema do Caixeiro-Viajante" ou problemas de
ordenação de tarefas.
 Na Codificação por Permutação, cada
cromossomo é uma série de números que
representa uma posição em uma seqüência>.

cromossomo A
1 5 3 2 6 4 7 9 8
cromossomo B
8 5 6 7 2 3 1 4 9
Exemplo de cromossomo com codificação por permutação
36
CODIFICAÇÃO POR PERMUTAÇÃO
A Codificação por Permutação é útil para solução
de problemas de ordenação.
 Para alguns tipos de cruzamentos e mutações,
são necessárias correções para que os
cromossomos fiquem consistentes (isto é
contenham seqüências reais) para alguns
problemas.

37
CODIFICAÇÃO POR PERMUTAÇÃO


Exemplo de Problema: Problema do Caixeiro
Viajante (Travelling Salesman Problem - TSP)
O problema: São dadas cidades e as distâncias entre
elas. O caixeiro viajante tem que visitar todas elas,
sem viajar mais do que o necessário. A solução do
problema consiste em encontrar a seqüência de
cidades em que as viagens devem ser feitas de forma
que a distância percorrida seja a mínima possível.

Codificação: Os cromossomos descrevem a ordem em
que o caixeiro visitará as cidades.
38
CODIFICAÇÃO DE VALORES
A codificação direta dos valores pode ser usada
em problemas em que são usados valores mais
complicados tais como números reais.
 Usar codificação binária para esse tipo de
problema seria muito difícil.
 Na Codificação de Valores, cada cromossomo é
uma seqüência de alguns valores.
 Esses valores podem ser qualquer coisa
relacionada com o problema, tais como: números
reais, caracteres ou qualquer outro objeto.

39
CODIFICAÇÃO DE VALORES
cromossomo A 1.2324 5.3243 0.4556 2.3293 2.4545
cromossomo B ABDJEIFJDHDIERJFDLDFLFEGT
cromossomo C (atrás), (atrás), (direita), (frente), (esquerda)
Exemplo de cromossomo com codificação de valores
Codificação de Valores é uma boa escolha para
alguns problemas especiais.
 Entretanto, para essa codificação, é
frequentemente necessário desenvolver um
método de cruzamento e mutação específico para
o problema.

40
CODIFICAÇÃO DE VALORES



Exemplo de Problema: Cálculo de Pesos para
uma Rede Neural
O problema: É dada uma rede neural com
arquitetura definida. Encontre os pesos entre os
neurônios da rede de forma a obter a resposta
desejada da rede.
Codificação: Valores reais dos cromossomos
representam os pesos da rede neural.
41
CODIFICAÇÃO EM ÁRVORE
Codificação em Árvore é usada principalmente
para desenvolver programas ou expressões, isto é,
para programação genética.
 Na Codificação em Árvore cada cromossomo é
uma árvore de alguns objetos, tais como funções
ou comandos de uma linguagem de programação.

42
CODIFICAÇÃO EM ÁRVORE
Cromossomo A
Cromossomo B
(+ x (/ 5 y))
( do_until step wall )
Exemplo de cromossomo com codificação em árvore


A Codificação em Árvore é útil para desenvolver programas ou
qualquer outra estrutura que pode ser codificada em árvores.
A programação na linguagem LISP é frequentemente utilizada
para este propósito uma vez que os programas em LISP são
diretamente representados na forma de árvores e podem ser
facilmente processados como uma árvore, de forma que o
cruzamento e a mutação podem ser realizados com relativa
43
CODIFICAÇÃO EM ÁRVORE


Exemplo de Problema: Encontrar uma função
que aproxime um dado par de valores
O problema: São dados os valores de entrada e
de saída. A tarefa é encontrar uma função que
forneça a melhor saída (isto é, a que dê o
resultado mais próximo do desejado) para todas
as entradas.

Codificação: cromossomos são funções
representadas em uma árvore.
44
CRUZAMENTO E MUTAÇÃO
Cruzamento e Mutação são os dois operadores
básicos de AG.
 O desempenho do AG depende muito deles.
 O tipo e a implementação desses operadores
dependem da codificação e também do problema
 Há diversas maneiras de como fazer o
cruzamento e a mutação.

45
CODIFICAÇÃO BINÁRIA

Cruzamento

Ponto de Cruzamento Único - um ponto de
cruzamento é escolhido, a série binária desde o
começo do cromossomo até o ponto de cruzamento é
copiada do primeiro pais e o resto copiado do outro
pai.
11001011+11011111 = 11001111
46
CODIFICAÇÃO BINÁRIA

Dois pontos de cruzamento - são definidos
dois pontos de cruzamento, a série binária desde
o início do cromossomo até o primeiro ponto de
cruzamento é copiada do primeiro pai, a parte do
primeiro ponto de cruzamento até o segundo
ponto é copiada do outro pai e o resto do
cromossomo é copiado do primeiro pai
novamente.
11001011 + 11011111 = 11011111
47
CODIFICAÇÃO BINÁRIA

Cruzamento Uniforme - os bits são copiados
aleatoriamente do primeiro ou segundo pai.
11001011 + 11011101 = 11011111
48
CODIFICAÇÃO BINÁRIA

Cruzamento Aritmético - é realizada uma
operação aritmética para obter a nova geração.
11001011 + 11011111 = 11001001 (AND)
49
CODIFICAÇÃO BINÁRIA

Mutação

Inversão de Bit - determinados bits são invertidos
11001001 => 10001001
50
CODIFICAÇÃO POR PERMUTAÇÃO

Cruzamento

Ponto de Cruzamento Único - um ponto de cruzamento é
selecionado e a permutação é copiada até um ponto de
cruzamento selecionado, a permutação é copiada do
primeiro pai até o ponto de cruzamento, daí o outro pai é
rastreado e se o número ainda não estiver na descendência,
é adicionado:
(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

Mutação

Mudança de Ordem - dois números são escolhidos e
trocados entre si
(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)
51
CODIFICAÇÃO DE VALORES

Cruzamento


Todos os cruzamentos de codificação binária podem
ser usados.
Mutação

Adicionando um número pequeno (para codificação
de valores reais) - um número pequeno é adicionado a
(ou subtraído de) valores selecionados
(1.29 5.68 2.86 4.11 5.55) => (1.29 5.68 2.73 4.22 5.55)
52
CODIFICAÇÃO EM ÁRVORE

Cruzamento


Cruzamento de Árvores - um ponto de cruzamento é
escolhido em ambos os pais, os pais são divididos nesse
ponto e as partes abaixo do ponto de cruzamento são
trocadas para produzir a descendência
Mutação

Mudando o operador - os nós escolhidos são mudados
53
PROBLEMA DO CAIXEIRO VIAJANTE
Relembrando, são dadas cidades e as distâncias
entre elas.
 O caixeiro viajante tem que visitar todas elas,
mas não quer viajar demais.
 A tarefa consiste em encontrar a seqüência de
cidades que faz com que a distância percorrida
seja a menor possível.
 Em outras palavras, o problema é achar a rota
mínima Hamiltoniana num gráfico de N nós.

54
IMPLEMENTAÇÃO
Será usada uma população de 16 cromossomos.
 Para codificá-los foi utilizada Codificação por
Permutação, como forma de codificar a
permutação das cidades para o Problema do
Caixeiro Viajante.
 O problema é selecionado completando o gráfico
(isto é, cada nó é conectado ao outro) com
distâncias euclidianas.
 Depois de adicionar ou excluir uma cidade é
necessário criar novos cromossomos e reiniciar
completamente o algoritmo.

55
CRUZAMENTO
Ponto único - parte do primeiro pai (isto é, parte
da seqüencia das cidades) é copiada e o resto das
cidades é copiada na mesma seqüência do
segundo pai.
 Dois pontos - duas partes do primeiro pai são
copiadas e o restante (que está entre essas duas
partes) é colocada na mesma ordem que estão no
segundo pai.
 Nenhum - sem cruzamento, a descendência é
uma cópia exata dos pais.

56
MUTAÇÃO






Aleatória Normal (Normal Random Mutation) - umas
poucas cidades são escolhida e trocadas.
Aleatória se Melhora (Random, only improving) - umas
poucas cidades são escolhidas aleatóriamente somente se
elas melhoram a solução (isto é, aumentam a adequação) .
Sistemática se Melhora (Systematic, only improving) cidades são escolhidas sistematicamente e trocadas
somente se melhoram a solução (aumentam a adequação) .
Aleatória Melhorada (Random improving) - o mesmo que
"Aleatória se Melhora", porém antes que a mutação
aleatória normal seja executada .
Sistemática Melhorada (Systematic improving) - o mesmo
que "Sistemática se Melhora", porém antes que a mutação
aleatória normal seja executada.
Nenhuma - sem mutação.
57
REFERÊNCIAS
http://www.obitko.com/tutorials/geneticalgorithms/portuguese/index.php
 www.linux.ime.usp.br/~cleberc/seminarios/AG.p
pt
 www.di.ufpe.br/~compint/aulas-IAS/ga.ppt
 www.inf.unioeste.br/~josue/Genticos%20I.ppt

58