Hardware acceleration of simulated annealing for constraint satisfaction problems

Abstract

Abstract Simulated annealing (SA), a metaheuristic algorithm inspired by physical annealing processes, attempts to solve combinatorial optimization problems by performing a stochastic search that iteratively explores the solution space. Probabilistic solution evaluation allows the algorithm to escape local minima and progressively converge toward a global optimum, even within complex solution landscapes. In this work, we present the hardware acceleration of SA for spatial optimization within constrained environments, specifically targeting drone placement that maximizes area coverage while avoiding no-fly zones. Stochasticity is introduced through a true random number generator (TRNG) based on two-dimensional (2D) materials. The system energy is evaluated using a 2D logic circuit and the acceptance of candidate solutions is governed by a programmable 2D circuit with tunable threshold behavior. For a representative drone placement task, our hardware-based annealing accelerator circuit modules consume 43 nJ of energy per iteration and achieve an 1800-fold search acceleration relative to brute-force exploration of the solution space. This work also underscores the potential of 2D-material-enabled stochastic and programmable hardware for real-time constrained optimization.