Neighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA, and ACO (bibtex)
by M Gruber, van Hemert, J and GR Raidl
Abstract:
We consider the Bounded Diameter Minimum Spanning Tree problem and describe four neighbourhood searches for it. They are used as local improvement strategies within a variable neighbourhood search (VNS), an evolutionary algorithm (EA) utilising a new encoding of solutions, and an ant colony optimisation (ACO).We compare the performance in terms of effectiveness between these three hybrid methods on a suite f popular benchmark instances, which contains instances too large to solve by current exact methods. Our results show that the EA and the ACO outperform the VNS on almost all used benchmark instances. Furthermore, the ACO yields most of the time better solutions than the EA in long-term runs, whereas the EA dominates when the computation time is strongly restricted.
Reference:
Neighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA, and ACO (M Gruber, van Hemert, J and GR Raidl), In Genetic and Evolutionary Computation (Maarten Keijzer et al., ed.), ACM, volume 2, 2006.
Bibtex Entry:
@article{GHR2006,
	_day = {08},
	abstract = {We consider the Bounded Diameter Minimum Spanning Tree problem and describe four neighbourhood searches for it. They are used as local improvement strategies within a variable neighbourhood search (VNS), an evolutionary algorithm (EA) utilising a new encoding of solutions, and an ant colony optimisation (ACO).We compare the performance in terms of effectiveness between these three hybrid methods on a suite  f popular benchmark instances, which contains instances too large to solve by current exact methods. Our results show that the EA and the ACO outperform the VNS on almost all used benchmark instances. Furthermore, the ACO yields most of the time better solutions than the EA in long-term runs, whereas the EA dominates when the computation time is strongly restricted.},
	address = {Seattle, USA},
	author = {M Gruber and van Hemert, J and GR Raidl},
	date-added = {2008-08-18 12:44:11 +0100},
	date-modified = {2008-08-18 12:44:11 +0100},
	editor = {Maarten Keijzer et al.},
	journal = {Genetic and Evolutionary Computation},
	keywords = {evolutionary computation; constraint satisfaction},
	pages = {1187--1194},
	pdf = {http://www.vanhemert.co.uk/publications/gecco2006.Neighbourhood_Searches_for_the_Bounded_Diameter_Minimum_Spanning_Tree_Problem_Embedded_in_a_VNS,_EA,_and_ACOpdf},
	publisher = {ACM},
	title = {Neighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a {VNS}, {EA}, and {ACO}},
	volume = {2},
	year = {2006}}
Powered by bibtexbrowser