Optimization with 2-OPT - Part 2 - Animated TSP Solver

I’m dividing this post into 2 parts:

Interactive Demo (2-OPT applied to TSP)

Algorithm

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

  1. Find a trial Solution \(s \in S\), for which M(s) is as small as we can make it at a first try.
  2. Apply some transformations, called ‘inversions’, which transforms this trial solutions into some other elements of S, whose measures are progressive smaller.
  3. Check C for elements which might be included in the final s at an advantage. If there are any such elements try to find a transformation which decreases the measure of the sequence.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
function two_opt(currentTour){
    var n = currentTour.vertices.length;
    var bestTour = currentTour;
    for(let i=1; i<n-2; i++){
        for(let j=i+1; j<n+1; j++){
            if(j-i == 1) continue;
            var swap = currentTour.vertices.slice(0,i).concat(currentTour.vertices.slice(i,j).reverse(), currentTour.vertices.slice(j,n))
            var newTour = {vertices:swap, cost:cost(swap)};
            if(newTour.cost < bestTour.cost) bestTour = newTour;
        }
    }
    return bestTour;
}

That’s pretty much the algorithm behind the interactive demo at the beginning of this page. It is executed until the given ‘iteration limit’ is reached or until there’s no cost improvement after reversing the edges, whatever comes first.

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