NEW METAHEURISTIC APPROACHES FOR THE LEAF-CONSTRAINED MINIMUM SPANNING TREE PROBLEM
作者： Alok Singh , Anurag Singh Baghel , None
DOI: 10.1142/S0217595908001870
关键词:
摘要: Given an undirected, connected, weighted graph, the leaf-constrained minimum spanning tree (LCMST) problem seeks a of graph with smallest weight among all trees which contains at least l leaves. In this paper we have proposed two new metaheuristic approaches for LCMST problem. One is ant-colony optimization (ACO) algorithm, whereas other tabu search based algorithm. Similar to previously genetic these also use subset coding that represents by set its interior vertices. Our perform well in comparison best heuristics reported literature — subset-coded algorithm and greedy heuristic.
sci-hub.se 参考文章(18)
Christian Blum, Ant colony optimization for the edge-weighted k -cardinality tree problem genetic and evolutionary computation conference. pp. 27- 34 ,(2002)
Thomas Sttzle, Holger H. Hoos, Improvements on Ant-System: Introducing MAX-MIN Ant System ,(1996)
Serge Fenet, Christine Solnon, Searching for maximum cliques with ant colony optimization Lecture Notes in Computer Science. pp. 236- 245 ,(2003) , 10.1007/3-540-36605-9_22
Luca M. Gambardella, Marco Dorigo, Ant-Q: A Reinforcement Learning approach to the traveling salesman problem Machine Learning Proceedings 1995. pp. 252- 260 ,(1995) , 10.1016/B978-1-55860-377-6.50039-6
Olfa Sammoud, Sébastien Sorlin, Christine Solnon, Khaled Ghédira, A comparative study of ant colony optimization and reactive search for graph matching problems european conference on evolutionary computation in combinatorial optimization. pp. 234- 246 ,(2006) , 10.1007/11730095_20
Finbarr Tarrant, Derek Bridge, When Ants Attack: Ant Algorithms for Constraint Satisfaction Problems Artificial Intelligence Review. ,vol. 24, pp. 455- 476 ,(2005) , 10.1007/S10462-005-9005-7
M. Birattari, T. Stutzle, M. Dorigo, Ant Colony Optimization ,(2004)
G. Leguizamon, Z. Michalewicz, A new version of ant system for subset problems congress on evolutionary computation. ,vol. 2, pp. 1459- 1464 ,(1999) , 10.1109/CEC.1999.782655
Christian Blum, Maria J. Blesa, New metaheuristic approaches for the edge-weighted k -cardinality tree problem Computers & Operations Research. ,vol. 32, pp. 1355- 1377 ,(2005) , 10.1016/J.COR.2003.11.007
Cory J. Hoelting, Dale A. Schoenefeld, Roger L. Wainwright, Approximation techniques for variations of the p-median problem acm symposium on applied computing. pp. 293- 299 ,(1995) , 10.1145/315891.315997