Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/11612/1304| Autor(a): | Costa, Wilson Wolf |
| Orientador: | Rocha, Marcelo Lisboa |
| Título: | Aplicação de otimização por enxame de partículas aprimorada na solução do problema da árvore de Steiner Euclidiano no ℝ𝑛 |
| Palavras-chave: | árvore de Steiner Euclidiana; Meta-heurística; Otimização por enxame de partículas aprimorada |
| Data do documento: | 14-Mar-2019 |
| Editor: | Universidade Federal do Tocantins |
| Programa: | Programa de Pós-Graduação em Modelagem Computacional de Sistemas - PPGMCS |
| Citaçã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. |
| 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 |
| Aparece nas coleções: | Mestrado em Modelagem Computacional de Sistemas |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| Wilson Wolf Costa - Dissertação.pdf | 3.13 MB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.