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 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:

• Concise problem representation - The problem representation includes both a representation of the solution space and an appropriate and easily computable cost function C() measuring the quality of a given solution.
• Transition mechanism between solutions - To move from one state to the next, we need a collection of simple transition mechanisms that slightly modify the current solution. Typical transition mechanisms include swapping the position of a pair of items or inserting/deleting a single item. Ideally, the effect that these incremental changes have on measuring the quality of the solution can be computed incrementally, so cost function evaluation takes time proportional to the size of the change (typically constant) instead of linear in the size of the solution.
• Cooling schedule - These parameters govern how likely we are to accept a bad transition as a function of time. At the beginning of the search, we are eager to use randomness to explore the search space widely, so the probability of accepting a negative transition is high. As the search progresses, we seek to limit transitions to local improvements and optimizations. The cooling schedule can be regulated by the following parameters:  
  • Initial system temperature - Typically .
  • Temperature decrement function - Typically , where . This implies an exponential decay in the temperature, as opposed to a linear decay.
  • Number of iterations between temperature change - Typically, 100 to 1,000 iterations might be permitted before lowering the temperature.
  • Acceptance criteria - A typical criterion is to accept any transition from to when and to accept a negative transition whenever

    

    where r is a random number . The constant c normalizes this cost function, so that almost all transitions are accepted at the starting temperature.

  • Stop criteria - Typically, when the value of the current solution has not changed or improved within the last iteration or so, the search is terminated and the current solution reported.

  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.

• Traveling Salesman Problem
• Maximum Cut
• Independent Set
• Circuit Board Placement