PAPERBACK
\$52.75

• #### 12 Missing Pieces, Derandomization, and Concluding Remarks 175-178

1. For every i, a collection of positive coefficients qij, , such that . It is assumed that if and only if .

2. A nonincreasing function , called the cooling schedule. Here N is the set of positive integers, and T(t) is called the temperature at time t.

3. An initial "state" .

Given the above elements, the simulated annealing algorithm consists of a discrete-time inhomogeneous Markov chain x(t), whose evolution we now describe. If the current state x(t) is equal to i, choose a neighbor j of i at random; the probability that any particular is selected is equal to qij. Once j is chosen, the next state x(t +1) is determined as follows:

Formally,

If and , then P[x(t+1) = j | x(t) = i] = 0.

The rationale behind the SA algorithm is best understood by considering a homogeneous Markov chain xT(t) in which the temperature T(t) is held at a constant value T. Let us assume that the Markov chain xT (t) is irreducible and aperiodic and that qij = qji for all i, j. Then xT(t) is a reversible Markov chain, and its invariant probability distribution is given by

where ZT is a normalizing constant. (This is easily shown by verifying that the detailed balance equations hold.) It is then evident that as , the probability distribution πT is concentrated on the set S* of global minima of J. This latter property remains valid if the condition qij = qji is relaxed (Faigle and Kern, 1989).

The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001