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 of transition from energy to at temperature T is given by
where 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.
Simulated-Annealing()
Create initial solution S
Initialize temperature t
repeat
for i=1 to iteration-length do
Generate a random transition from S to
If then
else if then
Reduce temperature t
until (no change in C(S))
Return S
There are three components to any simulated annealing algorithm for combinatorial search:
where r is a random number . The constant c normalizes this cost function, so that almost all transitions are accepted at the starting temperature.
Creating the proper cooling schedule is somewhat of a trial and error process. It might pay to start from an existing implementation of simulated annealing, pointers to which are provided in Section .
We provide several examples below to demonstrate how these components can lead to elegant simulated annealing algorithms for real combinatorial search problems.