Evolutionary Approach to the Euclidean Steiner Tree Problem in n-Space

Abstract

This article presents the application of a genetic algorithm for solving the Euclidean Steiner problem in spaces of dimensionality greater than 2. The Euclidean Steiner problem involves finding the minimum spanning network that connects a given set of vertices, including the additional Steiner vertices, in a multi-dimensional space. The focus of this research is to compare several different settings of the method, including the crossover operators and sorting of the input data. The paper points out that significant improvement in results can be achieved through proper initialization of the initial population, which depends on the appropriate sorting of vertices. Two approaches were proposed, one based on the nearest neighbor method, and the other on the construction of a minimum spanning tree.

Keywords

• Euclidean Steiner problem
• evolutionary optimization
• genetic algorithm
• heuristics