An analysis of problem difficulty for a class of optimisation heuristics
作者： Enda Ridge , Daniel Kudenko
DOI: 10.1007/978-3-540-71615-0_18
关键词:
摘要: This paper investigates the effect of cost matrix standard deviation Travelling Salesman Problem (TSP) instances on performance a class combinatorial optimisation heuristics. Ant Colony Optimisation (ACO) is heuristic investigated. Results demonstrate that for given instance size, an increase in results difficulty instances. implies ACO, it insufficient to report problems classified only by problem as has been commonly done most ACO research date. Some description distribution also required when attempting explain and predict these algorithms TSP.
core.ac.uk
springer.com
sci-hub.se 参考文章(14)
Mark Zlochin, Marco Dorigo, Model-Based Search for Combinatorial Optimization: A Comparative Study parallel problem solving from nature. ,vol. 2439, pp. 651- 664 ,(2002) , 10.1007/3-540-45712-7_63
Thomas Fischer, Thomas FischerThomas Stutzle, Holger Hoos, Peter Merz, An Analysis of the Hardness of TSP Instances for Two High-performance Algorithms Proceedings of the 6th Metaheuristics International Conference. pp. 361- 367 ,(2005)
David S. Johnson, A theoretician's guide to the experimental analysis of algorithms. Data Structures, Near Neighbor Searches, and Methodology. pp. 215- 250 ,(1999)
M. Birattari, T. Stutzle, M. Dorigo, Ant Colony Optimization ,(2004)
Bob Kanefsky, Peter Cheeseman, William M. Taylor, Where the really hard problems are international joint conference on artificial intelligence. pp. 331- 337 ,(1991)
David Applegate, Robert Bixby, Vašek Chvátal, William Cook, Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems Mathematical Programming. ,vol. 97, pp. 91- 153 ,(2003) , 10.1007/S10107-003-0440-4
Thomas Stützle, Holger H. Hoos, – Ant System Future Generation Computer Systems. ,vol. 16, pp. 889- 914 ,(2000) , 10.1016/S0167-739X(00)00043-1
Keld Helsgaun, An effective implementation of the Lin–Kernighan traveling salesman heuristic European Journal of Operational Research. ,vol. 126, pp. 106- 130 ,(2000) , 10.1016/S0377-2217(99)00284-2
M. Dorigo, L.M. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem IEEE Transactions on Evolutionary Computation. ,vol. 1, pp. 53- 66 ,(1997) , 10.1109/4235.585892
Jano I. van Hemert, Property Analysis of Symmetric Travelling Salesman Problem Instances Acquired Through Evolution Evolutionary Computation in Combinatorial Optimization. pp. 122- 131 ,(2005) , 10.1007/978-3-540-31996-2_12