Upload
doanthien
View
228
Download
0
Embed Size (px)
Citation preview
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 1
Algoritmos Evolutivos – Visão Geral
1 Introdução
A computação evolutiva pode desempenhar os seguintes papéis básicos:
1. Modelo computacional para simular (reproduzir) processos evolutivos naturais;
2. Ferramenta (de otimização) para a solução de problemas.
Objetivo importante: criação, na forma de programas computacionais, de novas
manifestações de seres inteligentes (inteligência artificial) e de novas formas de
vida (vida artificial).
Habilidades envolvidas: auto-replicação, aprendizado, adaptação, controle do
meio, representação e processamento de informação altamente eficientes.
Sistemas naturais: metáfora diretora (fonte de inspiração) / utilização de
mecanismos naturais para computação.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 2
Pergunta 1: Se há uma diversidade impressionante de algoritmos para solução de
problemas, por que existe a necessidade de novas abordagens?
Resposta: Porque problemas importantes continuam sendo “difíceis” de
resolver.
Pergunta 2: Por que alguns problemas continuam sendo “difíceis” de resolver?
Resposta: 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.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 3
Figura 1 – Posicionamento dos problemas computáveis e factíveis (problemas factíveis vistos como um caso
especial dos problemas computáveis).
Problemas computáveis são aqueles para os quais é possível fornecer um
algoritmo que leve à sua solução. A complexidade dos problemas computáveis
está associada à quantidade de memória e ao tempo de processamento necessários
para se chegar à solução explorando o espaço de busca. Se uma dessas
Todos os problemas
Problemas Computáveis
Problemas
Factíveis
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 4
quantidades, ou ambas, não forem tratáveis computacionalmente, então diz-se que
o problema é infactível.
Pergunta 3: Mas e se eu simplificar ou realizar aproximações junto ao problema?
Resposta: A aplicabilidade dos algoritmos clássicos aumenta. Mas
continuarão a existir problemas importantes e “difíceis” de resolver, e
aumentará a probabilidade de se obter a resposta certa para o problema
errado.
Pergunta 4: Então, que nova abordagem poderia substituir as abordagens
clássicas?
Resposta: A computação evolutiva é uma candidata, embora não seja a única.
Com efeito, as meta-heurísticas formam um grupo mais abrangente de
métodos que constituem alternativas promissoras às abordagens clássicas.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 5
2 Meta-heurísticas
Definição: Meta-heurísticas compreendem metodologias de busca em espaços de
soluções candidatas capazes de gerenciar operadores computacionais de busca
local e de busca global, promovendo robustez e eficácia na busca de soluções
(GLOVER & KOCHENBERGER, 2002).
Estratégia: abrir mão da garantia de obtenção da solução desejada em prol da
factibilidade – afinal, uma “boa” solução, não necessariamente a ótima, é melhor
que nenhuma solução ou uma solução tomada aleatoriamente do espaço de busca.
A ideia é propor algoritmos que explorem o espaço de busca de forma eficaz,
visando localizar soluções de boa qualidade, que até podem corresponder à
solução ótima. A implementação dessa ideia se faz com base em heurísticas e
meta-heurísticas (heurísticas que comandam outras heurísticas).
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 6
As meta-heurísticas possuem um amplo repertório de possíveis aplicações, com
especial destaque para os cenários nos quais os métodos clássicos de otimização se
mostram ineficientes ou, até mesmo, infactíveis.
É preciso, porém, enfatizar que as meta-heurísticas, de uma maneira geral, NÃO
apresentam as seguintes propriedades:
Garantia de obtenção da solução ótima;
Garantia de convergência;
Garantia de custo máximo para se chegar a uma solução.
3 Conceitos importantes em computação evolutiva
Os algoritmos de computação evolutiva trabalham com um repertório (população)
de soluções candidatas que interagem entre si e competem pela permanência na
população. (Note que isto é diferente de processar várias soluções em paralelo,
como no iterated hill-climbing).
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 7
A evolução é caracterizada basicamente por um processo constituído de três
passos:
1. reprodução com herança genética;
2. introdução de variação aleatória em uma população de indivíduos;
3. aplicação da “seleção natural” para produção da próxima geração.
A variação cria diversidade na população; a diversidade é transmitida por herança
e a seleção tende a eliminar os indivíduos inaptos.
Quatro operações são fundamentais junto à população de indivíduos: (1)
reprodução; (2) variação; (3) atribuição de um valor de adaptação (fitness); e (4)
escolha de indivíduos que vão compor a próxima geração.
A disponibilidade de uma quantidade significativa de recursos computacionais é
um requisito básico para viabilizar a implementação computacional de algoritmos
evolutivos.
Formalização matemática (notação voltada para problemas de otimização):
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 8
Representação genotípica: codificação das soluções candidatas (um
subconjunto delas comporá a população a cada geração);
Representação fenotípica: interpretação do código.
Espaço de busca: tem como elementos todos os candidatos à solução do
problema;
Função de adaptação ou de fitness: atribui a cada elemento do espaço de
busca um valor de adaptação, que será usado como medida relativa de
desempenho. Representa a pressão do ambiente sobre o fenótipo dos
indivíduos.
Operadores de inicialização: produzem a primeira geração de indivíduos
(população inicial), tomando elementos do espaço de busca.
Operadores genéticos: implementam o mecanismo de introdução de
variabilidade aleatória no genótipo da população.
Operadores de seleção: implementam o mecanismo de “seleção natural”.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 9
A evolução pode ser vista como um processo de busca que, atuando nos
fenótipos, acaba por guiar os indivíduos na direção de um ótimo da superfície
de adaptação, dadas as condições iniciais e as restrições do ambiente.
Essa é a perspectiva adotada ao aplicarmos a biologia evolutiva como fonte de
inspiração para o desenvolvimento da computação evolutiva.
4 Algoritmo Evolutivo Básico (Padrão)
Tendo por base a teoria neo-Darwiniana da evolução, é possível propor um
algoritmo evolutivo básico ou padrão com as seguintes características:
Uma população de candidatos à solução (denominados indivíduos ou
cromossomos) que se reproduzem com herança genética: cada indivíduo
corresponde a uma estrutura de dados que representa ou codifica um ponto em
um espaço de busca. Esses indivíduos devem se reproduzir (de forma sexuada
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 10
ou assexuada), gerando filhos que herdam algumas das características de seu(s)
pai(s). No caso de reprodução sexuada, há troca de material genético entre dois
ou mais indivíduos pais;
Variação genética: durante o processo reprodutivo, os filhos não apenas herdam
características de seu(s) pai(s), como eles também podem sofrer mutações
genéticas;
Seleção natural: a avaliação dos indivíduos em seu ambiente – através de uma
função de avaliação ou fitness – resulta em um valor correspondente à
adaptação (qualidade) ou ao fitness deste indivíduo. A comparação dos valores
individuais de fitness resultará em uma competição pela sobrevivência e
reprodução no ambiente, havendo uma vantagem seletiva daqueles indivíduos
com valores elevados de fitness.
Quando todos os passos acima (reprodução, variação genética e seleção) tiverem
sido executados, diz-se que ocorreu uma geração.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 11
Em cada iteração, sejam P uma população contendo N indivíduos P = {x1, x2, …,
xN} (estruturas de dados), fi, i = 1,...N, o valor do fitness de cada indivíduo da
população, e pc e pm as probabilidades de crossover e mutação, respectivamente.
Sendo assim, é possível propor um algoritmo evolutivo padrão da seguinte forma:
procedimento [P] = algoritmo_evolutivo(N,pc,pm)
P’’ inicializa(N)
fit avalia(P’’)
t 1
enquanto condição_de_parada não for satisfeita faça,
P seleciona(P’’,fit)
P’ reproduz(P,fit,pc)
P’’ varia(P’,pm)
fit avalia(P’’)
t t + 1
fim enquanto
fim procedimento
O critério de parada utilizado é, geralmente, um número fixo de gerações
percorrido ou a determinação de uma solução satisfatória.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 12
Quase todos os algoritmos evolutivos podem ser implementados a partir desse
algoritmo padrão.
Figura 2 - Fluxograma de um
algoritmo evolutivo padrão.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 13
Figura 3 - Visão pictórica da força evolutiva
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 14
5 Os principais Algoritmos Evolutivos
Tipos:
Algoritmos Genéticos (AG) – Genetic Algorithms (GA)
Estratégias Evolutivas (EE) – Evolution Strategies (ES)
Programação Evolutiva (PE) – Evolutionary Programming (EP)
Programação Genética (PG) – Genetic Programming (GP)
Sistemas Classificadores (SC) – Classifier Systems (CS) (serão discutidos
posteriormente)
Quais são as diferenças entre eles?
Representação (codificação): qual estrutura de dados?
Operadores genéticos: crossover e/ou mutação?
Operadores de seleção: determinísticos ou probabilísticos?
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 15
5.1 Características Principais
Algoritmos Genéticos: formalizados por J. HOLLAND (1975) com o nome de
planos adaptativos, enfatizam a recombinação como o principal operador de busca
e aplicam mutação com baixas probabilidades (operador secundário). Operam com
representação binária de indivíduos e possuem seleção probabilística proporcional
ao fitness (implementada com um algoritmo denominado roulette wheel).
Estratégias Evolutivas: desenvolvidas por RECHENBERG (1973) e SCHWEFEL
(1975, 1977), utilizam mutações com distribuição normal para modificar vetores
reais e enfatizam a mutação (e, em segundo plano, a recombinação) como
operadores essenciais ao processo de busca tanto no espaço de busca quanto no
espaço de parâmetros. O operador de seleção é determinístico, e o tamanho da
população de pais e de filhos pode ser distinto.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 16
Programação Evolutiva: formalizada por FOGEL et al. (1966), enfatiza a mutação
e não incorpora a recombinação. Assim como as EEs, quando aplicada a
problemas de otimização de valores reais, a PE também emprega mutações com
distribuição normal e estende o processo evolutivo ao espaço de parâmetros. O
operador de seleção é probabilístico, e a maioria das aplicações atuais emprega
vetores reais como codificação, embora ela tenha sido originalmente desenvolvida
para evoluir máquinas de estados finitos.
Programação Genética: KOZA (1992) estendeu os algoritmos genéticos para o
espaço de programas computacionais. As estruturas de dados são representadas
utilizando árvores, e os operadores de crossover e mutação (adaptados para
operarem com estruturas do tipo árvore) são empregados. O processo de seleção
segue aquele dos algoritmos genéticos, ou seja, a seleção é probabilística e
proporcional ao fitness.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 17
Em resumo (tabela adaptada de BÄCK, 1994):
AG EE PE PG
Representação Cadeias binárias Vetores reais Vetores reais Árvores
Auto-adaptação Nenhuma Desvio padrão e
co-variâncias
Desvio padrão e
coeficiente de co-
relação
Nenhuma
O fitness é Valor escalonado
da função objetivo
Valor da função
objetivo
Valor
(escalonado) da
função objetivo
Valor escalonado
da função
objetivo
Mutação Operador
secundário
Principal operador Único operador Um dos
operadores
Recombinação Principal operador Diferentes
variações,
importante para a
auto-adaptação
Nenhuma Um dos
operadores
Seleção Probabilística Determinística Probabilística Probabilística
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 18
É importante salientar que todas as características acima correspondem aos
algoritmos originais (versões padrão). Entretanto, todos os algoritmos são
passíveis de variações e hibridizações de representação e operadores.
De fato, a fronteira entre todos eles está cada dia mais estreita, e a comunidade
científica já prefere descrever seus algoritmos como métodos evolutivos com
características específicas em vez de mencionar uma classe em particular.
6 Origens da Computação Evolutiva
Complementando a breve introdução histórica apresentada em aulas anteriores, os
seguintes eventos foram importantes para o estabelecimento da área.
Encontro de pesquisadores em algoritmos evolutivos na conferência Parallel
Problem Solving from Nature (PPSN), realizada em Dortmund em 1990.
Organização da primeira International Conference on Genetic Algorithms
(ICGA’91) em 1991.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 19
Chegada a um consenso para o nome da área – computação evolutiva – e o
estabelecimento de um jornal homônimo pela MIT Press em 1993.
Inclusão da área na primeira World Conference on Computational Intelligence
(WCCI) em 1994, que contemplou os seguintes temas: redes neurais artificiais,
sistemas nebulosos e algoritmos evolutivos.
7 Algumas Possíveis Aplicações da Computação Evolutiva
Aplicações de computação evolutiva podem ser encontradas em diversas áreas.
Por conveniência, elas serão divididas aqui em cinco grandes áreas não exaustivas
e não mutuamente exclusivas (BÄCK, 1994):
Planejamento
Projeto (Design)
Simulação e identificação
Controle
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 20
Classificação
7.1 Aplicações em Planejamento
Roteamento:
Caixeiro viajante: qual a melhor ordem de cidades a serem visitadas dado o
custo entre cidades?
Roteamento de veículos: generalização do caixeiro viajante para mais de um
veículo (caixeiro).
Problema de transporte: um único material deve ser distribuído para um
número de clientes partindo de mais de um depósito.
Robótica: um caminho factível, seguro e sem colisões deve ser percorrido por
um robô.
Sequenciamento de tarefas (scheduling): desenvolver um plano para executar uma
determinada quantidade de tarefas em um período de tempo, com recursos
limitados, restrições e, eventualmente, mais que um objetivo a ser cumprido.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 21
Job shop scheduling: são dadas uma planta de manufatura e (diferentes tipos de)
máquinas. Existe uma certa quantidade de trabalhos a serem executados, cada
um composto por um conjunto de tarefas. Cada tarefa requer um tipo específico
de máquina durante um intervalo de tempo, e as tarefas devem ser executadas
em uma determinada ordem. Qual seqüência (scheduling) permite que todas as
tarefas sejam executadas com custo mínimo?
Tabelas de horários – agenda (Timetabling): desenvolver uma agenda de
provas, aulas, organização de horários de trabalho etc.
Processamento computacional: alocação de processos computacionais em
diferentes estações ou processadores, políticas de substituição de memória etc.
Empacotamento (Knapsack): dado um pacote (e.g. mochila, caixa) com uma
determinada capacidade e um conjunto de itens - cada um com seu tamanho,
peso etc. - encontre o conjunto máximo de itens que pode ser acomodado no
pacote.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 22
7.2 Aplicações em Projeto
Processamento de Sinais / Filtragem: projeto de sistemas eletrônicos ou digitais
FIR e IIR que implementam uma determinada resposta em freqüência. Existem
ainda trabalhos que empregam algoritmos evolutivos no âmbito da filtragem
adaptativa.
Sistemas inteligentes: definição de arquitetura e/ou parâmetros de redes neurais
artificiais, sistemas nebulosos, autômatos celulares, sistemas imunológicos
artificiais etc.
Outras aplicações em engenharia: redes de telecomunicações, projetos estruturais,
projeto de aeronaves, projeto de estruturas espaciais, reatores químicos e circuitos
integrados, teste e diagnóstico de falhas etc.
7.3 Aplicações em Simulação e Identificação
A simulação envolve a determinação de como um sistema vai se comportar a
partir de um modelo ou projeto deste sistema.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 23
Determinação de equilíbrio de sistemas químicos.
Determinação de estruturas de proteínas.
A identificação envolve a determinação do projeto de um sistema a partir de seu
comportamento.
Determinação de pólos e zeros de um sistema, por exemplo.
7.4 Aplicações em Controle
Duas abordagens distintas: controle online e offline.
Offline: um algoritmo evolutivo é utilizado para projetar um controlador que é
depois utilizado para controlar um sistema.
Online: um algoritmo evolutivo é utilizado como uma parte ativa do
controlador.
Um aspecto interessante de um controlador evolutivo é que ele pode ser utilizado
em ambientes dinâmicos.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 24
7.5 Aplicações em Classificação
Sistemas classificadores têm sido utilizados como partes de outros sistemas como,
por exemplo, sistemas de controle.
Algoritmos evolutivos também têm sido aplicados a problemas de jogos (game
playing).
Muitas outras aplicações de AEs existem em economia, biologia, processamento
de imagens, mineração de dados etc.
8 Hill Climbing, Simulated Annealing, Algoritmos Evolutivos
“Note que em todos os métodos de subida da montanha discutidos, os cangurus
podem no máximo encontrar o topo de uma montanha perto de onde ele começou.
Não existe garantia de que esta montanha seja o Everest, ou mesmo uma montanha
alta. Vários métodos são usados para tentar encontrar o ótimo global.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 25
No algoritmo de simulated annealing, o canguru está bêbado e fica pulando
aleatoriamente por um longo tempo. Entretanto, ele vai ficando sóbrio gradualmente
e tende a subir a montanha.
Nos algoritmos genéticos, existem vários cangurus que saltam de pára-quedas em
locais aleatórios do Himalaia (se o piloto não se perdeu). Estes cangurus não sabem
que eles deveriam estar procurando pelo topo do Evereste. Entretanto, de pouco em
pouco tempo você atira nos cangurus em baixas altitudes e torce para que aqueles
sobreviventes sejam bem sucedidos e se reproduzam.”
(Trecho retirado de Sarle, 1993; citado por Michalewicz, 1996; p. 30)
9 Referências bibliográficas
BÄCK, T., FOGEL, D.B. & MICHALEWICZ, Z. (eds.) “Evolutionary Computation 1: Basic Algorithms and
Operators”, Institute of Physics Publishing, 2000a.
BÄCK, T., FOGEL, D.B. & MICHALEWICZ, Z. (eds.) “Evolutionary Computation 2: Advanced Algorithms and
Operators”, Institute of Physics Publishing, 2000b.
IA707 – Profs. Leandro de Castro/Levy Boccato/Fernando Von Zuben / Romis Attux
Tópico 3 –Algoritmos Evolutivos – Visão Geral 26
BÄCK, T., “Evolutionary Algorithms: Comparison of Approaches”, in R. Paton (ed.) Computing with
Biological Metaphors, Chapman & Hall, Capítulo 14, pp. 227-243, 1994.
FOGEL, D. B. Evolutionary Computation – Toward a New Philosophy of Machine Intelligence, 2a edição, IEEE Press,
1999.
FOGEL, L.J., OWENS, A.J. & WALSH, M.J. Artificial Intelligence through Simulated Evolution. John Wiley, 1966.
GLOVER, F. W. & KOCHENBERGER, G. A., Handbook of Metaheuristics, Kluwer Academic Publishers, 2002.
HOLLAND, J.H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1st. ed. 1975 (The
MIT Press, 2nd. ed. 1992).
KOZA, J.R. Genetic Programming: On the Programming of Computers by means of Natural Selection, MIT Press,
1992.
MICHALEWICZ, Z. “Genetic Algorithms + Data Structures = Evolution Programs”, 3rd edition, Springer,
1996.
RECHENBERG, I. Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution.
Frommann-Holzboog Verlag, 1973.
SARLE, W. (1993), Kangoroos, article posted on comp.ai.neural-nets on the 1st September.
SCHWEFEL, H.-P. Evolutionsstrategie und numerische Optimierung. Tese de Doutorado, Technische Universität
Berlin, 1975.
SCHWEFEL, H.-P. Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie. Basel:
Birkhäuser, 1977.