Algoritmos_Geneticos

Prévia do material em texto

1
Inteligência Artificial Prof. Álvaro Guarda Técnicas Evolucionistas - 1
Definição
Conjunto de técnicas de otimização inspiradas na teoria da evolução natural. 
Esta abordagem remonta o início da computação, entre os anos 50 e 60, quando 
vários cientistas da computação estudaram sistemas evolucionários com a idéia de 
que a evolução poderia ser usada como um ferramenta de otimização para 
problemas na engenharia.
Principal idéia da teoria da evolução 
Uma população de indivíduos evolui durante as gerações, sendo que aqueles mais 
aptos possuem uma probabilidade maior de terem uma prole mais numerosa, 
resultando em indivíduos cada vez melhores (mais adaptados).
Principais Técnicas
� Programação Evolucionista
� Estratégia Evolucionista
� Sistemas Classificadores
� Algoritmos Genéticos
� Programação Genética
ComputaComputaçção Evolucionista ão Evolucionista 
Nota:
O espaço de busca é um
espaço de soluções
Nota:Nota:
O espaço de busca é um
espaço de soluções
Inteligência Artificial Prof. Álvaro Guarda Técnicas Evolucionistas - 2
IntroduIntroduççãoão
� Inventados por John Holland nos anos 60 e desenvolvidos por ele e seus alunos 
na Universidade de Michigan em meados de 1970.
� Nesta técnica a analogia com os sistemas biológicos é mais forte, pois, além de 
ser baseado nos mecanismos de seleção natural, também se baseia na genética.
Principais ConceitosPrincipais Conceitos
� Indivíduo -> Hipótese de Solução
� Fenótipo x Genótipo
� Aptidão (“Fitness”) de um Indivíduo -> aplicação da Função Heurística
� População -> Os AG vasculham várias regiões do espaço de busca de cada vez
� Geração
Algoritmos GenAlgoritmos Genééticos ticos -- IntroduIntroduççãoão
Notas:
Em Resolução de Problemas a 
cadeia genética é uma cadeia 
binária de tamanho fixo.
Em alguns casos a representação
binária não é adequada.
Notas:Notas:
Em Resolução de Problemas a 
cadeia genética é uma cadeia 
binária de tamanho fixo.
Em alguns casos a representação
binária não é adequada.
Inteligência Artificial Prof. Álvaro Guarda Técnicas Evolucionistas - 3
Algoritmo GenAlgoritmo Genéético tico -- Exemplo de ModelagemExemplo de Modelagem
Problema das NProblema das N--Rainhas:Rainhas:
A posição de cada rainha é dada pelo número da coluna que ela ocupa.
Exemplo para N = 4:Exemplo para N = 4:
Cadeia GenCadeia Genéética: tica: 01 11 00 10 
Representação de uma Hipótese de Solução:
Lista onde o primeiro elemento 
corresponde à Rainha da Linha 1 
e assim sucessivamente.
[ 2; 4; 1; 3]
RepresentaRepresentaçção de uma Hipão de uma Hipóótese de Solutese de Soluçção:ão:
Lista onde o primeiro elemento 
corresponde à Rainha da Linha 1 
e assim sucessivamente.
[ 2; 4; 1; 3]
Nota:
A partir da cadeia genética 
é possível reconstruir o 
indivíduo.
Nota:Nota:
A partir da cadeia genética 
é possível reconstruir o 
indivíduo.
Inteligência Artificial Prof. Álvaro Guarda Técnicas Evolucionistas - 4
SeleSeleçção (proporcional ão (proporcional àà aptidão)aptidão)
Probabilidade de que uma hipótese H seja selecionada:
Exemplo: Exemplo: 5 indivíduos
Algoritmos GenAlgoritmos Genééticos ticos -- Operadores GenOperadores Genééticosticos
( ) ( )( )∑
∈
=
PopH
i
i Hf
HfHp
E
D
C
B
A
Indivíduo 
Hi
3
10
5
12
20
Nota 
f(Hi)
0,06
0,20
0,10
0,24
0,40
P(Hi)
A
B
C
D
E
Roleta:Roleta:
Nota:
Regras de transição probabilísticas 
e não regras determinísticas
Nota:Nota:
Regras de transição probabilísticas 
e não regras determinísticas
2
Inteligência Artificial Prof. Álvaro Guarda Técnicas Evolucionistas - 5
Clonagem Clonagem 
Replica a Hipótese de Solução na próxima geração
MutaMutaççãoão
Gera uma nova Hipótese de Solução a partir de uma pequena modificação
� Operador randômico de manipulação
� Introduz e mantém a variedade genética da população
� Garante a possibilidade de se alcançar qualquer ponto do espaço de busca
� Contorna mínimos locais
CruzamentoCruzamento
Gera novas Hipóteses de Solução a partir de 2 pais
Algoritmos GenAlgoritmos Genééticos ticos -- Operadores GenOperadores Genééticosticos
Inteligência Artificial Prof. Álvaro Guarda Técnicas Evolucionistas - 6
Algoritmos GenAlgoritmos Genééticos ticos -- Operadores GenOperadores Genééticosticos
Cruzamento de um pontoCruzamento de um ponto
Corta os pais em uma posição aleatória e recombina as partes
001000111101001Pai 1Pai 1
011100010000111Pai 2Pai 2
011100010001001Filho 1Filho 1
001000111100111Filho 2Filho 2
001000111101001Pai 1Pai 1
011100010000111Pai 2Pai 2
001000010001001Filho 1Filho 1
011100111100111Filho 2Filho 2
CruzamentoCruzamento de de doisdois pontospontos
Corta os pais em duas posições aleatórias e recombina as partes
Inteligência Artificial Prof. Álvaro Guarda Técnicas Evolucionistas - 7
Algoritmos GenAlgoritmos Genééticos ticos -- Operadores GenOperadores Genééticosticos
001000111101001Pai 1Pai 1
011100010000111Pai 2Pai 2
011100110001001Filho 1Filho 1
001000011100111Filho 2Filho 2
CruzamentoCruzamento uniformeuniforme
Gera uma máscara de bits aleatórios e recombina os bits dos pais
de acordo com a máscara
100000110001111MMááscarascara
Inteligência Artificial Prof. Álvaro Guarda Técnicas Evolucionistas - 8
Algoritmo GenAlgoritmo Genéético tico ((TamPopTamPop, , NumGerNumGer,...),...)
1. Crie a popula1. Crie a populaçção inicial:ão inicial: Pop ← TamPop hipóteses geradas aleatoriamente
2.2. Avalie Pop:Avalie Pop: para cada hipótese H Є Pop, calcule a sua aptidão f(H)
3.3. Evolua a populaEvolua a populaççãoão Pop uma geração (faça até condição de término)
3.1.3.1. Crie a nova populaCrie a nova populaçção ão NovaPopNovaPop (faça até gerá-la completamente)
3.1.1. Escolha um operador gen3.1.1. Escolha um operador genééticotico
3.1.2. Selecione hip3.1.2. Selecione hipóótesesteses (a quantidade depende do operador)
3.1.3. Aplique o operador gen3.1.3. Aplique o operador genééticotico sobre as hipóteses selecionadas: 
Hnova ← operador(H)
3.1.4. Adicione a(s) hip3.1.4. Adicione a(s) hipóótese(s) resultante(s) na nova populatese(s) resultante(s) na nova populaçção:ão:
NovaPop ← NovaPop + Hnova
3.2.3.2. Atualize a populaAtualize a populaçção:ão: Pop ← NovaPop
3.3.3.3. Avalie Pop:Avalie Pop: calcule a aptidão f(H) de cada hipótese H 
4.4. Retorne resultado:Retorne resultado: a hipótese com a maior aptidão de todas as gerações.