next up previous contents index CD CD Algorithms
Next: Traveling Salesman Problem Up: Heuristic Methods Previous: Heuristic Methods

Simulated Annealing


The inspiration for simulated annealing comes from the physical process of cooling molten materials down to the solid state. When molten steel is cooled too quickly, cracks and bubbles form, marring its surface and structural integrity. To end up with the best final product, the steel must be cooled slowly and evenly. Annealing is a metallurgical technique that uses a disciplined cooling schedule to efficiently bring the steel to a low-energy, optimal state.  

In thermodynamic theory, the energy state of a system is described by the energy state of each of the particles constituting it. The energy state of each particle jumps about randomly, with such transitions governed by the temperature of the system. In particular, the probability tex2html_wrap_inline25809 of transition from energy tex2html_wrap_inline25811 to tex2html_wrap_inline25813 at temperature T is given by


where tex2html_wrap_inline25815 is a constant, called Boltzmann's constant.  

What does this formula mean? Consider the value of the exponent under different conditions. The probability of moving from a high-energy state to a lower-energy state is very high. However, there is also a non-zero probability of accepting a transition into a high-energy state, with small energy jumps much more likely than big ones. The higher the temperature, the more likely such energy jumps will occur.

What relevance does this have for combinatorial optimization? A physical system, as it cools, seeks to go to a minimum-energy state. For any discrete set of particles, minimizing the total energy is a combinatorial optimization problem. Through random transitions generated according to the above probability distribution, we can simulate the physics to solve arbitrary combinatorial optimization problems.


Create initial solution S

Initialize temperature t


for i=1 to iteration-length do

Generate a random transition from S to tex2html_wrap_inline25819

If tex2html_wrap_inline25821 then tex2html_wrap_inline25823

else if tex2html_wrap_inline25825 then tex2html_wrap_inline25827

Reduce temperature t

until (no change in C(S))

Return S

There are three components to any simulated annealing algorithm for combinatorial search:

We provide several examples below to demonstrate how these components can lead to elegant simulated annealing algorithms for real combinatorial search problems.

next up previous contents index CD CD Algorithms
Next: Traveling Salesman Problem Up: Heuristic Methods Previous: Heuristic Methods

Mon Jun 2 23:33:50 EDT 1997