Dissertação

Aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de Steiner Euclidiano no ℝ𝑛

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...

ver descrição completa

Autor principal: Costa, Wilson Wolf
Grau: Dissertação
Idioma: pt_BR
Publicado em: Universidade Federal do Tocantins 2019
Assuntos:
árvore de Steiner Euclidiana; Meta-heurística; Otimização por enxame de partículas aprimorada
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Acesso em linha: http://hdl.handle.net/11612/1304
id ir-11612-1304
recordtype dspace
spelling ir-11612-13042019-08-24T06:00:50Z Aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de Steiner Euclidiano no ℝ𝑛 Costa, Wilson Wolf Rocha, Marcelo Lisboa árvore de Steiner Euclidiana; Meta-heurística; Otimização por enxame de partículas aprimorada CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO 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. 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. 2019-08-23T12:01:42Z 2019-08-23T12:01:42Z 2019-03-14 Dissertação 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. http://hdl.handle.net/11612/1304 pt_BR Open Access application/pdf application/pdf Universidade Federal do Tocantins BR Programa de Pós-Graduação em Modelagem Computacional de Sistemas - PPGMCS Palmas
institution Repositório Institucional - Universidade Federal do Tocantins - UFT
collection RepositorioUFT
language pt_BR
topic árvore de Steiner Euclidiana; Meta-heurística; Otimização por enxame de partículas aprimorada
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
spellingShingle árvore de Steiner Euclidiana; Meta-heurística; Otimização por enxame de partículas aprimorada
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
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 ℝ𝑛
topic_facet árvore de Steiner Euclidiana; Meta-heurística; Otimização por enxame de partículas aprimorada
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
description 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.
author_additional Rocha, Marcelo Lisboa
author_additionalStr Rocha, Marcelo Lisboa
format Dissertação
author Costa, Wilson Wolf
title Aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de Steiner Euclidiano no ℝ𝑛
title_short Aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de Steiner Euclidiano no ℝ𝑛
title_full Aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de Steiner Euclidiano no ℝ𝑛
title_fullStr Aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de Steiner Euclidiano no ℝ𝑛
title_full_unstemmed Aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de Steiner Euclidiano no ℝ𝑛
title_sort aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de steiner euclidiano no ℝ𝑛
publisher Universidade Federal do Tocantins
publishDate 2019
url http://hdl.handle.net/11612/1304
_version_ 1787134238585257984
score 11.755432

Registros relacionados