Optimization with Simulated Annealing - Part 2 - Animated TSP Solver

I’m dividing this post into 2 parts:

Interactive Demo (SA applied to TSP)

Algorithm

The algorithm implementation follows the 5 main steps described for Simulated Annealing in the previous post using stochastic sampling, but now applied to TSP:

  1. Find a feasible solution for the TSP
  2. While temperature is greater than 1:
    1. Build a new solution from the current one
    2. Try to use the new answer
      1. If new solution is better than current use new solution as current, keep the best overall
      2. Else If \(e^{\frac{current-new}{temperature}} > random(0,1)\), use new solution as current
    3. Decrement temperature
  3. Return the overall best answer

The JavaScript code follows (and for any other language really, the implementation is trivial):

1
2
3
4
5
6
7
8
9
while(temperature > 1){
  var newTour = findNeighbour(currTour);
  if(newTour.cost <= currTour.cost || Math.exp((currTour.cost-newTour.cost)/temperature) > Math.random()){
    currTour = newTour;
    bestTour = Math.min(bestTour, currTour);
  }
  temperature *= 1-dropRate; // make it cooler
}
return bestTour;

Voila! That’s pretty much the algorithm behind the interactive demo at the beginning of this page. Quite naive in some aspects, yes, but faithful tied to the theory.

Those small details

Yeah, I know! There’s always some minor, but important, details of implementation that usually gone missing but, don’t worry, I’ll ty to cover them all. Let’s repeat the steps but this time going diving into implementation details:

  1. Find a feasible solution for the TSP: A TSP problem is, by convention, a complete graph (edge from everyone to everyone) so to find a valid tour (hamiltonian cycle) one can just list the cities (vertices) without repetition. Ex. If there are five 5 cities={A,B,C,D,E}, then A-B-C-D-E-A is already a valid tour and so is any random distinct other like C,B,D,E,A,C.
  2. While temperature is greater than 1:
    1. Build a new solution from the current one: this one can be tricky because this step is very important, an intelligent method here can quite improve the convergence of the algorithm. Although we want to find a random new answer it is no entirely random because we must use the current one to do this and, while we want it to be different from the current, we also want to change it way da it can somehow improve convergence as we just saw. The algorithm of this post chooses 2 random cities and swap them, you can see that ir works it is obviously quite naive.
    2. Try to use the new answer
      1. If the new solution is less than or equal to current one use the new solution as current: we are after the best possible answer, if we found one we should keep it.
      2. Else If \(E^{\frac{current-new}{temperature}} > random(0,1)\), use the new solution as current: here lies all the mathematical fun =D. We will talk about this more in a few, for now we just need to understand that both sides of the equation will return a number between 0 and 1. So based on their sizes there will be more/less chances to evaluate to true;
    3. Keep the overall best answer: again, we are after the best possible answer so if we found one we should keep it.
    4. Decrement temperature: make it some percent smaller so we can, eventually, end the algorithm
  3. Return the overall best answer: that’s it, our algorithm succeeded (well, it found an answer at least).

The Mathematical Fun

You may be challenged by the equation: \[e^{\frac{current-new}{temperature}} > random(0,1)\] Don’ be. Just take a closer look at it and you will understand it. Everytime you reach this line of code is because \(current>new\), so this subtraction always return a number \(< 0\). This negative result will then be divided by the current temperature so:

  • if the temperature is high then the negative number will be divided by a big number making it small
  • else the negative number will be divided by a small number making it big.

Remember, though, that we are making “e” to the power of this negative number so it’s an inverse relationship, the bigger the negative number is the smaller will be ‘e’ to its power, ex. \(e^{-x}>e^{-2x}\).
At the final part we are comparing the result to see if it’s bigger than a random number \(0\leq random(0,1)<1\) so the bigger the result is, more likely it is to be greater than the randomly generated number. More especifically: if temperature is high, higher are the chances that the result will be greater than the randomly generated number.

The real challenge of this equation is demonstrating the probabilities in play, something in which we are better of reading one of the papers that originated it.

References

  1. Wikipedia - Simulated Annealing
  2. Kirkpatrick, Scott, C. Daniel Gelatt, and Mario P. Vecchi. “Optimization by simulated annealing.” science 220.4598 (1983): 671-680.
  3. Černý, V. (1985). “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm”. Journal of Optimization Theory and Applications. 45: 41–51.
  4. Semenovskaya, S.; Khachaturyan, K.; Khachaturyan, A. (1985). “Statistical Mechanics Approach to the Determination of a Crystal”. Acta Crystallographica (A41): 268–273.
  5. Almost Looks Like Work by Jason Cole
  6. Wikipedia - Local optimum
  7. Wikipedia - Maxima and minima