Índice
-
- INF05010: Otimização combinatória
- INF05016/CMP 588: Algoritmos avançados
- CMP612: Algorithms
- CMP268: Técnicas de busca heurística
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, TBD..
Consultas: A ser combinado.
Súmula: Na página do PPGC e no plano de ensino adaptado.
No. | Data | Tópicos | Notas cáp. | Exercícios | Soluções | Leitura | Prazos |
---|---|---|---|---|---|---|---|
1 | 15/05 | Administrativa, Definições, Almoços de graça | 1.1-1.2 | R3.4.4,4.2 | |||
2 | 17/05 | Representação e transformação. | 1.3-1.5 | R4.2 | |||
Busca local | |||||||
3 | 22/05 | Busca local: Vizinhanças e exemplos. | 2.1 | R4.3.2,ZBB6.1 | |||
Busca local monótona | |||||||
4 | 24/05 | Busca local: Vizinhanças e exemplos. | 2.1 | R4.3.2,ZBB6.1 | |||
5 | 29/05 | Busca local monótona: Exemplos e resultados teóricos. | 2.2 | L1 | S1 | M5.2 | |
Busca local não-monótona | |||||||
6 | 31/05 | Busca local monótona: Exemplos e resultados teóricos. | 2.2 | M5.2 | |||
7 | 05/06 | Simulated Annealing e aceitação por limite. | 2.3 | M5.3 | |||
8 | 07/06 | Busca Tabu, otimização extremal, busca local guidada. | 2.3 | R5.1 | |||
9 | 12/06 | Métodos iterados, vizinhanças múltiplas e grandes. | 2.4 | R5.1 | |||
Busca por construção | |||||||
10 | 14/06 | Matroides, algoritmos gulosos e de prioridade. | 3.1 | PS12 | |||
11 | 19/06 | Construção independente: Múltiplos inicios, Bubble search, GRASP. | 3.2 | ZBB5.1 | |||
12 | 21/06 | Construção dependente: guloso iterado, squeaky wheel, sistemas de formigas. | 3.3 | ZBB5.2 | |||
Busca por recombinação | |||||||
13 | 26/06 | Operadores de recombinação, Probe, scatter search, e GRASP com religamento de caminhos. | 4, 4.4 | R4.3.3, ZBB7.2 | |||
14 | 27/06 | Algoritmos genéticos e meméticos, algoritmos evolucionários, enxames. | 4.5-4.7 | ZBB7.1,R5.2.1 | |||
15 | 03/07 | Algoritmos de estimação de distribuição. | 4.8 | R5.2.2 | |||
Metodologia de projeto e avaliação experimental | |||||||
16 | 05/07 | Metodologia de projeto. | 6.1 | ||||
17 | 10/07 | Analise de paisagens de otimização. | 6.2 | L2 | S2 | HS5 | |
18 | 12/07 | Complexidade empírica, distribuição de tempo e qualidade. | 6.3 | HS4 | |||
10 | 17/07 | Estratégias de reinício, Teste de hipóteses. | 6.3 | ||||
20 | 19/07 | Teste de hipóteses. Projeto de experimentos e escolha de parâmetros. | 6.3 | ||||
21 | 24/07 | Configuração automática de algoritmos. | 6.3 | ||||
Tópicos | |||||||
22 | 26/07 | Híper-heurísticas. Hibridização de heurísticas. | 5.1 | ||||
23 | 31/07 | Hibridização de heurísticas. Heurísticas para problemas contínuos. | 5.5 | ||||
24 | 02/08 | Heurísticas para problemas contínuos. | 5.6 | ||||
25 | 07/08 | Heurísticas para problemas contínuos. | 5.6 | L3 | S3 | ||
26 | 09/08 | Aula de revisão | |||||
27 | 14/08 | Prova | P | S | |||
28 | 16/08 | Heurísticas multi-objetivos e paralelas, e para problemas estocásticos. | 5.2-5.4 | ||||
29 | 21/08 | Apresentação de trabalhos. | |||||
30 | 23/08 | Apresentação de trabalhos. | |||||
Provas de recuperação. | |||||||
16/09 | Término oficial das aulas. |
R = Rothlauf, M = Michiels, ZBB = Zäpfl. et al., HS= Hoos & Stützle
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).