Objetivos da Unidade Curricular

Ensinar diferentes técnicas para obter (boas) soluções admissíveis para problemas combinatórios e mostrar como seleccionar a mais adequada na presença de um determinado problema.

---

Pré-requisitos

Sem pré-requisitos

---

Conteúdos

Introdução. Conceito de Heurística. Análise de heurísticas.

Heurísticas para o Problema do Caixeiro Viajante (como exemplo de vários temas):

Heurísticas de Melhoramento. Noção de Vizinhança. Vizinhanças Exponenciais de Pesquisa Polinomial.

Simulated Annealing

Introdução – breve perspectiva histórica; Procedimento básico de simulated annealing; Decisões genéricas; Decisões específicas; Exemplos. Afinações; Melhoramentos e modificações.

Algoritmos Genéticos           

Introdução, definições e conceitos básicos. Algorimo genético convencional. Operadores básicos. Estudo da convergência de um algoritmo genético. Representação e codificação das soluções.  Exemplos de aplicação

Tabu Search

Introdução – breve perspectiva histórica, Conceito de Metaheurística; Procedimento básico; Variantes. Exemplos. Melhoramentos e modificações.

Bibliotecas e Softwares de Optimização.

Introdução – breve perspectiva histórica;

Uma perspectiva unificadora. 

 

---

Descrição detalhada dos conteúdos programáticos

Componente Teórica

Introdução e Motivação.
Conceito de Heurística.
Análise: i) garantias de qualidade; ii) análise probabilística; iii) análise empírica.
  
Heurísticas para o Problema do Caixeiro Viajante (como exemplo de vários temas):
Instâncias com desigualdade triangular
Heurística do Vizinho Mais Próximo. Análise com garantias de qualidade
Heurística da Árvore de Suporte Duplicada. Análise com garantias de qualidade
Heurística de Christofides. Análise com garantias de qualidade.
Heurísticas de Inserção. Análise com garantias de qualidade.
Análise Empírica.
Heurísticas de Melhoramento. Conceito de Vizinhança.
Heurística 2-optimal e Heurísica de Lin-Kernigham.
Vizinhanças de dimensão exponencial e pesquisa polinomial: heurística de K-inserções, Heurística 2-opt combinada,
2.10 Formulação em Programação Dinâmica. Formulações Restritas como casos particulares de heurísticas de melhoramento com pesquisa polinomial e vizinhanças exponenciais.

Simulated Annealing
Introdução – breve perspectiva histórica;
Procedimento básico de simulated annealing;
Decisões genéricas;
Decisões específicas;
Exemplos – Problema do caixeiro viajante e problema da coloração dos vértices de um grafo;
Afinações;
Melhoramentos e modificações.

Algoritmos Genéticos  
Introdução aos algoritmos genéticos, definições e conceitos básicos.
Breve referência à teoria da evolução natural das espécies.
Algorimo genético convencional. Operadores básicos. Exemplo.
Noção de padrão ou arranjo. Paralelismo intrínseco e a hipótese da construção dos blocos. Teorema fundamental. Estudo da convergência de um algoritmo genético.
Representação e codificação das soluções. Restrições. Factores referentes à população. Novos operadores. Hibridização. Implementações paralelas.
Exemplos de aplicação: problema da determinação da p-coloração de peso máximo de um grafo; problema do caixeiro viajante; problema de cobertura de custo mínimo de um conjunto


Tabu Search
Introdução – breve perspectiva histórica, Conceito de Metaheurística;
Procedimento básico de tabu search;
Decisões genéricas;
Decisões específicas;
Reactive Tabu Search
Reverse Elimination Method
Outras variantes do algoritmo tabu search.
Exemplos: knapsack multidimensional, p-median e árvore de Steiner;
Afinações;
Melhoramentos e modificações.

Bibliotecas e Softwares de Optimização.
Introdução – breve perspectiva histórica;
Procedimento básico.
Exemplos – Simulated Annealing, Tabu Search, Pilot Method;
Exemplos de aplicação: Problema de pickup and delivery;
Melhoramentos e modificações, hibridização de metaheurísticas (Exemplos – Simulated Annealing, Tabu Search);
Uma perspectiva unificadora das heurísticas já mencionadas.

 

Componente Teórica-Prática

Discussão de estratégias para aplicação dos procedimentos dados
nas aulas teóricas a diversos problemas concretos.

 

Componente Prática

Utilização de heurísticas para resolver prblemas

 

---

Bibliografia

Recomendada

Folhas de apoio dos docentes.

 

Outros elementos de estudo

Davis, L. (1996). A Genetic Algorithms Tutorial. In L. Davis (Ed), Handbook of Genetic Algorithms, pp 1-101.International Thomson Computer Press;
Duin, C. and Voß, S. (1999) The pilot method. Networks 34, 181-191.
Gutenschwager, K., Niklaus, C. and Voß, S. (2004) Dispatching of an electronic monorail system: Applying meta-heuristics to an online pickup and delivery problem. Transportation Science 38, 434 - 446.
Glover, F.W. and Kochenberger, G.A. (eds.) (2003) Handbook of Metaheuristics, Kluwer, Boston [ISBN: 1-4020-7263-5];
Glover, F. and Laguna, M. (1997) Tabu Search. Kluwer, Boston;
Goldberg, D. (1989). Genetic Algorithms in Search, Optimization & Machine Learning. Addison Wesley, Reading, MA;
Lawler, E., Lenstra, J., Rinnooy Kan, A., and Shmoys, D., “The Traveling Salesman Problem: Capítulos 5 e 7.
Michalewicz, Z.and Fogel, D. (2000). How to solve it: Modern heuristics. Springer – Verlag;
Michalewicz, Z. (1992). Genetic Algorithms + Data Structures = Evolution Programs. Springer – Verlag;
Orlin, J., “Very Large Scale Neighborhood Search” (slides).
Osman, I. H. (1996). Meta-Heuristics: Theory & Applications. I. H. Osman and J. P. Kelly (eds.), Kluwer Academic Publishers;
Reeves, C. (1993). Modern Heuristic Techniques for Combinatorial Problems, pp 151-196. Oxford:Blackwell;
Voß, S. (2008) Metaheuristics. In: C.A. Floudas and P.M. Pardalos (eds.) Encyclopedia of Optimization, 2nd ed., Springer, New York (2008);
Voß, S. and Woodruff, D. (eds.) (2002) Optimization Software Class Libraries. Kluwer, Boston [ISBN: 1-4020-7002-0];

 

---

Métodos de Ensino

Aulas teóricas e teórico-práticas.

 

---

Métodos de Avaliação

Trabalho que engloba todas as componentes.
O Trabalho consiste na aplicação dos métodos a um problema específico

 

---

Língua de ensino

Português. Pode ser inglês se houver alunos estrangeiros.