Download PDF

GECCO (Genetic and Evolutionary Computation Conference), Date: 2015/07/11 - 2015/07/15, Location: Madrid, Spain

Publication date: 2015-07-11
Pages: 1379 - 1380
ISSN: 978-1-4503-3488-4
Publisher: ACM; New York, NY, USA

Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Author:

Decroos, Tom
De Causmaecker, Patrick ; Demoen, Bart ; Silva, Sara

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.