Example 2: 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 distance 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