#### 4.8.2.4 Simulated Annealing

The last method maintains no data structure of conflicts; instead it picks a neighbor at random and either rejects or accepts the new assignment.

Annealing is a process in metallurgy where metals are slowly cooled to make them reach a state of low energy where they are very strong. Simulated annealing is an analogous method for optimization. It is typically described in terms of thermodynamics. The random movement corresponds to high temperature; at low temperature, there is little randomness. Simulated annealing is a process where the temperature is reduced slowly, starting from a random search at high temperature eventually becoming pure greedy descent as it approaches zero temperature. The randomness should tend to jump out of local minima and find regions that have a low heuristic value; greedy descent will lead to local minima. At high temperatures, worsening steps are more likely than at lower temperatures.

Simulated annealing maintains a current assignment of values to variables. At each step, it picks a variable at random, then picks a value at random. If assigning that value to the variable is an improvement or does not increase the number of conflicts, the algorithm accepts the assignment and there is a new current assignment. Otherwise, it accepts the assignment with some probability, depending on the temperature and how much worse it is than the current assignment. If the change is not accepted, the current assignment is unchanged.

To control how many worsening steps are accepted, there is a positive real-valued temperature
*T*. Suppose *A* is the current assignment of a value to each
variable. Suppose that
*h(A)* is the evaluation of assignment *A*
to be minimized. For solving constraints, *h* is typically the number of
conflicts.
Simulated annealing selects a neighbor at random, which gives a new assignment *A'*.
If *h(A') ≤ h(A)*, it accepts the assignment and *A'* becomes
the new assignment. Otherwise, the assignment is only accepted randomly
with
probability

e^{(h(A)-h(A'))/T}.

Thus, if *h(A')* is close to *h(A)*, the assignment is more likely to be accepted. If the temperature
is high, the exponent will be close to zero, and so the probability
will be close to 1. As the temperature
approaches zero, the exponent approaches *-∞*, and the
probability approaches zero.

Temperature | Probability of acceptance | ||

1-worse | 2-worse | 3-worse | |

10 | 0.9 | 0.82 | 0.74 |

1 | 0.37 | 0.14 | 0.05 |

0.25 | 0.018 | 0.0003 | 0.000006 |

0.1 | 0.00005 | 2×10 ^{-9} | 9×10
^{-14} |

Figure 4.8 shows the probability of accepting
worsening steps at different temperatures. In this figure, *k*-worse
means that *h(A')-h(A)=k*. For example, if the temperature is 10 (i.e., *T=10*), a change that is one worse (i.e., if
*h(a)-h(a')=-1*) will be accepted with
probability *e ^{-0.1} approx 0.9*; a change that is two worse will be
accepted with probability

*e*. If the temperature

^{-0.2}approx 0.82*T*is 1, accepting a change that is one worse will happen with probability

*e*. If the temperature is 0.1, a change that is one worse will be accepted with probability

^{-1}approx 0.37*e*. At this temperature, it is essentially only performing steps that improve the value or leave it unchanged.

^{-10}approx 0.00005If the temperature is high, as in the *T=10* case, the algorithm
tends to accept steps that only worsen a small amount; it
does not tend to accept very large worsening steps. There is a slight
preference for improving steps. As the
temperature is reduced (e.g., when *T=1*), worsening steps, although still
possible, become much less likely. When
the temperature is low (e.g., 0.1), it is very rare that it chooses a
worsening step.

Simulated annealing requires an **annealing schedule**, which
specifies how the temperature is reduced as the search
progresses. Geometric cooling is one of the most widely used
schedules. An example of a geometric cooling schedule is to start with
a temperature of 10 and multiply by 0.97 after each step; this will have a
temperature of 0.48 after 100 steps.
Finding a good annealing schedule is an art.