Aplicação de A-Teams ao problema de recobrimento de um conjunto
AUTOR(ES)
Humberto Jose Longo
DATA DE PUBLICAÇÃO
1995
RESUMO
Esta dissertação tem como tema central o Problema de Recobrimento de um Conjunto (SCP - Set Covering Problem). O objetivo principal é a proposta de uma nova abordagem para sua resolução, mais precisamente, este objetivo visa o desenvolvimento de um método heurístico, multi-algorítmico, baseado no paradigma de Times Assíncronos. Um segundo objetivo desta dissertação, e de grande importância na fundamentação do método ora proposto, é um estudo das principais características estruturais do problema; de sua formulação como um problema de programação linear inteira 0-1 e dos principais métodos computacionais (heurísticos e exatos) atualmente disponíveis para sua resolução. Times Assíncronos são organizações de software que visam a interação eficiente entre vários algoritmos, para a resolução de problemas adequados à abordagem multi-algorítmica. A arquitetura proposta utiliza métodos aproximados para a resolução do SCP e do dual da relaxação linear do mesmo. Esta abordagem primal-dual permite garantir que a melhor solução encontrada esteja a um certo percentual da solução ótima, ou mesmo, eventualmente, provar a otimalidade da solução. Segundo este enfoque, os principais componentes da arquitetura proposta são algoritmos gulosos e de consenso, procedimentos de busca tabu, métodos de otimização por subgradientes e geradores de planos de corte. Os principais métodos exatos para a resolução do SCP são baseados em metodologias enumerativas. A maioria desses métodos combina ao esquema de enumeração diversas das técnicas heurísticas utilizadas na arquitetura aqui proposta. Contudo, esses métodos apresentam desempenho insatisfatório para algumas classes de instâncias, por não obterem boas soluções em um limite razoável de tempo. A arquitetura proposta foi aplicada a instâncias dessas classes de difícil resolução. Os resultados obtidos mostraram que é possível alcançar, com um esforço computacional aceitável, resultados no mínimo comparáveis aos dos melhores algoritmos para o SCP
ASSUNTO(S)
otimização combinatoria heuristica pesquisa operacional
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=000107793Documentos Relacionados
- A-teams para um problema de transporte de derivados de petroleo
- Otimização do processo de inserção automática de componentes eletrônicos empregando a técnica de times assíncronos.
- Um estudo da aplicação de algoritmos bio-inspirados ao problema de estimação de direção de chegada
- Transgenética computacional: uma aplicação ao problema quadrático de alocação
- Aplicação de métodos numéricos de otimização ao problema conjunto da dirigibilidade e conforto veicular.