Quick Search: Journal  Author  Title/Abstract  Vol./Year 

J. Phys. Soc. Jpn. 72 (2003) pp. 1380-1383  |Next Article|  |Table of Contents|
|Full Text PDF (87K)| |Buy This Article|

A Comparison of Extremal Optimization with Flat-Histogram and Equal-Hit Dynamics for Finding Spin–Glass Ground States

Jian-Sheng Wang1 and Yutaka Okabe2

1Singapore-MIT Alliance and Department of Computational Science, National University of Singapore, Singapore 119260, Republic of Singapore
2Department of Physics, Tokyo Metropolitan University, Hachioji, Tokyo 192-0397

(Received October 4, 2002)

We compare the performance of extremal optimization (EO), flat-histogram and equal-hit algorithms for finding spin–glass ground states. The first-passage-times to a ground state are computed. At optimal parameter of τ=1.15, EO outperforms other methods for small system sizes, but equal-hit algorithm is competitive to EO, particularly for large systems. Flat-histogram and equal-hit algorithms offer additional advantage that they can be used for equilibrium thermodynamic calculations. We also propose a method to turn EO into a useful algorithm for equilibrium calculations. ©2003 The Physical Society of Japan

KEYWORDS: extremal optimization, flat-histogram algorithm, equal-hit algorithm, spin–glass model, ground state
URL: http://jpsj.ipap.jp/link?JPSJ/72/1380/
DOI: 10.1143/JPSJ.72.1380


|Full Text PDF (87K)| |Buy This Article| Citation:

References | Citing Article (1)

  1. S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi: Science 220 (1983) 671.
  2. J. Holland: Adaptation in Natural and Artificial Systems (University of Michigan Press, Ann Arbor, 1975).
  3. N. Kawashima and M. Suzuki: J. Phys. A 25 (1992) 1055[IoP STACKS].
  4. F.-M. Dittes: Phys. Rev. Lett. 76 (1996) 4651[APS].
  5. K. F. Pal: Physica A 223 (1996) 283[CrossRef].
  6. A. K. Hartmann: Europhys. Lett. 40 (1997) 429[CrossRef].
  7. K. Chen: Europhys. Lett. 43 (1998) 635[CrossRef].
  8. B. A. Berg and W. Janke: Phys. Rev. Lett. 80 (1998) 4771[APS].
  9. J. Houdayer and O. C. Martin: Phys. Rev. Lett. 83 (1999) 1030[APS].
  10. J. Dall and P. Sibani: Comput. Phys. Commun. 141 (2001) 260[CrossRef].
  11. S. Boettcher and A. G. Percus: Artif. Intell. 119 (2000) 275.
  12. S. Boettcher and A. G. Percus: Phys. Rev. Lett. 86 (2001) 5211[APS].
  13. P. Bak, C. Tang and K. Wiesenfeld: Phys. Rev. Lett. 59 (1987) 381[APS].
  14. B. A. Berg and T. Neuhaus: Phys. Rev. Lett. 68 (1992) 9[APS].
  15. B. Hesselbo and R. B. Stinchcombe: Phys. Rev. Lett. 74 (1995) 2151[APS].
  16. K. Hukushima and Y. Nemoto: J. Phys. Soc. Jpn. 65 (1996) 1604[IPAP].
  17. J.-S. Wang: Eur. Phys. J. B 8 (1999) 287[CrossRef].
  18. Z. F. Zhan, L. W. Lee and J.-S. Wang: Physica A 285 (2000) 239[CrossRef].
  19. K. Binder and A. P. Young: Rev. Mod. Phys. 58 (1986) 801[APS]; M. Mezard, G. Parisi and M. A. Virasoro: Spin Glass Theory and Beyond (World Scientific, Singapore, 1987).
  20. F. Barahona: J. Phys. A 15 (1982) 3241[IoP STACKS].
  21. P. M. C. de Oliveira, T. J. P. Penna and H. J. Herrmann: Braz. J. Phys. 26 (1996) 677.
  22. B. A. Berg: Nature 361 (1993) 708[CrossRef].
  23. A. B. Bortz, M. H. Kalos and J. L. Lebowitz: J. Comput. Phys. 17 (1975) 10.
  24. J.-S. Wang and R. H. Swendsen: J. Stat. Phys. 106 (2002) 245.
  25. R. H. Swendsen, B. Diggs, J.-S. Wang, S.-T. Li, C. Genovese and J. B. Kadane: Int. J. Mod. Phys. C 10 (1999) 1563.
  26. http://www.informatik.uni-koeln.de/ls_juenger/projects/sgs.html. We thank Thomas Lange for generating the samples used in the comparisons.
  27. P. M. C. de Oliveira: Eur. Phys. J. B 6 (1998) 111[CrossRef]; P. M. C. Oliveira: cond-mat/0204332[e-print arXiv].
  28. B. A. Berg and U. H. E. Hansmann: Eur. Phys. J. B 6 (1998) 395[CrossRef].
|TOP|  |Next Article|  |Table of Contents| |JPSJ Home|
Copyright © 2010 The Physical Society of Japan
Contact Information