Pesquisa e Optimização
Código
8289
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Informática
Créditos
6.0
Professor responsável
Pedro Manuel Corrêa Calvente Barahona
Horas semanais
4
Língua de ensino
Português
Objectivos
Conhecimento:
- Problemas de satisfação de restrições e de optimização.
- Tipos de restrições (simples / globais).
- Propagação de restrições e tipos de consistência.
- Algoritmos completos e incompletos para satisfação/optimização.
- Heurísticas e meta-heurísticas.
Aptidões:
- Modelação de problemas de satisfação/optimização de restrições.
- Escolha das restrições mais adequadas.
- Escolha dos algoritmos mais apropriados.
- Escolha das heurísticas mais eficientes.
Competências:
- Compreensão de especificações informais (eventualmente incompletas).
- Identificação de problemas de restrições.
- Análise e explicação de resultados.
- Capacidade de pesquisa de literatura.
Pré-requisitos
Os alunos devem ter conhecimentos básicos de
- Programação, nomeadamente programação orientada por objectos,
- Inteligência Artificial
Conteúdo
1. Problemas de Decisão e Otimização
1.1. Exemplos.
1.2.Complexidade.
2. Resolução Completa de Restrições - Pesquisa com Retrocesso.
2.1.Tipos de restrições.
2.1.1. Aritméticas.
2.1.2. Disjuntivas.
2.1.3. Reificadas.
2.1.4. Globais.
2.2. Redes de restrições
2.2.1. Consistências locais (nó, arco, domínio/limites).
2.2.2. Consistências não-locais (caminho, k).
2.2.3. Algoritmos para a sua manutenção.
2.3. Heurísticas para Pesquisa.
2.3.1. Seleção de variável e valor.
2.3.2. Heurísticas genéricas (dom, deg, dom/wdeg, impact).
2.3.3. Optimização - Branch & Bound
3. Resolução Incompleta de Restrições - Pesquisa Local Restringida.
3.1.Modelação declarativa de restrições.
3.1.1. Invariantes e objetos diferenciáveis.
3.1.2. Grau de satisfação de restrições.
3.2. Heurísticas
3.2.1. Baseadas em variáveis ou em restrições.
3.2.2. Ávidas e estocásticas.
3.3. Meta-heurísticas
3.3.1. Recomeços.
3.3.2. Pesquisa tabu.
3.3.3. Arrefecimento simulado.
3.3.4. Pesquisa com vizinhança variável.
3.3.5. Colónias de formigas.
Bibliografia
Livros de Texto / Text Books
- Dina Rechter, Constraint Processing, Morgan Kauffman, 2003.
- Constraint-Based Local Search, MIT Press, 2005.
- Comet Tutorial, Dynamic Decision Technologies Inc., August 28, 2009
Manuais /Manuals
- Comet Tutorial, Dynamic Decision Technologies Inc., August 28, 2009