Ant colony optimization for the edge-weighted k -cardinality tree problem
作者： Christian Blum
DOI:
关键词: Computational problem 、 Optimization problem 、 Ant colony optimization algorithms 、 Mathematics 、 Generalized assignment problem 、 Combinatorial optimization 、 Metaheuristic 、 Steiner tree problem 、 Mathematical optimization 、 Parallel metaheuristic
摘要: In this paper we deal with an NP-hard combinatorial optimization problem, the k-cardinality tree problem in edge-weighted graphs. This has several applications practice, which justify need for efficient methods to obtain good solutions. Metaheuristic have already been shown be successful tackling past. propose ACO algorithm based on Hyper-Cube Framework Ant Colony Optimization. We investigate usefulness of a higher order pheromone representation contrast standard first and compare our algorithms multi-start local search heuristic developed tackle problem.
参考文章(21)
Andrea Roli, Christian Blum, Marco Dorigo, HC-ACO: The Hyper-Cube Framework for Ant Colony Optimization Proceedings of the Fourth Metaheuristics International Conference. pp. 399- 403 ,(2001)
Matthias Ehrgott, Horst. W. Hamacher, F. Maffioli, J. Freitag, Heuristics for the K-Cardinality Tree and Subgraph Problems ,(1996)
M. Dorigo, Optimization, Learning and Natural Algorithms Ph.D. Thesis, Politecnico di Milano, Italy. ,(1992)
Christian Blum, Marco Dorigo, Andrea Roli, ACO for Maximal Constraint Satisfaction Problems Proceedings of the Fourth Metaheuristics International Conference. pp. 187- 191 ,(2001)
N. Garg, D. S. Hochbaum, An O (log k)-Approximation Algorithm for the k Minimum Spanning Tree Problem in the Plane. Algorithmica. ,vol. 18, pp. 111- 121 ,(1997) , 10.1007/BF02523691
Nenad Mladenović, Dragan Urošević, Variable neighborhood search for the k-cardinality tree Metaheuristics. pp. 481- 500 ,(2004) , 10.1007/978-1-4757-4137-7_23
C. Blum, M. Sampels, Ant colony optimization for FOP shop scheduling: a case study on different pheromone representations congress on evolutionary computation. ,vol. 2, pp. 1558- 1563 ,(2002) , 10.1109/CEC.2002.1004474
Matteo Fischetti, Horst W. Hamacher, Kurt Jørnsten, Francesco Maffioli, Weighted k-cardinality trees: complexity and polyhedral structure Networks. ,vol. 24, pp. 11- 21 ,(1994) , 10.1002/NET.3230240103
T. Dudás, B. Klinz, G.J. Woeginger, The computational complexity of the κ-minimum spanning tree problem in graded matrices☆ Computers & Mathematics With Applications. ,vol. 36, pp. 61- 67 ,(1998) , 10.1016/S0898-1221(98)00150-3
Christian Blum, Andrea Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison ACM Computing Surveys. ,vol. 35, pp. 268- 308 ,(2003) , 10.1145/937503.937505