Computação Evolucionária
Aurora Pozo
Motivação
“...Se variações úteis para qualquer
organismo devam ocorrer para que ele venha
a existir, certamente indivíduos assim
caracterizados terão a melhor chance de
serem preservados na luta por sobrevivência;
e do forte princípio de hereditariedade,
eles tenderão a produzir gerações com
características similares. Este princípio de
preservação, eu batizei, para ser sucinto, de
Seleção Natural.”
(Darwin, 1859)
Ambientação
Teoria de
Computação
Evolucionária
Modelo
Biológico
Natureza
Modelo
Computacional
Teoria de Darwin
Sumário

Computação Evolucionária



Conceitos básicos
Algoritmos Genéticos
Programação Genética

Diferenças fundamentais
Computação Evolucionária


Área da Inteligência Artificial que
engloba um conjunto de métodos
computacionais inspirados na Teoria da
Evolução das Espécies.
auto-organização e o comportamento
adaptativo
Ramos

Estratégias Evolucionárias:


Programação Evolutiva:


Previsão do comportamento de máquinas de estado finitas.
Algoritmos Genéticos:


ênfase na auto-adaptação. O papel da recombinação é
aceito, mas como operador secundário.
Indivíduos contém um genótipo formado por cromossomos
Programação Genética

Evolução de programas
Evolução Natural

Embora tenham origens bastante
diversas, todas essa abordagens têm
em comum o modelo conceitual inicial
Aplicações

Grande variedade de aplicações

Otimização


Busca


Indústria, solução de problemas: máquinas x
processos, alocação de recursos, rota de veiculos.
Mineração de Dados, descoberta de conhecimento
em bases de dados, indução de classificadores
(caracteristicas x doenças, estrutura de proteinas)
Aprendizado e adaptação
Características Comuns


Usam um processo de evolução
baseado em Darwin para resolver
problemas computacionais de IA
Inspirados na Teoria da Evolução: os
indivíduos mais adaptados
sobrevivem
Elementos Chaves de
Algoritmos Evolucionarios




Uma população de individuos
A noção de fitness
Um ciclo de nascimento e morte
baseados na fitness
A noção de herança
Visão Geral do
Algoritmo Evolucionário
população de
pais
seleção
recombinação
população de
filhos
solução
Visão Geral do
Algoritmo Evolucionário
1.
2.
Gerar uma população inicial
aleatoriamente
Fazer até um critério de parada:



3.
selecionar indivíduos para pais (fitness)
produzir filhos
selecionar indivíduos para morrer (fitness)
Retornar um resultado
início
população inicial
Algoritmo
seleção (fitness)
pais selecionados
operadores
genéticos
cruz
repr
mut
filhos gerados
não
fim
solução
sim
satisfeito c/
a solução?
nova pop
completa?
sim
nova população
não
Algorithmos Geneticos




Holland 1960
São algoritmos de busca
Objetivo: robusto, sistema adaptativo
Combinam: Sobrevivência do mais
ajustado com um estruturado, aleatorio
intercâmbio de informações
AG


Apesar de aleatorios, AG não funcionam
unicamente com este conceito.
Eles explotam informação historica para
experimentar novos pontos de busca.
Terminologia Biologica




Em AG são utilizados termos biologicos
como analogia com a biologia.
Cromossoma: codificação de uma
possivel solução – individuo
Genes: Codifica uma caracteristica
particular
Genotipo x Fenotipo
Indivíduos




Material genético
Conjunto de atributos da solução
Cada atributo uma sequência de bits e
o individuo como a concatenação das
sequências de bits
Codificação binaria, real, códigos
População

Conjunto de individuos que estão sendo
cogitados como solução


Populações pequenas têm grandes chances
de perder a diversidade necessária
(exploração de todo o espaço de soluções)
Populações grandes perderá grande parte
de sua eficiência pela demora em avaliar a
função de fitness
Reprodução


Reprodução sexual, genes são
intercambiados entre dois pais –
crossover
Os filhos são sujeitos a modificações,
na qual bits elementares são mudados mutação
Função de fitness




Mede a adaptação do indivíduo ou quão
boa é a solução dada por este
indivíduo.
Representativa do problema: diferencie
uma solução boa de uma má.
Heuristica de busca no espaço de
estado
Cuidados com o custo computacional.
Requisitos para usar AG
 Representações das possíveis soluções do problema no formato
de um código genético;
 População inicial que contenha diversidade suficiente para
permitir ao algoritmo combinar características e produzir novas
soluções;
 Existência de um método para medir a qualidade de uma solução
potencial;
 Um procedimento de combinação de soluções para gerar novos
indivíduos na população;
 Um critério de escolha das soluções que permanecerão na
população ou que serão retirados desta;
 Um procedimento para introduzir periodicamente alterações em
algumas soluções da população. Desse modo mantém-se a
diversidade da população e a possibilidade de se produzir
soluções inovadoras para serem avaliadas pelo critério de
seleção dos mais aptos.
População
Avaliação de Aptidão
Seleção
Cruzamento
Mutação
Não
Operadores
genéticos
Critério de
Parada ?
Sim
Retornar Melhor Indivíduo
Figura 1 - Estrutura básica de um Algoritmo Genético
Seleção

O operador escolhe quais indivíduos
participarão na criação da próxima
geração
Exemplo
Indivíduos
Fitness
% Fitness
10101010110101010111 12
23,08
00001001010101110010 8
15,38
00001100001011011101 9
17,31
00000110010010000010 6
11,54
11100011100010011111 12
23,08
00010101001000010000 5
9,62
Total
100,00
52
Roleta
10%
23%
23%
15%
12%
17%
Roleta
Inicio
T = soma dos valores de aptidão de todos os indivíduos da população
Repita N vezes para selecionar n indivíduos
r = valor aleatório entre 0 e T
Percorra sequencialmente os indivíduos da população,
acumulando
em S o valor de aptidão dos indivíduos já percorridos
Se S >= r então
Selecione o indivíduo corrente
Fim se
Fim Repita
Fim
Torneio
Inicio
k = 0.75
Repita N vezes
Escolha 2 indivíduos da população aleatoriamente
r = valor aleatório entre 0 e 1
Se r < k
O melhor indivíduo é escolhido
Senão
O pior indivíduo é escolhido
Fim se
Fim Repita
Fim
Pressão de Seleção
K
filhos
M pais
Com sobreposição
Sem sobreposição
Pressão de Seleção

Generações com sobreposição




Estrategias de seleção (pressão decrecente)





Mais pressão que sem sobreposição
M moderado, K=M, GA tradicionais
M grande, K pequeno “steady state” GA
Truncação
Torneio e ranking
Proporcional a fitness
Uniforme
Estocastica vs deterministica
Problemas da Roleta



Tecnicamente resulta numa distribuição
proporcional de indivíduos
Convergência muito rápida
Variância quase nula
Seleção por Ranking



Não parametrica
Os indivíduos são ordenados de acordo
com sua fitness
Os offspring são alocados de acordo ao
ranking (pode ser linearmente)
Reprodução



Preserva caracteristicas uteis
Introduz variedade e novedades
Estrategias


Parentes unicos: clonar + mutuação
Parentes multiplos: recombinação +
mutação
Metodos de Recombinação



Cruzamento: cria novos indivíduos
misturando características de dois
indivíduos pais (crossover)
Copia de segmentos entre os pais
Crossovers multi-ponto, dois pontos,
um ponto, uniforme e inversão
Cruzamento



Pai 1: 10101010110101010111
Pai 2: 00001001010101110010
Cruzamento em um ponto


10101010110101110010,
00001001010101010111
Cruzamento uniforme: os filhos são
formados a partir dos bits dos pais
(sorteado)
Cruzamento em dois pontos
Individuo 1
1
1
0
1
0
1
0
1
Individuo 2
1
0
0
0
0
1
0
0
Descendente 1
1
1
0
0
0
1
0
1
Descendente 2
1
0
0
1
0
1
0
0
Mutação



Esta operação inverte aleatoriamente
alguma característica do indivíduo
Cria novas características que não
existiam
Mantem diversidade na população
Balance ExplotaçãoExploração

Pressão de seleção: explotação


Reprodução: exploração


Reduz o espaço de busca
Expande o espaço de busca
Balance


Seleção forte + taxas de mutação altas
Seleçao fraca + taxas de mutação baixas