View
108
Download
1
Category
Preview:
Citation preview
1
Computação Evolutiva: Uma Nova Forma de Resolver
Problemas
DCA-FEEC-Unicamp
Fernando J. Von Zuben
ftp://ftp.dca.fee.unicamp.br/pub/docs/vonzuben/tutorial/apresEC.pdf
2
Motivação
Se há uma multiplicidade impressionante de algoritmos para solução de problemas, por que então existe a necessidade de novas abordagens?
Porque problemas importantes continuam sendo “difíceis” de resolver.
3
Motivação
Por que alguns problemas continuam sendo “difíceis” de resolver?
Porque as seguintes características (isoladas ou em conjunto) impedem o uso ou degradam o efeito da aplicação de algoritmos clássicos: intratabilidade matemática, não-linearidades, ausência de informação suficiente acerca do problema, observações ruidosas, variação no tempo, descontinuidade, explosão combinatória de candidatos à solução.
4
Motivação
Mas e se eu simplificar ou realizar aproximações junto ao problema?
A aplicabilidade dos algoritmos clássicos aumenta. Mas vão continuar a existir problemas importantes e “difíceis” de resolver, e vai aumentar a probabilidade de se obter a resposta certa do problema errado.
5
Motivação
Muito bem. Então, que nova abordagem poderia substituir as abordagens clássicas?
A computação evolutiva é uma candidata, embora não seja a única.
6
Introdução
Técnicas de solução de problemas inspiradas na natureza será que o homem teria perseguido tão tenazmente
a idéia de voar se não existissem animais que voam?
os benefícios advindos da imitação de processos observados na natureza são inquestionáveis.
Esta imitação pode se dar em vários níveis: fonte de inspiração (animais que voam); simulação de comportamentos (insetos sociais, táticas de caça); mecanismos de processamento de informação (seleção natural); reprodução na forma de dispositivos físicos (antenas).
7
Introdução
o objetivo nem sempre envolve o tratamento de problemas exclusivamente com base em técnicas inspiradas na natureza, mas sim o desenvolvimento de sistemas híbridos.
efeito colateral marcante: a iniciativa de buscar imitar determinados processos naturais ajuda a entendê-los melhor.
princípios éticos envolvidos: audácia ou ingenuidade?
a disponibilidade de uma quantidade significativa de recursos computacionais é um requisito básico para viabilizar a implementação computacional.
8
Áreas de Atuação Científica
Computação Natural Inteligência Computacional Vida Artificial
Inteligência Computacional Computação Evolutiva Redes Neurais
Computação Evolutiva algoritmos genéticos estratégias evolutivas programação evolutiva
Sistemas Complexos Geometria Fractal
Sistemas Nebulosos Agentes Autônomos
sistemas classificadores programação genética
9
O que é Computação Evolutiva ?
Computação Evolutiva Modelo computacional de processos evolutivos naturais Ferramenta adaptativa para a solução de problemas Elemento gerador de criatividade
na prática: aplicação do processo de seleção natural como um paradigma de solução de problemas, a partir de sua implementação em computador.
a vantagem mais significativa da computação evolutiva está na possibilidade de resolver problemas pela simples descrição matemática do que se quer ver presente na solução, não havendo necessidade de se indicar explicitamente os passos até o resultado, que certamente seriam específicos para cada caso.
10
O que é Computação Evolutiva ?
estrutura básica comum dos algoritmos evolutivos: realizam reprodução, impõem variações aleatórias, promovem competição e executam seleção de indivíduos de uma dada população.
o enfoque desta apresentação está vinculado ao emprego da computação evolutiva no desenvolvimento de técnicas para solução de problemas de otimização.
o problema a ser resolvido faz o papel do ambiente, e cada indivíduo da população é associado a uma solução-candidata. Sendo assim, um indivíduo vai estar mais adaptado ao ambiente sempre que ele corresponder a uma solução mais eficaz para o problema.
11
Computação Evolutiva como Estratégia de Solução de Problemas
métodos fortes: são concebidos para resolverem problemas genéricos, mas foram desenvolvidos para operarem em um mundo específico, onde impera linearidade, continuidade, diferenciabilidade e/ou estacionariedade. Exemplo: método do gradiente e técnicas de programação linear (busca iterativa).
métodos específicos: são concebidos para resolverem problemas específicos em mundos específicos. Exemplo: toda técnica que conduz a uma solução na forma fechada, como solução de sistemas lineares.
métodos fracos: são concebidos para resolverem problemas genéricos em mundos genéricos. Operam em mundos não-lineares e não-estacionários, embora não garantam eficiência total na obtenção da solução. No entanto, geralmente garantem a obtenção de uma “boa aproximação” para a solução, requerendo uma quantidade aceitável de recursos computacionais. Exemplo: técnicas baseadas em computação evolutiva.
12
Histórico
três algoritmos para computação evolutiva foram desenvolvidos independentemente: algoritmos genéticos: Holland (1962), Bremermann (1962) e
Fraser (1957); programação evolutiva: Fogel (1962); estratégias evolutivas: Rechenberg (1965) e Schwefel (1965).
hoje temos também os sistemas classificadores (Booker et al., 1989) e a programação genética (Koza, 1992). Uma coletânea dos artigos seminais, a partir de 1956, pode ser encontrada em Fogel (1998).
aprofundamento no estudo: Bäck (1996), (Bäck et al., 1997), (Bäck et al., 2000a,b), Davis (1991), Fogel (1999), Goldberg (1989), Holland (1992), Kinnear (1994), Koza (1992), Michalewicz (1996), Mitchell (1996) e Schwefel (1995).
13
Histórico
Pesquisa de ponta Congressos Anuais
CEC - IEEE Congress on Evolutionary Computation GECCO - Genetic and Evolutionary Computation
Conference Revistas Especializadas
Evolutionary Computation - The MIT Press IEEE Transactions on Evolutionary Computation
buscas através da internet podem conduzir a sites interessantes e ricos em informação organizada na forma de hipertextos, mas nem todos os sites merecem esta classificação, sendo que o controle de qualidade deve ser feito pelo próprio usuário.
14
Evolução
Bases Biológicas Genética e Hereditariedade Teoria da Evolução e Seleção Natural (Darwin) Neodarwinismo
Terminologia Biológica cromossomo genes recombinação (crossover) mutação genótipo fenótipo
15
Algoritmos Evolutivos
um indivíduo pode ser visto como uma dualidade entre seu código genético (genótipo) e suas características comportamentais, fisiológicas e morfológicas (fenótipo)
Os algoritmos evolutivos não devem ser considerados “prontos para uso”, mas sim um elenco de procedimentos gerais que podem ser prontamente adaptados a cada contexto de aplicação. Basicamente, eles são modelos computacionais que recebem como entrada: uma população de indivíduos em representação
genotípica (geração inicial), que correspondem a soluções-candidatas junto a problemas específicos; e
uma função que mede a adequação relativa de cada indivíduo (fenótipo) frente aos demais (função de adequação, adaptabilidade ou fitness).
16
Algoritmos Evolutivos
Características Principais AE's trabalham com a codificação de um indivíduo, e
não com os próprios indivíduos AE's fazem busca com base em uma população de
indivíduos e não com base em um único indivíduo AE's não requerem informações detalhadas acerca das
propriedades do problema e dos indivíduos GA's utilizam regras de transição probabilística, e
não regras determinísticas Algoritmo Genético Clássico
Codificação Binária, Reprodução e Seleção Natural via algoritmo Roulette Wheel, Crossover Simples, Mutação
17
Módulos Básicos de um Algoritmo Evolutivo
Initial population
Current population
Reproduction (Pr) Crossover (Pc)
Mutation (Pm)
New population
Solution
18
Algoritmos Genéticos
Roullete Wheel Probabilidade de seleção de um cromossomo é
diretamente proporcional ao valor da função de fitness. Exemplo
N Cromossomo Fitness Graus1 0001100101010 6.0 1802 0101001010101 3.0 903 1011110100101 1.5 454 1010010101001 1.5 45
0
1
0.25
0.75
0.5
1
2
3
4
19
Algoritmos Genéticos
POPULAÇÃOINICIAL
011001010100001110011010010010010100100100100101000101001001010010100101001001001000101000101101010101001001010010111010101011111010101001010100010100
001010010111010110011010010010
010100100100100011001010100001
010010100101001001001000101000
011001010100001001010010111010
101011111010101001010100010100
00101 001011101011001 1010010010
0101001001 001000110010101 00001
010 010100101001001 001000101000
01100101 010000100101001 0111010
10 101111101010100 1010100010100
00101 101001001011001 0010111010
0101001001 000010110010101 00100
010 001000101000001 010100101001
01100101 011101000101001 0100001
10 101010001010000 1011111010101
001011010010010110010010111010010100100100001011001010100100010001000101000001010100101001011001010111010001010010100001101010100010100001011111010101
001011010010010110000010111010010100100100001011001010101100010001000101000001010100101001011001010111010001110010100001101010100010100001011111010001
PRÓXIMAGERAÇÃO
Seleção depares viaRouletteWheel
Crossover
Mutação
Determinaçãodos pontos de
Crossover
20
Algoritmos Genéticos
Problemas com o algoritmo clássico Permite a perda do melhor indivíduo Posição do gene influi na probabilidade de realizar crossover Dificuldades quando os parâmetros são números reais
Algumas estratégias de solução Codificação em strings de números reais Crossover Uniforme Mecanismos alternativos de seleção
Algoritmo Genético Modificado Geração de sub-populações por meio de operações sobre
membros da população inicial e das próprias sub-populações Reprodução e re-classificação da população intermediária Seleção para nova geração
21
Algoritmos Genéticos
POPULAÇÃOINICIAL
SUB-POPULAÇÕES
SEL
EÇ
ÃO
PRÓXIMAGERAÇÃO
POPULAÇÃOINTERMEDIÁRIA
MELHOR INDIVÍDUO
OPE
RA
ÇÕ
ES
RE
PR
OD
UÇ
ÃO
22
Sistemas Classificadores (Classifier Systems)
Sistemas Classificadores Sistemas baseados em regras e que interagem fortemente com
o ambiente. Operam em ambientes com as seguintes
características: Eventos novos e sucessivos, acompanhados de fortes doses de
ruído e dados irrelevantes Necessidade de agir de maneira contínua e em tempo real Metas implícitas ou inexatas Recompensas esparsas, obtidas depois de ações continuadas
Criados p/ absorver novas informações continuamente, Avaliando conjuntos de hipóteses competindo entre si, sem
prejudicar as capacidades já adquiridas.
23
Sistemas Classificadores
Interface de Entrada Lista de Mensagens
Lista de Classificadores
Interface de Saída
AMBIENTE
24
Sistemas Híbridos
Combinações entre sistemas computação evolutiva redes neurais sistemas fuzzy (sistemas nebulosos) agentes autônomos
Resultados sistemas fuzzy-genéticos sistemas neuro-fuzzy sistemas neuro-fuzzy-genéticos
25
Princípio de Operação: Uma Visão Pictórica
regiãopromissora
regiãopromissora
regiãonão-promissora
regiãonão-promissora
geração atualvisão geral do espaço de busca
escolha dos indivíduos que irão se reprodu-zir e aqueles que irão ser substituídos próxima geração
26
Exemplo de Aplicação: Otimização de Parâmetros de Uma Caixa Preta
sinal desaída
27
Exemplo de Aplicação: Otimização de Parâmetros de Uma Caixa Preta
representação binária: existem 16 posições possíveis paracada um dos 9 botões, de modo que 4 bits são suficientespara representar cada uma das 16 posições, na forma:
0 12
3
4
56
78910
11
12
1314
15Posição Representação Posição Representação
0 0000 8 10001 0001 9 10012 0010 10 10103 0011 11 10114 0100 12 11005 0101 13 11016 0110 14 11107 0111 15 1111
Posição atual: 0010
28
sinal desaída
001001001111011011011000000011111001
FENÓTIPO
GENÓTIPO
29
Exemplo de Aplicação: Otimização de Parâmetros de Uma Caixa Preta
cromossomo associado à solução candidata apresentada na figura :
001001001111011011011000000011111001 número de possíveis configurações de botões (soluções
candidatas): 236 68,72*109
operadores genéticos: mutação simples e crossover uniforme
valores arbitrados pelo usuário: probabilidade de bits 1 nos cromossomos da população inicial:
50% taxa de mutação: 3% taxa de crossover: 60% tipo de seleção para aplicação de crossover: bi-classista (50%
dos melhores e 10% dos piores indivíduos)
30
Exemplo de Aplicação: Otimização de Parâmetros de Uma Caixa Preta
0 10 20 30 40 500
5
10
15
20
25
Comportamento do melhor indivíduo e da média
Gerações
Sinal
de
saída
número de indivíduos testados: 1500 (dentre os possíveis68,72 109 candidatos)
tempo de simulação em um Pentium III 450 MHz: 0,38 segundos
31
Exemplo de Aplicação: Problema do Caixeiro Viajante
0 20 40 60 80 1000
10
20
30
40
50
60
70
80
90
100
Posicionamento das 100 Cidades
32
Exemplo de Aplicação: Problema do Caixeiro Viajante
Codificação representação inteira: cada cromossomo conterá todos os
números de 1 a 100 (cada número associado a uma cidade, e a ordem de aparecimento dos números no cromossomo vai indicar o percurso, sendo necessário fechar o percurso da última para a primeira cidade. Detalhe: como se trata de um percurso fechado, a origem do percurso pode ser qualquer uma das cidades, ao menos para efeito da implementação computacional.
número de possíveis percursos: 99! 9,33 10155
função de adequação (fitness): o inverso da distância associada a cada percurso.
solução ótima: desconhecida, em razão da impossibilidade de testar todas as soluções candidatas (único meio existente para se garantir a obtenção da solução ótima);
33
FENÓTIPO
GENÓTIPO
1
2
3
4
6
5
7
8
9
10
11
12
1 2 3 5 6 7 12 11 10 9 8 4
34
Exemplo de Aplicação: Problema do Caixeiro Viajante
valores arbitrados pelo usuário: tipo de mutação: sorteio de duas cidades para troca de
posição taxa de mutação: 1% tipo de crossover: OX (uma espécie de crossover de um
ponto, caracterizado pela junção de uma parte de um cromossomo com a parte de um outro, mas com a substituição das cidades repetidas pelas ausentes, na seqüência)
taxa de crossover: 60% tipo de seleção: rank ou torneio (50% dos melhores)
número de indivíduos testados: 400000 (dentre os possíveis 9,3310155 candidatos)
tempo de simulação em um Pentium III 450 MHz: 287 segundos
35
Exemplo de Aplicação: Problema do Caixeiro Viajante
0 20 40 60 80 1000
10
20
30
40
50
60
70
80
90
100
Melhor indivíduo na população inicial
0 20 40 60 80 1000
10
20
30
40
50
60
70
80
90
100
Melhor indivíduo após 500 gerações
0 20 40 60 80 1000
10
20
30
40
50
60
70
80
90
100
Melhor indivíduo após 2000 gerações
0 20 40 60 80 1000
10
20
30
40
50
60
70
80
90
100
Melhor indivíduo após 4000 gerações
36
Contraste com uma abordagem via redes neurais artificiais auto-organizáveis
500 1000 1500 2000 2500 3000 3500
200
400
600
800
1000
1200
1400
1600
1800
500 1000 1500 2000 2500 3000 3500
200
400
600
800
1000
1200
1400
1600
1800
500 1000 1500 2000 2500 3000 3500
200
400
600
800
1000
1200
1400
1600
1800
500 1000 1500 2000 2500 3000 3500
200
400
600
800
1000
1200
1400
1600
1800
500 1000 1500 2000 2500 3000 3500
200
400
600
800
1000
1200
1400
1600
1800
500 1000 1500 2000 2500 3000 3500
200
400
600
800
1000
1200
1400
1600
1800
37
Pro
ble
ma d
o Q
uad
rad
o
Mág
ico
38
Visão Geral
Compromisso nunca antes atingido entre exploração e explotação
Princípio de operação do método científico
Métodos específicos Métodos genéricos
Princípio da força bruta
39
Computação Inspirada na Natureza
Sistemas Imunológicos ArtificiaisParticle SwarmArmy AntsAutômatos CelularesVida Artificial
40
Paradigmas
No free lunchSistemas HíbridosAtuação MultidisciplinarPrincípio da Parcimônia
41
Conclusão
Todos os problemas
Problemas computáveis
Problemastratáveis
42
Grupo de Inteligência Computacional na FEEC/Unicamp
Membros do Grupo Prof. Dr. Fernando Antonio Campos Gomide Prof. Dr. Fernando José Von Zuben Prof. Dr. Márcio Luiz de Andrade Netto Prof. Dr. Ricardo Ribeiro Gudwin
Cursos de Pós-graduação Redes Neurais (I e II) Sistemas Nebulosos Computação Evolutiva Agentes Inteligentes Semiótica Computacional
Recommended