A comparison of encodings and algorithms for multiobjective minimum spanning tree problems
Joshua D. Knowles, David Corne · 2002
Finding minimum-weight spanning trees (MST) in graphs is a classic problem in operations research with important applications in network design. The basic MST problem can be solved efficiently, but the degree constrained and multiobjective versions are NP-hard. Current approaches to the degree-constrained single objective MST include Raidl's (2000) evolutionary algorithm (EA) which employs a direct tree encoding and associated operators, and Knowles and Corne's (2000) encoding based on a modified version of Prim's (1957) algorithm. Approaches to the multiobjective MST include various approximate constructive techniques from operations research, along with Zhou and Gen's (1999) evolutionary algorithm using a Prufer (1918) based encoding. We apply (appropriately modified) the best of recent methods for the (degree-constrained) single objective MST problem to the multiobjective MST problem, and compare with a method based on Zhou and Gen's approach. Our evolutionary computation approaches, using the different encodings, involve a new population-based variant of Knowles and Corne's PAES algorithm. We find the direct encoding to considerably outperform the Prufer encoding. We find that a simple iterated approach, based on Prim's algorithm modified for the multiobjective MST, also significantly outperforms the Prufer encoding.