2
$\begingroup$

I have a question regarding performance of 2-opt and 3-opt algorithms.

I tried implementing the 3-opt and 2-opt algorithms and most of the time 3-opt outperforms the 2-opt algorithm around 5%.

Surprisingly, in few cases my 2-opt algorithm outperforms the 3-opt algorithm. I am wondering, is it some kind of error or it may happen that the 2-opt algorithms sometimes end in the better local optimum?

(I know that if solution is 3-opt, then it is also 2-opt. But we can find multiple 2-opt or 3-opt solutions in the same route, don't we?)

$\endgroup$
2
$\begingroup$

Your experiments show that 2-opt could outperform 3-opt. The reason is that there are many local optima, and some of the are better than others. Local search guarantees reaching a local optimum with respect to the moves being considered, but it doesn't provide any guarantee beyond that. It could be that one point which is locally optimal with respect to 2-opt is better than another point which is locally optimal with respect to 3-opt.

You can modify your algorithm to first try local search with respect to 2-opt and then with respect to 3-opt, and take the better solution. You could improve this by running a 3-opt local search starting at the 2-opt local minimum.

There are other degrees of freedom in the local search algorithm: for example, when there are several possible local improvements, which do you choose? A uniformly random one? The first one you found? The one which results in the best improvement? A random one chosen in proportion to the improvement? And so on. Each of these could result in a different solution. If you use a randomized strategy, each single run using the same heuristic could result in a different solution, so it makes sense to run local search many times.

An even more drastic option would be to replace local search with simulated annealing, which sometimes allows taking a local change which worsens the situation a bit. This might fare better on some instances.

$\endgroup$
  • $\begingroup$ Thank you Yuval. You confirmed what I was just assuming. $\endgroup$ – BraveDistribution Feb 7 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.