A new simulated annealing algorithm

Abstract

Simulated Annealing (SA) is a powerful stochastic search algorithm applicable to a wide range of problems for which little prior knowledge is available. The annealing schedule, i.e., the temperature decreasing rate used in SA is an important factor which affects SA's rate of convergence. This paper investigates annealing schedules used in various SA algorithms, e.g., the classical SA (CSA) [1], fast SA (FSA) [2] and very fast SA (VFSA) [3], and proposes a new SA (NSA) algorithm whose annealing schedule is exponentially faster than that of VFSA. The heuristic proof given in the paper follows the same method as that used by Szu and Hartley [2] and Ingber [3] in their studies. The paper also discusses the relationship between the annealing schedule and SA's rate of convergence