Understanding Simulated Annealing

Get the entire book!

The previous sections showed you where the simulated annealing algorithm came from, as well as what applications it is used for. In this section you will be shown how to implement the simulated annealing algorithm. You will first be presented with the algorithm. In the next section we will develop a genetic algorithm class that can be used to solve the traveling salesman problem, which was introduced in Chapter 8. We will begin by examining the structure of the simulated annealing algorithm.

What is the Structure of a Simulated Annealing Algorithm

We will now examine the structure of the simulated annealing algorithm. There are several distinct steps that the simulated annealing process goes through as the temperature is decreased, and randomness is applied to the input values. Figure 9.1 shows this process as a flowchart.

Figure 9.1: Overview of the simulated annealing process

As you can see from Figure 9.1 there are two major processes that are occurring during the simulated annealing algorithm. First, for each temperature the simulated annealing algorithm runs through a number of cycles. This number of cycles is predetermined by the programmer. As the 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 kept.

Once the specified number of training cycles has been completed, the temperature can be lowered. Once the temperature is lowered, it is determined of the temperature has reached the lowest allowed temperature. If the temperature is not lower than the lowest allowed temperature, then the temperature is lowered and another cycle of randomizations will take place. If the temperature is lower than the minimum temperature allowed, the simulated annealing algorithm is complete.

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. This randomization process must often be customized for different problems. In this chapter we will discuss randomization methods that can be used both for 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. This randomization process takes the previous values of the inputs 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 and randomization.

There is no exact method defined by the simulated annealing algorithm for how to randomize the inputs. The exact nature by which this is done often depends on the nature of the problem being solved. When comparing the methods used in simulated annealing for both the traveling salesman and neural network weight optimization we can see some of these 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. 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.

Because of this 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 the ratio will cause a larger change in the weight matrix. A lower temperature will most likely produce a smaller ratio. This is the method that is used for the simulated annealing algorithm that will be presented in Chapter 10. In chapter 10 you will be shown an exact Java implementation of the algorithm.

Simulated Annealing and the Traveling Salesman Problem

The method used to randomize the path of the traveling salesman is somewhat more complex than randomizing the weights of a neural network. This is because there are constraints that exist on the path of the traveling salesman problem that do not exist when optimizing the weight matrix of the neural network.

The biggest difference is that the traveling salesman cannot visit the same city more than once during his trip. The randomization of the path must be controlled enough that it does not cause the traveling salesman to visit the same city more than once. By the same token, the traveling salesman must visit each city once. No cities can be skipped. The randomization algorithm must also be careful that it does not cause any cities to be dropped from the list.

You can think of the traveling salesman randomization as simply moving elements of a fixed sized list. This fixed size list is the path that the traveling salesman must follow. Because the traveling salesman can neither skip nor revisit cities, the path of the traveling salesman will always have the same number of "stops" as there are cities.

Because of the constraints imposed by the traveling salesman problem, most randomization methods used with the traveling salesman problem work simply by jumbling the order of the previous path through the cities. By simply jumbling the data, and not modifying original values, we can be assured that the final result of this jumbling will neither skip, nor revisit, cities.

This is the method that is used to randomize traveling salesman's path in this chapter. Using a combination of the temperature and distance between two cities, the simulated annealing algorithm determines if the positions of these two cities should be changed. You will see the actual Java implementation of this method later in this chapter.

The final portion of the simulated annealing algorithm that we will explore in this section is temperature reduction. Temperature reduction will be discussed in the next section.

Temperature Reduction

There are several different methods that can be used for temperature reduction. In this chapter we will examine two methods. The most common is to simply reduce the temperature by a fixed amount through each cycle. This is the method that is used in this chapter for the traveling salesman problem example.

Another method is to specify a beginning and ending temperature. This is the method that will be used by the simulated annealing algorithm that is shown in Chapter 10. To do this we must calculate a ratio at each step in the simulated annealing process. This is done by using an equation that guarantees that the step amount will cause the temperature to fall to the ending temperature in the number of cycles requested. The following equation shows how to logarithmically decrease the temperature between a beginning and ending temperature.

    double ratio = Math.exp(Math.log(stopTemperature/startTemperature)/(cycles-1));

The above line calculates a ratio that should be multiplied against the current temperature. This will produce a change that will cause the temperature to reach the ending temperature in the specified number of cycles. This method is used in Chapter 10 when simulated annealing is applied to neural network training.