Simulated Annealing Background

    Simulated annealing was developed in the mid 1970s by Scott Kirkpatrick and several other researchers. It was originally developed to better optimize the design of integrated circuit (IC) chips by simulating the actual process of annealing.

    Annealing is the metallurgical process of heating up a solid and then cooling it slowly until it crystallizes. The atoms of such materials have high-energy values at very high temperatures. This gives the atoms a great deal of freedom in their ability to restructure themselves. As the temperature is reduced, the energy levels of the atoms decrease. If the cooling process is carried out too quickly, many irregularities and defects will be seen in the crystal structure. The process of cooling too rapidly is known as rapid quenching. Ideally, the temperature should be reduced slowly to allow a more consistent and stable crystal structure to form, which will increase the metal’s durability.

    Simulated annealing seeks to emulate this process. It begins at a very high temperature, at which the input values are allowed to assume a wide range of random values. As the training progresses, the temperature is allowed to fall, thus restricting the degree to which the inputs are allowed to vary. This often leads the simulated annealing algorithm to a better solution, just as a metal achieves a better crystal structure through the actual annealing process.

Simulated Annealing Applications

    Given a specified number of inputs for an arbitrary equation, simulated annealing can be used to determine those inputs that will produce the minimum result for the equation. In the case of the traveling salesman, this equation is the calculation of the total distance the salesman must travel. As we will learn later in this chapter, this equation is the error function of a neural network.

    When simulated annealing was first introduced, the algorithm was very popular for integrated circuit (IC) chip design. Most IC chips are composed of many internal logic gates. These gates allow the chip to accomplish the tasks that it was designed to perform. Just as algebraic equations can often be simplified, so too can IC chip layouts. Simulated annealing is often used to find an IC chip design that has fewer logic gates than the original. The result is a chip that generates less heat and runs faster.

    The weight matrix of a neural network provides an excellent set of inputs for the simulated annealing algorithm to minimize. Different sets of weights are used for the neural network until one is found that produces a sufficiently low return from the error function.