Analysis of the statistical behavior of the genetic cluster-exact approximation

Abstract

The genetic cluster-exact approximation algorithm is an efficient method to calculate ground states of EA spin glasses. The method can be used to study ground-state landscapes by calculating many independent ground states for each realization of the disorder. The algorithm is analyzed with respect to the statistics of the ground states and the,valleys of the energy landscape. Furthermore, the distribution inside each valley is evaluated. It is shown that the algorithm does not lead to a true T = 0 thermodynamic distribution, i.e. each ground state has not the same frequency of occurrence when performing many runs. An extension of the technique is outlined, which guarantees that each ground states occurs with the same probability. (C) 2000 Elsevier Science B.V. All rights reserved.