e-Science logo Nesc logo
 
 
About NeSC
e-Science Institute
e-Science Hub
TOE
Contacts
e-Science Events
Resources
Newsroom
Presentations & Lectures
Technical Papers
Global Grid Links
Projects
UK e-Science Centres
UK e-Science Teams
Career Opportunities
Bibliographic Database
 

 

Paper ID: 2685

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
Page Numbers:1187--1194
Publisher: ACM
Year: 2006
ISBN/ISSN:
Contributing Organisation(s):
Field of Science: e-Science

URL:

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,


BIB DOC HTM HTML PDF PPT PS RTF TEX TXT ZIP




 

Last Updated: 22 Jun 12 11:02
This is an archived website, preserved and hosted by the School of Physics and Astronomy at the University of Edinburgh. The School of Physics and Astronomy takes no responsibility for the content, accuracy or freshness of this website. Please email webmaster [at] ph [dot] ed [dot] ac [dot] uk for enquiries about this archive.