You are here

Neighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA, and ACO

TitleNeighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA, and ACO
Publication TypeConference Paper
Year of Publication2006
AuthorsGruber, M, van Hemert, JI, Raidl, GR
Conference NameProceedings of the Genetic and Evolutionary Computation Conference (GECCO 2006)
PublisherACM
Conference LocationSeattle, USA
EditorKeijzer, M, et al,
Keywordsconstraint satisfaction; evolutionary computation; variable neighbourhood search
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.

Full Text