Optimization by multicanonical annealing and the traveling salesman problem.
作者： Jooyoung Lee , M. Y. Choi
关键词:
摘要: We demonstrate a powerful and general simulated annealing method to study combinatorial optimization problems. It combines the multicanonical method, which samples directly microcanonical entropy of system, with an elaborate but straightforward scheme. The idea is fully utilize information about local obtained during short Monte Carlo simulations for in iterative fashion. present results extensive investigation traveling salesman problem unit square.
harvard.edu
springer.com
osti.gov
sci-hub.se 参考文章(40)
G.M. Torrie, J.P. Valleau, Nonphysical sampling distributions in Monte Carlo free-energy estimation: Umbrella sampling Journal of Computational Physics. ,vol. 23, pp. 187- 199 ,(1977) , 10.1016/0021-9991(77)90121-8
J. Michael Steele, Subadditive Euclidean Functionals and Nonlinear Growth in Geometric Probability Annals of Probability. ,vol. 9, pp. 365- 376 ,(1981) , 10.1214/AOP/1176994411
B. K. Ambati, J. Ambati, M. M. Mokhtar, Heuristic combinatorial optimization by simulated Darwinian evolution: a polynomial time algorithm for the Traveling Salesman Problem Biological Cybernetics. ,vol. 65, pp. 31- 35 ,(1991) , 10.1007/BF00197287
DAVID JOHNSON, More approaches to the travelling salesman guide Nature. ,vol. 330, pp. 525- 525 ,(1987) , 10.1038/330525A0
Jillian Beardwood, J. H. Halton, J. M. Hammersley, The shortest path through many points Mathematical Proceedings of the Cambridge Philosophical Society. ,vol. 55, pp. 299- 327 ,(1959) , 10.1017/S0305004100034095
S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by Simulated Annealing Science. ,vol. 220, pp. 671- 680 ,(1983) , 10.1126/SCIENCE.220.4598.671
Manfred Padberg, Giovanni Rinaldi, A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems SIAM Review. ,vol. 33, pp. 60- 100 ,(1991) , 10.1137/1033004
Bernd A. Berg, Thomas Neuhaus, Multicanonical algorithms for first order phase transitions Physics Letters B. ,vol. 267, pp. 249- 253 ,(1991) , 10.1016/0370-2693(91)91256-U
F. Favata, R. Walker, A study of the application of Kohonen-type neural networks to the Travelling Salesman Problem Biological Cybernetics. ,vol. 64, pp. 463- 468 ,(1991) , 10.1007/BF00202610
S. Lin, B. W. Kernighan, An Effective Heuristic Algorithm for the Traveling-Salesman Problem Operations Research. ,vol. 21, pp. 498- 516 ,(1973) , 10.1287/OPRE.21.2.498