Edge-Sets: An Effective Evolutionary
Coding of Spanning Trees

Günther R. Raidl
Institute for Computer Graphics and Algorithms
Vienna University of Technology
Favoritenstraße 9-11/1861
1040 Vienna, Austria
raidl@ads.tuwien.ac.at

Bryant A. Julstrom
Department of Computer Science
St. Cloud State University
720 Fourth Avenue South
St. Cloud, MN 56301 USA
julstrom@eeyore.stcloudstate.edu

Abstract

The fundamental design choices in an evolutionary algorithm are its representation of candidate solutions and the operators that will act on that representation. We propose representing spanning trees in evolutionary algorithms for network design problems directly as sets of their edges, and we describe initialization, recombination, and mutation operators for this representation. The operators offer locality, heritability, and computational efficiency. Initialization and recombination depend on an underlying random spanning tree algorithm; three choices for this algorithm, based on the minimum spanning tree algorithms of Prim and Kruskal and on random walks, respectively, are examined analytically and empirically. We demonstrate the usefulness of the edge-set encoding in an evolutionary algorithm for the NP-hard degree-constrained minimum spanning tree problem. The algorithm's operators are easily extended to generate only feasible spanning trees and to incorporate local, problem-specific heuristics. Comparisons of this algorithm to others that encode candidate spanning trees via the Blob code, with network random keys, and as strings of weights indicate the superiority of the edge-set encoding, particularly on larger instances.