====== Técnicas de busca heurística (2016/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 102, [[http://mapa.ufrgs.br/index.php?verb=pan&building=44|prédio 43425]] (73).\\ **Consultas:** Seg 10.30-12.00, sala 201, [[http://mapa.ufrgs.br/index.php?verb=pan&building=44|prédio 43425]] (73).\\ **Súmula:** [[http://www.inf.ufrgs.br/ppgc/disciplinas/lista-de-disciplinas/cmp601/|Na página do PPGC]]. ===== Resultados ===== * [[2016-1-Notas|Notas]] * [[2016-1-Trabalhos|Trabalhos]] ===== Notícias ===== * Primeiro dia de aula: 29 de fevereiro. ===== Materiais ===== * Página da disciplina em [[2014-1|2014/1]] e [[2013-1|2013/1]] * {{notas-6592.pdf|Notas de aula}} (atualizado: 6/4/2016) ==== Aulas ==== ^ No. ^ Data ^ Tópicos ^ Notas pág. ^ Exercícios ^ Soluções ^ Leitura ^ | 1 | 29/02 | Administrativa, Definições, Almoços de graça, representação e transformação. | 5-12 | | | R3.4.4,4.2 | | 2 | 02/03 | Busca local: Vizinhanças. | 13-16 | | | | | 3 | 07/03 | Busca local monótona: Vizinhanças e exemplos. | 16-19 | | | | | 4 | 09/03 | Busca local monótona: Vizinhanças e exemplos. | 10-23 | | | M5.2 | | 5 | 14/03 | Busca local monótona: Segue os vencedores. Complexidade. | 23-29 | | | M5.3 | | 6 | 16/03 | Busca local não-monótona: Aceitação por limite e variantes, Simulated Annealing. | 30-34 | {{:cmp268:e01b20161.pdf|E1}} | {{:cmp268:s01b20161.pdf|S1}} | R5.1 | | 7 | 21/03 | Busca local não-monótona: otimização extremal, busca local guidada, busca tabu | 34-39 | | | R5.1 | | 8 | 23/03 | Busca local não-monótona: Métodos iterados, vizinhanças múltiplas e grandes. | 39-44 | | | R5.1 | | 9 | 28/03 | Busca por construção: Matroides, algoritmos gulosos e de prioridade. | 45-50 | | | | | 10 | 30/03 | Busca por construção: Construção independente: Múltiplos inicios, Bubble search, GRASP. | 50-59 | | | | | 11 | 04/04 | Busca por construção: Construção dependente: guloso iterado, squeaky wheel, sistemas de formigas. Busca por recombinação: introdução. | 52-59 | | | | | 12 | 06/04 | Busca por recombinação: Probe, scatter search, e GRASP com religamento de caminhos. | 59-62 | | | | | 13 | 11/04 | Busca por recombinação: Algoritmos genéticos e meméticos. | 62-70 | {{:cmp268:e02b20161.pdf|E2}} | {{:cmp268:s02b20161.pdf|S2}} | | | 14 | 13/04 | Busca por recombinação: Algorítmos genéticos e meméticos, evolucionários, enxames. | 62-74 | | | | | 15 | 18/04 | Metodologia de projeto. | | | | | | 16 | 20/04 | Discussão lista 1. Metodologia de projeto. | 91-95 | | | | | 17 | 25/04 | Avaliação experimental: Analise de paisagens de otimização. | 95-98 | | | | | 18 | 27/04 | Avaliação experimental: Complexidade empírica, distribuição de tempo e qualidade. | 99-103 | | | | | 19 | 02/05 | Avaliação experimental: Teste de hipóteses. | 103-107 | | | | | 20 | 04/05 | Avaliação experimental: Teste de hipóteses. | 108-111 | | | | | 21 | 09/05 | Avaliação experimental: Projeto de experimentos e escolha de parâmetros. | 111-114 | | | | | 22 | 11/05 | Tópicos: Hibridização e híper-heurísticas. | 75-79 | | | | | 23 | 16/05 | Tópicos: Heurísticas paralelas. | 79-83 | {{:cmp268:e03b20161.pdf|E3}} | | | | 24 | 18/05 | Tópicos: Heurísticas multi-objetivos. | 83-89 | | | | | 25 | 23/05 | Tópicos: Demais heurísticas. | | | | | | 26 | 25/05 | Revisão. | | | | | | 27 | 30/05 | **Prova** | | {{p01b.pdf|P}} | {{sp01b.pdf|S}} | | | 28 | 06/06 | Apresentação de trabalhos. | | | | | | 29 | 08/06 | Apresentação de trabalhos. | | | | | | 30 | 13/06 | Apresentação de trabalhos. | | | | | | | 20/06 | Prova de recuperação. | | | | | | | | | | | | | | | 09/07 | Término oficial das aulas. | | | | | R = Rothlauf, M = Michiels. ==== 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 ==== * {{http://www-e.uni-magdeburg.de/mertens/TSP/TSP.html|TSP Algorithms in Action}} ==== Bibliografia ==== Locations of visitors to this page