Simulated Annealing with estimated temperature

Article type: Research Article

Authors: Poupaert, Eric | Deville, Yves

Affiliations: Department of Computing Science and Engineering, Université Catholique de Louvain, Louvain‐la‐Neuve, B‐1348 Belgium

Abstract: Temperature is the control parameter of Simulated Annealing, one of the best‐known local search optimisation algorithms. Scheduling the temperature evolution during optimisation is a crucial component of simulated annealing. We propose to elect acceptance probability as a new control parameter of simulated annealing. The concept of imposing a schedule to acceptance probability throughout optimisation yields a new algorithm. A general local search optimisation platform has been designed and implemented to evaluate this algorithm on various representative problems. An efficiency analysis method of stochastic algorithms is proposed to compare the performance of this algorithm with other classical and state‐of‐the‐art algorithms. Beyond excellent performance, our algorithm demonstrates the advantage of the new exploit of acceptance probability. This concept can also be applied to other stochastic algorithms such as Evolutionary Algorithms.

Keywords: Optimisationsep metaheuristics, stochastic, local search, simulated annealing, evolutionary algorithms, temperature schedule, travelling salesman problem (TSP), function optimisation, efficiency analysis

Journal: AI Communications, vol. 13, no. 1, pp. 19-26, 2000