Return to search

Meta-heurísticas híbridas aplicadas ao problema da árvore geradora multiobjetivo / Hybrid metaheuristics applied to the multi-objective spanning tree problem

Submitted by Automação e Estatística (sst@bczm.ufrn.br) on 2018-08-01T21:05:14Z
No. of bitstreams: 1
IslameFelipeDaCostaFernandes_DISSERT.pdf: 12085812 bytes, checksum: 11b3cc3f73ed5f2051b48e441b6ee204 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-08-02T23:01:50Z (GMT) No. of bitstreams: 1
IslameFelipeDaCostaFernandes_DISSERT.pdf: 12085812 bytes, checksum: 11b3cc3f73ed5f2051b48e441b6ee204 (MD5) / Made available in DSpace on 2018-08-02T23:01:50Z (GMT). No. of bitstreams: 1
IslameFelipeDaCostaFernandes_DISSERT.pdf: 12085812 bytes, checksum: 11b3cc3f73ed5f2051b48e441b6ee204 (MD5)
Previous issue date: 2018-07-06 / Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq / O Problema da Árvore Geradora Multiobjetivo (AGMO) é uma extensão NP-Difícil da
Árvore Geradora Mínima (AGM). Devido à sua habilidade em modelar inúmeros problemas
reais onde objetivos conitantes devem ser otimizados simultaneamente, a AGMO tem
sido intensamente estudada na literatura e muitos algoritmos exatos e heurísticos lhe
foram propostos. Além disso, nos últimos anos, pesquisas têm demonstrado considerável
desempenho dos algoritmos que combinam estratégias de várias meta-heurísticas. Estes
algoritmos são chamados híbridos e trabalhos anteriores os aplicaram com sucesso a vários
problemas de otimização. Neste trabalho, cinco novos algoritmos híbridos são propostos para
duas versões da AGMO: três para a versão bi-objetivo (AG-Bi) baseada em dominância de
Pareto e dois para a versão com muitos objetivos baseada no operador de média ponderada
ordenada (AG-OWA). Esta pesquisa hibridizou diversas abordagens meta-heurísticas com
respeito a diferentes categorias de hibridização. Experimentos computacionais avaliaram
as novas abordagens com base no tempo computacional e na qualidade das soluções
encontradas. Os resultados foram comparados com o estado da arte. / The Multi-objective Spanning Tree Problem (MSTP) is an NP-hard extension of the
Minimum Spanning Tree (MST). Once the MTSP models several real-world problems in
which conicting objectives need to be optimized simultaneously, it has been extensively
studied in the literature and several exact and heuristic algorithms were proposed for
it. Besides, over the last years, researchs have showed the considerable performance of
algorithms that combine various metaheuristic strategies. They are called hybrid algorithms
and previous works successfully applied them to several optimization problems. In this
work, five new hybrid algorithms are proposed for two versions of the MSTP: three
for the bi-objective version (BiST) based on Pareto dominance and two for the manyobjective
version based on the ordered weighted average operator (OWA-ST). This research
hybridized elements from various metaheuristics. Computational experiments investigated
the potential of the new algorithms concerning computational time and solution quality.
The results were compared to the state-of-the-art.

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/25660
Date06 July 2018
CreatorsFernandes, Islame Felipe da Costa
Contributors81652011749, Goldbarg, Marco Cesar, 25841025953, Maia, Silvia Maria Diniz Monteiro, 01397968435, Souza, Thatiana Cunha Navarro de, 05332814402, Goldbarg, Elizabeth Ferreira Gouvea
PublisherPROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO, UFRN, Brasil
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Sourcereponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0018 seconds