Made available in DSpace on 2014-06-12T15:52:55Z (GMT). No. of bitstreams: 2
arquivo4789_1.pdf: 837778 bytes, checksum: 2aadfef7452c9a1089fd78c8e6bb91dc (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2003 / 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)
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/1878 |
| Date | January 2003 |
| Creators | Martins de Abreu Silva, Ricardo |
| Contributors | Lisboa Ramalho, Geber |
| Publisher | Universidade Federal de Pernambuco |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds