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.4221

  title =        "Manipulating Valid Solutions in a Genetic Algorithm
                 for the Bounded-Diameter Minimum Spanning Tree
  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 =          "",
  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
  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

Genetic Programming entries for Bryant A Julstrom