Analysis of Evolutionary Algorithms on the One-Dimensional Spin Glass with Power-Law Interactions

Abstract

This paper provides an in-depth empirical analysis of several evolutionary algorithms on the one-dimensional spin glass model with power-law interactions. The considered spin glass model provides a mechanism for tuning the effective range of interactions, what makes the problem interesting as an algorithm benchmark. As algorithms, the paper considers the genetic algorithm (GA) with twopoint and uniform crossover, and the hierarchical Bayesian optimization algorithm (hBOA). hBOA is shown to outperform both variants of GA, whereas GA with uniform crossover is shown to perform worst. The differences between the compared algorithms become more significant as the problem size grows and as the range of interactions decreases. Unlike for GA with uniform crossover, for hBOA and GA with twopoint crossover, instances with short-range interactions are shown to be easier. The paper also points out interesting avenues for future research.

References in corpus (10)

• A Bayesian Approach to Learning Bayesian Networks with Local Structure
• Monte Carlo studies of the one-dimensional Ising spin glass with power-law interactions
• Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses
• Ground-state clusters of two-, three- and four-dimensional +-J Ising spin glasses
• Universality-class dependence of energy distributions in spin glasses
• Hysteretic optimization for the Sherrington-Kirkpatrick spin glass
• Local field distributions in spin glasses
• Spin glasses and algorithm benchmarks: A one-dimensional view
• Finding Ground States of Sherrington-Kirkpatrick Spin Glasses with Hierarchical BOA and Genetic Algorithms
• Ground-state energy and frustration of the Sherrington-Kirkpatrick model and related models

Cited by in corpus (2)

• A probabilistic evolutionary optimization approach to compute quasiparticle braids
• Evolutionary Approaches to Optimization Problems in Chimera Topologies