Please use this identifier to cite or link to this item: http://hdl.handle.net/11612/1304
Authors: Costa, Wilson Wolf
metadata.dc.contributor.advisor: Rocha, Marcelo Lisboa
Title: Aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de Steiner Euclidiano no ℝ𝑛
Keywords: árvore de Steiner Euclidiana; Meta-heurística; Otimização por enxame de partículas aprimorada
Issue Date: 14-Mar-2019
Publisher: Universidade Federal do Tocantins
metadata.dc.publisher.program: Programa de Pós-Graduação em Modelagem Computacional de Sistemas - PPGMCS
Citation: COSTA, Wilson Wolf. Aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de Steiner Euclidiano no ℝ𝑛.2019. 110f. Dissertação (Mestrado em Modelagem Computacional e Sistemas) – Universidade Federal do Tocantins, Programa de Pós-graduação em Modelagem Computacional e Sistemas, Palmas, 2019.
metadata.dc.description.resumo: Dado um conjunto fixo de pontos em um espaço N-dimensional (𝑁≥3) com métrica euclidiana, o Problema da Árvore de Steiner Euclidiano no ℝ𝑛 consiste em encontrar uma árvore de menor comprimento que ligue todos estes pontos usando, se necessário, pontos extras (pontos de Steiner). A busca desta solução é um problema NP-difícil. Este trabalho apresenta uma meta-heurística modificada baseada em Otimização por Enxame de Partículas Aprimorada para o problema considerado. Finalmente, experimentos computacionais comparam o desempenho da heurística proposta, considerando a qualidade da solução e o tempo computacional, em relação a trabalhos anteriores na literatura.
Abstract: Given a fixed set of points in a N-dimensional space (𝑁≥3) with Euclidean metric, the Euclidean Steiner Tree Problem in ℝ𝑛 consists on finding a minimum length tree that spans all these points using, if necessary, extra points (Steiner points). The finding of such solution is a NP-hard problem. This work presents a modified metaheuristic based on Improved Particle Swarm Optimization to the problem considered. Finally, computational experiments compare the performance of the proposed heuristic, considering solution’s quality and computational time, regard to previous works in the literature.
URI: http://hdl.handle.net/11612/1304
Appears in Collections:Mestrado em Modelagem Computacional de Sistemas

Files in This Item:
File Description SizeFormat 
Wilson Wolf Costa - Dissertação.pdf3.13 MBAdobe PDFThumbnail
View/Open


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