Simulated Annealing for the Traveling Salesman Problem

    Simulated annealing can provide potential solutions to the traveling salesman problem. The traveling salesman problem was introduced in chapter 6, “Understanding Genetic Algorithms.” Aside from the fact that the traveling salesman problem from this chapter uses simulated annealing, it is the same as the program presented in chapter 6.

    The simulated annealing traveling salesman problem implements a special version of the SimulatedAnnealing class. The class is named TSPSimulatedAnnealing. The most important method is the randomize method. The signature for the randomize method is shown here:

public void randomize()

    First, the length of the path is determined.

final int length = this.path.length;

    Next, we iterate through the loop a number of times equal to the temperature. The higher the temperature, the more iterations. The more iterations, the more “excited” the underlying path becomes and the more changes made.

for (int i = 0; i < this.temperature; i++) {

    Two random index locations are chosen inside the path.

  int index1 = (int) Math.floor(length * Math.random());
  int index2 = (int) Math.floor(length * Math.random());

    A basic distance number is calculated based on the two random points.

  final double d = distance(index1, index1 + 1) 
  + distance(index2, index2 + 1)					
  - distance(index1, index2) 
  - distance(index1 + 1, index2 + 1);

    If the distance calculation is greater than zero, then the array elements in the path are excited.

  if (d > 0) {

    The index locations, index1 and index2, are sorted if necessary.

if (index2 < index1) {
  final int temp = index1;
  index1 = index2;
  index2 = temp;
}

    All cities between the two random index points are sorted.

for (; index2 > index1; index2--) {
  final int temp = this.path[index1 + 1];
  this.path[index1 + 1] = this.path[index2];
  this.path[index2] = temp;
  index1++;
}

    When the new path is returned to the iteration function, it will be evaluated. If it is an improvement over the last path, it will be retained.