I’m dividing this post into 2 parts:
- Part 1: Discuss the technique definition, idea and time complexity.
- Part 2 (this post): Applies this technique to a real problem by implementing an heuristic algorithm for the Traveling Salesman Problem.
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:
- Find a trial Solution \(s \in S\), for which M(s) is as small as we can make it at a first try.
- Apply some transformations, called ‘inversions’, which transforms this trial solutions into some other elements of S, whose measures are progressive smaller.
- 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
- Wikipedia - Simulated Annealing
- Kirkpatrick, Scott, C. Daniel Gelatt, and Mario P. Vecchi. “Optimization by simulated annealing.” science 220.4598 (1983): 671-680.
- Černý, V. (1985). “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm”. Journal of Optimization Theory and Applications. 45: 41–51.
- Semenovskaya, S.; Khachaturyan, K.; Khachaturyan, A. (1985). “Statistical Mechanics Approach to the Determination of a Crystal”. Acta Crystallographica (A41): 268–273.
- Almost Looks Like Work by Jason Cole
- Wikipedia - Local optimum
- Wikipedia - Maxima and minima