Finding Ground States of Sherrington-Kirkpatrick Spin Glass by Modified Extremal Optimization
作者： Guo-Qiang Zeng , Yong-Zai Lu , Wei-Jie Mao
DOI: 10.1109/CISE.2010.5677137
关键词: Distribution (mathematics) 、 Probability distribution 、 Combinatorics 、 Spin glass 、 Approximation algorithm 、 Stationary state 、 Statistical physics 、 Extremal optimization 、 Strongly connected component 、 Mathematics 、 Exponential distribution
摘要: Finding the ground states of Sherrington-Kirkpatrick (SK) spin glass, mean-filed glass model with strongly connected variables, is well known as a typical NP-hard problem. This paper presents modified extremal optimization (EO) framework to approximate its grounds states. The basic idea behind proposed generalize evolutionary probability distribution original EO algorithm. experimental results show that algorithms provide better performances than one and further support observation power-law not only good in EO, others such exponential hybrid distributions may be choices.
sci-hub.se 参考文章(33)
Claudio Giberti, Cecilia Vernia, Numerical study of ground state energy fluctuations in spin glasses arXiv: Disordered Systems and Neural Networks. ,(2008)
S. Kobe, Ground-state energy and frustration of the Sherrington-Kirkpatrick model and related models arXiv: Disordered Systems and Neural Networks. ,(2003)
Allon G. Percus, Stefan Boettcher, Extremal optimization: methods derived from co-evolution genetic and evolutionary computation conference. pp. 825- 832 ,(1999)
Per Bak, Kim Sneppen, Punctuated equilibrium and criticality in a simple model of evolution. Physical Review Letters. ,vol. 71, pp. 4083- 4086 ,(1993) , 10.1103/PHYSREVLETT.71.4083
S F Edwards, P W Anderson, Theory of spin glasses Journal of Physics F: Metal Physics. ,vol. 5, pp. 965- 974 ,(1975) , 10.1088/0305-4608/5/5/017
S. Boettcher, Extremal optimization for Sherrington-Kirkpatrick spin glasses European Physical Journal B. ,vol. 46, pp. 501- 505 ,(2005) , 10.1140/EPJB/E2005-00280-6
M. Mezard, G. Parisi, M. A. Virasoro, David J. Thouless, Spin Glass Theory and Beyond ,(1986)
Aaron Clauset, Cosma Rohilla Shalizi, M. E. J. Newman, Power-Law Distributions in Empirical Data Siam Review. ,vol. 51, pp. 661- 703 ,(2009) , 10.1137/070710111
Gary S. Grest, C. M. Soukoulis, K. Levin, Cooling-rate dependence for the spin-glass ground-state energy: Implications for optimization by simulated annealing. Physical Review Letters. ,vol. 56, pp. 1148- 1151 ,(1986) , 10.1103/PHYSREVLETT.56.1148
Karl Hoffmann, Frank Heilmann, Peter Salamon, Fitness threshold accepting over extremal optimization ranks Physical Review E. ,vol. 70, pp. 046704- ,(2004) , 10.1103/PHYSREVE.70.046704