A new hybrid evolutionary algorithm for the huge k-cardinality tree problem

ABSTRACT

In recent years it has been shown that an intelligent combination of metaheuristics with other optimization techniques can significantly improve over the application of a pure metaheuristic. In this paper, we combine the evolutionary computation paradigm with dynamic programming for the application to the NP-hard k-cardinality tree problem. Given an undirected graph G with node and edge weights, this problem consists of finding a tree in G with exactly k edges such that the sum of the weights is minimal. The genetic operators of our algorithm are based on an existing dynamic programming algorithm from the literature for finding optimal subtrees in a given tree. The simulation results show that our algorithm is able to improve the best known results for benchmark problems from the literature in 60 cases.

REFERENCES

• 1: Thomas Bäck, Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms, Oxford University Press, Oxford, 1996
• 2: C. Blum. Revisiting dynamic programming for finding optimal subtrees in trees. European Journal of Operational Research, 2006. In press.
• 3: C. Blum and M. Blesa. Combining Ant Colony Optimization with Dynamic Programming for solving the k-cardinality tree problem. In 8th International Work-Conference on Artificial Neural Networks, Computational Intelligence and Bioinspired Systems (IWANN'05), volume 3512 of Lecture Notes in Computer Science, pages 25--33. Springer-Verlag, Berlin, 2005.
• 4: C. Blum and M.J. Blesa. New metaheuristic approaches for the edge-weighted k-cardinality tree problem. Computers & Operations Research, 32(6):1355--1377, 2005.
• 5: Christian Blum , Matthias Ehrgott, Local search algorithms for the k-cardinality tree problem, Discrete Applied Mathematics, v.128 n.2-3, p.511-540, 01 June 2003 [doi>10.1016/S0166-218X(02)00548-6]
• 6: Christian Blum , Matthias Ehrgott, Local search algorithms for the k-cardinality tree problem, Discrete Applied Mathematics, v.128 n.2-3, p.511-540, 01 June 2003 [doi>10.1016/S0166-218X(02)00548-6]
• 7: R. Borndörfer, C. Ferreira, and A. Martin. Matrix decomposition by Branch-and-Cut. Technical report, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, 1997.
• 8: Ralf Borndörfer , Carlos E. Ferreira , Alexander Martin, Decomposing Matrices into Blocks, SIAM Journal on Optimization, v.9 n.1, p.236-269, 1998 [doi>10.1137/S1052623497318682]
• 9: J. Brimberg, D. Urovšević, and N. Mladenović. Variable neighborhood search for the vertex weighted k-cardinality tree problem. European Journal of Operational Research, 2005. In press.
• 10: T. N. Bui and G. Sundarraj. Ant system for the k-cardinality tree problem. In K. Deb et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference - GECCO 2004, volume 3102 of Lecture Notes in Computer Science, pages 36--47. Springer Verlag, Berlin, Germany, 2004.
• 11: S. Y. Cheung and A. Kumar. Efficient quorumcast routing algorithms. In Proceedings of INFOCOM '94, Los Alamitos, USA, 1994. IEEE Society Press.
• 12: M. Ehrgott and J. Freitag. K_TREE / K_SUBGRAPH: A program package for minimal weighted k-cardinality-trees and -subgraphs. European Journal of Operational Research, 1(93):214--225, 1996.
• 13: M. Ehrgott, J. Freitag, H. W. Hamacher, and F. Maffioli. Heuristics for the k-cardinality tree and subgraph problem. Asia-Pacific Journal of Operational Research, 14(1):87--114, 1997.
• 14: M. Fischetti, H. W. Hamacher, K. Jørnsten, and F. Maffioli. Weighted k-cardinality trees: Complexity and polyhedral structure. Networks, 24:11--21, 1994.
• 15: L. R. Foulds and H. W. Hamacher. A new integer programming approach to (restricted) facilities layout problems allowing flexible facility shapes. Technical Report 1992-3, Department of Management Science, University of Waikato, New Zealand, 1992.
• 16: L. R. Foulds, H. W. Hamacher, and J. Wilson. Integer programming approaches to facilities layout models with forbidden areas. Annals of Operations Research, 81:405--417, 1998.
• 17: J. Freitag. Minimal k-cardinality trees. Master's thesis, Department of Mathematics, University of Kaiserslautern, Germany, 1993. In german.
• 18: N. Garg and D. Hochbaum. An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. Algorithmica, 18:111--121, 1997.
• 19: H. W. Hamacher and K. Joernsten. Optimal relinquishment according to the Norwegian petrol law: A combinatorial optimization approach. Technical Report No. 7/93, Norwegian School of Economics and Business Administration, Bergen, Norway, 1993.
• 20: H. W. Hamacher, K. Jörnsten, and F. Maffioli. Weighted k-cardinality trees. Technical Report 91.023, Politecnico di Milano, Dipartimento di Elettronica, Italy, 1991.
• 21: A. Hertz and D. Kobler. A framework for the description of evolutionary algorithms. European Journal of Operational Research, 126:1--12, 2000.
• 22: F. Maffioli. Finding a best subtree of a tree. Technical Report 91.041, Politecnico di Milano, Dipartimento di Elettronica, Italy, 1991.
• 23: R. Ravi , R. Sundaram , M. V. Marathe , D. J. Rosenkrantz , S. S. Ravi, Spanning Trees---Short or Small, SIAM Journal on Discrete Mathematics, v.9 n.2, p.178-200, May 1996 [doi>10.1137/S0895480194266331]
• 24: H. W. Philpott and N. Wormald. On the optimal extraction of ore from an open-cast mine. Technical report, University of Auckland, New Zeland, 1997.
• 25: J. Puchinger and G. R. Raidl. Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification. In J. Mira and J. R. Álvarez, editors, Proceedings of the First International Work-Conference on the Interplay Between Natural and Artificial Computation, volume 3562 of Lecture Notes in Computer Science, pages 41--53. Springer Verlag, Berlin, Germany, 2005.
• 26: R. Uehara. The number of connected components in graphs and its applications. IEICE Technical Report COMP99-10, Natural Science Faculty, Komazawa University, Japan, 1999.
• 27: Dragan Uroševic´ , Jack Brimberg , Nenad Mladenović, Variable neighborhood decomposition search for the edge weighted k-cardinality tree problem, Computers and Operations Research, v.31 n.8, p.1205-1213, July 2004 [doi>10.1016/S0305-0548(03)00073-X]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms

Keywords:
k-cardinality tree problem, evolutionary computation