Técnicas de busca heurística (2020/1)

There ain't no such thing as a free lunch.

Bem-vindo.

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, online no Zoom.
Consultas: Online, a ser combinado, ou no discord.
Súmula: Na página do PPGC.

• Notas
• Trabalhos

• Primeiro dia de aula: 19 de agosto.
• Plano de ensino adaptado aprovado.

• Página da disciplina em 2019/1, 2017/2, 2016/1, 2014/1 e 2013/1
• Notas de aula (atualizado: 19/10/2020)

No.	Data	Tópicos	Notas pág.	Exercícios	Soluções	Leitura
1	19/08	Administrativa, Definições, Almoços de graça	9-11			R3.4.4,4.2
2	24/08	Representação e transformação.	11-15
		Busca local
3	26/08	Busca local: Vizinhanças e exemplos.	15-20
		Busca local monótona
4	31/08	Busca local monótona: Exemplos e resultados teóricos.	20-24			M5.2
5	02/09	Busca local monótona: Exemplos e resultados teóricos.	25-31			M5.2
		Busca local não-monótona
	07/09	Independência do Brasil
6	09/09	Simulated Annealing e aceitação por limite.	31-33			M5.3
7	14/09	Busca Tabu, otimização extremal, busca local guidada.	33-37	E1	S1	R5.1
8	16/09	Métodos iterados, vizinhanças múltiplas e grandes.	37-43			R5.1
		Busca por construção
9	21/09	Matroides, algoritmos gulosos e de prioridade.	43-48
10	23/09	Construção independente: Múltiplos inicios, Bubble search, GRASP.	48-50
11	28/09	Construção dependente: guloso iterado, squeaky wheel, sistemas de formigas.	50-53
		Busca por recombinação
12	30/09	Operadores de recombinação.	53-56
13	05/10	Probe, scatter search, e GRASP com religamento de caminhos.	56-59
14	07/10	Algoritmos genéticos e meméticos, algoritmos evolucionários, enxames.	59-65
	09/10			E2	S2
	12/10	Nossa Senhora Aparecida
15		Algoritmos de estimação de distribuição.	65-68
		Metodologia de projeto e avaliação experimental
16	14/10	Metodologia de projeto.	89-93
17	19/10	Analise de paisagens de otimização.	93-96
18	21/10	Complexidade empírica, distribuição de tempo e qualidade.	96-99
19	26/10	Teste de hipóteses.	99-106
	28/10	Dia do Servidor Público
		Tópicos
	02/11	Finados
20		Hibridização de heurísticas.	77-79
21		Heurísticas para para problemas contínuos.	Cáp. 5.5
22	04/11	Projeto de experimentos e escolha de parâmetros.	106-109	E3	S3
23	09/11	Escolha de parâmetros, estratégias de reinicio.
24	11/11	Aula de revisão
25	16/11	Prova		P	SP
26	18/11	Estratégias de reinício, Híper-heurísticas.	80-82
27	23/11	Heurísticas multi-objetivos.	Cáp 5.4
28	25/11	Apresentação de trabalhos.
29	30/11	Prova de recuperação.
30	02/12	Heurísticas multi-objetivos e parelas	Cáp. 5.[34]
	02/12	Término oficial das aulas.
Final da suspensão atual: 31 de dezembro

R = Rothlauf, M = Michiels.

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).

* TSP Algorithms in Action

• 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.