Heurísticas e Metaheurísticas
Tabela de conteúdo |
Apresentação
- Disciplina: Heurísticas e Metaheurísticas
- Professor: Thiago Ferreira de Noronha
Objetivos
Este curso visa apresentar técnicas fundamentais e avançadas para a construção de heurísticas eficientes para problemas de otimização.
Pré-requisitos
- Obrigatórios: (DCC005) AEDSIII
- Desejáveis: (DCC035) Pesquisa Operacional, Gostar de programar! (C/C++)
Material didático de apoio
Apresentação do curso (2012/1)
- - Visão geral dos problemas de otimização
- - Visão geral sobre algoritmos heurísticos
Visão geral sobre Teoria da Complexidade
- - Algoritmos e algoritmos heurísticos
- - Complexidade de algoritmos e complexidade de problemas
- - Problemas de decisão, busca e otimização
- - Classes de problemas computacionais: Classes NP, P, NP-Complete e NP-Hard
- - Heurísticas Construtivas gulosas
- - Algoritmos Aproximativos
- - Heurístícas de Transformação
- - Heurísticas de Arredondamento Aleatorizado
- - Método Científico
- - Classificação
- - Estrutura do Artigo
Heurísticas de Refinamento: Busca Local
- - Noção de vizinhança
- - Espaço de busca
- - Ótimos locais e globais
- - Simulated Annealing
- - Tabu Search
- - GRASP
- - VNS
- - ILS
- - Genetic Algorithms
- - Ant Colony Optimization
- - Particle Swarm Optimization
--Afonso Henrique Sampaio 20h12min de 28 de maio de 2012 (BRT)
Trabalho de Implementação
Utilize as instâncias em http://tinyurl.com/8xkqtcb para avaliar o seu algoritmo.
Informações sobre o formato dos arquivos estão em http://tinyurl.com/7uc8l2q.
Informe os resultados do seu algoritmo em http://tinyurl.com/847zt53.
Bibliografia
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Cliford Stein. Introduction to Algorithms, The MIT Press, 2009 (3rd ed.).
- Emile Aarts, Jan Karel Lenstra. Local Search in Combinatorial Optimization, Princeton University Press, 1997.
- Holger H. Hoos, Thomas Stützle. Stochastic Local Search Foundations and Applications, Morgan Kaufmann/Elsevier, 2004.
- El-Ghazali Talbi. Metaheuristics: From Design to Implementation, John Wiley, 2009 (1st ed.)
- Fred W. Glover, Gary A. Kochenberger. Handbook of Metaheuristics (International Series in Operations Research & Management Science)
- Edmund K. Burke, Graham Kendall. Search methodologies: introductory tutorials in optimization and decision, Springer, 2005.
- Fred Glover, Manuel Laguna. Tabu Search, Springer, 1998.
--Afonso Henrique Sampaio 19h07min de 19 de março de 2012 (BRT)
