Tema 09 - 04 - SLIDE PPT - AlgoritmoGenético

Prévia do material em texto

Inteligência Artificial
TEMA 9: Algoritmo Genético
Profª Daisy Albuquerque
Profª Daisy Albuquerque 2
Unidade 4: 
Computação Evolucionária
• Otimização
• Algoritmo Genético
• Aplicação
Uma definição simplista
Algoritmos Genéticos 
são técnicas de
otimização global
inspiradas na
Teoria da Evolução das Espécies.
Isto é...
Algoritmos Genéticos
são algoritmos de busca inspirados na
⚫ teoria da evolução,
⚫ seleção natural e
⚫ nos processos biológicos envolvidos.
são algoritmos evolutivos que usam técnicas inspiradas 
pela biologia evolutiva como: hereditariedade, mutação, 
seleção natural e recombinação (ou crossing over).
➢ Otimização em escopo global.
➢ Opera sobre uma codificação genérica dos
parâmetros da otimização.
➢ Não necessita de conhecimento, a priori,
de características do espaço de busca.
Pontos fortes dos AG
Definição 1:
É a busca da melhor solução para um
determinado problema.
Otimização
Processo de otimização clássico
1. Propor candidato a solução.
2. Obtém-se saídas de interesse e avalia-se
os objetivos.
3. Baseado em algum tipo de análise do
resultado obtido, propõe-se nova tentativa.
4. Voltar ao passo 2.
Otimização global e
sem conhecimento do espaço de busca.
Uma tarefa difícil
Otimização Global
V1
V2
Função Multi-modal (vários sub-ótimos)
Ótimo Local ou 
sub-ótimo
Ótimo Global
O Clássico “Hill-Climbing”
1. “Chuta-se” ponto inicial.
3. Analisa-se a tendência, ou seja, a direção e sentido
para onde deve caminhar a próxima tentativa.
2. Avalia a proposta.
4. Novo “chute”.
5. Se parar de melhorar, FIM, senão, volta para 2”.
O Clássico “Hill-Climbing”
V1
V2
Chute inicial
Melhora
O Clássico “Hill-Climbing”
V1
V2
Tentativa 2
Melhora
O Clássico “Hill-Climbing”
V1
V2
Tentativa 3
Melhora
O Clássico “Hill-Climbing”
V1
V2
Tentativa 4
O Clássico “Hill-Climbing”
V1
V2
Tentativa 5
➢ Técnicas formais de otimização global
demandam conhecimento do espaço de
busca (concavidade, limites, derivadas, etc)
➢ Técnicas que não demandam conhecimento
do espaço de busca são susceptíveis à
convergência local.
Um dilema
Utilizar algoritmos baseados em população,
como por exemplo:
Algoritmos Genéticos (AG).
Uma proposta de solução
Elevado custo computacional, quando
comparado com o custo demandado por
técnicas tradicionais.
O preço da solução
V1
V2
AG e otimização global
V1
V2
AG e otimização global
V1
V2
AG e otimização global
V1
V2
AG e otimização global
V1
V2
AG e otimização global
V1
V2
AG e otimização global
V1
V2
AG e otimização global
V1
V2
AG e otimização global
V1
V2 Redondezas do 
Ótimo Global
AG e otimização global
V1
V2 Redondezas do 
Ótimo Global
AG e otimização global
➢ Problemas multi-modais (vários sub-ótimos)
onde não se tem conhecimento do espaço
de busca a ser explorado.
➢ Estes problemas, tipicamente, se encontram
nas seguintes áreas:
⚫ Configuração de sistemas complexos,
⚫ Alocação de tarefas, 
⚫ Seleção de rotas e
⚫ Outros problemas de otimização.
Aplicações dos AGs
Aplicações dos AGs
https://www.youtube.com/watch?v=NIzDYdOoNdQ
https://www.youtube.com/watch?v=NIzDYdOoNdQ
Aplicações dos AGs
https://www.youtube.com/watch?v=0IdYg1IdKvg
https://www.youtube.com/watch?v=0IdYg1IdKvg
Numa dada população, os indivíduos mais fortes
têm 
mais chances de reprodução
e, consequentemente, 
de passar suas características para seus 
descendentes, gerando, assim, uma 
população cada vez mais adaptada ao meio.
A metáfora dos AG
Meio
Adaptação
Espaço de busca
Cumprimento dos objetivos
Nos Algoritmos Genéticos
➢ Definição de uma estrutura de dado para
conter um candidato à solução.
➢ Definição de uma forma de avaliação do
resultado, considerando os objetivos e as
restrições do problema.
➢ Mecanismo de controle e geração de novos
candidatos a solução.
Otimização Automática
Controle e geração 
de novos candidatos
Operações de seleção, 
cruzamento, mutação, elitismo…
parâmetros
Avaliação Função Objetivo
Estrutura de Dado Genótipo ou cromossoma
Nos Algoritmos Genéticos
Genótipo
➢É a estrutura de dado que codifica
um candidato à solução.
➢Nos Algoritmos Genéticos clássicos
isto é feito através de uma “string”
binária de tamanho fixo.
➢ É a função que reúne as saídas de
interesse e avalia o quão “boa” é a solução
proposta.
➢ O valor da função objetivo para um
indivíduo é chamado prêmio ou aptidão
(“fitness”).
Função Objetivo
➢ Cruzamento (“crossover): é a troca de
informação genética entre indivíduos
(mistura de soluções).
➢ Mutação: é a alteração aleatória de parte
do genótipo (no AG clássico, 1 bit).
Operações Genéticas Clássicas
Cruzamento (“crossover”)
1 0 1 0 1 0 0 0 1 1 
0 0 0 1 1 0 0 0 0 1 
1 0 1 0
0 0 0 1 1 0 0 0 1 1 
1 0 0 0 0 1 
Pais Filhos
Ponto de crossover (escolhido aleatoriamente)
Cruzamento (“crossover”)
Mutação
Escolhe-se uma posição aleatoriamente e inverte-se este bit.
1 0 1 0 0 0 0 0 1 1
Antes da mutação
Ponto de mutação (escolhido aleatoriamente)
Mutação
Escolhe-se uma posição aleatoriamente e inverte-se este bit.
Antes da mutação
Ponto de mutação (escolhido aleatoriamente)
1 0 1 0 1 0 0 0 1 1
Mutação
Elitismo
➢Técnica utilizada para eliminar a possibilidade
de perda do melhor indivíduo até então
encontrado.
➢ Isto é feito através da simples cópia do
melhor indivíduo para a próxima geração.
Parâmetros Genéticos
➢Tamanho da população
➢Taxa de cruzamento
➢Taxa de mutação
➢Intervalo de geração
Problema exemplo
➢Problema: Obter valores de V1 (podendo variar
entre 1 e 32) e V2 (podendo variar entre 0 e 15.5)
de forma que se obtenha o maior valor de
f(V1,V2) = V1 + V2.
v1
v2
f
1. Inicializa população de candidatos à solução;
2. Avalia população de candidatos;
3. Seleciona candidatos para operações genéticas;
5. Atualiza população de candidatos;
6. Se convergiu, FIM, senão, volta para 2;
4. Opera e transforma população de candidatos;
Algoritmo Genético Clássico
Início
Inicializa(População);
Enquanto (NÃO Terminar) Faça
Avalia (População);
NovaPopulação := Seleciona (População);
Opera (NovaPopulação);
Populaçao := NovaPopulação;
Fim Enquanto;
Fim.
Algoritmo Genético Clássico
Exemplo de Genótipo
1 0 0 0 1 0 0 0 1 1 
v1
v2
v1 v2
18 1.5
Genótipo
Gene 1
Codificação das variáveis Codificação de um 
candidato à solução:
Gene 2
0 - 00000
0.5 - 00001
15.5 - 11111
15.0 - 11110
...
1 - 00001
32 - 10000
2 - 00010
31 - 11111
...
Indivíduo Genótipo v1 v2
1 
2
3
4
5 
6
É a geração aleatória de uma população inicial.
0 0 0 1 1 0 0 0 1 0
0 1 0 1 0 1 1 1 1 0
0 1 1 0 0 0 0 1 0 0
0 0 1 0 1 0 1 0 1 1
0 0 0 1 0 0 0 0 0 0
1 1 1 0 0 1 1 1 0 0
4 1
10 15
13 2
5 5
2 0
29 14
Inicialização
Indivíduo Genótipo v1 v2 f(v1,v2)
1 
2 
3
4 
5
6
Cálculo da função objetivo para cada candidato.
5
25
15
10
2
43
0 0 0 1 1 0 0 0 1 0
0 1 0 1 0 1 1 1 1 0
0 1 1 0 0 0 0 1 0 0
0 0 1 0 1 0 1 0 1 1
0 0 0 1 0 0 0 0 0 0
1 1 1 0 0 1 1 1 0 0
4 1
10 15
13 2
5 5
2 0
29 14
Avaliação
Seleção Proporcional
Indivíduo f
1 5
2 25
3 15
4 10
5 2
6 43
A fitness indica o tamanho do arco correspondente ao indivíduo
Indivíduo 6 
selecionado
Seleção Proporcional
Conclusão
➢O processo de evolução de um AG realiza a busca em um
espaço de soluções potenciais para o problema
(população).
➢Os AGs são mais robustos, devido a que existe uma
direção ótima no processo de busca da solução.
➢Os AGs mentem populações das soluções potenciais
intercambiando informações.
➢Os AGs não garatem uma solução GLOBAL, entretanto a
solução obtida pode se encontrar próxima da global
(solução local).
Conclusão
➢A velocidade de convergência do AGs dependerá dos
parâmetros de configuração, tais como: tamanho da
população, taxa de cruzamento, etc.
➢ Para sair de um estágio de estagnação poderia se
implementarum operador genético de mutação
aumentando o número de gerações.
➢Observa-se que para cada nova execução do AGs a
solução obtida tem variações assim como sua curva de
convergência.
Problema da Mochila
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Exemplo
Dúvidas?