OtimizaÃÃo baseada em colÃnia de formigas aplicada ao problema de cobertura de colonos

AUTOR(ES)

Ricardo Martins de Abreu e Silva

DATA DE PUBLICAÇÃO

2003

RESUMO

O presente trabalho avalia o desempenho e o funcionamento da meta-heurÃstica Ant Colony Optimization â ACO em instÃncias de grande porte do problema de cobertura de conjuntos (Set Covering Problem - SCP). A meta-heurÃstica ACO à um mÃtodo de otimizaÃÃo baseado no comportamento de colÃnias de formigas reais e que vem obtendo resultados promissores em vÃrios problemas combinatoriais. Entretanto, nÃs constatamos que, na maior parte dos artigos publicados pela comunidade ACO, a anÃlise efetuada sobre as heurÃsticas nÃo seguia um mÃtodo de avaliaÃÃo rigoroso, principalmente no que se refere à carÃncia de estudos da influÃncia dos parÃmetros destas heurÃsticas sobre a qualidade dos resultados alcanÃados. Uma vez que eventuais descuidos ocorridos na etapa de avaliaÃÃo de um algoritmo podem levar a conclusÃes equivocadas a respeito de seu desempenho, resolvemos utilizar um mÃtodo de anÃlise experimental para avaliar a adaptaÃÃo da meta-heurÃstica ACO em algum problema de otimizaÃÃo combinatorial previamente abordado pela comunidade ACO. O interesse em torno das instÃncias de grande porte do problema de cobertura de conjuntos surgiu de sua complexidade (NPCompleto), e de sua capacidade de atender uma grande quantidade de problemas reais, os quais geralmente nÃo possuem escala reduzidas na prÃtica. A principal contribuiÃÃo deste trabalho, sobretudo com relaÃÃo à surpresa do seu resultado em vista da literatura vigente, encontra-se na revelaÃÃo da pouca importÃncia do feromÃnio no mÃtodo ACO em instÃncias SCP de grande porte, assim como na exposiÃÃo de teorias, baseadas no conceito da correlaÃÃo da distÃncia de adaptaÃÃo, capazes de explanar nÃo somente as causas responsÃveis pela atuaÃÃo do feromÃnio, mas tambÃm a melhoria oriunda das hibridizaÃÃes (via busca local) do mÃtodo ACO em SCP, a ponto deste Ãltimo ser prescindÃvel. Ou seja, chegamos à conclusÃo de que nÃo se justifica a utilizaÃÃo do mÃtodo ACO em instÃncias SCP de grande porte, uma vez que existem tÃcnicas mais simples e eficientes capazes de tratar este mesmo problema, como por exemplo, a busca local desenvolvida por Jacobs e Brusco (1995)

ASSUNTO(S)

colÃnia de formigas artificiais ciencia da computacao anÃlise experimental heurÃsticas de otimizaÃÃo

Documentos Relacionados

• OtimizaÃÃo multiobjetivo da confiabilidade via sistemas multiagentes baseado em colÃnia de formigas
• ProgramaÃÃo nÃo-linear aplicada à otimizaÃÃo de redes pressurizadas de distribuiÃÃo de Ãgua
• Mecanismo rnolecular da resistÃncia de urna colÃnia de Culex quinquefasciatus (Diptera: Culicidae) ao Bacillus sphaericus
• Modelos de mobilidade: propriedades, simulaÃÃo e aplicaÃÃo a um problema de otimizaÃÃo de recursos
• OtimizaÃÃo da produÃÃo de Biodiesel