Optimal schedules for annealing algorithms
arXiv:2402.14717 · doi:10.1103/PhysRevE.109.065301
Abstract
Annealing algorithms such as simulated annealing and population annealing are widely used both for sampling the Gibbs distribution and solving optimization problems (i.e. finding ground states). For both statistical mechanics and optimization, additional parameters beyond temperature are often needed such as chemical potentials, external fields or Lagrange multipliers enforcing constraints. In this paper we derive a formalism for optimal annealing schedules in multidimensional parameter spaces using methods from non-equilibrium statistical mechanics. The results are closely related to work on optimal control of thermodynamic systems [Sivak and Crooks, PRL 108, 190602 (2012)]. Within the formalism, we compare the efficiency of population annealing and multiple weighted runs of simulated annealing ("annealed importance sampling") and discuss the effects of non-ergodicity on both algorithms. Theoretical results are supported by numerical simulations of spin glasses.
17 pages, 5 figures
References in corpus (21)
- A nonequilibrium equality for free energy differences
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Simulated Tempering: A New Monte Carlo Scheme
- Equilibrium free energy differences from nonequilibrium measurements: a master equation approach
- Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram
- Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference
- Thermodynamic metrics and optimal paths
- Feedback-optimized parallel tempering Monte Carlo
- Universality in three-dimensional Ising spin glasses: A Monte Carlo study
- The geometry of thermodynamic control
- Population Annealing with Weighted Averages: A Monte Carlo Method for Rough Free Energy Landscapes
- Make life simple: unleash the full power of the parallel tempering algorithm
- Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
- Dynamic Riemannian Geometry of the Ising Model
- Population annealing: Theory and application in spin glasses
- GPU accelerated population annealing algorithm
- Strengths and Weaknesses of Parallel Tempering
- Chaos in spin glasses revealed through thermal boundary conditions
- Understanding population annealing Monte Carlo simulations
- Optimization of population annealing Monte Carlo for large-scale spin-glass simulations
- Analysis and Optimization of Population Annealing