Artificial
Intelligence

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.

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^-0.2 approx 0.82. If the temperature T is 1, accepting a change that is one worse will happen with probability e^-1 approx 0.37. If the temperature is 0.1, a change that is one worse will be accepted with probability e^-10 approx 0.00005. At this temperature, it is essentially only performing steps that improve the value or leave it unchanged.

If 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.