====== Técnicas de busca heurística (2020/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, online no [[http://zoom.us|Zoom]].\\ **Consultas:** Online, a ser combinado, ou no [[https://discord.gg/Yes8xT|discord]].\\ **Súmula:** [[http://www.inf.ufrgs.br/ppgc/en/courses/list/cmp268|Na página do PPGC]]. ===== Resultados ===== * [[2020-1-Notas|Notas]] * [[2020-1-Trabalhos|Trabalhos]] ===== Notícias ===== * Primeiro dia de aula: 19 de agosto. * [[http://www.inf.ufrgs.br/~mrpritt/msc/pea.pdf|Plano de ensino adaptado]] aprovado. ===== Materiais ===== * Página da disciplina em [[2019-1|2019/1]], [[2017-2|2017/2]], [[2016-1|2016/1]], [[2014-1|2014/1]] e [[2013-1|2013/1]] * {{notas-11158.pdf|Notas de aula}} (atualizado: 19/10/2020) ==== Aulas ==== ^ No. ^ Data ^ Tópicos ^ Notas pág. ^ Exercícios ^ Soluções ^ Leitura ^ | 1 | 19/08 | [[:cmp268:l01|Administrativa, Definições, Almoços de graça]] | 9-11 | | | R3.4.4,4.2 | | 2 | 24/08 | [[:cmp268:l02|Representação e transformação.]] | 11-15 | | | | | || ** Busca local ** ||||| | 3 | 26/08 | [[:cmp268:l03|Busca local: Vizinhanças e exemplos.]] | 15-20 | | | | | || ** Busca local monótona ** ||||| | 4 | 31/08 | [[:cmp268:l04|Busca local monótona: Exemplos e resultados teóricos.]] | 20-24 | | | M5.2 | | 5 | 02/09 | [[:cmp268:l05|Busca local monótona: Exemplos e resultados teóricos.]] | 25-31 | | | M5.2 | | || ** Busca local não-monótona ** ||||| | | 07/09 | [[wppt>Independência do Brasil]] ||||| | 6 | 09/09 | [[:cmp268:l06|Simulated Annealing e aceitação por limite.]] | 31-33 | | | M5.3 | | 7 | 14/09 | [[:cmp268:l07|Busca Tabu, otimização extremal, busca local guidada.]] | 33-37 | {{e0120201.pdf|E1}} | {{s0120201a.pdf|S1}} | R5.1 | | 8 | 16/09 | [[:cmp268:l08|Métodos iterados, vizinhanças múltiplas e grandes.]] | 37-43 | | | R5.1 | | || ** Busca por construção ** ||||| | 9 | 21/09 | [[:cmp268:l09|Matroides, algoritmos gulosos e de prioridade.]] | 43-48 | | | | | 10 | 23/09 | [[:cmp268:l10|Construção independente: Múltiplos inicios, Bubble search, GRASP.]] | 48-50 | | | | | 11 | 28/09 | [[:cmp268:l11|Construção dependente: guloso iterado, squeaky wheel, sistemas de formigas.]] | 50-53 | | | | | || ** Busca por recombinação ** ||||| | 12 | 30/09 | [[:cmp268:l12|Operadores de recombinação.]] | 53-56 | | | | | 13 | 05/10 | [[:cmp268:l13|Probe, scatter search, e GRASP com religamento de caminhos.]] | 56-59 | | | | | 14 | 07/10 | [[:cmp268:l14|Algoritmos genéticos e meméticos, algoritmos evolucionários, enxames.]] | 59-65 | | | | | | 09/10 | | | {{e0220201.pdf|E2}} | {{s0220201.pdf|S2}} | | | | 12/10 | [[wppt>Nossa Senhora Aparecida]] ||||| | 15 | | [[:cmp268:l15|Algoritmos de estimação de distribuição.]] | 65-68 | | | | | || ** Metodologia de projeto e avaliação experimental ** ||||| | 16 | 14/10 | [[:cmp268:l16|Metodologia de projeto.]] | 89-93 | | | | | 17 | 19/10 | [[:cmp268:l17|Analise de paisagens de otimização.]] | 93-96 | | | | | 18 | 21/10 | [[:cmp268:l18|Complexidade empírica, distribuição de tempo e qualidade.]] | 96-99 | | | | | 19 | 26/10 | [[:cmp268:l19|Teste de hipóteses.]] | 99-106 | | | | | | 28/10 | [[wppt>Dia do Servidor Público]] ||||| | || ** Tópicos ** ||||| | | 02/11 | [[wppt>Finados]] ||||| | 20 | | [[:cmp268:l20|Hibridização de heurísticas.]] | 77-79 | | | | | 21 | | [[:cmp268:l21|Heurísticas para para problemas contínuos.]] | Cáp. 5.5 | | | | | 22 | 04/11 | [[:cmp268:l22|Projeto de experimentos e escolha de parâmetros.]] | 106-109 | {{e0320201.pdf|E3}} | {{s0320201.pdf|S3}} | | | 23 | 09/11 | [[:cmp268:l23|Escolha de parâmetros, estratégias de reinicio.]] | | | | | | 24 | 11/11 | Aula de revisão | | | | | | 25 | 16/11 | ** Prova ** | | {{p20201.pdf|P}} | {{sp20201.pdf|SP}} | | | 26 | 18/11 | [[:cmp268:l26|Estratégias de reinício, Híper-heurísticas.]] | 80-82 | | | | | 27 | 23/11 | [[:cmp268:l27|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 | [[:cmp268:l30|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. ==== 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 ==== * {{http://www-e.uni-magdeburg.de/mertens/TSP/TSP.html|TSP Algorithms in Action}} ==== Bibliografia ====