 |
    |
Encoding Bounded-Diameter Spanning Trees with Permutations and with Random Keys
Bryant A. Julstrom
Department of Computer Science, St. Cloud State University, St. Cloud, MN, 56301 USAjulstrom@eeyore.stcloudstate.edu
Abstract. Permutations of vertices can represent constrained spanning trees for evolutionary search via a decoder based on Prim’s algorithm, and random keys can represent permutations. Though we might expect that random keys, with an additional level of indirection, would provide inferior performance compared with permutations, a genetic algorithm that encodes spanning trees with random keys is as effective as one whose genotypes are permutations of vertices in comparisons on a variety of instances of the bounded-diameter minimum spanning tree problem. These results suggest that either coding may be used, at the programmer’s convenience, in evolutionary algorithms for problems involving constrained spanning trees.
LNCS 3102, p. 1272 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004