11. Acceptance Rules
Society for Industrial and Applied Mathematics eBooks · 2002
Recall that in the Metropolis algorithm a move is made by 1. selecting a neighbor according to the move class, and 2. deciding whether to accept a move to the selected neighbor. The previous chapter dealt with the first step; this chapter deals with the second. The acceptance rule specified in the Metropolis algorithm is to accept the next state with probability PMetropolis =min (1,exp (−ΔE/T) ) 11.1 and thus depends on the current temperature T. As with all aspects of simulated annealing, there is a significant body of literature exploring variants of this acceptance criterion. We caution the reader that varying the acceptance rule might also vary the resulting equilibrium distribution. The oldest variant comes not from annealing but from John Holland's classic work [Hol75] leading to genetic algorithms. This family of algorithms is outside the scope of the present book, but we nevertheless mention one simple variant of a population-based acceptance criterion. Select K neighbors (offspring) for each member of a population of size N and make up the population of the next generation by accepting the N lowest energy states of the K N states for breeding at the next iteration. This acceptance rule has the problem that the population loses diversity rather quickly, and it has to be modified to guarantee the possibility of some large moves along the lines of the discussions in the second half of Chapter 10. The first true variant of the Metropolis acceptance criterion probably dates back to Szu and Hartley's fast annealing (see Chapter 10), which used the acceptance probability PFA = 1 1+exp (Δ E/T) , 11.2 which, like Metropolis acceptance, has the Boltzmann distribution as its stationary distribution at a fixed temperature T. The fast annealing acceptance probability is always less than the Metropolis acceptance probability with the difference becoming negligible for large ΔE/T.