Í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:2014-1
Tabela de Conteúdos
Técnicas de busca heurística (2014/1)
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, sala 112, prédio 43425.
Consultas: Seg 10.30-12.00, sala 2012, prédio 43425.
Súmula: Na página do PPGC.
Resultados
Notícias
- Cronograma nova, prova (a ser confirmando) dia 24/6, 13.00, sala 220 (Conselho).
Materiais
- Página da disciplina em 2013/1
- Notas de aula (atualizado: 17/4/2016)
- Mais informação sobre o trabalho disponível.
Aulas
| No. | Data | Tópicos | Notas pág. | Exercícios | Soluções | Leitura |
|---|---|---|---|---|---|---|
| 1 | 24/02 | Administrativa, Definições, Almoços de graça, representação e transformação. | 5-11 | R3.4.4,4.2 | ||
| 03/03 | Dia não letivo | |||||
| 05/03 | Dia não letivo | |||||
| 2 | 10/03 | Busca local: Vizinhanças. | 13-16 | |||
| 3 | 12/03 | Busca local monótona: Vizinhanças e exemplos. | 17-24 | |||
| 4 | 17/03 | Busca local monótona: Segue os vencedores. Complexidade. | 25-29 | |||
| 5 | 19/03 | Busca local não-monótona: Simulated Annealing e aceitação por limite. | 30-34 | |||
| 6 | 24/03 | Busca local não-monótona: Simulated Annealing e aceitação por limite, Busca Tabu. | 34-36 | |||
| 7 | 26/03 | Busca local não-monótona: Busca Tabu, otimização extremal, busca local guidada | 34-38 | E11) | S1 | |
| 8 | 31/03 | Busca local não-monótona: Métodos iterados, vizinhanças múltiplas e grandes. | 38-43 | |||
| 9 | 02/04 | Busca por construção: Matroides, algoritmos gulosos e de prioridade. | 45-50 | |||
| 10 | 07/04 | Busca por construção: Construção independente: Múltiplos inicios, Bubble search, GRASP. | 50-52 | |||
| 11 | 09/04 | Busca por construção: Construçao dependente: guloso iterado, squeaky wheel, sistemas de formigas. | 52-54 | |||
| 12 | 14/04 | Busca por recombinação: Operadores de recombinação genéricos, religamento de caminhos, exemplos. | 55-59 | Prazo E1: 14/04 | ||
| 13 | 16/04 | Busca por recombinação: Probe, scatter search, e GRASP com religamento de caminhos. | 59-62 | |||
| 21/04 | Tiradentes | |||||
| 14 | 23/04 | Busca por recombinação: Algoritmos genéticos e meméticos. | 62-70 | E2 | S2 | |
| 15 | 28/04 | Busca por recombinação: Algoritmos evolucionários, enxames. | 70-74 | |||
| 16 | 30/04 | Metodologia de projeto. | 91-95 | |||
| 17 | 05/05 | Avaliação experimental: Analise de paisagens de otimização. | 95-98 | Prazo E2: 07/05 | ||
| 18 | 07/05 | Avaliação experimental: Complexidade empírica, distribuição de tempo e qualidade. | 99-103 | |||
| 12/05 | Semana acadêmica | |||||
| 14/05 | Semana acadêmica | |||||
| 19 | 19/05 | Avaliação experimental: Teste de hipóteses. | 103-107 | |||
| 20 | 21/05 | Avaliação experimental: Teste de hipóteses. | 108-111 | |||
| 21 | 26/05 | Avaliação experimental: Projeto de experimentos e escolha de parâmetros. | 111-114 | |||
| 22 | 28/05 | Tópicos: Hibridização e híper-heurísticas. | 75-79 | |||
| 23 | 02/06 | Tópicos: Heurísticas paralelas. | 79-83 | E3 | S3 | |
| 24 | 04/06 | Tópicos: Heurísticas multi-objetivos. | 83-89 | |||
| 25 | 09/06 | Tópicos: Demais heurísticas. | ||||
| 26 | 11/06 | Revisão para prova. | ||||
| 16/06 | Sem aula | |||||
| 18/06 | Dia não-letivo | Prazo E3: 20/06 | ||||
| 27 | 24/06 | Prova as 13.00 (a ser confirmado, 43412(65) - sala 220 (Sala do conselho) | P | S | ||
| 25/06 | Dia não letivo | |||||
| 30/06 | Dia não letivo | |||||
| 28,29 | 01/07 | Apresentação de trabalhos: 10.30 e 13.30 (Sala: 43412(65): 214) | ||||
| 30 | 02/07 | Apresentação de trabalhos: 13.30 | ||||
| 07/07 | Prova de recuperação. | |||||
| 20/07 | Término oficial das aulas. |
R = Rothlauf.
Avaliação
A nota final é composto pela nota obtido 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, 2007.
- 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.
- 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.
