Local Energy Distribution Based Hyperparameter Determination for Stochastic Simulated Annealing

Abstract

This paper presents a local energy distribution based hyperparameter determination for stochastic simulated annealing (SSA). SSA is capable of solving combinatorial optimization problems faster than typical simulated annealing (SA), but requires a time-consuming hyperparameter search. The proposed method determines hyperparameters based on the local energy distributions of spins (probabilistic bits). The spin is a basic computing element of SSA and is graphically connected to other spins with its weights. The distribution of the local energy can be estimated based on the central limit theorem (CLT). The CLT-based normal distribution is used to determine the hyperparameters, which reduces the time complexity for hyperparameter search from O(n^3) of the conventional method to O(1). The performance of SSA with the determined hyperparameters is evaluated on the Gset and K2000 benchmarks for maximum-cut problems. The results show that the proposed method achieves mean cut values of approximately 98% of the best-known cut values.

arXiv comment15 pages

References in corpus (12)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Quantum annealing with more than one hundred qubits
• Stochastic p-bits for Invertible Logic
• VLSI Implementation of Deep Neural Network Using Integral Stochastic Computing
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• p-Bits for Probabilistic Spin Logic
• Efficient CMOS Invertible Logic Using Stochastic Computing
• Experimental quantum annealing: case study involving the graph isomorphism problem
• Memory-Efficient FPGA Implementation of Stochastic Simulated Annealing
• Solving maximum cut problems by simulated annealing
• Fast Solving Complete 2000-Node Optimization Using Stochastic-Computing Simulated Annealing

Cited by in corpus (3)

• A Ferroelectric Compute-in-Memory Annealer for Combinatorial Optimization Problems
• GPU-accelerated simulated annealing based on p-bits with real-world device-variability modeling
• pc-COP: An Efficient and Configurable 2048-p-Bit Fully-Connected Probabilistic Computing Accelerator for Combinatorial Optimization