Classical Thermodynamics-based Parallel Annealing Algorithm for High-speed and Robust Combinatorial Optimization
Kyo Kuroki, Satoru Jimbo, Thiem Van Chu, Masato Motomura, Kazushi Kawamura · Proceedings of the Genetic and Evolutionary Computation Conference · 2024
In recent years, quantum annealing has triggered active research on annealing methods for solving various combinatorial optimization problems (COPs) by mapping them to the Ising model based on spin glass theory. In particular, parallel annealing algorithms (PAAs) that can update all variables simultaneously attract attention due to fast optimization using parallel computers, either as an extension of Simulated Annealing rooted in classical thermodynamics or as a quantum-inspired algorithm. However, both types of PAAs face their own challenges. The classical thermodynamics-based PAAs (c-PAAs) perform inferior to the quantum-inspired PAAs (q-PAAs), whereas the q-PAAs require more parameters to be tuned than the c-PAAs. This paper proposes a new c-PAA based on Mean Field Annealing, which has the unique feature of updating analog variables deterministically. The proposed PAA achieves high speed and robustness despite fewer parameters than the q-PAAs, which means the proposed PAA breaks through the challenges of conventional PAAs. We demonstrate its performance through experiments on four types of COPs: Maximum Cut Problem, Graph Coloring Problem, Maximum Independent Set Problem, and Traveling Salesman Problem. These results imply that unless a real physical phenomenon is used, quantum-inspired algorithms cannot be considered superior to classical thermodynamics-based algorithms.