Upload
hakhanh
View
219
Download
0
Embed Size (px)
Citation preview
Algoritmos Genéticos eAlgoritmos Genéticos eEvolucionáriosEvolucionários
DjalmaDjalma M. Falcão M. FalcãoCOPPE/UFRJPEE e NACAD [email protected]
http://www.nacad.ufrj.br/~falcao/http://www.nacad.ufrj.br/~falcao/ag/ag.htm
© D.M. Falcão 1-2
Resumo do CursoResumo do Curso
l Introdução à Computação Evolucionárial Algoritmo Genético Simples ou Canônico (AGS)l Aperfeiçoamentos no AGSl Estratégias Evolucionáriasl Programação Evolucionárial Particle Sworm Optimization (PSO)l Problemas Multiobjetivosl Exemplos de Aplicações Reais
© D.M. Falcão 1-3
Algoritmos EvolucionáriosAlgoritmos Evolucionários
“Algoritmos Evolucionários sãotécnicas estocásticas de busca eotimização, poderosas e largamenteaplicáveis, inspiradas nos mecanismosnaturais da evolução e da genética.”
© D.M. Falcão 1-4
Computação EvolucionáriaComputação Evolucionária
l Algoritmos Genéticos
l Programação Evolucionária
l Estratégias Evolucionárias
l Programação Genética
l “Particle Sworm Optimization”
(Holland, 1962)
(Fogel , 1962)
(Kennedy & Eberhart, 1995)
(Rechenberg & Schweffel, 1962)
(Koza, 1990)
© D.M. Falcão 1-5
Computação NaturalComputação Natural
INTELIGÊNCIA COMPUTACIONAL
Computação Evolucionária
Lógica FuzzyRedes NeuraisArtificiais
SimulatedAnnealing
Fractais
SistemasComplexos
ArtificialLife
© D.M. Falcão 1-6
Princípio BásicoPrincípio Básico
“Uma população de estruturascomputacionais evolui de forma talque existe uma melhora na adequaçãomédia dos indivíduos dessa populaçãoao ambiente.”
© D.M. Falcão 1-7
Exemplos de EstruturasExemplos de Estruturas
l Seqüência de símbolos ( 0010100 , ABADF , 72457)– Algoritmos Genéticos– Programação Evolucionária– Estratégias Evolucionárias– PSO
l Programas (em LISP)– Programação Genética
l Regras (if__then__)– Sistemas classificadores usando AGs
© D.M. Falcão 1-8Genótipos Fenótipos
CodificaçãoCodificação//DecodificaçãoDecodificação
l Forma compacta de representação de soluções potenciaisdo problema
l Relação bi-unívoca entre espaço de codificação(genótipos) e espaço de solução (fenótipos)
Legal
Ilegal
Legal eInviável
e viável
RegiãoViável
© D.M. Falcão 1-9
Metáfora BiológicaMetáfora Biológica
l População: conjunto de estruturas (no caso de AG,PE e EE são soluções potenciais)
l Indivíduos: cada uma das estruturasl Geração: cada passo do processo evolutivol Princípios:
– Evolução: Sobrevivência do mais apto– Genética: recombinação e mutação
© D.M. Falcão 1-10
AlgoritmoAlgoritmo Conceitual Conceitual[
Inicie a população Avalie a população inicial Faça_enquanto critério_de_parada não é satisfeito [
Selecione indivíduos da população Altere esses indivíduos para criar nova população Avalie nova população ]
]
© D.M. Falcão 1-11
Elementos Elementos do do AlgoritmoAlgoritmo
l Inicialização: aleatória (em geral)l Avaliação: função adequabilidade (fitness
function)l Seleção: escolhe melhores indivíduosl Alteração: operadores genéticos (cruzamento e
mutação)l Critério de parada: estagnação, objetivo alcançado,
tempo, número de gerações
© D.M. Falcão 1-12
AplicaçõesAplicações
l Otimização– Projetos– Tomada de decisões– Controle– Etc.
l Síntese e treinamento de redes neuraisl Regras de inferência fuzzyl Aprendizado de máquina (machine learning)
© D.M. Falcão 1-13
PorPor que CE ? que CE ?
l Ponto de vista filosófico– É o algoritmo de otimização preferido pela natureza
l Ponto de vista prático– Resolve problemas com modelos matemáticos difíceis– Interação fácil com aplicações específicas– Flexibilidade para hibridizar com outras técnicas– Segunda melhor opção para resolver qualquer
problema
© D.M. Falcão 1-14
Interação com AplicaçõesInteração com Aplicações
Soluções
Potenciais
Avaliação
Algoritmo Evolucionário Aplicação
© D.M. Falcão 1-15
OtimizaçãoOtimização
l Problema de otimização
Encontrar x∈ M tal que f (x):M→ℜ é minimizada oumaximizada
l Elementos:– Vetor de variáveis de decisão ou parâmetros: x∈ M ⊂ ℜ n
– Função objetivo: f(x)– Restrições: muitas vezes são aceitáveis apenas as soluções
contidas em um subconjunto de M definido porF = { x∈ M | gj (x) ≥ 0 ∀ j }
© D.M. Falcão 1-16
Problemas de EngenhariaProblemas de Engenharia
l Grandes dimensões
l Não-linearidades fortesl Não-diferenciabilidade e/ou não-convexidadel Funções não disponíveis ou não-tratáveis
analiticamente (simulação, tabelas)l Variáveis inteiras ou discretas (otimização
combinatória)l Multimodalidade (vários máximos e mínimos)
© D.M. Falcão 1-17
Tipos de Tipos de SoluçãoSolução
l Máximo Globall Máximo Local
l Em muitos casos práticos o que se busca é apenasuma solução “melhor”
© D.M. Falcão 1-18
Métodos de SoluçãoMétodos de Soluçãol Diretos: solução de equações não-lineares
representando condições de otimalidade
( ∇∇ f(x) = 0 )l Indiretos: seqüência de pontos gerados a partir de
uma condição inicial caminhando em direçõesassociadas a ∇∇ f(x)
l Enumerativosl Busca Aleatórial Evolucionários
© D.M. Falcão 1-19
Máximo Global
Máximo Local
f ( x1 , x2 )
© D.M. Falcão 1-20
Máximo Global
Máximo Local
© D.M. Falcão 1-21 © D.M. Falcão 1-22
Otimização CombinatóriaOtimização Combinatória
l F: conjunto discreto e finito de soluções possíveisl Pode ser resolvido por enumeração; esforço computacional
excessivo em aplicações práticasl Exemplo: caminho mínimo em redes
1
2
4
3
5
63
7
4
2
1
9
6
3 3
3
© D.M. Falcão 1-23
AplicaçõesAplicações
l Minimização de:– custos– tempo– risco
l Maximização de:– lucro– eficiência
© D.M. Falcão 1-24
Bibliografia (livros/periódicos)Bibliografia (livros/periódicos)l D. Goldberg, Genetic Algorithms in Search,
Optimization and Machine Learning, 1989.l L. Davis, Handbook of Genetic Algorithms, 1991.l Z. Michalewicz, Genetic Algorithm + Data Structure
= Evolution Programs, 2nd ed., 1994.l M. Gen and R. Cheng, Genetic Algorithms and
Engineering Design, 1997.l Evolutionary Computation ( MIT Press, 1993)l Transactions on Evolutionary Computation (IEEE,
1997)
© D.M. Falcão 1-25
Bibliografia (artigos)Bibliografia (artigos)l M. Srinivas and L.M. Patnaik, “Genetic Algorithms a Survey”,
IEEE Computer, vol. 27, no. 6, pp. 17-26, 1994.l J. Tanomaru, “Motivação, Fundamentos e Aplicações de
Algoritmos Genéticos”, II congresso Brasileiro de RedesNeurais , Curitiba, Outubro de 1995.
l T. Back, U. Hammel, and H.-P. Schweffel, “EvolutionaryComputation: Comments on the History and Current State”,IEEE Transactions on Evolutionary Computation, vol . 1, no. 1,pp. 3-17, April 1997.
l D.E. Goldberg, “Genetic and evolutionary algorithms come ofage”, Communications of the Association For ComputingMachinery, vol. 37, no. 3, pp. 113-119, March, 1994.
© D.M. Falcão 1-26
Bibliografia (Bibliografia (internetinternet))l The Hitch-Hikers’s Guide to Evolutionary Computacion:
http://alife.santafe.edu/~joke/encore/www/l The Genetic Algorithms Archives:
http://www.aic.nrl.navy.mil/galist/l Evoweb (European Network of Excellence in Evolutionary
Computing: http://evonet.dcs.napier.ac.uk/l Illinois Genetic Algorithms Laboratory (Illigal)
http://gal4.ge.uiuc.edu/illigal.home.htmll Nova Genetica: http://www.aracnet.com/~wwir/NovaGenetica/l The Genetic Programming Notebook:
http://www.geneticprogramming.com/