Hybrid Differential Evolution for the Euclidean Steiner Tree Problem

This paper presents a hybrid differential evolution algorithm for the Euclidean Steiner tree problem. This is an optimization problem whose goal is to obtain a minimum length tree to interconnect a set of fixed points, and for this to be achieved, new auxiliary points (called Steiner points) can be added. The proposed heuristic uses the Delaunay triangulation to insert Steiner points into good candidate positions, and then these points have their positions optimized by a differential evolution algorithm. From the set of points, a greedy algorithm searches for minimum spanning tree with degree restriction, if the topology presents errors, another algorithm corrects it; at the end, the Steiner points are placed in their optimum positions according to the topology, thus generating a Steiner tree. Results from numerical experiments for benchmark library problem (OR-Library) are presented.