Um Estudo abrangente sobre Metaheurstica, incluindo um Histrico

Seminrio - MAC 5758Prof.: Dr. Alfredo Goldman

Me. Christiane Zim Zapelini

MAC5856

AgendaObjetivoConceitoViso geralPropriedades desejveisClassificaesLevantamentoHistrico

*

Metaheurstica::ObjetivoApresentar um estudo sobre metaheursticas em um contexto mais amplo, no focando somente em mtodos ou tipos especficos, mas sim em uma viso mais abrangente sobre o assunto, na rea de Cincia da Computao

E como decorrncia disso, mostrar o levantamento histrico, uma linha de tempo desde seu surgimento at os dias atuais (etapa final) *

Metaheurstica::ConceitoEureka Arquimedes

Heurstico: encontrar, descobrir, inventar

O nome combina o prefixo grego "meta" ("mais alm", aqui no sentido de "alto nvel")

So estratgias inteligentes para projetar ou melhorar procedimentos heursticos mais gerais com alto rendimento (Mlian)

*

Metaheurstica::Viso GeralO termo metaheurstica apareceu pela primeira vez em um artigo sobre Busca Tabu de Fred Glover em 1986A partir de ento tem surgido mltiplas propostas para projetar bons procedimentos para resolver certos problemas que ampliam seu campo de aplicao, da a denominao de metaheursticaPor Sucupira trs caractersticas as diferem uma das outras:As solues inviveis, a funo objetivo e o critrio de parada*

Metaheurstica::Viso GeralO critrio para lidar com as solues inviveis dificilmente estipulado pelas metaheursticasA prtica mais comum a relaxao do problemaOu impedir a manipulao de solues inviveisA funo objetivo um problema relevante apenas nos casos em que avaliar uma soluo uma tarefa computacionalmente custosaAproximao simplificada da funo objetivo Ou estratgia para avaliar cada nova soluo a partir, se for o caso, de uma ou mais solues que tenham dado origem a elaO critrio de parada a estratgia que define o momento em que o algoritmo est concludo Fatores: tempo consumido, o nmero de iteraes realizadas, o nmero de iteraes subseqentes que no geraram uma soluo superior melhor soluo j produzida, etc.

*

Metaheurstica::Propriedades desejveisSegundo MlianFavorecem o interesse prtico e terico das metaheursticasIndicam as direes para onde os esforos devem ser seguidos para contribuir no desenvolvimento e construo de uma metaheurstica SimplesPrecisaCoerenteEfetiva*

Metaheurstica::Propriedades desejveisEficazEficienteGeralAdaptvelRobustaInterativaMltipla (diferentes solues)Autnoma (livre parmetros ou estabelecer automaticamente)*

Metaheurstica::ClassificaesClassificao Melian et alMetaheurstica de mtodos de relaxao: so procedimentos de resoluo de problemas que utilizam flexibilizaes do modelo original (ou seja, modelo com modificaes que tornam o problema mais fcil de resolver), cuja soluo fornece a soluo para o problema original

Metaheurstica para processos construtivos: baseia-se em procedimentos que tratam da obteno de uma soluo a partir da anlise e seleo paulatina dos componentes que a formam

*

Metaheurstica::ClassificaesClassificao Melian et alMetaheurstica de busca por entornos: chamamos dessa forma para qualquer mtodo que percorra espaos de busca compostos por solues levando em conta fundamentalmente, em cada passo, a vizinhana da soluo obtida na iterao anteriorMetaheurstica para mtodos evolutivos: enfocam os mtodos baseados em conjuntos de solues que evoluem sobre o espao de soluesMetaheurstica hbrida: so metaheursticas intermedirias em relao aos quatro tipos anteriores

*

Metaheurstica::ClassificaesClassificao Sucupira

Metaheursticas de Busca por Entornos

Metaheursticas Populacionais

*

Metaheurstica::ClassificaesClassificao Manuel Laguna

Trs critrios bsicos:

Uso de memria adaptativaTipo de explorao de vizinhana utilizada, eNmero de solues correntes utilizadas na prxima iterao

*

Metaheurstica::LevantamentoLevantamento por Classificao:: Mlian et alRelaxao::Exemplo

Relaxao Lagrangeana: remove algumas restries de um problema de programao linear, atribui um peso (multiplicador de Lagrange) a cada uma delas e altera a funo objetivo para penalizar as solues que seriam inviveis no problema original

*

Metaheurstica::LevantamentoLevantamento por Classificao:: Mlian et alConstrutiva::Exemplo

GRASP (Greedy Randomized Adaptive Search Procedure): cada iterao composta por uma fase construtiva e uma fase de busca por entornos*

Metaheurstica::LevantamentoLevantamento por Classificao:: Mlian et alBusca por Entornos::Exemplos

GLS (Guided Local Search)Recozimento Simulado (Simulated Annealing)Busca TabuBusca Reativa: Busca Tabu com deteco de ciclos

*

Metaheurstica::LevantamentoLevantamento por Classificao:: Mlian et alEvolutiva::Exemplos

Algoritmos genticosAlgoritmos memticos (genticos com otimizao local)Estimao de distribuioBusca dispersa e Path relinking

*

Metaheurstica::LevantamentoLevantamento por Classificao:: Mlian et alOutros/Hbridas::Exemplos

Meta-heursticas de decomposioAnt colony optimizationOtimizao extremaParticle swarm optimizationIterated local search

*

Metaheurstica::LevantamentoLevantamento por Classificao :: SucupiraBusca por Entornos::ExemplosHill-ClimbingBusca por Entornos Variveis (Variable Neighbourhood Search)Busca Gulosa por Entornos Variveis (Variable Neighbourhood Descent)BEV Reduzida (Reduced VNS)BEV Bsica (Basic VNS) e a BEV Geral (General VNS)Busca Local Guiada (Guided Local Search)

*

Metaheurstica::LevantamentoLevantamento por Classificao :: SucupiraBusca por Entornos::Exemplos

Recozimento Simulado (Simulated Annealing)Busca TabuBusca Reativa GRASP (Greedy Randomized Adaptive Search Procedures)Busca Local Iterada (Iterated Local Search)

*

Metaheurstica::LevantamentoLevantamento por Classificao :: LagunaX/Y/ZX: A (usa memria adaptativa) e M ("sem memria")Y: N (usa pesquisa sistemtica de vizinhana/selecionar prximo movimento/melhorar uma determinada soluo) e S (usa amostragem aleatria)Z: 1(se o mtodo move de uma soluo atual para a abordagem seguinte, aps cada iterao) ou P (para uma base populacional, com uma populao de tamanho P)

*

Metaheurstica::LevantamentoLevantamento por Classificao :: Laguna

*

MetaheursticaClassificao 1Classificao 2Algoritmos genticosM/S/PM/N/PBusca dispersaM/N/PA/N/PRecozimento simuladoM/S/1M/N/1Busca tabu A/N/1A/N/P

Bibliografia*BALIEIRO, Inocncio Fernandes, Tese de Doutorado: Arquimedes, Pappus, Descartes e Polya - Quatro Episdios na Histria da Heurstica. Rio Claro: IGCE . Cp. de Rio Claro-UNESP, 2004.SUCUPIRA, Igor Ribeiro, Dissertao de Mestrado: Um Estudo Emprico de Hiper-Heursticas. IME/USP, 2007.B. MELIN, J. PREZ, e J. VEGA. Metaheuristics: A Global View. Revista Iberoamericana de Inteligencia Artificial (Asociacin Espaola de Inteligencia Artificial), 2(19), 2003.NETO, Dimitrius Fraga, Monografia de Concluso de Curso: Algoritmos de Estimao de Distribuio Aplicados ao Problema do Roteamento de Veculos. Salvador: UFBA, 2008.LAGUNA, Manuel. Global Optimization and Meta-heuristics, College of Business, University of Colorado at Boulder, USA.

**