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

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Genetic embedded matching approach to ground states in continuous-spin systems

Martin Weigel*

  • Department of Mathematics and the Maxwell Institute for Mathematical Sciences, Heriot-Watt University, Edinburgh, EH14 4AS, United Kingdom and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

  • *Present address: Institut für Physik, Johannes-Gutenberg-Universität Mainz, Staudinger Weg 7, 55099 Mainz, Germany; weigel@uni-mainz.de
PDF

Phys. Rev. E 76, 066706 – Published 20 December, 2007

DOI: https://doi.org/10.1103/PhysRevE.76.066706

Abstract

Due to an extremely rugged structure of the free energy landscape, the determination of spin-glass ground states is among the hardest known optimization problems, found to be NP hard in the most general case. Owing to the specific structure of local (free) energy minima, general-purpose optimization strategies perform relatively poorly on these problems, and a number of specially tailored optimization techniques have been developed in particular for the Ising spin glass and similar discrete systems. Here, an efficient optimization heuristic for the much less discussed case of continuous spins is introduced, based on the combination of an embedding of Ising spins into the continuous rotators and an appropriate variant of a genetic algorithm. Statistical techniques for insuring high reliability in finding (numerically) exact ground states are discussed, and the method is benchmarked against the simulated annealing approach.

View figure in article

Article Text

References (80)

  1. D. J. Wales, Energy Landscapes (Cambridge University Press, Cambridge, 2003).
  2. K. Binder and A. P. Young, Rev. Mod. Phys. 58, 801 (1986).
  3. A. K. Hartmann and H. Rieger, Optimization Algorithms in Physics (Wiley, Berlin, 2002).
  4. S. S. Plotkin and J. N. Onuchic, Q. Rev. Biophys. 35, 111 (2002).
  5. D. A. Huse and D. S. Fisher, Phys. Rev. Lett. 57, 2203 (1986).
  6. P. Garstecki, T. X. Hoang, and M. Cieplak, Phys. Rev. E 60, 3219 (1999).
  7. S. Mertens, Comput. Sci. Eng. 4, 31 (2002).
  8. C. H. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, MA, 1994).
  9. S. F. Edwards and P. W. Anderson, J. Phys. F: Met. Phys. 5, 965 (1975).
  10. F. Barahona, J. Phys. A 15, 3241 (1982).
  11. C. P. Bachas, J. Phys. A 17, L709 (1984).
  12. I. Bieche, R. Maynard, R. Rammal, and J. P. Uhry, J. Phys. A 13, 2553 (1980).
  13. L. Saul and M. Kardar, Phys. Rev. E 48, R3221 (1993).
  14. A. Galluccio, M. Loebl, and J. Vondrák, Phys. Rev. Lett. 84, 5924 (2000).
  15. F. Liers, M. Palassini, A. K. Hartmann, and M. Jünger, Phys. Rev. B 68, 094406 (2003).
  16. S. Kirkpatrick, J. Stat. Phys. 34, 975 (1984).
  17. B. A. Berg, U. E. Hansmann, and T. Celik, Phys. Rev. B 50, 16444 (1994).
  18. K. Hukushima and K. Nemoto, J. Phys. Soc. Jpn. 65, 1604 (1996).
  19. A. K. Hartmann, Physica A 224, 480 (1996).
  20. K. F. Pál, Physica A 223, 283 (1996).
  21. E. Marinari and G. Parisi, Phys. Rev. B 62, 11677 (2000).
  22. J. Houdayer and O. C. Martin, Phys. Rev. E 64, 056704 (2001).
  23. S. Boettcher and A. G. Percus, Phys. Rev. Lett. 86, 5211 (2001).
  24. J. J. Moreno, H. G. Katzgraber, and A. K. Hartmann, Int. J. Mod. Phys. C 14, 285 (2003).
  25. G. S. Grest, C. M. Soukoulis, and K. Levin, Phys. Rev. Lett. 56, 1148 (1986).
  26. N. Kawashima and H. Rieger, in Frustrated Spin Systems, edited by H. T. Diep (World Scientific, Singapore, 2005), Chap. 9, p. 491.
  27. C. Amoruso, A. K. Hartmann, M. B. Hastings, and M. A. Moore, Phys. Rev. Lett. 97, 267202 (2006).
  28. R. Fisch, J. Stat. Phys. 125, 789 (2006).
  29. A. Aromsawa and J. Poulter, Phys. Rev. B 76, 064427 (2007).
  30. A. K. Hartmann, e-print arXiv:0704.2748.
  31. J. E. Greedan, J. Mater. Chem. 11, 37 (2001).
  32. P. A. Ferrari, A. Frigessi, and P. G. de Sá, J. R. Stat. Soc. Ser. B (Methodol.) 57, 485 (1995).
  33. J. M. Kosterlitz and N. Akino, Phys. Rev. Lett. 82, 4094 (1999).
  34. L. R. Walker and R. E. Walstedt, Phys. Rev. B 22, 3816 (1980).
  35. B. W. Morris, S. G. Colborne, M. A. Moore, A. J. Bray, and J. Canisius, J. Phys. C 19, 1157 (1986).
  36. H. Kawamura and M. Tanemura, J. Phys. Soc. Jpn. 60, 608 (1991).
  37. J. Maucourt and D. R. Grempel, Phys. Rev. Lett. 80, 770 (1998).
  38. L. W. Lee and A. P. Young, Phys. Rev. E 72, 036124 (2005).
  39. M. Weigel and M. J. P. Gingras, Phys. Rev. Lett. 96, 097206 (2006).
  40. M. Weigel and M. J. P. Gingras, e-print arXiv:0706.0227.
  41. G. Toulouse, Commun. Phys. (London) 2, 115 (1977).
  42. A. Gibbons, Algorithmic Graph Theory (Cambridge University Press, Cambridge, 1985).
  43. J. Edmonds, J. Res. Natl. Bur. Stand., Sect. B 69, 125 (1965).
  44. W. Cook and A. Rohe, INFORMS J. Comput. 11, 138 (1999).
  45. J. W. Landry and S. N. Coppersmith, Phys. Rev. B 65, 134404 (2002).
  46. C. Amoruso, E. Marinari, O. C. Martin, and A. Pagnani, Phys. Rev. Lett. 91, 087201 (2003).
  47. U. Wolff, Phys. Rev. Lett. 62, 361 (1989).
  48. C. L. Henley, Ann. Phys. (N.Y.) 156, 368 (1984).
  49. N. D. Mermin, Rev. Mod. Phys. 51, 591 (1979).
  50. G. Toulouse, Phys. Rep. 49, 267 (1979).
  51. M. Weigel and M. J. P. Gingras, J. Phys.: Condens. Matter 19, 145217 (2007).
  52. D. S. Fisher and D. A. Huse, Phys. Rev. Lett. 56, 1601 (1986).
  53. A. J. Bray and M. A. Moore, in Heidelberg Colloquium on Glassy Dynamics, edited by J. L. van Hemmen and I. Morgenstern (Springer, Heidelberg, 1987), p. 121.
  54. M. Mezard, G. Parisi, N. Sourlas, G. Toulouse, and M. Virasoro, J. Phys. (Paris) 45, 843 (1984).
  55. J. Houdayer and O. C. Martin, Europhys. Lett. 49, 794 (2000).
  56. C. L. Henley, Ann. Phys. (N.Y.) 156, 324 (1984).
  57. J. Hoshen and R. Kopelman, Phys. Rev. B 14, 3438 (1976).
  58. Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs (Springer, Berlin, 1996).
  59. P. Sutton and S. Boyden, Am. J. Phys. 62, 549 (1994).
  60. U. Gropengiesser, J. Stat. Phys. 79, 1005 (1995).
  61. A. K. Hartmann, Phys. Rev. B 59, 3617 (1999).
  62. K. Pál, Biol. Cybern. 73, 335 (1995).
  63. M. Palassini and A. P. Young, Phys. Rev. Lett. 83, 5126 (1999).
  64. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science 220, 671 (1983).
  65. B. A. Berg and W. Janke, Phys. Rev. Lett. 80, 4771 (1998).
  66. S. Alder, S. Trebst, A. K. Hartmann, and M. Troyer, J. Stat. Mech.: Theory Exp. 2004, P07008.
  67. S. Geman and D. Geman, IEEE Trans. Pattern Anal. Mach. Intell. 6, 721 (1984).
  68. E. Castillo, Extreme Value Theory in Engineering (Academic Press, London, 1988).
  69. P. Dayal, S. Trebst, S. Wessel, D. Würtz, M. Troyer, S. Sabhapandit, and S. N. Coppersmith, Phys. Rev. Lett. 92, 097201 (2004).
  70. E. Bittner and W. Janke, Europhys. Lett. 74, 195 (2006).
  71. W. Feller, An Introduction to Probability Theory and its Applications (Wiley, New York, 1968), Vol. 1.
  72. M. A. Moore, Phys. Rev. Lett. 58, 1703 (1987).
  73. S. Kobe and T. Klotz, Phys. Rev. E 52, 5660 (1995).
  74. H. Kawamura, Phys. Rev. B 51, 12398 (1995).
  75. W. M. Saslow and G. Parker, Phys. Rev. Lett. 56, 1074 (1986).
  76. H. Kawamura, Phys. Rev. Lett. 68, 3785 (1992).
  77. A. K. Hartmann, Eur. Phys. J. B 13, 539 (2000).

  78. The product ∏nΦ◻n over all plaquettes of the lattice is +1 for an even and −1 for an odd number of frustrated plaquettes. On the other hand, ∏nΦ◻n=∏⟨ij⟩(sgnJij)2=+1, since each bond occurs twice in the product when taking into account external plaquettes for open boundaries.

  79. It is easy to see, for instance, that a pure Ising ground state Si=±(1,0,…)T, i=1,…,L2 is invariant under the embedded matching algorithm as well as the local spin quench (2).

  80. Computationally, this enlargement of transformations is not very efficient since for inversions Si↦−Si the identification of frustrated plaquettes of the embedded Ising model depends on the configuration {Si} of the O(n) spins, i.e., one finds sgnJ̃ijr≠sgnJij in general.

Outline

Information

Phys. Rev. E 76, 066706– Published 20 December, 2007
  • Received 29 June 2007

© 2007 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation