Optimization and benchmarking of the thermal cycling algorithm
arXiv:2012.09801 · doi:10.1103/PhysRevE.104.035302
Abstract
Optimization plays a significant role in many areas of science and technology. Most of the industrial optimization problems have inordinately complex structures that render finding their global minima a daunting task. Therefore, designing heuristics that can efficiently solve such problems is of utmost importance. In this paper we benchmark and improve the thermal cycling algorithm [Phys. Rev. Lett. 79, 4297 (1997)] that is designed to overcome energy barriers in nonconvex optimization problems by temperature cycling of a pool of candidate solutions. We perform a comprehensive parameter tuning of the algorithm and demonstrate that it competes closely with other state-of-the-art algorithms such as parallel tempering with isoenergetic cluster moves, while overwhelmingly outperforming more simplistic heuristics such as simulated annealing.
arXiv comment8 pages, 5 figures, 1 table
References in corpus (18)
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum Annealing in the Transverse Ising Model
- Quantum annealing with more than one hundred qubits
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- Machine learning modeling of superconducting critical temperature
- Architectural considerations in the design of a superconducting quantum annealing processor
- Probing for quantum speedup in spin glass problems with planted solutions
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Population Annealing with Weighted Averages: A Monte Carlo Method for Rough Free Energy Landscapes
- Population annealing: Theory and application in spin glasses
- A deceptive step towards quantum speedup detection
- Optimization by thermal cycling
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Combinatorial Optimization by Iterative Partial Transcription
- Optimization of population annealing Monte Carlo for large-scale spin-glass simulations
- Analysis and Optimization of Population Annealing
- Feeding the multitude: A polynomial-time algorithm to improve sampling