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. We will first examine the algorithm and then we will develop a simulated annealing algorithm class that can be used to solve the traveling salesman problem, which was introduced in chapter 6.

The Structure of a 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 7.1 presents a flowchart of this process.

Figure 7.1: Overview of the simulated annealing process.

    As you can see in Figure 7.1, 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. In this chapter we will discuss randomization methods that can be used for both the traveling salesman problem and neural network training. In the next section, we will examine how this randomization occurs.

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. This is the method that is used for the simulated annealing algorithm that will be presented later in this chapter.