Métodos Heurísticos

Conhecimentos de Base Recomendados

Otimização, algoritmos, 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 teóricas 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 para a 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. São também dados 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. 

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. Relação com métodos exatos

2. Modelação de problemas de otimização

2.1. Definição do espaço de decisão

2.2. Representação das soluções

2.3. Avaliação da qualidade das soluções

2.4. Regras de construção e estruturas de vizinhança

2.5. Tratamento de restrições

3. Heurísticas e meta-heurísticas

3.1. Construção gulosa, GRASP, procura em feixe, algoritmos de colónias de formigas

3.2. Trepa colinas, simulated annealing, procura tabu, procura local iterada

3.3. Algoritmos evolutivos e algoritmos de enxames de partículas

3.4. Algoritmos de estimação de distribuição

4. Questões de desempenho

4.1. Dificuldade de problemas

4.2. Noções de desempenho

4.3. Sintonização e adaptação de parâmetros

4.4. Benchmarking.

Docente(s) responsável(eis)

Carlos Manuel Mira da Fonseca

Métodos de Avaliação

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

Bibliografia

Rafael Martí, Panos M. Pardalos, Mauricio G. C. Resende, Handbook of Heuristics, Springer, 2018.

Éric D. Taillard, Design of Heuristic Algorithms for Hard Optimization, Springer, 2023. Open access.

Mauricio G. C. Resende and Celso C. Ribeiro, Optimization by GRASP, Springer, 2016.

Marco Dorigo and Thomas Stützle, Ant Colony Optimization, MIT Press, 2004.

Holger H. Hoos and Thomas Stützle, Stochastic Local Search, Morgan Kaufmann, 2004.

D.-Z. Du, K.-I Ko, and X. Hu, Design and Analysis of Approximation Algorithms, Springer, 2012.

A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing, 2^nd ed., Springer, 2015.

S. S. Skiena, The Algorithm Design Manual, 3^rd ed., Springer, 2020.

A. Laaksonen, Guide to Competitive Programming, 3^rd ed., Springer, 2024.