A hill climbing algorithm that never makes “down hill” moves towards states with lower value (highest cost) is guaranteed to be incomplete, because it can get stuck on a local maximum. In contrast, a purely random walk i.e. moving to a successor chosen uniformly at random from the set of successors – is complete but extremely in efficient. Therefore, it seems reasonable to try to combine hill climbing with a random walk in some way that yields both efficiency and completeness simulated annealing is such an algorithm. In metallurgy, annealing is the process used to temper or harden metals and glass by heating them to a high temperature and then gradually cooling them, thus allowing the material to coalesce into a low energy crystalline state.

To understand simulated annealing, lets switch out point of view from hill climbing to gradient descent (i.e. minimizing cost) and imagine the task of getting a ping pong ball into the deepest crevice in a bumpy surface.

If we just let the ball roll, it will come to rest at a local minimum, if we shake the surface, we can bounce the ball out of the local minimum. The trick is to shake just hard enough to bounce the ball out of the local minima, but not hard enough to dislodge it from the global minimum. The simulated annealing solutions to start by shaking hard. (i.e. at a high temperature) and then gradually reduce the intensity of the shaking (i.e. lower the temperature). The inner most loop of the simulated annealing algo. Figure 4.14 is quite similar to hill climbing.

a solution state

function SIMULATED – ANNEALING (problem,schedule) returns

inputs: problem, a problem.

schedule, a mapping from time to “temperature”

local variables : current, a node

next, a node

T, a “temperature” controlling the probability of downward steps.

: current $\leftarrow$ MAKE – NODE (INITIAL – STATE [Problem])

for t $\leftarrow$ 1 to $\infty$ do

T $\leftarrow$ schedule [t]

if T = 0 then return current

next $\leftarrow$ a randomly selected successor of current

$\triangle E$ $\leftarrow$ VALUE [next] – VALUE [current]

else current $\leftarrow$ next only with probability $e^{\triangle E/T}$

Fig 4.14. The simulated annealing search algo, a version of stochastic hill climbing where same downhill moves are allowed. Downhill moves are accepted readily early in the annealing schedule and then less often as time goes on. The schedule input determines the value of T as a function of time.

Instead of picking the best move, however, it picks a random move. If the move improves the situation, it is always accepted. Otherwise, the algo, accepts the move with some probability less than 1. Simulated annealing was first used extensively to solve VLSI layout problems in the early 1980s. It has been applied widely to factory scheduling and other large – scale optimization tasks.