Skip navigation
Please use this identifier to cite or link to this item: https://repositorio.ufpe.br/handle/123456789/1878
Title: Otimização baseada em colônia de formigas aplicada ao problema de cobertura de conjuntos
Authors: Martins de Abreu Silva, Ricardo
Keywords: Colônia de formigas artificiais; Análise experimental; Heurísticas de otimização
Issue Date: 2003
Publisher: Universidade Federal de Pernambuco
Citation: Martins de Abreu Silva, Ricardo; Lisboa Ramalho, Geber. Otimização baseada em colônia de formigas aplicada ao problema de cobertura de conjuntos. 2003. Tese (Doutorado). Programa de Pós-Graduação em Ciência da Computação, Universidade Federal de Pernambuco, Recife, 2003.
Abstract: 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)
URI: https://repositorio.ufpe.br/handle/123456789/1878
Appears in Collections:Teses de Doutorado - Ciência da Computação

Files in This Item:
File Description SizeFormat 
arquivo4789_1.pdf818.14 kBAdobe PDFView/Open


This item is protected by original copyright



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.