VEO, a Vectorized Heuristic to Solve Complex Spin Glass Problems

We will discuss a new evolutionary search heuristic for NP-hard combinatorial optimization problems. It develops the framework of Extremal Optimization (EO) [1] into a fully vectorized heuristic at a gain in speed of up to ∼N²/100 over EO to solve NP-hard problems such as finding ground-state configurations for many spin glass problems that form complex energy landscapes. To that effect, the random sequential access for updating poorly adapted variables that endows EO with its accuracy has to be significantly re-conceptualized. The resulting implementation of vectorized EO (VEO) deterministically moves an extensive number of those unstable or barely stable variables in each parallel update and only infuses a measured amount of randomness into the process when all such variables are resolved and the system finds itself in a near-optimal configuration. In its focus on updating variables at the edge of stability, VEO (like EO) operates near a critical point of the update dynamics where its high susceptibility entails a broad, pseudo-random exploration of the energy landscape through adaptive avalanches that lead to frequent returns to near-optimal states. Even in its most naive (sequential) implementation, it produces results, e.g., for ground states of the Sherrington-Kirkpatrick spin glass (SK), at much higher efficiency than other methods while producing physically significant results (with <0.1% accuracy) for systems of size N ≈ 10⁴, an order of magnitude improvement. We demonstrate its effectiveness in determining the finite-size corrections to Parisi's replica symmetry breaking calculation for the ground state energy of SK.

 

[1] SB and AG Percus, "Optimization with Extremal Dynamics", PRL86(2001)5211 (https://doi.org/10.1103/PhysRevLett.86.5211).