APC-SCA: A Fully-Parallel Annealing Algorithm with Autonomous Pinning Effect Control
Daiki Okonogi, Satoru Jimbo, Kota Ando, Thiem Van Chu, Jaehoon Yu, Masato Motomura, Kazushi Kawamura · 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) · 2022
Annealing computation has recently attracted attention as it can efficiently solve various combinatorial optimization problems using an Ising model. Stochastic cellular automata annealing (SCA) is a promising algorithm that can realize fast spin-update by utilizing its parallel computing capability. However, in SCA, preparing an appropriate control of the pinning parameter is a hard task, which degrades its usability. This paper proposes a novel approach called APC-SCA (Autonomous Pinning effect Control SCA) where the spin pinning parameter can be controlled autonomously by observing individual spin flips. The evaluation results using max-cut and N-queen problems demonstrate that the proposed approach can obtain better solutions than the conventional approach with a grid search of optimal pinning parameter control.