Manipulating Valid Solutions in a Genetic Algorithm for the Bounded-Diameter Minimum Spanning Tree Problem

Created by W.Langdon from gp-bibliography.bib Revision:1.8051

@InProceedings{julstrom:2002:gecco:lbp,

• title = "Manipulating Valid Solutions in a Genetic Algorithm for the Bounded-Diameter Minimum Spanning Tree Problem",
• author = "Bryant A. Julstrom",
• booktitle = "Late Breaking Papers at the Genetic and Evolutionary Computation Conference ({GECCO-2002})",
• editor = "Erick Cant{\'u}-Paz",
• year = "2002",
• month = jul,
• pages = "247--254",
• address = "New York, NY",
• publisher = "AAAI",
• publisher_address = "445 Burgess Drive, Menlo Park, CA 94025",
• keywords = "genetic algorithms, genetic programming",
• URL = "http://web.stcloudstate.edu/bajulstrom/ga_abstracts/gecco2002lbp.html",
• abstract = "Given a connected, weighted, undirected graph G and a bound D, the bounded-diameter minimum spanning tree problem seeks a shortest spanning tree on G in which no path between two vertices contains more than D edges. In general, this problem is NP-hard. A greedy heuristic for it imitates Prim's algorithm. Beginning at an arbitrary start vertex, it builds a bounded-diameter spanning tree by repeatedly appending the lowest-weight edge between a vertex in the tree and one not yet connected to it whose inclusion does not violate the diameter bound. A genetic algorithm for the problem encodes candidate bounded-diameter spanning trees as lists of their edges and applies operators based on the greedy heuristic that maintain the diameter bound. In tests on sixteen Euclidean instances of the problem, the genetic algorithm consistently identifies much shorter trees; however, it is slower than the greedy heuristic and becomes infeasible on larger problem instances.",
• notes = "Late Breaking Papers, {GECCO-2002}. A joint meeting of the eleventh International Conference on Genetic Algorithms ({ICGA-2002}) and the seventh Annual Genetic Programming Conference ({GP-2002}) part of cantu-paz:2002:GECCO:lbp",

}

Genetic Programming entries for Bryant A Julstrom

Citations