Heurísticas para o Problema Euclidiano de Steiner em Rn
Autores
|
2052 |
44,878
|
|
|
2053 |
44,878
|
Informações:
Publicações do PESC
O problema de Steiner euclidiano (PSE) é um problema de otimização que envolve aspectos combinatórios e contínuos. Dado um conjunto de pontos em Rn com métrica euclidiana, queremos encontrar uma árvores mínima conectando todos estes pontos, usando ou não pontos extras. Tem sido desenvolvida uma boa quantidade de algoritmos heurísticos e exatos para o PSE em dimensão n = 2. Entretanto, existem relativamente poucas propostas em dimensões mais altas. Esta tese apresenta algumas novas heurísticas para o PSE em n > 3. Estas são basicamente: uma extensão para n > 3 de um esquema de relaxação baseado em um modelo físico para o PSE plano; uma busca local de estruturas topológicas do PSE aplicada no contexto de uma busca tabu; um algoritmo genético e uma metaheurística desenvolvida recentemente, chamada Otimização Microcanônica, aplicados a uma estrutura vetorial resultante de um esquema de enumeração de soluções para o PSE. Resultados computacionais são fornecidos e usados para análise de desempenho de tais heurísticas.
The Euclidean Steiner problem (ESP) is an optimization problem involving both combinatorial and continuous aspects. Given a set of points in Rn with Euclidean metric, we look for a minimum tree which spans these points using or not extra points. A number of heuristics and exact algorithms have been developed for the ESP in dimension n = 2. However, there are relatively few proposals in higher dimensions. This thesis presents some new heuristics for the ESP in n > 3. These are basically: an extension for n > 3 of a relaxation scheme based on a physical model to the plane ESP; a local search of topological ESP structures applied in the context of a tabu search technique, and a genetic algorithm and a recently developed metaheuristic, called Microcanonical Optimization, which are applied to a vector structure resulting of an enumerative scheme of solutions for the ESP. Computational results are provided and used to analize the performances of such heuristics.