Chapter 2: Simulated Annealing

 Download CD Content

In this chapter, we'll investigate an optimization method called simulated annealing. As the name implies, the search method mimics the process of annealing. Annealing is the physical process of heating and then cooling a substance in a controlled manner. The desired result is a strong crystalline structure, compared to fast untempered cooling which results in a brittle defective structure. The structure in question is our encoded solution, and the temperature is used to determine how and when new solutions are accepted.

Natural Motivation

The structural properties of a solid depend upon the rate of cooling after the solid has been heated beyond its melting point. If the solid is cooled slowly, large crystals can be formed that are beneficial to the composition of the solid. If the solid is cooled in a less controlled way, the result is a fragile solid with undesirable properties.

When the solid has reached its melting point, a large amount of energy is present within the material. As the temperature is reduced, the energy within the material decreases as well. Another way of looking at annealing is as a process of "shaking," where at higher temperatures there exists higher molecular activity within a physical system. Consider the shaking of a box containing a physical landscape, where a marble is moved around randomly searching for the global minimum [Gallant 1994]. At higher temperatures, the marble is able to move freely around the landscape, while at lower temperatures the shaking is reduced, leading to less movement of the marble. The goal is to encounter the global minimum while shaking violently. As the temperature is reduced, it is less likely that the marble will be moved from the minimum. This is the search process as borrowed from annealing.