- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Rapid Communication
  • Access by Xinjiang University

Optimization by multicanonical annealing and the traveling salesman problem

Jooyoung Lee

M. Y. Choi

  • Supercomputer Computations Research Institute B-186, Florida State University, Tallahassee, Florida 32306-4052

  • Department of Physics, Seoul National University, Seoul 151-742, Korea
  • Department of Physics, University of Washington, Seattle, Washington 98195

PDF

Phys. Rev. E 50, R651(R) – Published 1 August, 1994

DOI: https://doi.org/10.1103/PhysRevE.50.R651

Abstract

We propose a powerful and general simulated annealing method to study combinatorial optimization problems. It combines the multicanonical method, which samples directly the microcanonical entropy of the system, with an elaborate but straightforward annealing scheme. The information about the local entropy obtained during short Monte Carlo simulations is fully utilized for optimization in an iterative fashion. We present results of an extensive investigation of the traveling salesman problem in a unit square. We estimate the optimal length in the limit of a large number of cities.

View figure in article

References (29)

  1. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, edited by E. L. Lawler, J. K. Lenstra, A. H. G. Ringnooy Kan, and D. B. Shmoys (Wiley, Chichester, 1985).
  2. M. Padberg and G. Rinaldi, SIAM (Soc. Ind. Appl. Math.) Rev. 33, 60 (1991).
  3. S. Lin and B. W. Kernighan, Oper. Res. 21, 498 (1973).
  4. S. Kirkpatrick, C. D. Jr. Gelatt and M. P. Vecchi, Science 220, 671 (1983); V. Cerny, J. Optimization Theory Appl. 45, 41 (1985).
  5. See, e.g., Monte Carlo Methods in Statistical Physics, edited by K. Binder (Springer Verlag, Berlin, 1986).
  6. (a) J. Vannimenus and M. Mèzard, J. Phys. Lett. 45, L1145 (1984); M. Mèzard and G. Parisi, J. Phys. (Paris) 47, 1285 (1986); (b) W. Krauth and M. Mèzard, Europhys. Lett. 8, 213 (1989).
  7. J. J. Hopfield and D. Tank, Biol. Cybern. 5, 141 (1985).
  8. R. Durbin and D. Willshaw, Nature (London) 336, 689 (1987).
  9. F. Favata and R. Walker, Biol. Cybern. 64, 463 (1991).
  10. R. M. Brady, Nature (London) 317, 804 (1985); T. Boseniuk, W. Ebeling and A. Engel, Phys. Lett. A 125, 307 (1987).
  11. B. K. Ambati, J. Ambati and M. M. Mokhtar, Biol. Cybern. 65, 31 (1991).
  12. P. Ruján, Z. Phys. B 73, 391 (1988).
  13. D. Johnson, Nature (London) 330, 525 (1987); Proceedings of the 17th Colloquium on Automata, Language, and Programming (Springer Verlag, Berlin, 1990), pp. 446 461.
  14. E. Bonomi and J. L. Lutton, SIAM (Soc. Ind. Appl. Math.) Rev. 26, 551 (1984).
  15. S. Kirkpatrick and G. Toulouse, J. Phys. (Paris) 46, 1277 (1985); H. Guo, M. Zuckermann, R. Harris and M. Grant, Phys. Scri. T 38, 40 (1991).
  16. N. E. Collins, R. W. Eglese and B. L. Golden, Am. J. Math. Mgmt. Sci. 8, 209 (1988).
  17. J. Y. Yi, D. J. Oh and J. Bernholc, Phys. Rev. Lett. 67, 1594 (1991); I. A. Campbell, ibid. 68, 3351 (1992); P. C. Weakliem, C. J. Wu and E. A. Carter, ibid. 69, 200 (1992).
  18. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller and E. Teller, J. Chem. Phys. 21, 1087 (1953).
  19. J. P. Valleau and D. N. Card, J. Chem. Phys. 57, 5457 (1972); G. M. Torrie and J. P. Valleau, J. Comput. Phys. 23, 187 (1977).
  20. B. A. Berg and T. Neuhaus, Phys. Lett. B 267, 249 (1991); Phys. Rev. Lett. 68, 9 (1992).
  21. A. Hüller, Z. Phys. B 88, 79 (1992).
  22. B. A. Berg and T. Celik, Phys. Rev. Lett. 69, 2292 (1992); B. A. Berg, Int. J. Mod. Phys. C 3, 1083 (1992).
  23. E. Marinari and G Parisi, Europhys. Lett. 19, 451 (1992).
  24. B. A. Berg, Nature (London) 361, 708 (1993).
  25. J. Lee, Phys. Rev. Lett. 71, 211 (1993); ibid. 71, 2353(E) (1993).
  26. In the multicanonical notation, S(E)=β(E)E-α(E). α(E) and β(E), which appear only here, should not be confused with α and β defined in the text.
  27. J. Beardwood, J. H. Halton and J. M. Hammersley, Proc. Cambridge Philos. Soc. 55, 299 (1959); J. M. Steele, Ann. Prob. 9, 365 (1981).
  28. G. A. Croes, Oper. Res. 6, 791 (1958); S. Lin, Bell Syst. Tech. J. 44, 2245 (1965).
  29. See, e.g., Finite Size Scaling and Numerical Simulation of Statistical Systems, edited by V. Privman, (World Scientific, Singapore, 1990).

Outline

Information

Phys. Rev. E 50, R651(R)– Published 1 August, 1994

    © 1994 American Physical Society

    Sign In to Your Journals Account

    Filter

    Filter

    Article Lookup

    Enter a citation