Finding Ground States of Sherrington-Kirkpatrick Spin Glass by Modified Extremal Optimization

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.