Steiner Trees Optimization using Genetic Algorithms
Mário Jesus, S. M. Jesus, Alberto Márquez · 2004
We present a practical method to approximate good solutions to one of the most studied and difficult optimization problems, the Euclidean Steiner Tree Problem for a large number of points. This method is developed using a genetic algorithm, as the main optimization tool, which was enhanced by some specific heuristics originated from Computational Geometry for the most part. The intrinsic complexity of the problem and the large amount of points that we propose to deal with, requires a specific approach in order to obtain good solutions considering its practical use. To fulfill this objective, our genetic algorithm operates on a previously subdivided input instance. A clustering technique and the use of some geometric operators, both contribute to bound the error of the approximations obtained by our technique.