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 | Size | Format | |
|---|---|---|---|---|
| Wilson Wolf Costa - Dissertação.pdf | 3.13 MB | Adobe PDF |  View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.