GECCO (Genetic and Evolutionary Computation Conference), Date: 2015/07/11 - 2015/07/15, Location: Madrid, Spain
Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation
Author:
Keywords:
Artifical Intelligence, Problem Solving, Control Methods, Search, Heuristic Methods
Abstract:
A new iterative heuristic algorithm, based on Multi Swarm Optimization, is presented for Steiner Tree Problems (STP) in the 2-dimensional Euclidean plane. The basic algorithm is made practical for large instances by applying a result from graph theory, and a well-informed approximation. The algorithm’s performance is compared to perfect solutions for the classic Steiner Tree Problem and to a deterministic heuristic for the k-bottleneck STP, a variant of STP. The algorithm often produces near optimal solutions with limited resources. The approach can be applied to higher dimensions and to other variants of the Steiner Tree Problem.