Solving Euclidean Steiner Tree Problems with Multi Swarm Optimization

descriptionPublicationkeyboard_double_arrow_right Article , Conference object , Report 11 Jul 2015 Belgium Publisher:ACMJournal:Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Authors: Decroos, Tom; De Causmaecker, Patrick; Demoen, Bart;

doi: 10.1145/2739482.2764676

Solving Euclidean Steiner Tree Problems with Multi Swarm Optimization

- Summary
- Subjects
- Metrics

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.

Country

Belgium

Related Organizations

KU Leuven
Belgium
Katholieke Universiteit Leuven
Belgium

Keywords

Heuristic Methods, Control Methods, iMinds, ITEC, Artifical Intelligence, Search, Problem Solving

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	1
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average