Simulated Annealing and the Traveling Salesman Problem

    The method used to randomize the path of the traveling salesman is somewhat more complex than the method used to randomize 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 most significant constraint is that the randomization of the path must be controlled enough to prevent the traveling salesman from visiting the same city more than once, and at the same time ensure that he does visit each city once; no cities may be skipped.

    You can think of the traveling salesman randomization as the reordering of elements in a fixed-size list. This fixed-size list is the path that the traveling salesman must follow. Since the traveling salesman can neither skip nor revisit cities, his path will always have the same number of “stops” as there are cities.

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

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

Temperature Reduction

    There are several different methods that can be used for temperature reduction; we will examine two. 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.

    Another method is to specify a beginning and ending temperature. To use this method, 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 specified. Equation 7.1 describes how to logarithmically decrease the temperature between a beginning and ending temperature. It calculates the ratio and ensures that the temperature naturally decreases for each cycle.

Equation 7.1: Scaling the Temperature

    The variables are s for starting temperature, e for ending temperature, and c for cycle count. The equation can be implemented in Java as follows:

    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 later in this chapter when simulated annealing is applied to neural network training.