Genetic embedded matching approach to ground states in continuous-spin systems

Abstract

Due to an extremely rugged structure of the free energy landscape, the determination of spin-glass ground states is among the hardest known optimization problems, found to be NP-hard in the most general case. Owing to the specific structure of local (free) energy minima, general-purpose optimization strategies perform relatively poorly on these problems, and a number of specially tailored optimization techniques have been developed in particular for the Ising spin glass and similar discrete systems. Here, an efficient optimization heuristic for the much less discussed case of continuous spins is introduced, based on the combination of an embedding of Ising spins into the continuous rotators and an appropriate variant of a genetic algorithm. Statistical techniques for insuring high reliability in finding (numerically) exact ground states are discussed, and the method is benchmarked against the simulated annealing approach.

17 pages, 12 figures, 1 table

References in corpus (6)

• Performance Limitations of Flat Histogram Methods and Optimality of Wang-Landau Sampling
• Conformal Invariance and SLE in Two-Dimensional Ising Spin Glasses
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• Finite-Size Scaling of the Domain Wall Entropy Distributions for the 2D $\pm J$ Ising Spin Glass
• Domain wall entropy of the bimodal two-dimensional Ising spin glass
• Spin and chiral stiffness of the XY spin glass in two dimensions

Cited by in corpus (9)

• Error estimation and reduction with cross correlations
• Domain-wall excitations in the two-dimensional Ising spin glass
• Exact Ground States of Large Two-Dimensional Planar Ising Spin Glasses
• The ground state energy of the Edwards-Anderson spin glass model with a parallel tempering Monte Carlo algorithm
• Optimized GPU simulation of continuous-spin glass models
• Zero-temperature phase of the XY spin glass in two dimensions: Genetic embedded matching heuristic
• A comparative study of selected parallel tempering methods
• Approximate ground states of the random-field Potts model from graph cuts
• Quasi-exact ground-state algorithm for the random-field Potts model