Simulated Annealing Background

Get the entire book!

Simulated annealing was developed in the mid 1970's by Scott Kirkpatric, along with a few other researchers. Simulated annealing was original developed to better optimized the design of integrated circuit (IC) chips. Simulated annealing simulates the actual process of annealing.

Annealing is the metallurgical process of heating up a solid and then cooling slowly until it crystallizes. The atoms of this material have high energies 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 of these atoms decreases.

If this cooling process is carried out too quickly many irregularities and defects will be seen in the crystal structure. The process of too rapid of cooling is known as rapid quenching.

Ideally the temperature should be deceased at a slower rate. A slower fall to the lower energy rates will allow a more consistent crystal structure to form. This more stable crystal form will allow the metal to be much more durable.

Simulated annealing seeks to emulate this process. Simulated annealing begins at a very high temperature where the input values are allowed to assume a great range of random values. As the training progresses the temperature is allowed to fall. This restricts 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.

What is Simulated Annealing Used for

Simulated annealing can be used to find the minimum of an arbitrary equation that has a specified number of inputs. Simulated annealing will find the inputs to the equation that will produce a minimum value. In the case of the traveling salesman, this equation is the calculation of the total distance that the salesman must travel. In the case of a neural network, as we will learn in Chapter 10, this equation is the error function of the neural network.

When simulated annealing was first introduced the algorithm was very popular for integrated circuit (IC) chip design. Most IC chips are composed internally of many logic gates. These gates allow the chip to perform that tasks that the chips were designed to perform. Just as algebraic equations can often be simplified so too can the IC chip layouts. Simulated annealing is often used to find a IC chip design that has fewer logic gates than the original. This causes the chip to generate less heat and run faster.

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