For our next approach, we will make an analogy with the world of physics and crystal growing.
To grow a crystal, one begins by heating the raw materials to a liquid state. This molten material is then slowly cooled, until the crystal structure is frozen in. If the temperature is decreased too quickly, flaws in the crystal can be locked in. Slow temperature decrease allows these flaws to ``work themselves out'' forming a much better crystal. This process is called annealing.
One can think of the final state of a crystal as a local optimum: no small movement of the molecules can decrease the total energy content. A perfect crystal contains the minimum energy content of all the final possibilities. Because molecules only move locally, the laws of physics only require that some local optimum be found. But if annealing creates better solutions, perhaps we can simulate this annealing process.
The essential aspect of annealing is that the energy contained in the heat can be used to move from one energy level to a higher level. Our goal is to move to as low a level as possible, but maybe it is useful to move uphill once in a while.
Simulated annealing works just like local search in that it examines exchanged solutions and always takes a better solution. The only difference is that it sometimes (with some probability) takes a worse one. This probability decreases over time (just like the temperature decreases) until we freeze in a local optimal solution, hopefully better than one we would get to otherwise.
An example of this would be to keep a counter i. We would accept a worse solution with probability 1/i. Every 50 exchanges or so we would increment i. Once i is 1000, we would simply set the probability we would accept a worse solution to 0 and freeze our solution into a local optimum.
Most real uses of simulated annealing use a more complicated probability function, based on the amount of worsening of the solution. Solutions that are only slightly worse are much more likely to be accepted than those that are much worse.
Generally, simulated annealing gets much better answers, but it takes a very slow cooling process. Therefore, for some problems, it may be better to use iterated local search, generating many solutions. Often, however, the quality of the simulated annealing solution is unreachable by iterated local search.