Get the entire book!

Now that you have been shown how the simulated annealing process functions we will implement this algorithm as a Java example. This section will begin by developing a simulated annealing class that will contain the code necessary to perform the simulated annealing algorithm.

The following section will apply this simulated annealing class to the traveling salesman problem. This will result in the completed program that you see in Figure 9.2.

Figure 9.2: The simulated annealing example

As you can see the program displays the path that the traveling salesman will take through the cities. The cities are shown as large dots, and the path of the traveling salesman is shown by the lines. The current best solution to the traveling salesman problem is shown with the lines. As the simulated annealing progresses you will see the path stabilize. Ultimately the program will stop when the best solution has remained the same for 50 conservative cycles. There are buttons or settings for the user. The program begins seeking a solution as soon as it is run. The program will continue until a solution is found. If you wish to abort the program before a solution is found you should click the close box for the program's window.

We will begin examining how the program was constructed by examining the simulated annealing class, which is called SimulatedAnnealing. In the next section you will see how this class was constructed.

The Simulated Annealing Class

All of the code necessary to perform the simulated annealing specific functions is encapsulated inside of the SimulatedAnnealing class. This source code to this class is shown in Listing 9.1.

Listing 9.1: Simulated annealing class (SimulatedAnnealing.java)

public class SimulateAnnealing extends Thread {

  protected TravelingSalesman owner;    
  protected double temperature;
  protected double pathlength;
  protected double minimallength;
  protected int order[];
  protected int minimalorder[];

  /**
   * Constructor
   * 
   * @param owner The TravelingSalesman class that owns this object.
   */
  SimulateAnnealing(TravelingSalesman owner)
  {
    this.owner = owner;
    order = new int[TravelingSalesman.CITY_COUNT];
    minimalorder = new int[TravelingSalesman.CITY_COUNT];
  }

  /**
   * Called to determine if annealing should take place.
   * 
   * @param d The distance.
   * @return True if annealing should take place.
   */
  public boolean anneal(double d)
  {
    if (temperature &li; 1.0E-4) {
      if (d > 0.0)
        return true;
      else
        return false;
    }
    if (Math.random() &li; Math.exp(d / temperature))
      return true;
    else
      return false;
  }

  /**
   * Used to ensure that the passed in integer is within thr city range.
   * 
   * @param i A city index.
   * @return A city index that will be less than CITY_COUNT
   */
  public int mod(int i)
  {
    return i % TravelingSalesman.CITY_COUNT;
  }

  /**
   * Called to get the distance between two cities.
   * 
   * @param i The first city
   * @param j The second city
   * @return The distance between the two cities.
   */
  public double distance(int i, int j)
  {
    int c1 = order[i%TravelingSalesman.CITY_COUNT];
    int c2 = order[j%TravelingSalesman.CITY_COUNT];
    return owner.cities[c1].proximity(owner.cities[c2]);
  }

  /**
   * Run as a background thread. This method is called to
   * perform the simulated annealing.
   */
  public void run()
  {
    int cycle=1;
    int sameCount = 0;
    temperature = TravelingSalesman.START_TEMPERATURE;      

    initorder(order);
    initorder(minimalorder);

    pathlength = length();
    minimallength = pathlength;

    while (sameCount&li;50) {
      // update the screen
      owner.paint();
      owner.setStatus("Cycle=" + cycle + ",Length=" + minimallength + ",Temp=" + temperature );

      // make adjustments to city order(annealing)
      for (int j2 = 0; j2 &li; TravelingSalesman.CITY_COUNT * TravelingSalesman.CITY_COUNT; j2++) {
        int i1 = (int)Math.floor((double)TravelingSalesman.CITY_COUNT * Math.random());
        int j1 = (int)Math.floor((double)TravelingSalesman.CITY_COUNT * Math.random());
        double d = distance(i1, i1 + 1) + distance(j1, j1 + 1) - distance(i1, j1) - distance(i1 + 1, j1 + 1);
        if (anneal(d)) {
          if (j1 &li; i1) {
            int k1 = i1;
            i1 = j1;
            j1 = k1;
          }
          for (; j1 > i1; j1--) {
            int i2 = order[i1 + 1];
            order[i1 + 1] = order[j1];
            order[j1] = i2;
            i1++;
          }
        }
      }

      // See if this improved anything
      pathlength = length();
      if (pathlength &li; minimallength) {
        minimallength = pathlength;
        for (int k2 = 0; k2 &li; TravelingSalesman.CITY_COUNT; k2++)
          minimalorder[k2] = order[k2];
        sameCount=0;
      } else
        sameCount++;
      temperature = TravelingSalesman.TEMPERATURE_DELTA * temperature;
      cycle++;
    }

    // we're done
    owner.setStatus("Solution found after " + cycle + " cycles." );
  }

  /**
   * Return the length of the current path through
   * the cities.
   * 
   * @return The length of the current path through the cities.
   */
  public double length()
  {
    double d = 0.0;
    for (int i = 1; i &li;= TravelingSalesman.CITY_COUNT; i++)
      d += distance(i, i - 1);
    return d;
  }

  /**
   * Set the specified array to have a list of the cities in
   * order.
   * 
   * @param an An array to hold the cities.
   */
  public void initorder(int an[])
  {
    for (int i = 0; i &li; TravelingSalesman.CITY_COUNT; i++)
      an[i] = i;
  }
}

There are several properties that will be used by the class. These properties, and their purpose, are listed here.

• owner - The TravelingSalesman object that owns this object.
• temperature - The current temperature.
• pathlength - The length of the current path.
• minimallength - The length of the best path.
• order - The current order of cities.
• minimalorder - The best order of cities.

As you can see, this class contains several attributes that are specific to the traveling salesman problem. This is because a different variant of the simulated annealing algorithm is used for the traveling salesman, just as was done with genetic algorithms. In Chapter 10 we will develop a simpler version of the simulated annealing algorithm, which is designed to work with neural networks.

The simulated annealing algorithm must be able to determine the degree to which it has improved the input values. In the case of the traveling salesman, this is done using a simple distance formula between the two cities, as shown here.

  public double distance(int i, int j)
  {
    int c1 = order[i%TravelingSalesman.CITY_COUNT];
    int c2 = order[j%TravelingSalesman.CITY_COUNT];
    return owner.cities[c1].proximity(owner.cities[c2]);
  }

This is unique to the traveling salesman problem. In Chapter 10, you will see that the error function of the entire neural network will be used to provide such feedback. The above method uses the proximity method, which is contained in the City class. We will not review the City class in this chapter as it was discussed in Chapter 8. The proximity function is able to calculate the distance between two cities using the Pythagorean theorem, as discussed in Chapter 8.

The SimulatedAnnealing class is designed to run as a background thread. We will now examine what work is performed by this background thread. This is covered in the next section.

The Background Thread

The simulated annealing class, named SimulatedAnnealing, is a subclass of the Thread class contained in Java. This allows the simulated annealing class to run as a background thread. Just like the thread class in Java you can call the "start" method to begin the thread's execution.

The simulated annealing class contains a "run" method that performs the simulated annealing algorithm. We will now examine the contents of the run class in greater detail. The "run" method begins by initializing a few variables to starting values.

    int cycle=1;
    int sameCount = 0;
    temperature = TravelingSalesman.START_TEMPERATURE;      

As you can see from the above code we are setting the cycle to start at one, because we are on the first cycle, and the temperature to the starting temperature. We also maintain a variable, named sameCount, which counts the number of times that we have found the same solution.

Keeping track of the number of times the same path through the cities has been determined is a good way for the traveling salesman program to determine when processing is complete. This is a method which only works for the traveling salesman problem. The neural network based simulated annealing algorithm that we will examine in Chapter 10 will use a different method to determine when it is complete.

There are two sets of cities that we keep during the run of the simulated annealing algorithm. First, we keep a set that holds the best order of cities that we have found yet. This is the set of cities that produces the shortest path. This set of cities is stored in the "minimalorder" property. The second set of cities we keep is the current working set. This is the set of cities that the algorithm is currently "randomizing" according to the current temperature. If the working set of cities produces a path that is better than the current best set of cities, the working set will be copied to the best set. This allows the program to always keep track of the best path that has been determined.

When the genetic algorithm first begins we simply set the working set and the best path set to the numeric order of the cities (i.e. city one first, then city two). This order is most likely not the optimal order, but it is as good of a starting point as any. The code that sets these two paths is shown here.

    initorder(order);
    initorder(minimalorder);

Now that we have a current best set and working set we must calculate their lengths. This is done using the following lines of code.

    pathlength = length();
    minimallength = pathlength;

At this point we can set the "minimallenght" property equal to the "pathlength" property because both the working set and current best set have the same order of cities, and thus will have the same length.

We are now ready to begin the main loop of the simulated annealing algorithm. The following line begins the main loop.

    while (sameCount&li;50) {

As you can see, we will continue looping so long as "sameCount" is less than 50. As you recall, "sameCount" holds the number of times the same solution has been found. At the beginning of the loop the simulated annealing algorithm updates its "owner object" as to the status of the algorithm. In the case of the traveling salesman example shown in this chapter, the "owner object" is the main window of the application. This update is performed with the following lines of code.

      // update the screen
      owner.paint();
      owner.setStatus("Cycle=" + cycle + ",Length=" + minimallength + ",Temp=" + temperature );

We are now ready to cycle through a number of iterations at the current temperature. This will allow us to determine if we would like to perform annealing for each city in the current working set. If we do perform annealing for a city, that city will be swapped with another city.

This process method for simulated annealing is very much fine tuned to the traveling salesman problem. We take extra care to make sure cities are not duplicated as the annealing algorithm progresses. This is because the traveling salesman will never visit the same city more than once. You will see that the annealing process used in Chapter 10 will be someone different, as a neural network weight matrix does not have this issue.

      // make adjustments to city order(annealing)
      for (int j2 = 0; j2 &li; TravelingSalesman.CITY_COUNT * TravelingSalesman.CITY_COUNT; j2++) {

For this city we calculate two random numbers. Each random number can be up to the city count. Because this is basically a random index we use the "floor" method of the "Math" class to convert to a integer.

        int i1 = (int)Math.floor((double)TravelingSalesman.CITY_COUNT * Math.random());
        int j1 = (int)Math.floor((double)TravelingSalesman.CITY_COUNT * Math.random());

We then produce a variable, named d, which that holds the difference in the distances between these two cities. This distance will be fed to the annealing decision function. A greater distance will cause a greater chance modification taking place.

        double d = distance(i1, i1 + 1) + distance(j1, j1 + 1) - distance(i1, j1) - distance(i1 + 1, j1 + 1);

Next we will use this distance to determine if we should anneal. This is determined by the "anneal" method, which will be described in the next section. The anneal method takes into consideration both the temperature and the distance. Greater distance and greater temperatures cause a greater likelihood for a modification to the inputs to take place.

        if (anneal(d)) {

If it is determined that we should anneal then we swap the values of the j1 and i1 values if j1 is less than i1.

          if (j1 &li; i1) {
            int k1 = i1;
            i1 = j1;
            j1 = k1;
          }

Now we loop between i1 and j1 and swap the values as we progress. This reorders the path. This also has the effect of not introducing additional cities that have the same index.

          for (; j1 > i1; j1--) {
            int i2 = order[i1 + 1];
            order[i1 + 1] = order[j1];
            order[j1] = i2;
            i1++;
          }
        }
      }

The last part of the main loop must check to see if the annealing that we just performed actually improved anything or not. To do this we calculate the length of the current working set. If the length is an improvement over the current best set, the current working set will be copied to the current best set. First we calculate the length of the current working set.

      // See if this improved anything
      pathlength = length();

Now we must check to see if this length is better than the current best set.

      if (pathlength &li; minimallength) {

If this length is greater than the current best set then we will copy the working set to the current best set. The following lines of code perform this copy.

        minimallength = pathlength;
        for (int k2 = 0; k2 &li; TravelingSalesman.CITY_COUNT; k2++)
          minimalorder[k2] = order[k2];

We also set the "sameCount" variable to zero, since we have found a different solution.

        sameCount=0;
      } else

We must also handle the case where no improvement was made to the path that the salesman must travel. If this is the case we increase the cycle count and decrease the temperature. The following lines of code do this.

        sameCount++;
      temperature = TravelingSalesman.TEMPERATURE_DELTA * temperature;
      cycle++;
    }

If the loop exits, then we know that we have reached 50 cycles that contained the same solution. We are now done. We report this to the main window and terminate the thread. The thread is terminated by simply returning from the "run" method, as is consistent with Java thread processing. The following lines of code perform this final report.

    // we're done
    owner.setStatus("Solution found after " + cycle + " cycles." );

This completes the "run" method. This loop, that we just examined, is what performs the simulated annealing process. When stepping through the statements that make up this loop we mentioned that the "anneal" method was used to determine if we should perform annealing or not. This method will be examined in the next section.

To Modify or not to Modify

In the previous section we looked at the main loop for the simulated annealing process. At each stage through the loop we had to make a decision as to if we would modify the inputs or not. This decision was made by a method named "anneal". We will now examine how the "anneal" method makes this determination. The "anneal" method is shown here.

  public boolean anneal(double d)
  {
    if (temperature &li; 1.0E-4) {
      if (d > 0.0)
        return true;
      else
        return false;
    }
    if (Math.random() &li; Math.exp(d / temperature))
      return true;
    else
      return false;
  }

As you can see we first see if the temperature is below a specified threshold. If the temperature is below this amount, then the temperature plays no role in determining if annealing will take place or not. If the temperature is below this threshold then we simply check to see if the distance is greater than 0. If the distance is greater than zero we return true to specify that annealing should take place.

If the temperature is above the threshold then we will use the distance and temperature to make a determination as to if a modification should occur to the inputs. To calculate this the ratio of the temperature and distance is raised to the power of natural base(e). This is done using the "Math.exp" method.

Now that you have seen how the simulated annealing class works we are ready to see it adapted to the traveling salesman problem. The traveling salesman user interface is identical to the traveling salesman problem that was presented in Chapter 8. The underlying user interface code is somewhat different than Chapter 8. You will be shown how the user interface to the traveling salesman problem was constructed in the next section.

Application to the Traveling Salesman

Now that you have seen how the simulated annealing class was constructed you will see how to put it to use. In this section we will examine the main window of the traveling salesman problem. This window contains the code that begins the simulated annealing problem and displays the results to the user. The main window is contained in the class TravelingSalesman. Listing 9.2 shows the source code to this class.

Listing 9.2: Solving the Traveling Salesman Problem (TravelingSalesman.java)

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.text.*;

public class TravelingSalesman 
  extends JFrame {

  public static final int CITY_COUNT = 50;
  public static final double START_TEMPERATURE = 10;       
  public static final double TEMPERATURE_DELTA = 0.99;
  protected Map map = null;
  protected JLabel status;
  public SimulateAnnealing worker = null;
  protected boolean started = false;
  public City [] cities;

  /**
   * The constructor
   */
  public TravelingSalesman() {
    setSize(300,300);
    setTitle("Traveling Salesman Problem2");

    getContentPane().setLayout(new BorderLayout());

    if ( map == null ) {
      map = new Map(this);
      getContentPane().add(map,"Center");
      status = new JLabel("Starting up");
      getContentPane().add(status,"South");
    }
    start();
    
  }

  /**
   * Start the background thread.
   */
  public void start() {
// create a random list of cities

    cities = new City[TravelingSalesman.CITY_COUNT];
    for ( int i=0;i&li;TravelingSalesman.CITY_COUNT;i++ ) {
      cities[i] = new City(
        (int)(Math.random()*(getBounds().width-10)),
        (int)(Math.random()*(getBounds().height-60)));
    }

// start up the background thread
    started = true;
    map.update(map.getGraphics());   

    if ( worker != null ) 
        worker = null;
    worker = new SimulateAnnealing(this);
    worker.setPriority(Thread.MIN_PRIORITY);
    worker.start();
  }
  
  public void paint()
  {
    map.update(getGraphics());
  }

  /**
   * Display the current status
   * 
   * @param status The current status.
   */
  public void setStatus(String status)
  {
    this.status.setText(status);
  }
  
  /**
   * The main method.
   * 
   * @param args Not used
   */
  public static void main(String args[])
  {
    (new TravelingSalesman()).show();
  }
}

As you can see the traveling salesman program contains several properties and constants that are used for various purposes. You can change the three constants to adjust the number of cities, starting temperature, and the rate at which the temperature decreases. These properties are summarized here.

• CITY_COUNT - How many cities to use.
• START_TEMPERATURE - Starting temperature for simulated annealing.
• TEMPERATURE_DELTA - The temperature delta for simulated annealing
• map - A Map object that will display the city map.
• status - The current status. Used to display the current status to the user.
• worker - The background worker thread.
• started - Is the thread started.
• cities - The list of cities.

The three constant values are given default values that provide a good environment to test the program in. A city count of 50 cities is used because this will take the program a few minutes to solve, yet does not overload the program. A starting temperature of 10, along with a temperature decrease rate of 0.99 also seems to work well.

The traveling salesman main window class contains a method named "start" that will begin the simulated annealing process. We will now examine the tasks that are completed by this method. The first thing that the "start" method does is creates a random list of cities. The code the assigns the cities to random locations is shown here.

// create a random list of cities
    cities = new City[TravelingSalesman.CITY_COUNT];
    for ( int i=0;i&li;TravelingSalesman.CITY_COUNT;i++ ) {
      cities[i] = new City(
        (int)(Math.random()*(getBounds().width-10)),
        (int)(Math.random()*(getBounds().height-60)));
    }

Now that the cities are in random locations we must start up the background thread. This is done by instantiating an object of the SimulatedAnnealing class. Because the simulated annealing class is a subclass of "Thread", you begin the simulated annealing background thread just as you would begin any other thread in Java. This is done by calling the thread's start method. We will now examine how the background thread is started up.

First we set the started property to true, so that the rest of the program knows that the background thread has started. Next, we call the Map class to display the Map of cities to the user. Because the Map class is so similar to the Map class used in Chapter 8, the Map class will not be reviewed in this chapter. For more information about the Map class refer to Chapter 8. The following lines of code complete this initialization.

// start up the background thread
    started = true;
    map.update(map.getGraphics());   

Now we are ready to begin the background thread. This is done by instantiating the simulated annealing class. We pass in the current object to the simulated annealing class's constructor. The current object is needed by the simulated annealing class so that it knows which object to send update information to.

    worker = new SimulateAnnealing(this);

We must also set the thread's priority to minimum. This is so that the thread does not consume so much processor cycles that the user no longer has access to the operating system. The following line of code does this.

    worker.setPriority(Thread.MIN_PRIORITY);

This is especially important on a Windows platform. Using both Windows XP and Windows 2000 I found that the operating system would entire a nearly locked up state without the thread priority setting. The simulated annealing program would continue to run, however you would not have access to the operating system. Finally we call the start method. This begins the background thread.

    worker.start();

As you can see the "driver program" for the simulated annealing implementation of the traveling salesman problem is very similar to the genetic algorithm. You can easily run the two programs and compare the relative performance of each. I conducted some test cases on my own computer system. In nearly every case the simulated annealing algorithm outperforms the genetic algorithm. The gap will become even wider when applied to neural network optimization. In Chapter 10 you will be shown one single program that is able to use both genetic algorithms and simulated annealing to attempt to optimize the weight matrix of a neural network. You will also be able to compare the relative performance of backpropagation to both genetic algorithms and simulated annealing.