Índice
-
- INF 5010: Otimização combinatória
- INF 5016: Algoritmos avançados
- INF 5023: Técnicas de busca heurística.
Ferramentas de Utilizador
Barra Lateral
cmp268:homepage
Tabela de Conteúdos
Técnicas de busca heurística (2025/2)
There ain't no such thing as a free lunch.
Bem-vindo.
Informações gerais
Carga horária: 60 h (em 30 aulas de 2h)
Créditos: 4
Súmula: Introduction to heuristic and meta-heuristic search methods: design, calibration, evaluation, and comparison. Case studies of applications of heuristic search methods.
Turma: U.
Horário/Sala: Seg/Qua 13.30, 106/43413.
Consultas: A ser combinado.
Súmula: Na página do PPGC e no plano de ensino adaptado.
Resultados
Notícias
- Primeiro dia de aula: 11 de agosto.
Materiais
- Notas de aula (atualizado: 14/01/2022)
Aulas
| No. | Data | Tópicos | Notas cáp. | Exercícios | Soluções | Leitura | Prazos |
|---|---|---|---|---|---|---|---|
| 1 | 11/08 | Administrativa, Definições, Almoços de graça | 1.1-1.2 | R3.4.4,4.2 | |||
| 2 | 13/08 | Representação e transformação. | 1.3-1.5 | R4.2 | |||
| Busca local | |||||||
| 3 | 18/08 | Busca local: Vizinhanças e exemplos. | 2.1 | R4.3.2,ZBB6.1 | |||
| Busca local monótona | |||||||
| 4 | 20/08 | Busca local: Vizinhanças e exemplos. | 2.1 | R4.3.2,ZBB6.1 | |||
| 5 | 25/08 | Busca local monótona: Exemplos e resultados teóricos. | 2.2 | M5.2 | |||
| 6 | 27/08 | Busca local monótona: Resultados teóricos. | 2.2 | M5.2 | |||
| 7 | 01/09 | Busca local monótona: Resultados teóricos. | 2.2 | M5.2 | |||
| Busca local não-monótona | |||||||
| 8 | 03/09 | Variantes de aceitação por limite, algoritmo Metropolis e Simulated Annealing | 2.3 | M5.3 | |||
| 9 | 08/09 | Busca Tabu, otimização extremal, busca local guidada. | 2.3 | L1 | R5.1 | ||
| 10 | 10/09 | Métodos iterados, vizinhanças múltiplas e grandes. | 2.4 | R5.1 | |||
| Busca por construção | |||||||
| 11 | 15/09 | Laboratório Busca Local (102, 43425). | |||||
| 17/09 | Sem aula | ||||||
| 12 | 22/09 | Matroides, algoritmos gulosos e de prioridade. | 3.1 | PS12 | |||
| 13 | 24/09 | Construção independente: Múltiplos inicios, Bubble search, GRASP. | 3.2 | ZBB5.1 | |||
| 14 | 29/09 | Construção dependente: guloso iterado, squeaky wheel, sistemas de formigas. | 3.3 | L2 | ZBB5.2 | ||
| Busca por recombinação | |||||||
| 15 | 01/10 | Operadores de recombinação, Religamento de caminhos (RL), Probe. | 4, 4.4 | R4.3.3, ZBB7.2 | |||
| 16 | 06/10 | Laboratório Algoritmos Construtivos (104, 43425). | |||||
| 17 | 08/10 | Scatter search, GRASP/RL, alg. genéticos, meméticos, evolucionários, enxames. | 4.5-4.7 | ZBB7.1,R5.2.1 | |||
| 18 | 13/10 | Algoritmos de estimação de distribuição. | 4.8 | R5.2.2 | |||
| 19 | 15/10 | CMA-ES. | |||||
| 20/10 | Semana Acadêmica | ||||||
| 22/10 | Semana Acadêmica | ||||||
| 27/10 | Dia do Servidor Público | ||||||
| Metodologia de projeto e avaliação experimental | |||||||
| 20 | 29/10 | Metodologia de projeto. | 6.1 | ||||
| 21 | 03/11 | Analise de paisagens de otimização. | 6.2 | HS5 | |||
| 22 | 05/11 | Complexidade empírica, distribuição de tempo e qualidade. | 6.3 | HS4 | |||
| 23 | 10/11 | Estratégias de reinício, Teste de hipóteses. | 6.3 | ||||
| 24 | 12/11 | Teste de hipóteses. Projeto de experimentos e escolha de parâmetros (sala 107/43425). | 6.3 | ||||
| 25 | 17/11 | Configuração automática de algoritmos (sala TBD). | 6.3 | ||||
| Tópicos | |||||||
| 26 | 19/11 | Híper-heurísticas. Hibridização de heurísticas. Heurísticas para problemas contínuos. | 5.[156] | ||||
| 27 | 24/11 | Aula de revisão | |||||
| 28 | 26/11 | Prova | |||||
| 29 | 01/12 | Heurísticas multi-objetivos e paralelas, e para problemas estocásticos. | 5.2-5.4 | ||||
| 30 | 03/12 | Apresentação de trabalhos. | |||||
| 10/12 | Provas de recuperação. | ||||||
| 20/12 | Término oficial das aulas. | ||||||
R = Rothlauf, M = Michiels, ZBB = Zäpfl. et al., HS= Hoos & Stützle
Avaliação
A nota final é composta pela nota obtida na solução dos exercícios (1/3), a nota do projeto (1/3) e a nota da prova (1/3).
Ferramentas
Bibliografia
- El-Ghazali Talbi. Metaheuristics. From Design to Implementation. Wiley, 2009.
- Zbigniew Michalewicz and David B. Fogel. How to Solve It: Modern Heuristics. Springer, 2nd edition, 2004. INF 65.012.122 M622h.
- Sean Luke. Essentials of Metaheuristics. lulu.com, 2011.
- Emile Aarts and Jan Karel Lenstra, editors. Local Search in Combinatorial Optimization. Princeton University Press, 2003.
- Wil Michiels, Emile Aarts, and Jan Korst. Theoretical Aspects of Local Search. Springer, 2007. INF: Recurso eletrônico.
- David E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989. INF 681.3.011 G618g.
- Gabriel Luque and Enrique Alba. Parallel Genetic Algorithms: Theory and Real World Applications. Springer, 2011. INF: Recurso eletrônico.
- Xin-She Yang. Nature-Inspired Metaheuristic Algorithms. Luniver Press, 2nd edition, 2010.
- Agoston E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. Springer, 2008. INF 681.3.011 E34i.
- Teofile F. Gonzalez, editor. Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall, 2nd edition, 2018.
- Holger H. Hoos and Thomas Stützle. Stochastic Local Search : Foundations & Applications. Morgan Kaufmann, 2004.
- Franz Rothlauf. Design of Modern Heuristics: Principles and Application. Springer, 2011. INF: Recurso eletrônico.
- Ibrahim H. Osman and James P. Kelly. Meta-heuristics: Theory and Applications. Kluwer, 1996. INF 65.012.122 M587.
- Stefan Edelkamp and Stefan Schroeder. Heuristic Search: Theory and Applications. Morgan Kaufmann, 2011.
- Michel Gendreau and Jean-Yves Potvin. Handbook of Metaheuristics. Springer, 2nd edition, 2011. INF: Recurso eletrônico.
- Günter Zäpfel, Roland Braune, and Michael Bögl. Metaheuristic search concepts. Springer, 2010. INF: Recurso eletrônico.
- Warren B. Powell. Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley, 2nd edition, 2011.
- M. Birattari. The Problem of Tuning Metaheuristics. IOS Press, 2005.
- Christian Blum, Maria José Blesa Aguilera, Andrea Roli, and Michael Sampels, editors. Hybrid Metaheuristics : An Emerging Approach to Optimization. Springer, 2008. INF: Recurso eletrônico. (doi:10.1007/978-3-540-78295-7)
- Carlos Cotta, Marc Sevaux, and Kenneth Sörensen, editors. Adaptive and Multilevel Metaheuristics. Springer, 2008. INF: Recurso eletrônico.
- Fred Glover and Gary A. Kochenberger, editors. Handbook of metaheuristics. Kluwer, 2002. INF 65.012.122 H237.
- Vittorio Maniezzo, Thomas Stützle, and Stefan Voß, editors. Matheuristics. Springer, 2009. INF: Recurso eletrônico.
- J. Dréo, A. Pétrowski, P. Siarry, and E. Taillard. Metaheuristics for hard optimization. Springer, 2006.
