|NeSC Bibliographic Database|
Neighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA, and ACO
Gruber,M. van Hemert,J.I. Raidl,G.R. ,
Appeared in: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2006),Seattle, USA
Field of Science: e-Science
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.
Keywords: evolutionary computation, constraint satisfaction, variable neighbourhood search,
|Last Updated: 22 Jun 12 11:02|