Edge sets: an effective evolutionary coding of spanning trees
- 20 June 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 7 (3), 225-239
- https://doi.org/10.1109/tevc.2002.807275
Abstract
The fundamental design choices in an evolutionary algorithm (EA) are its representation of candidate solutions and the operators that will act on that representation. We propose representing spanning trees in EAs 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 EA 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.Keywords
This publication has 34 references indexed in Scilit:
- Network Random Keys—A Tree Representation Scheme for Genetic and Evolutionary AlgorithmsEvolutionary Computation, 2002
- Representations for Genetic and Evolutionary AlgorithmsPublished by Springer Science and Business Media LLC ,2002
- Genetic algorithms for communications network design - an empirical study of the factors that influence performanceIEEE Transactions on Evolutionary Computation, 2001
- A new evolutionary approach to the degree-constrained minimum spanning tree problemIEEE Transactions on Evolutionary Computation, 2000
- A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problemPublished by Association for Computing Machinery (ACM) ,2000
- Pruefer Numbers and Genetic Algorithms: A Lesson on How the Low Locality of an Encoding Can Harm the Performance of GasLecture Notes in Computer Science, 2000
- Genetic Algorithms and Random Keys for Sequencing and OptimizationINFORMS Journal on Computing, 1994
- A Connectionist Machine for Genetic HillclimbingPublished by Springer Science and Business Media LLC ,1987
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957
- On the Shortest Spanning Subtree of a Graph and the Traveling Salesman ProblemProceedings of the American Mathematical Society, 1956