Replicated Simulated Annealing with a Global-Best Reference for Efficient Hardware Implementation
Makiko Konoshima, Hirotaka Tamura, Yoshiyuki Kabashima · Journal of the Physical Society of Japan · 2022
We propose a metaheuristic method that efficiently finds the optimal solution of combinatorial problems of a certain type by avoiding local minima using multiple replicas. The device is similar to that of the Replicated Simulated Annealing (RSA) developed by Baldassi et al. (2016), in which a reference state is employed for taking the replicas out of local minima. However, RSA needs to update the reference state at each iteration of the annealing process, which can be computational and communication bottlenecks in hardware implementation. For reducing this drawback, we propose to replace the reference state with the lowest energy state obtained up to each iteration. Extensive numerical experiments for three example problems show that the number of steps required to obtain the optimal solution is similar to that of RSA while the number of updates of the reference state is reduced significantly. This implies that the proposed method is more suitable for hardware implementation than RSA.