Computação Evolutiva : Um Novo Paradigma
Para a Resolução de Problemas Complexos
Aurora Pozo
Pós-graduação em Informática, Pós-graduação em Métodos
Numéricos para Engenharia. Grupo EsCeL,
Motivação
Algoritmos Genéticos e Evolutivos são eficientes
métodos de otimização e planejamento
inspirados na natureza baseados nos princípios
da evolução natural e genética.
Devido a sua eficiência e simples princípios, estes
métodos são usados em uma variedade de
problemas de otimização e aprendizado de
maquina.
Ambientação
Teoria de
Computação
Evolucionária
Modelo
Biológico
Natureza
Modelo
Computacional
Teoria de Darwin
Exemplos de Aplicações Reais
•
•
•
•
•
Projeto de Antenas
Projeto de Drogas
Classificação Química
Circuitos Elétricos
Escalonamento de
Fabricas (Volvo, Deere,
outras)
• Projeto de Turbina
• Projeto de Carros
“Crashworthy”
• Projeto de Redes
• Projeto de Sistemas de
Controle
• Parâmetros de Produção
• Projeto de Satélite
• Stock/commodity/ analises/
tendências
• Ajuste de Celulares
• Data Mining
Sumário
• Computação Evolutiva
– Conceitos básicos
• Algoritmos Genéticos
• Projetos
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:
– ênfase na auto-adaptação. O papel da recombinação é
aceito, mas como operador secundário.
• Programação Evolutiva:
– Previsão do comportamento de máquinas de estado finitas.
• Algoritmos Genéticos:
– Indivíduos contém um genótipo formado por cromossomos
• Programação Genética
– Evolução de programas
• Estimativa de Distribuição
– AG competentes
Historia
• Estratégias Evolutivas:
• Desenvolvida por Rechenberg, Schwefel, etc.
em 1960.
• Foco: Otimização de parâmetros de valores
reais
• Individuo: vetor de parâmetros de valores reais
• Reprodução: Mutação Gaussiana dos
parâmetros
• M pais, K>>M filhos
Historia
• Programação Evolutiva:
• Desenvolvida por Fogel in 1960
• Objetivo: evoluir comportamento
inteligente
• Indivíduos: Maquina de estado finita
• Filhos via mutação das MEF
• M pais, M filhos
Historia
•
•
•
•
•
Algoritmos Genéticos:
Desenvolvidos por Holland em 1960s
Objetivo: robustos, sistemas adaptativos
Utiliza uma codificação “genética” de pontos
Reprodução via mutação e recombinação do
código genético.
• M pais, M filhos
Historia
• Programação Genética
• Desenvolvidos por Koza em 1990s
• Objetivo: Evolução de programas
• Reprodução via recombinação do código
genético.
• M pais, M filhos
Historia
•
•
•
•
Alg. de Estimativa de Distribuição
Inicia com os trabalhos de Baluja 1994
AG competentes ???
Modelam os relacionamentos entre as
variáveis do indivíduos.
• Evoluem o modelo
– Alguns utilizam redes bayesianas para isto
Estado Atual
• Grande variedade de Algoritmos
Evolutivos
• Grande variedade de aplicações
– Otimização, busca, aprendizado, adaptação
• Analise
– teórico
– experimental
Características Comuns
• Uso de um processo de evolução pseudoDarwinian para solucionar problemas
difíceis.
• Computação Evolutiva
Evolução Natural
• Embora tenham origens bastante
diversas, todas essa abordagens têm em
comum o modelo conceitual inicial
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 Evolucionários
• Uma população de indivíduos
• 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. Gerar uma população inicial
aleatoriamente
2. Fazer até um critério de parada:
– selecionar indivíduos para pais (fitness)
– produzir filhos
– selecionar indivíduos para morrer (fitness)
3. Retornar um resultado
Algorithmos Geneticos
•
•
•
•
Holland 1960
São algoritmos de busca
Objetivo: robusto, sistema adaptativo
Combinam: Sobrevivência do mais
ajustado com um estruturado, aleatório
intercâmbio de informações
AG
• Apesar de aleatórios, AG não funcionam
unicamente com este conceito.
• Eles exploram informação histórica para
experimentar novos pontos de busca.
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
Terminologia Biológica
• Em AG são utilizados termos biológicos
como analogia com a biologia.
• Cromossomo: codificação de uma
possível solução – individuo
• Genes: Codifica uma característica
particular
• Genótipo x Fenótipo
Indivíduos
• Material genético
• Conjunto de atributos da solução
• Cada atributo uma seqüência de bits e o
individuo como a concatenação das
seqüências de bits
• Codificação binária, códigos
População
• Conjunto de indivíduos que estão sendo
cogitados como solução
– Relacionado a dimensão do espaço de busca.
– 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 trocados
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á.
• Heurística 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.
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
52
100,00
Roleta
10%
23%
23%
15%
12%
17%
Reprodução
• Preserva características úteis
• Introduz variedade e novidades
• Estratégias
– Parentes únicos: clonar + mutação
– Parentes múltiplos: recombinação + mutação
Métodos 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)
Mutação
• Esta operação inverte aleatoriamente
alguma característica do indivíduo
• Cria novas características que não
existiam
• Mantém diversidade na população
Balance Explotação-Exploração
• Pressão de seleção: explotação
– Reduz o espaço de busca
• Reprodução: exploração
– Expande o espaço de busca
• Balance
– Seleção forte + taxas de mutação altas
– Seleção fraca + taxas de mutação baixas
Quando AG é bom ?
• Funções multímodas
• Funções discretas ou continuas
• Funções altamente dimensionais, incluindo
combinatórias
• Dependência não linear dos parâmetros
• Usada freqüentemente para obter solução a
problemas NP completos
• Não usar quando outro método como hillclimbing, etc., funciona bem
Técnicas Avançadas em AGs
• AGs são apropriados para problemas
complexos, mas algumas melhorias
devem ser feitas