Rare Events of Ising Spin Glasses

Title: Rare Events of Ising Spin Glasses

Research Question: How can we efficiently find ground states in Ising spin glasses, which are known for their complex and multimodal energy landscapes?

Methodology: The researchers used a hierarchical Bayesian optimization algorithm (hBOA) combined with a deterministic bit-flip hill climber. The hBOA is a global searcher that explores the problem space to find promising regions, while the local searcher, the bit-flip hill climber, refines the solution within these regions.

Results: The researchers found that the complexity of all studied spin glass systems is dominated by rare events of extremely hard spin glass samples. They also discovered that the number of steps performed by both the global and local searchers follows Fréchet distribution. This indicates good scalability of hBOA with local search.

Implications: The results suggest that for highly multimodal constraint satisfaction problems like Ising spin glasses, recombination-based search can provide qualitatively better results than mutation-based search. This is particularly important for genetic and evolutionary computation, as it highlights the potential of combining global and local search strategies to tackle complex optimization problems.

Link to Article: https://arxiv.org/abs/0402030v1 Authors: arXiv ID: 0402030v1