PUC-Rio Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão Período: 2008.1
    Horário: 2as feiras de 12 às 15 horas
Tópicos em Algoritmos, Paralelismo e Otimização

Algoritmos para Problemas de Otimização: Metaeurísticas e Heurísticas Matemáticas

Objetivos: Este curso visa fornecer noções fundamentais para a contrução de sistemas eficientes, através da concepção de algoritmos que se utilizam de informações disponíveis ou obtidas durante o processo de busca de soluções. O curso apresenta técnicas fundamentais e avançadas, focalizando nos princípios básicos para a construção de algoritmos inteligentes. Estes princípios são aplicados a problemas de Otimização Combinatória.

CONTEÚDO

Parte I: Noções básicas

· Fundamentos de modelagem: caracterização de problemas de otimização, representação de soluções, definição do espaço de soluções, construção de soluções, soluoeparciais e incompletas, vizinhança e topologia do espaço de soluções, papel da randomização em métodos de solução.

· Heurísticas construtivas: intuição e seu papel na construção de uma solução, algoritmos gulosos, algoritmos gulosos probabilísticos, esquemas de aproximação, construção randômica de soluções, avaliação da qualidade, garantia de qualidade.

· Métodos de busca local: intuição na modificação de uma solução, busca local, heurísticas de melhoria (hill climbing), métodos do tipo multiple restart.

· Metaeurísticas: o que é uma metaeurística, níveis de instanciação de uma metaeurística, principais classes de métodos, busca em grafos, algoritmo A*, aplicações em inteligência artificial.

· Tópicos avançados: estudo de tópicos avançados, selecionados entre os seguintes temas - simulated annealing, busca tabu, GRASP, heurísticas baseadas em regras, algoritmos genéticos, ant colonies, heurísiticas matemáticas, etc.

Parte II: Tópicos avançados

· Tópico 1 - Simulated annealing: histórico, convergência assintótica, velocidade de resfriamento, aspectos de implementação, aplicações em sistemas de computação.

· Tópico 2 - Busca tabu: princípio fundamental, elementos básicos (vizinhança, movimentos, memórias, recentidade e freqüência, atributos, restrições, aspiração), estratégias de busca, intensificação, diversificação, oscilação estratégica, listas de candidatos, critérios probabilísticos, enfoques híbridos e conexões com outras metaeurísticas, cadeias de ejeção, estratégias síncronas e assíncronas de paralelização, reconexão de caminhos, aplicações.

· Tópico 3 - GRASP: algoritmos gulosos randomizados, greedy randomized adaptive search procedures, fase de construção, fase de busca local, GRASP como método de amostragem no espaço de soluções, reconexão de caminhos, aplicações.

· Tópico 4 - Heurísticas baseadas em regras: identificação de regras: análise do espaço de soluções, análise do problema real e análise da memória de busca; modelos de ativação das regras; combinação de regras; aplicações em segmentação de imagens.

· Tópico 5 - Algoritmos genéticos (e outros baseados em população): princípios fundamentais, populações, funções de avaliação, operadores genéticos, reprodução, cruzamento, mutação, paralelização de algoritmos genéticos, caracterização como uma organização de agentes independentes, agentes, memórias, comunicação assíncrona, fluxo de dados cíclico, parametrização, tamanho das memórias (quantidade de conhecimentos armazenados), políticas de eliminação, critérios de seleção, frequência de ativação dos agentes, ambientes de execução, arquiteturas e paralelização, aplicações.

· Tópico 6 - Busca em Vizinhanças Muito Grandes (VLNS): caracterização da vizinhança, definição do problema implícito, técnicas de resolução recorrente, aplicações.

· Tópico 7 - Heurísticas Matemáticas: modelos e formulações, técnicas básicas: exploração de vizinhanças, local branching, vizinhanças estendidas, reconexão de caminhos, arredondamentos sucessivos, aplicações.

This document was translated from LATEX by HEVEA.