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

Julstrom, B. A.

International Journal of Applied Mathematics and Computer Science, Tome 14 (2004) no. 3, pp. 385-396.

Résumé

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 least l 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.

Détail

Keywords: evolutionary codings, leaf-constrained spanning trees, Prüfer strings, Blob Code, fixed-length subsets
Mots-clés : algorytm ewolucyjny, algorytm genetyczny, kod Prüfera

Bibliographie

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

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

[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řıspĕvek k řěsenı otázky ekonomické stavby elektrovodnıch sıtı. — Elektronický obzor, Vol. 15, pp. 153–154.

[5] Cayley A. (1889): A theorem on trees. — Quart. J. Math., Vol. 23, pp. 376–378.

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

[10] Deo N. and Micikevicius P. (1999): A heuristic for a leaf constrained minimum spanning tree problem. — Congressus Numerantium, Vol. 141, pp. 61–72.

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

[12] Dibble C. and Densham P.J. (1993): Generating interesting alternatives in GIS and SDSS using genetic algorithms. — Proc. GIS/LIS 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. — Late-Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference, Las Vegas, NV, pp. 82–89.

[14] Estivill-Castro V. and Torres-Velásquez 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.

[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): Prüfer 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 rankbased 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 ConferenceWorkshop 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).

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

[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. Cantú-Paz et al., Eds.).—LNCS, Vol. 2724, pp. 1596–1597, Part II, Berlin: Springer.

[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. Männer and B. Manderick, Eds.).—Amsterdam: Elsevier.

[28] Narula G. and Ho C.A. (1989): Degree-constrained minimum spanning trees. — Comput. Oper. Res., Vol. 7, No. 4, pp. 39–49.

[29] Nešetil J., Milková E. and Nešetřilová H. (2001): Otakar Borůvka 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] Prüfer H. (1918): Neuer beweis eines satzes über permutationen. — Arch. Math. Phys., Vol. 27, No. 3, pp. 142–144.

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

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