I have a little doubt with respect to the two-opt improvement heuristic for TSP. I understand how it works, from the Wikipedia article on 2-opt and "Heuristics for the Traveling Salesman Problem". However, from my understanding and subsequent experiments, it appears this heuristic does not give any guarantee to at least not lead to a worse tour. If this is so, I don't understand how a two-opt move is any better than a random swap of cities. I would really appreciate if this can be clarified for me. Thanks!
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ Unfortunately, I am unable to access any of your links. $\endgroup$– Yuval FilmusMar 20, 2017 at 11:43
-
2$\begingroup$ 2-opt is indeed just a random change and the new tour may be worse, but it can be incorporated in e.g. simulated annealing. If the new tour is shorter, the chance is bigger that simulated annealing will accept the 2-opt change, otherwise it might undo it. $\endgroup$– Albert HendriksMar 20, 2017 at 11:51
-
$\begingroup$ @AlbertHendriks Thanks for the answer. That's quite interesting, though! One wonders then, why it's so much touted? And, sorry to bother you, but could you expatiate on why SA would have a greater chance of accepting a better 2-opt move than a better random swap? $\endgroup$– ayePeteApr 3, 2017 at 13:56
-
$\begingroup$ @AlbertHendriks PS: Sorry about the lateness in my reply! :) $\endgroup$– ayePeteApr 3, 2017 at 14:36
-
$\begingroup$ @ayePete SA just checks if the tour is shorter after applying the random 2-opt change. If so, it accepts the change. If not, it randomly undoes or accepts the change. It's basically just an "if"-statement like that. 2-opt is powerful with simulated annealing, since you can find good solutions this way. $\endgroup$– Albert HendriksApr 6, 2017 at 9:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2-Opt is a move that doesn't guarantee to give a better tour.
We use such moves ($k$-Opt, swap, insertion,..) in local searches to look for a better tour in the neighbor of the input (which is a tour).
Local search consists of browsing all (feasible) tours that can be produced with only one move from the input.
If the input tour is not improved, we call it a local optimum which may be the optimal solution.
