Codings and operators in two genetic algorithms for the leaf-constrained minimum spanning tree problem

Bryant Julstrom

International Journal of Applied Mathematics and Computer Science (2004)

  • Volume: 14, Issue: 3, page 385-396
  • ISSN: 1641-876X

Abstract

top
The features of an evolutionary algorithm that most determine its performance are the coding by which its chromosomes represent candidate solutions to its target problem and the operators that act on that coding. Also, when a problem involves constraints, a coding that represents only valid solutions and operators that preserve that validity represent a smaller search space and result in a more effective search. Two genetic algorithms for the leaf-constrained minimum spanning tree problem illustrate these observations. Given a connected, weighted, undirected graph G with n vertices and a bound l, this problem seeks a spanning tree on G with at l least leaves and minimum weight among all such trees. A greedy heuristic for the problem begins with an unconstrained minimum spanning tree on G, then economically turns interior vertices into leaves until their number reaches l. One genetic algorithm encodes candidate trees with Prüfer strings decoded via the Blob Code. The second GA uses strings of length n−l that specify trees’ interior vertices. Both GAs apply operators that generate only valid chromosomes. The latter represents and searches a much smaller space. In tests on 65 instances of the problem, both Euclidean and with weights chosen randomly, the Blob-Coded GA cannot compete with the greedy heuristic, but the subset-coded GA consistently identifies leaf-constrained spanning trees of lower weight than the greedy heuristic does, particularly on the random instances.

How to cite

top

Julstrom, Bryant. "Codings and operators in two genetic algorithms for the leaf-constrained minimum spanning tree problem." International Journal of Applied Mathematics and Computer Science 14.3 (2004): 385-396. <http://eudml.org/doc/207705>.

@article{Julstrom2004,
abstract = {The features of an evolutionary algorithm that most determine its performance are the coding by which its chromosomes represent candidate solutions to its target problem and the operators that act on that coding. Also, when a problem involves constraints, a coding that represents only valid solutions and operators that preserve that validity represent a smaller search space and result in a more effective search. Two genetic algorithms for the leaf-constrained minimum spanning tree problem illustrate these observations. Given a connected, weighted, undirected graph G with n vertices and a bound l, this problem seeks a spanning tree on G with at l least leaves and minimum weight among all such trees. A greedy heuristic for the problem begins with an unconstrained minimum spanning tree on G, then economically turns interior vertices into leaves until their number reaches l. One genetic algorithm encodes candidate trees with Prüfer strings decoded via the Blob Code. The second GA uses strings of length n−l that specify trees’ interior vertices. Both GAs apply operators that generate only valid chromosomes. The latter represents and searches a much smaller space. In tests on 65 instances of the problem, both Euclidean and with weights chosen randomly, the Blob-Coded GA cannot compete with the greedy heuristic, but the subset-coded GA consistently identifies leaf-constrained spanning trees of lower weight than the greedy heuristic does, particularly on the random instances.},
author = {Julstrom, Bryant},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {Blob Code; fixed-length subsets; evolutionary codings; Prüfer strings; leaf-constrained spanning trees},
language = {eng},
number = {3},
pages = {385-396},
title = {Codings and operators in two genetic algorithms for the leaf-constrained minimum spanning tree problem},
url = {http://eudml.org/doc/207705},
volume = {14},
year = {2004},
}

TY - JOUR
AU - Julstrom, Bryant
TI - Codings and operators in two genetic algorithms for the leaf-constrained minimum spanning tree problem
JO - International Journal of Applied Mathematics and Computer Science
PY - 2004
VL - 14
IS - 3
SP - 385
EP - 396
AB - The features of an evolutionary algorithm that most determine its performance are the coding by which its chromosomes represent candidate solutions to its target problem and the operators that act on that coding. Also, when a problem involves constraints, a coding that represents only valid solutions and operators that preserve that validity represent a smaller search space and result in a more effective search. Two genetic algorithms for the leaf-constrained minimum spanning tree problem illustrate these observations. Given a connected, weighted, undirected graph G with n vertices and a bound l, this problem seeks a spanning tree on G with at l least leaves and minimum weight among all such trees. A greedy heuristic for the problem begins with an unconstrained minimum spanning tree on G, then economically turns interior vertices into leaves until their number reaches l. One genetic algorithm encodes candidate trees with Prüfer strings decoded via the Blob Code. The second GA uses strings of length n−l that specify trees’ interior vertices. Both GAs apply operators that generate only valid chromosomes. The latter represents and searches a much smaller space. In tests on 65 instances of the problem, both Euclidean and with weights chosen randomly, the Blob-Coded GA cannot compete with the greedy heuristic, but the subset-coded GA consistently identifies leaf-constrained spanning trees of lower weight than the greedy heuristic does, particularly on the random instances.
LA - eng
KW - Blob Code; fixed-length subsets; evolutionary codings; Prüfer strings; leaf-constrained spanning trees
UR - http://eudml.org/doc/207705
ER -

References

top
  1. Achuthan N.R., Caccetta L., Caccetta P.A. and Geelan J.F. (1994): Computational methods for the diameter restricted minimum weight spanning tree problem. - Australasian J. Combinat., Vol. 10, pp. 51-71. Zbl0819.90114
  2. Alp O., Erkut O. and Drezner Z. (2003): An efficient genetic algorithm for the p-median problem. -Ann. Opers. Res., Vol. 122, No. 1-4, pp. 21-42. Zbl1038.90046
  3. Beasley J.E. (1990): OR-library: Distributing test problems by electronic mail. -J. Oper. Res. Soc., Vol. 41, pp. 1069-1072. 
  4. Borůvka O. (1926): Přispĕvek k řešeni otázky ekonomické stavby elektrovodnich siti. -Elektronicky obzor, Vol. 15, pp. 153-154. 
  5. Cayley A. (1889): A theorem on trees. -Quart. J. Math., Vol. 23, pp. 376-378. Zbl21.0687.01
  6. Correa E.S., Steiner M.T.A., Freitas A.A. and Carnieri C. (2001): A genetic algorithm for the p-median problem. -Proc. Genetic and Evolutionary Computation Conference, San Francisco, CA, pp. 1268-1275. 
  7. Crawford K.D., Hoelting C.J., Wainwright R.L. and Schoenefeld D.A. (1997): A study of fixed-length subset recombination, In: Foundations of Genetic Algorithms 4 (R.K. Belew and M.D. Vose, Eds.). - San Francisco, CA: Morgan Kaufmann, Vol. 4, pp. 365-378. 
  8. Crawford K.D., Wainwright K.D. and Vasicek D.J. (1995): Detecting multiple outliers in regression data using genetic algorithms. - Proc. ACM Symp. Applied Computing, New York, pp. 351-356. 
  9. Deo N. and Abdalla A. (2000): Computing a diameter-constrained minimum spanning tree in parallel, In: Algorithms and Complexity (G. Bongiovanni, G. Gambosi and R. Petreschi, Eds.). - LNCS, Vol. 1767, pp. 17-31, Berlin: Springer. Zbl0971.68591
  10. Deo N. and Micikevicius P. (1999): A heuristic for a leaf constrained minimum spanning tree problem. -Congressus Numerantium, Vol. 141, pp. 61-72. Zbl0967.68123
  11. Deo N. and Micikevicius P. (2002): A new encoding for labeled trees employing a stack and a queue. -Bull. Inst. Combinat. Its Appl., Vol. 34, pp. 77-85. Zbl0996.05035
  12. Dibble C. and Densham P.J. (1993): Generating interesting alternatives in GIS and SDSS using genetic algorithms. -Proc. GISLIS Symposium, Minneapolis, MN, pp. 180-189. 
  13. Edelson W. and Gargano M.L. (2000): Feasible encodings for GA solutions of constrained minimal spanning tree problems. -s Late-Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference, Las Vegas, NV, pp. 82-89. 
  14. Estivill-Castro V. and Torres-Velasquez R. (1999): Hybrid genetic algorithm for solving the p-median problem, In: Simulated Evolution and Learning: Second Asia-Pacific Conference on Simulated Evolution and Learning (B. McKay, X. Yao, C. S. Newton, J.-H. Kim and T. Furuhashi, Eds.). -LNCS, Vol. 1585, pp. 18-25, Berlin: Springer. 
  15. Even R. (1973): Algorithmic Combinatorics. - New York: Macmillan. Zbl0258.05101
  16. Goldberg D.E. and Deb K. (1991): A comparative analysis of selection schemes used in genetic algorithms, In: Foundations of Genetic Algorithms (G.J.E. Rawlins, Ed.). -San Mateo, CA: Morgan Kaufmann, pp. 69-93. 
  17. Gottlieb J., Julstrom B.A., Raidl G.R. and Rothlauf F. (2001): Prufer numbers: A poor representation of spanning trees for evolutionary search. - Proc. Genetic and Evolutionary Computation Conference, San Francisco, CA, pp. 343-350. 
  18. Hoelting C.J., Schoenefeld D.A. and Wainwright R.L. (1995): Approximation techniques for variations of the p-median problem. -Proc. ACM Symp. Applied Computing, New York, pp. 293-299. 
  19. Hosage C.M. and Goodchild M.F. (1986): Discrete space location-allocation solutions from genetic algorithms. -Ann. Oper. Res., Vol. 6, pp. 35-46. 
  20. Julstrom B.A. (1999): It's all the same to me: Revisiting rank-based probabilities and tournaments. -Proc. Congress Evolutionary Computation, CEC99, Vol. 2, pp. 1501-1505, Piscataway, NJ: IEEE Press. 
  21. Julstrom B.A. (2001): The Blob Code: A better string coding of spanning trees for evolutionary search, In: Genetic and Evolutionary Computation Conference Workshop Program, (A.S. Wu, Ed.). - pp. 256-261, San Francisco, CA. 
  22. Julstrom B.A. (2004): Better greedy heuristics for the leaf-constrained minimum spanning tree problem in complete graphs. -Discr. Appl. Math., (Submitted). Zbl1137.90734
  23. Julstrom B.A. and Raidl G. (2003): Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem. -Proc. ACM Symp. Applied Computing, pp. 747-752, New York, ACM Press. 
  24. Knowles J. and Corne D. (2000): A new evolutionary approach to the degree constrained minimum spanning tree problem. -IEEE Trans. Evolut. Comput., Vol. 4, No. 2, pp. 125-134. 
  25. Kruskal J.B. (1956): On the shortest spanning subtree of a graph and the traveling salesman problem. -Proc. Amer. Math. Soc., Vol. 7, No. 1, pp. 48-50. Zbl0070.18404
  26. Lim A. and Xu Z. (2003): A fixed-length subset genetic algorithm for the p-median problem, In: Genetic and Evolutionary Computation - GECCO 2003, (E. Cantu-Paz et al., Eds.). - LNCS, Vol. 2724, pp. 1596-1597, Part II, Berlin: Springer. Zbl1038.68772
  27. Lucasius C.B. and Kateman G. (1992): Towards solving subset selection problems with the aid of the genetic algorithm, In: Parallel Problem Solving from Nature II, (R. Manner and B. Manderick, Eds.). - Amsterdam: Elsevier. Zbl0825.68734
  28. Narula G. and Ho C.A. (1989): Degree-constrained minimum spanning trees. -Comput. Oper. Res., Vol. 7, No. 4, pp. 39-49. 
  29. Nevsetvril J., Milkova E. and Nevsetvrilova H. (2001): Otakar Borruvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history. -Discr. Math., Vol. 233, No. 1-3, pp. 3-36. 
  30. Palmer C.C. and Kershenbaum A. (1994): Representing trees in genetic algorithms. -Proc. 1st IEEE Conf. Evolutionary Computation, Orlando, FL, Vol. 1, pp. 379-384. 
  31. Picciotto S. (1999): How to encode a tree. - Ph.D. thesis, University of California, San Diego. 
  32. Prim R.C. (1957): Shortest connection networks and some generalizations. -Bell Syst. Tech. J., Vol. 36, No. 6, pp. 1389-1401. 
  33. Prufer H. (1918): Neuer beweis eines satzes uber permutationen. -Arch. Math. Phys., Vol. 27, No. 3, pp. 142-144. Zbl46.0106.04
  34. Radcliffe N.J. (1993): Genetic set recombination, In: Foundations of Genetic Algorithms 2, (L.D. Whitley, Ed.). - San Mateo, CA: Morgan Kaufmann, pp. 203-219. 
  35. Radcliffe N.J. and George F.A.W. (1993): A study in set recombination. -Proc. 5th Int. Conf. Genetic Algorithms, pp. 23-30, San Mateo, CA: Morgan Kaufmann. 
  36. Raidl G.R. (2000): An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem. -Proc. Congress Evolutionary Computation CEC00, pp. 104-111, Piscataway, NJ: IEEE Press. 
  37. Raidl G.R. and Julstrom B.A. (2003): Edge-sets: An effective evolutionary coding of spanning trees. -IEEE Trans. Evolut. Comput., Vol. 7, No. 3, pp. 225-239. 
  38. Rothlauf F. (2002): Representations for Genetic and Evolutionary Algorithms. - Heidelberg: Physica-Verlag. Zbl1030.68083
  39. Rothlauf F. and Goldberg D. (1999): Tree network design with genetic algorithms - An investigation in the locality of the Pruefernumber encoding. - Late Breaking Papers at the 1999 Genetic and Evolutionary Computation Conference, Orlando, FL, pp. 238-243. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.