Finding Ground States of Sherrington-Kirkpatrick Spin Glass by Modified Extremal Optimization
- Resource Type
- Conference
- Authors
- Zeng, Guo-Qiang; Lu, Yong-Zai; Mao, Wei-Jie
- Source
- 2010 International Conference on Computational Intelligence and Software Engineering Computational Intelligence and Software Engineering (CiSE), 2010 International Conference on. :1-5 Dec, 2010
- Subject
- Computing and Processing
General Topics for Engineers
Glass
Optimization
Probability distribution
Stationary state
Heuristic algorithms
Approximation algorithms
Algorithm design and analysis
- Language
Finding the ground states of Sherrington-Kirkpatrick (SK) spin glass, the mean-filed spin glass model with strongly connected variables, is well known as a typical NP-hard problem. This paper presents a modified extremal optimization (EO) framework to approximate its grounds states. The basic idea behind the proposed framework is to generalize the evolutionary probability distribution of the original EO algorithm. The experimental results show that the modified EO algorithms provide better performances than the original one and further support the observation that power-law is not the only good evolutionary distribution in EO, others such as exponential and hybrid distributions may be better choices.