Academic
Publications
Initialization is robust in evolutionary algorithms that encode spanning trees as sets of edges

Initialization is robust in evolutionary algorithms that encode spanning trees as sets of edges,10.1145/508791.508898,Bryant A. Julstrom,Günther R. Ra

Initialization is robust in evolutionary algorithms that encode spanning trees as sets of edges   (Citations: 12)
BibTex | RIS | RefWorks Download
Evolutionary algorithms (EAs) that search spaces of spanning trees can encode candidate trees as sets of edges. In this case, edge-sets for an EA's initial population should represent spanning trees chosen with uniform probabilities on the graph that underlies the target problem instance. However, the generation of random spanning trees is not as simple as it might appear. Mechanisms based on Prim's and Kruskal's minimum spanning tree algorithms are not uniform, and uniform mechanisms are slow, not guaranteed to terminate, or require that the underlying graph be complete.However, a non-uniform initial population of spanning trees need not harm an EA's performance. Trials of a crossover-only EA for the One-Max-Tree problem, using Prim-based, Kruskal-based, and uniform initialization, indicate that the distribution of edges in the initial population is far more important than the distribution of trees. A skewed distribution of edges in its initial population damages the EA's performance, but this is remedied by a reasonable amount of mutation.
Conference: ACM Symposium on Applied Computing - SAC , pp. 547-552, 2002
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: