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

**Understanding Simulated Annealing**

The previous sections discussed the background of the simulated annealing algorithm

and presented various applications for which it is used. In this section, you will

be shown how to implement the simulated annealing algorithm.

There are several distinct steps that the simulated annealing process must go

through as the temperature is reduced and randomness is applied to the input values.

Figure below presents a flowchart of this process.

As you can see , there are two major processes that take place in the

simulated annealing algorithm. First, for each temperature, the simulated annealing

algorithm runs through a number of cycles. The number of cycles is predetermined

by the programmer. As a cycle runs, the inputs are randomized. In the case of the

traveling salesman problem, these inputs are the order of the cities that the traveling

salesman will visit. Only randomizations which produce a better-suited set of inputs

will be retained.

Once the specified number of training cycles have been completed, the temperature

can be lowered. Once the temperature is lowered, it is determined whether or not

the temperature has reached the lowest temperature allowed. If the temperature is

not lower than the lowest temperature allowed, then the temperature is lowered and

another cycle of randomizations will take place. If the temperature is lower than the

lowest temperature allowed, the simulated annealing algorithm terminates.

At the core of the simulated annealing algorithm is the randomization of the input

values. This randomization is ultimately what causes simulated annealing to alter

the input values that the algorithm is seeking to minimize. The randomization process

must often be customized for different problems.

**How Are the Inputs Randomized?**

An important part of the simulated annealing process is how the inputs are randomized.

The randomization process takes the previous input values and the current

temperature as inputs. The input values are then randomized according to the temperature.

A higher temperature will result in more randomization; a lower temperature

will result in less randomization.

There is no specific method defined by the simulated annealing algorithm for how

to randomize the inputs. The exact nature by which this is done often depends upon

the nature of the problem being solved. When comparing the methods used in the

simulated annealing examples for the neural network weight optimization and the

traveling salesman problem, we can see some of the differences.

**Simulated Annealing and Neural Networks**

The method used to randomize the weights of a neural network is somewhat simpler

than the traveling salesman’s simulated annealing algorithm, which we will discuss

next. A neural network’s weight matrix can be thought of as a linear array of

floating point numbers. Each weight is independent of the others. It does not matter if

two weights contain the same value. The only major constraint is that there are ranges

that all weights must fall within.

Thus, the process generally used to randomize the weight matrix of a neural network

is relatively simple. Using the temperature, a random ratio is applied to all of

the weights in the matrix. This ratio is calculated using the temperature and a random

number. The higher the temperature, the more likely it is that the ratio will cause a

larger change in the weight matrix. A lower temperature will most likely produce a

smaller change.

*References:
Introduction to Neural Networks for C#, Second Edition
Second Edition
by Jeff Heaton
Heaton Research, Inc.
St. Louis*