Métodos Heurísticos

Conhecimentos de Base Recomendados

Otimização, programação, probabilidades e estatística, inglês.

Métodos de Ensino

O ensino está organizado em duas componentes complementares, teórica e prática. As aulas teóricas (T) destinam-se sobretudo à exposição da matéria pelo docente e ao esclarecimento de dúvidas de interesse geral para a turma. As aulas práticas (PL) visam consolidar os conceitos apresentados nas aulas T através da realização de exercícios e do estudo de casos simplificados. É ainda proposto e avaliado um projeto prático envolvendo a modelação e a resolução heurística de problemas do foro da investigação operacional.

Resultados de Aprendizagem

Pretende-se dotar os estudantes da capacidade de delinear, de forma sistemática, abordagens heurísticas conducentes à resolução prática de problemas concretos, aplicá-las e avaliar os resultados obtidos, com ênfase em problemas de otimização combinatória e/ou numérica. Pretende-se ainda dar a conhecer alguns dos métodos heurísticos mais relevantes na atualidade e suas aplicações mais bem sucedidas, focando sobretudo os princípios heurísticos que implementam, aspetos do seu desempenho, e ainda questões relacionadas com a sua utilização prática. Finalmente, pretende-se evidenciar a relação simbiótica entre os métodos heurísticos e a aprendizagem automática.

Estágio(s)

Não

Programa

1. Introdução
1.1. Resolução de problemas
1.2. Heurísticas construtivas e de melhoramento
1.3. Princípios heurísticos: analogia, indução, decomposição, intensificação, diversificação, recombinação, melhoramento guloso, aleatorização, degradação temporária, reinicialização.
1.4. Relação com métodos exatos
2. Formulação de problemas de otimização
2.1. Definição do espaço de procura
2.2. Representação das soluções
2.3. Avaliação da qualidade das soluções
2.4. Estruturas de vizinhança
2.5. Tratamento de restrições
3. Heurísticas e meta-heurísticas
3.1. Simulated annealing, procura tabu, procura local iterada
3.2. Algoritmos evolutivos e de enxames de partículas
3.3. Algoritmos de colónias de formigas
3.4. GRASP
3.5. Algoritmos de estimação de distribuição
4. Questões de desempenho
4.1. Dificuldade de problems
4.2. Noções de desempenho
4.3. Sintonização de parâmetros
4.4. Adaptação de parâmetros, auto-adaptação e aprendizagem
4.5. Hiper-heurísticas
4.6. Desconstrução de heurísticas.

Métodos de Avaliação

Avaliação
Projecto: 35.0%
Exame: 65.0%

Bibliografia

George Polya, How to Solve It: A New Aspect of Mathematical Method. Princeton University Press, 1945. Reprinted by Penguin Books, 1990.
Fred Glover and Manuel Laguna,Tabu Search, Kluwer, 1997.
Thomas Bäck, David B Fogel, and Zbigniew Michalewicz (eds.), Evolutionary Computation 1 - Basic Algorithms and Operators, CRC Press, 2000.
Thomas Bäck, David B Fogel, and Zbigniew Michalewicz (eds.), Evolutionary Computation 2 - Advanced Algorithms and Operators, CRC Press, 2000.
Marco Dorigo and Thomas Stützle, Ant Colony Optimization, MIT Press, 2004.
Holger H. Hoos and Thomas Stützle, Stochastic Local Search, Morgan Kaufmann, 2014.
Mauricio G. C. Resende and Celso C. Ribeiro, Optimization by GRASP, Springer, 2016.
Rafael Martí, Panos M. Pardalos, Mauricio G. C. Resende, Handbook of Heuristics, Springer, 2018.