JPS Conf. Proc. 1, 019009 (2014) [5 pages]
Proceedings of the 12th Asia Pacific Physics Conference (APPC12)
Simulated Annealing in the Variable Landscape
1Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan
2College of Engineering Systems, School of Science and Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan
Received July 15, 2013

An experimental analysis is conducted to test whether the appropriate introduction of the smoothness-temperature schedule enhances the optimizing ability of the MASSS method, the combination of the Metropolis algorithm (MA) and the search-space smoothing (SSS) method. The test is performed on two types of random traveling salesman problems. The results show that the optimization performance of the MA is substantially improved by a single smoothing alone and slightly more by a single smoothing with cooling and by a de-smoothing process with heating. The performance is compared to that of the parallel tempering method and a clear advantage of the idea of smoothing is observed depending on the problem.

©2014 The Physical Society of Japan

References

  • 1) M.Hasegawa and K.Hiramatsu, Physica A 392, 4491 (2013). 10.1016/j.physa.2013.05.037 Google Scholar
  • 2) J.Gu and X.Huang, IEEE Trans. Syst. Man Cybern. 24, 728 (1994). 10.1109/21.293486 Google Scholar
  • 3) J. E.Straub, in Recent Developments in Theoretical Studies of Proteins, ed. R.Elber (World Scientific, Singapore, 1996) p. 137. Google Scholar
  • 4) J.Schneider, M.Dankesreiter, W.Fettes, I.Morgenstern, M.Schmid, and J. M.Singer, Physica A 243, 77 (1997). 10.1016/S0378-4371(97)00207-0 Google Scholar
  • 5) N.Metropolis, A. W.Rosenbluth, M. N.Rosenbluth, A. H.Teller, and E.Teller, J. Chem. Phys. 21, 1087 (1953). 10.1063/1.1699114 Google Scholar
  • 6) S.Kirkpatrick, C. D.Gelatt,Jr., and M. P.Vecchi, Science 220,671 (1983) 10.1126/science.220.4598.671; Google ScholarV.Černý, J. Optimization Theory Appl. 45, 41 (1985). 10.1007/BF00940812 Google Scholar
  • 7) D. S.Johnson and L. A.McGeoch, in Local Search in Combinatorial Optimization, ed. E. H. L.Aarts and J. K.Lenstra (Wiley, Chichester, U.K., 1997) p. 215.Google Scholar
  • 8) F. H.Stillinger and T. A.Weber, Phys. Rev. A 25, 978 (1982) 10.1103/PhysRevA.25.978; Google ScholarF. H.Stillinger and T. A.Weber, Phys. Rev. A 28, 2408 (1983) 10.1103/PhysRevA.28.2408; Google ScholarF. H.Stillinger and T. A.Weber, Science 225, 983 (1984). 10.1126/science.225.4666.983 Google Scholar
  • 9) M.Hasegawa, Phys. Rev. E 83, 036708 (2011) 10.1103/PhysRevE.83.036708; Google ScholarM.Hasegawa, J. Phys. Soc. Jpn. 74, 2872 (2005). 10.1143/JPSJ.74.2872[Abstract] Google Scholar
  • 10) K.Hukushima and K.Nemoto, J. Phys. Soc. Jpn. 65, 1604 (1996) 10.1143/JPSJ.65.1604; [Abstract] Google ScholarB.Coluzzi and G.Parisi, J. Phys. A 31, 4349 (1998). 10.1088/0305-4470/31/19/004 Google Scholar