摘要: In recent years it has been shown that an intelligent combination of metaheuristics with other optimization techniques can significantly improve over the application a pure metaheuristic. this paper, we combine evolutionary computation paradigm dynamic programming for to NP-hard k-cardinality tree problem. Given undirected graph G node and edge weights, problem consists finding in exactly k edges such sum weights is minimal. The genetic operators our algorithm are based on existing from literature optimal subtrees given tree. simulation results show able best known benchmark problems 60 cases.
core.ac.uk
acm.org
sci-hub.se 参考文章(21)
Matthias Ehrgott, Horst. W. Hamacher, F. Maffioli, J. Freitag, Heuristics for the K-Cardinality Tree and Subgraph Problems ,(1996)
Christian Blum, Maria Blesa, Combining Ant Colony Optimization with Dynamic Programming for Solving the k-Cardinality Tree Problem Computational Intelligence and Bioinspired Systems. pp. 25- 33 ,(2005) , 10.1007/11494669_4
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
Thomas Bäck, Evolutionary Algorithms in Theory and Practice Oxford University Press. ,(1996) , 10.1093/OSO/9780195099713.001.0001
Jakob Puchinger, Günther R. Raidl, Combining Metaheuristics and Exact Algorithms in Combinatorial Optimization: A Survey and Classification Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach. ,vol. 3562, pp. 41- 53 ,(2005) , 10.1007/11499305_5
Thang N. Bui, Gnanasekaran Sundarraj, Ant System for the k-Cardinality Tree Problem genetic and evolutionary computation conference. pp. 36- 47 ,(2004) , 10.1007/978-3-540-24854-5_4
L. R. Foulds, H. W. Hamacher, J. M. Wilson, Integer Programming Approaches to Facilities Layout Models with Forbidden Areas Operations Research Proceedings. ,vol. 81, pp. 90- 95 ,(1998) , 10.1007/978-3-642-58891-4_13
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
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
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