Algoritmos de Otimização Aplicados ao Problema de Steiner em N Dimensões.
Autores
|
4735 |
Vinícius Leal do Forte
|
2095,44,878
|
|
4736 |
2095,44,878
|
|
|
4737 |
2095,44,878
|
Informações:
Publicações do PESC
Título
Algoritmos de Otimização Aplicados ao Problema de Steiner em N Dimensões.
Linha de pesquisa
Otimização
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
1/2/2010
Resumo
O Problema de Steiner Euclidiano em n dimensões consiste em, dado um conjunto de pontos em um espaço euclidiano n-dimensional, encontrar a rede de tamanho mínimo que os interconecta, podendo ser adicionados pontos extras à rede. Existem diversos algoritmos exatos e heurísticos para a resolução do PSE para n=2. No entanto, poucos algoritmos foram desenvolvidos para n≥3. Nesta disertação, apresentamos novos algoritmos para o problema n-dimensional baseados na metaheurística Busca Local Iterativa (ILS) e em heurísticas de relaxação dinâmica anteriormente propostas na literatura. Resultados computacionais são apresentados e utilizados para analisar a qualidade das soluções produzidas pelos algoritmos.
Abstract
The Euclidean Steiner Tree problem in n dimensions consists in, given a set of points in an n-dimesional Euclidean space, to find a network which spans these points with minimal length, being allowed to add extra points to the network. There exists several exact and heuristic algorithms to solve the PSE when n=2. However, only a few algorithms were developed for n≥3. In this dissertation, we present new algorithms for the n-dimensional problem which are based on the Iterated Local Search (ILS) metaheuristic and on a dynamic relaxation heuristic previously proposed in the literature. Computational results are presented and used to analyze the quality of the solutions produced by the algorithms.
Arquivo