Wednesday, April 18, 2012

2/3 Swing Follow-up

So the algorithm I spoke of in my last post is actually very similar to an algorithm known as v-opt. The difference between 2/3 swing and v-opt is that in v-opt, before ensuring that the solution is an n-opt minima, first ensures that it is also a k-minima for all k < n. So then, the solution is guaranteed to be  gets to a 2-opt minima, then a 3-opt minima, and stops, whereas mine swings back and forth. This difference is further seen when 4-opt is introduced. Then, v-opt would find a 2-opt minima, then a three-opt minima, then ensure it is at a two-opt minima again, then ensure it is in a three-opt minima again, etc. Finally, when both 2-opt and 3-opt minima is found, it ensures it is in a four-opt minima, then a two-opt minima, then a three-opt minima, then a two-opt minima again, until it is in both 2- and 3-opt minimas before it checks for 4-opt minima, etc. I know, kinda confusing.
Mine just ensures it's in a 2-opt minima, and goes round-robin instead of making sure the solution is a minima of all opt's below the current one (both 2- and 3- opt before we ensure 4-optimality). It just goes round and round - 2-opt, then 3-, then 4-, then 2-, then  3-, then 4-,... I found this approach did alot better than conventional v-opt as I understand it.
That may have been a little confusing, but I wanted to make sure I tied in my own research with what's already out there.