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
