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

• Ano de defesa: 2019
• Autor(a) principal: Costa, Wilson Wolf
• Orientador(a): Rocha, Marcelo Lisboa
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Tocantins; Palmas
• Programa de Pós-Graduação: Programa de Pós-Graduação em Modelagem Computacional de Sistemas - PPGMCS
• País: BR
• Palavras-chave em Português: árvore de Steiner Euclidiana; Meta-heurística; Otimização por enxame de partículas aprimorada
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://hdl.handle.net/11612/1304

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.