bigpo.ru
добавить свой файл
1 2





PROJETO INDIVIDUAL


DE PESQUISA


Algoritmos Aproximativos e Exatos

em

Otimização Combinatória


Carlos Alberto Martinhon



2004/2005


Conteúdo


I – Dados Cadastrais.................................................................................................................... 03

II – Otimização Combinatória.................................................................................................... 03

III – Métodos Exatos..................................................................................................................... 04


IV – Metaheurísticas..................................................................................................................... 05

V – Algoritmos Aproximativos..................................................................................................... 06

V.1 – Algoritmos Aproximativos Determinísticos............................................................. 07

V.2 – Algoritmos Randômicos Aproximativos.................................................................. 08

VI – Objetivos................................................................................................................................ 08

VII - Equipe do Projeto..................................................................................................................09

VIII - Resultados esperados......................................................................................................... 09

IX - Cronograma de Execução..................................................................................................... 09

X - Referências Bibliográficas ..................................................................................................... 10


I - Dados Cadastrais:

Título do Projeto de Pesquisa

Algoritmos Aproximativos e Exatos Otimização Combinatória

Responsável

Carlos Alberto de Jesus Martinhon

 Doutor em Eng. de Sistemas e Computação pela COPPE/UFRJ.

 Prof. Adjunto do Depto. de Computação / Instituto de Computação da Universidade Federal Fluminense.

Área do Conhecimento

Ciências Exatas e da Terra

Palavras Chaves

Algoritmos Aproximativos, Metaheurísticas, Métodos Exatos, Otimização Combinatória.

Local de Execução do Projeto

Depto. De Computação do Instituto de Computação da Universidade Federal Fluminense.

Duração Prevista

2004/2005



II - Otimização Combinatória:

Problemas de otimização ocorrem freqüentemente em uma grande quantidade de aplicações industriais, científicas e de gerenciamento. Problemas deste tipo podem ser definidos essencialmente por um par (X, f(.)), onde X é um conjunto qualquer associado ao conjunto de restrições e f:XR representa uma função de custo associada. Em particular, no caso de problemas de minimização, deseja-se encontrar uma solução viável x* X onde f(x*)  f(x), xX. Se X é um conjunto discreto, a determinação de uma solução ótima x* é teoricamente possível enumerando-se todos os elementos de X e computando-se, paralelamente, sua imagem associada. Na prática entretanto, essa abordagem é geralmente inviável já que o número de soluções viáveis cresce exponencialmente com o tamanho do problema.

Em função da elevada complexidade computacional necessária na determinação de uma solução exata para uma grande quantidade de problemas combinatórios (denominados problemas NP-árduos ou NP-difíceis), muitos dos algoritmos propostos para sua solução podem não buscar diretamente um mínimo global. Nestes casos, adota-se normalmente uma estratégia que vise equilibrar a qualidade da solução obtida com o tempo total de processamento. Isto pode ser viabilizado, por exemplo, através de métodos aproximativos. A utilização de métodos exatos, por exemplo, se justifica principalmente em situações especiais, onde as instâncias consideradas para um determinado problema são “suficientemente pequenas” para a aplicação considerada. Neste projeto, entre as técnicas de construção de algoritmos utilizadas, adotaremos, conforme o caso, algoritmos aproximativos e/ou exatos. O trabalho de Dell’Amico, Maffioli e Martello[1997] representa uma ótima compilação de bibliografias de várias destas técnicas aplicadas a problemas de Otimização Combinatória.

Nos métodos heurísticos (em particular nas metaheurísticas), uma solução viável de baixo custo computacional, obtida em tempo polinomial e idealmente “próxima” da solução ótima é procurada (limitantes superiores). Embora possuam uma abordagem bastante interessante, e sejam utilizadas em uma grande quantidade de problemas práticos, ela carece ainda de formalismo matemático. Em determinadas situações entretanto, ao se trabalhar com uma heurística polinomial, poderemos constatar a qualidade da solução apresentada utilizando-se algoritmos aproximativos, sejam eles determinísticos ou randômicos. Neste caso, pretende-se definir uma “distância” do valor ótimo mesmo sem conhecê-lo explicitamente. Neste projeto, daremos uma atenção especial à utilização de técnicas de algoritmos randômicos aproximativos aplicados a problemas combinatórios (algoritmos randômicos). Paralelamente a isso, na determinação de limitantes superiores (soluções viáveis) trabalharemos também com metaheurísticas do tipo GRASP (Greedy Randomized Adaptive Search Procedure), VNS (Variable Neighborhood Search) ou Busca Tabu.

Dependendo do tamanho das instâncias consideradas e do tempo disponível para processamento, uma solução ótima exata poderá ser determinada adotando-se uma estratégia busca em árvore conveniente (ferramentas do tipo Branch-and-Bound). Para tanto, a determinação de bons limites superiores e inferiores (p/ o valor ótimo do problema original) a um baixo custo computacional se torna imprescindível. Na determinação de soluções ótimas utilizaremos técnicas que visam combinar resultados de teoria poliédrica com relaxação lagrangeana (Relax-and-Cut) ou teoria poliédrica com relaxação linear (Branch-and-Cut). A determinação de limitantes inferiores portanto, será ferramenta importante, tanto na busca por soluções ótimas exatas (métodos exatos), como na busca por soluções viáveis aproximadas e de qualidade. Por se tratar de etapas distintas, embora complementares, o estudo de limites inferiores e superiores para o valor ótimo do problema original será desenvolvido em conjunto.

Neste projeto, daremos uma atenção especial ao problema de Roteamento de Veículos e suas extensões, Escalonamento de Tarefas e Biologia Computacional.

Roteamento de veículos é uma designação genérica utilizada para uma grande quantidade de problemas de otimização combinatória, envolvendo, basicamente, a distribuição e coleta de mercadorias e serviços. Deseja-se, essencialmente, determinar uma ou mais rotas através de um conjunto de clientes (ou cidades) satisfazendo a determinadas restrições adicionais. Os problemas de roteamento de veículos são classificados como NP-Árduos por se tratarem de extensões do Problema do Caixeiro Viajante (PCV), reconhecidamente NP-Árduo (vide Garey e Johnson[1975]). O PCV pode ser visto como um problema de roteamento com apenas um veículo de capacidade infinita. Várias formulações e algoritmos foram propostos para o Problema de Roteamento de Veículos - PRV. Entre alguns dos “estado da arte” sobre o assunto podemos citar Bodin, Golden, Assad e Ball[1983]; Laporte e Nobert[1987]; Laporte[1992]; Desrosiers, Dumas, Solomon e Soumis[1994] entre outros. Um grande número de variações interessantes sobre o problema foram apresentadas em Assad[1988].

Problemas de escalonamento são classificados como NP-Árduos e se referem, basicamente, à alocação ótima de recursos escassos à atividades que ocorrem no tempo. Podemos encontrar aplicações em planejamento da produção, escalonamento de projetos e pessoal, processamento paralelo e distribuído, entre outros. Em síntese, nos problemas de escalonamento n tarefas (atividades) devem ser atribuídas de maneira ótima a m máquinas (recursos) minimizando o tempo total de execução destas tarefas. O trabalho de Dell’Amico et. al. [1997] contém várias referências importantes sobre o problema de escalonamento de tarefas e suas extensões. Apenas para ilustrar a utilização dos algoritmos randômicos aproximativos em escalonamento podemos citar os trabalhos de Schulz & Skutela[1999] e Chekuri et al. [1997].

Podemos enumerar uma grande quantidade de problemas combinatórios em biologia computacional, muitos deles voltados à solução eficiente de problemas de sequênciamento e mapeameto de cromossomos e proteínas. Como exemplo, podemos citar aplicações em alinhamento de sequências (pairwise and multiple alignment) , árvores evolucionárias, rearranjo de genôma entre outros (vide Dell’Amico et al [1997]). O trabalho de Setubal e Meidanis [1997] é também uma ótima referência sobre este assunto.


II - Métodos Exatos:

Na última década, a utilização de modelos de Programação Linear Inteira Mista (PLIM) tem sido aperfeiçoada drasticamente. A disponibilidade de softwares robustos, máquinas mais rápidas e a possibilidade de se resolver instâncias relativamente grandes em um menor tempo de processamento tem tornado a programação inteira muito mais atrativa a pesquisadores e analistas da iniciativa privada e do setor público.

O sucesso na solução de problemas de Programação Linear Inteira Mista de larga escala requer formulações cuja relaxação linear correspondente defina uma boa aproximação do envoltório convexo do conjunto de soluções viáveis. Na última década, um grande esforço tem sido devotado a métodos do tipo Branch-and-Cut, Branch-and-Price e Relax-and-Cut na resolução destes problemas. Hoffman e Padberg[1985] e Nemhauser&Wolsey[1988], Wolsey[1998] apresentam um exposição geral destas metodologias.

A idéia básica presente nos métodos Branch-and-Cut é bastante simples. Classes de desigualdades válidas (idealmente facetas) associadas a uma formulação do problema original são desprezadas na relaxação linear. O grande número de restrições impede que o problema seja tratado convenientemente utilizando-se apenas ferramentas de programação linear. Dessa forma, se uma solução ótima associada à relaxação linear é inviável, um novo problema de separação deve ser “resolvido” buscando a identificação de uma ou mais restrições violadas pela relaxação corrente (cutting procedure). O novo problema obtido (com restrições adicionais) é novamente resolvido via programação linear e o processo é repetido até que novas classes de desigualdades violadas não sejam mais encontradas. Neste momento, interrompe-se o processo e retorna-se à árvore de busca (Branch-and-Bound).

A filosofia do método Branch-and-Price é similar à do método Branch-and-Cut. A diferença básica é que, no primeiro, faz-se uma geração de colunas ao invés de geração de linhas (restrições violadas). Na verdade, trata-se de procedimentos complementares visando um incremento dos limites inferiores gerados pela relaxação linear associada.

Os procedimentos Relax-and-Cut visam combinar relaxação lagrangena (na geração de limites inferiores) com resultados de teoria poliédrica e Branch-and-Bound. Neste caso, um subconjunto do conjunto de restrições é dualizado. Os multiplicadores de Lagrange associados a este subconjunto são então atualizados utilizando-se, por exemplo, o método subgradiente (vide Reeves[1993]), ou o algoritmo do Volume (Bararona[1997]). Neste caso, como o número de restrições dualizadas pode ser extremamente grande (exponencial), é necessário que se defina um subconjunto bem menor de restrições dualizadas permitindo sua atualização dinâmicamente (para maiores detalhes consulte Martinhon[1998])

Exemplos da utilização de métodos exatos para problema combinatórios podem ser encontrados em inúmeros trabalhos na literatura. Apenas para citar alguns exemplos, temos o trabalho de Barnhart, Johnson, Nemhauser, Salvesberg, Vance[1998]; Salvesbeg[1997] para o problema do Assignment Generalizado; Vance[1998] para o problema de cortes de bobinas unidimensional; Maculan, Passini, Loiseau[1999] entre outros. Algoritmos exatos utilizando Branch-and-Cut e Relax-and-Cut para o Problema de Roteamento de Veículos foram propostos por Cornuejols e Harche[1993]; Miller[1995]; Augerat[1995] Christofides, Mingozzi e Hadjconstantinou[1995]; Martinhon, Lucena e Maculan [2003] entre outros. Exemplos de utilização de geração de colunas e Branch-and-Price para o problema de Roteamento podem ser encontrados em Skitt, Levary[1985] e Desrosiers, Soumis, Desrochers[1984] (para o problema de Roteamento Veículos com Janelas de Tempo).


III - Metaheurísticas:

Uma das limitações dos métodos que visam a determinação de soluções ótimas para problemas combinatórios é que, raramente, eles resolvem grandes instâncias em um tempo computacional aceitável. Em função disso, muitos pesquisadores se concentraram no desenvolvimento de heurísticas ou metaheurísticas inteligentes como Simulated Annealing, Busca Tabu, GRASP (Greedy Randomized Adaptive Search Procedure), VNS (Variable Neighborhood Search), Algoritmos Genéticos entre outros. Artigos introdutórios sobre estes assuntos podem ser encontrados em Pirlot[1992], Reeves[1993] e Aarts&Lenstra[1997]. A utilização de diferentes metaheurísticas voltadas especificamente para o problema de roteamento de veículos podem ser encontradas em Gendreau, Laporte e Potvin[1994] e Hjorring[1995].

Estas técnicas se enquadram dentro de uma categoria especial mais conhecida na literatura como metaheurísticas ou métodos inteligentemente flexíveis (Redes Neurais, Algoritmos Genéticos, Simulated Annealing, etc). Trata-se de estratégias que buscam, da melhor maneira possível, fazer uso de técnicas já existentes como heurísticas especializadas juntamente com um conhecimento prévio do problema no intuito de escapar de mínimos locais e varrer de forma mais eficiente o espaço de busca (conjunto de soluções viáveis).

A utilização de metaheurísticas como GRASP, Busca Tabu, VNS, etc., tendem a melhorar a qualidade das soluções geradas através de ferramentas específicas, como o uso de estruturas de dados adequadas e ainda pelo aproveitamento de seu paralelismo intrínseco. O método GRASP por exemplo, pode ser caracterizado, basicamente, por um processo iterativo e adaptativo que visa obter, da melhor maneira possível, a combinação de heurísticas clássicas determinísticas com processos aleatórios. A melhor solução é sempre armazenada durante o processo iterativo. Cada iteração é constituída, basicamente, de duas etapas: a primeira, busca determinar uma boa solução utilizando heurísticas gulosas adaptativas, e a segunda, uma busca local é realizada objetivando uma melhoria da solução determinada na primeira etapa. Em Feo, Rezende[1995] e Resende[1995] encontramos uma descrição mais detalhada sobre este assunto. Alguns exemplos de aplicação desta técnica podem ser encontrados em Resende e Ribeiro[1995] para o problema da Planarização em Grafos; Martins, Pardalos, Resende e Ribeiro[1995] para o problema de Steiner em Grafos; Li, Pardalos e Resende[1994] para o Quadratic Assignment entre outros.

Basicamente, na Busca Tabu partimos de uma solução inicial e, a cada passo, movemos de uma solução xk para outra solução xk+1 pertencente a N(xk) (vizinhança de xk). O processo é repetido até que algum critério de parada tenha sido satisfeito. Se f(xk) denota o custo no ponto xk, então f(xk) não será necessariamente menor que f(xk). Como conseqüência, segue que um cuidado maior deve ser tomado no sentido de evitar soluções repetidas (ciclagem). Isto é feito criando-se uma ou mais listas tabu de movimentos proibitivos (para maiores detalhes vide Glover{1989],[1990]).

Vários exemplos de aplicação de Busca Tabu em problemas de roteamento (PRV) podem ser encontrados na literatura. Geandreau, Hertz e Laporte[1994] tratam do problema de roteamento com restrições capacidade imposta aos veículos. Willard[1989]; Pureza e França[1991]; Osman[1993] e Taillard[1993] consideram restrições de tempo e capacidade. Potvin, Kervahut, Garcia e Rousseau[1993] utilizam Busca Tabu para o PRV com Janelas de Tempo (Time Windows).

Encontramos ainda alguns exemplos de algoritmos híbridos combinando características dos métodos GRASP e Busca Tabu além de outras metaheurísticas. Alguns exemplos de aplicação desta estratégia podem ser encontrados em Motta, Ochi e Martinhon[2001], Gomes, Diniz e Martinhon [2000], Díaz e Fernández[1998] e Fernández e Martí[1997].



следующая страница >>