Mathematical programming in a hybrid genetic algorithm for Steiner point problems
David J. Thuente, Pulin Sampat · 1995
This paper presents two solution techniques for constructing a minimal weighted tree connecting a fixed set of n terminal vertices while alluwing extra vertices to be added to the tree to reduce the cost or length of the connection.The problem discussed is a variation of the Steiner tree problem that reduces to the classical Steiner tree problem for many special cases.It is also a generalization of the planar Steiner tree problem.The algorithms seek to detemline the location of points (Steiner points) such that each terminal vertex is connected to a Steiner point.The Steiner points are then connected to each other and the algorithm minimizes total cost.We present a solution to this problem for a modest number of terminal vertices using a mathematical programming approach and combinatorics.This approach is guaranteed to find the optimal points (Steiner points) that minimize the total cost.We also construct an algorithm that iteratively combines the early use of mathematical programming along with a hybrid genetic algorithm.The solution techniques were tested extensively on small planar problems but were also applied to large problems in two-, three-and five-dimensional space.The genetic algorithm is used to determine the appropriate structure of a solution and the mathematical prograrmning algorithm determines the optimal location of Steiner points for each structure.The structure determines the assignment of terminal vertices to the Steiner points.The mathematical programming algorithm is the optimization part of a very powerful evaluation function for the genetic algorithm approach to the problem.