Please use this identifier to cite or link to this item: https://repositorio.ufrn.br/jspui/handle/123456789/25660
Title: Meta-heurísticas híbridas aplicadas ao problema da árvore geradora multiobjetivo
Other Titles: Hybrid metaheuristics applied to the multi-objective spanning tree problem
Authors: Fernandes, Islame Felipe da Costa
Keywords: Árvore geradora multiobjetivo;Meta-heurísticas híbridas;Operador OWA;Algoritmos experimentais
Issue Date: 6-Jul-2018
Citation: FERNANDES, Islame Felipe da Costa. Meta-heurísticas híbridas aplicadas ao problema da árvore geradora multiobjetivo. 2018. 237f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2018.
Portuguese Abstract: 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.
Abstract: 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.
URI: https://repositorio.ufrn.br/jspui/handle/123456789/25660
Appears in Collections:PPGSC - Mestrado em Sistemas e Computação

Files in This Item:
File Description SizeFormat 
IslameFelipeDaCostaFernandes_DISSERT.pdf11,8 MBAdobe PDFThumbnail
View/Open


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