9.1
Simulated annealing (SA), introduced independently by [Cerny 1982,Cerny 1985] and [Kirkpatrick et al. 1982,Kirkpatrick et al. 1983], is a stochastic algorithm for combinatorial optimization. It simulates the physical annealing procedure in which a physical substance is melted and then slowly cooled in search of a low energy configuration. Instead of performing gradient descent, a random search method, such as Metropolis algorithm [Metropolis and etal 1953] or Gibbs sampler [Geman and Geman 1984], is used to locate the next configuration. The random search is controlled by a sequence of decreasing temperature T. At high T, large increases in E may be accepted; at lower T, only small increases may be accepted; and near the freezing T, no increases can be accepted. This enables the algorithm to escape from local minima into the global minimum.