Example Heuristics2: The Traveling Salesman Problem Using Simulated Annealing


Simulated Annealing is a generic probabalistic meta-algorithm used to find an approximate solution to global optimization problems.  It is inspired by annealing in metallurgy which is a technique of controlled cooling of material to reduce defects.  The simulated annealing algorithm starts with a random solution.  Each iteration forms a random nearby solution.  If this solution is a better solution, it will replace the current solution.  If it is a worse solution, it may be chosen to replace the current solution with a probability that depends on the temperature parameter.  As the algorithm progresses, the temperature parameter decreases, giving worse solutions a lesser chance of replacing the current solution.  Allowing worse solutions at the beginning helps to avoid converging to a local minimum rather than the global minimum.

We will use the simulated annealing algorithm to solve a fully connected travelling salesman problem  The table below displays the distances between each city that the salesman must visit.  The salesman must visit each city only once and return to the same city in which he began.

The varables that affect the outcome of the algorithm are the intial temperature, the rate at which the temperature decreases (alpha) and the stopping condition of the algorithm (epsilon).  You can adjust these values to see how that algorithm responds.  The best possible solution for this problem is a tour length of 17.

Enter the desired values of these variables and press the Start button.  This will bring you to a page that will display the outcome in a graph.  The blue curve on the graph plots the length of the given solution at every 200th iteration of the algorithm.  The green curve on the graph plots the length of the best solution found to that point.  To return to this page, press the back button on the browser.  To re-run the algorithm with the same parameters, refresh the page.


 



Starting Temperature:  Epsilon:  Alpha:  
   


To obtain the code for the used to solve this problem, click on the links below:
Simulated Annealing Code
Graphing Code
TSP Data