A comparison of encodings and algorithms for multiobjective minimum spanning tree problems

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 evolutionary algorithm (EA) which employs a direct tree encoding and associated operators, and Knowles and Corne's encoding based on a modified version of Prim's algorithm. Approaches to the multiobjective MST include various approximate constructive techniques from operations research, along with Zhou and Gen's recent evolutionary algorithm using a Prüfer based encoding. In this paper 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 encodi ngs, involve a new population-based variant of Knowles and Corne's PAES algorithm. We find the direct encoding to considerably outperform the Prüfer encoding. And we find that a simple iterated approach, based on Prim's algorithm modified for the multiobjective MST, also significantly outperforms the Prüfer encoding.