185.

[Cover] [Contents] [Index]

Page 264

probability P(w_r′|w_s−_(r}) instead of energy change as used by Metropolis et al. (1953), and can be regarded as a ‘hot bath’ version of Metropolis’s algorithm (i.e. a temperature parameter is added).

The algorithm is shown in Figure 6.19. It is started at a high temperature T. After the Metropolis algorithm converges to equilibrium at the current temperature T, the value of T is decreased according to some carefully defined criterion called a cooling schedule. The process is repeated until the system becomes frozen (i.e. T → 0). It is shown that a high temperature T can increase the probability of w_r being replaced by new class w_r′ (because Δ<0, large T indicates large exp(Δ/T)), even though the energy U(w_r′|d_r) of the new class w_r′ is higher (that is, probability is lower) than that of class w_r. As the system cools down and temperature T decreases, only small increases of U are accepted. Near the freezing point (T → 0), no increase of U can be accepted. The relationship between temperature T and exp(Δ/T) is shown in Figure 6.20.

The central idea of the SA algorithm is equivalent to the introduction of noise into the system to shake the search process away from a local minimum. The idea is similar to a process in metallurgy in which a small region of a metal structure is heated until it is pliable enough to be reconstructed into the desired shape. The metal is then cooled very slowly to make sure that it is given enough time to respond. Changes in temperature must be very small until the metal has hardened.

Geman and Geman (1984) present proofs of two convergence theorems. The first concerns the convergence of Metropolis algorithm: if every con

Figure 6.19 Simulated annealing algorithm. See text for details of parameter assignments.

[Cover] [Contents] [Index]