Joshua Knowles David Corne Martin Oates
Department of Computer Science, University of Reading, UK
J.D.Knowles@reading.ac.uk, D.W.Corne@reading.ac.uk, moates@srd.bt.co.uk
FAX: +44 (0) 118 975 1994, TEL: +44 (0) 118 931 8983
Finding the degree-constrained minimum spanning tree (d-MST) of a graph is a well studied NP-hard problem which is important in network design. We introduce a new method which improves on the best technique previously published for solving the d-MST, either using heuristic or evolutionary approaches. The basis of this encoding is a spanning-tree construction algorithm which we call the Randomised Primal Method (RPM), based on the well-known Prim's algorithm [6], and an extension [4] which we call `d-Prim's'. We describe a novel encoding for spanning trees, which involves using the RPM to interpret lists of potential edges to include in the growing tree. We also describe a random graph generator which produces particularly challenging d-MST problems. On these and other problems, we find that an evolutionary algorithm (EA) using the RPM encoding outperforms the previous best published technique from the operations research literature, and also outperforms simulated annealing and multistart hillclimbing (both also using the RPM encoding). We also note that an EA using the RPM also outperforms a recently published alternative EA approach on a standard test problem.