Ementa:
Técnicas para solução de problemas de otimização combinatória: Heurísticas clássicas, Meta-heurísticas. Principais meta-heurísticas: Recozimento Simulado (Simulated Annealing), Busca Tabu, Busca Local Iterada (Iterated Local Search – ILS), Busca em Vizinhança Variável (Variable Neighborhood Search – VNS), Procedimentos de Busca Adaptativa Aleatória e Gulosa (Greedy Randomized Adaptive Search Procedures – GRASP), Algoritmos Genéticos, Colônia de Formigas, Busca Dispersa (Scatter Search).
Conteúdo programático:
-
Introdução aos Métodos aproximados ou heurísticos: justificativa de uso a problemas combinatórios.
-
Métodos de Busca Local: Métodos Construtivos. Métodos de refinamento: Representação e avaliação de uma solução. Noção de vizinhança. Método da Descida. Método Randômico de Descida. Primeiro de Melhora.
-
Algoritmos meta-heurísticos: histórico, fundamentação, diferenças entre meta-heurísticas e heurísticas convencionais.
-
Meta-heurísticas de Busca Local: Simulated Annealing. Busca Tabu. Greedy Randomized Adaptive Search Procedures (GRASP). Iterated Local Search. Método de Pesquisa em Vizinhança Variável (VNS).
-
Meta-heurísticas de Busca Populacional: Algoritmos Genéticos. Colônia de Formigas. Scatter Search.
-
Aplicações de meta-heurísticas a problemas clássicos de otimização combinatória: Caixeiro Viajante, Mochila, Programação de horários, Roteamento de Veículos, Alocação e sequenciamento de tarefas, Localização, dentre outros.