The optimization algorithm “vopt” applied to any optimization problem is simple. I now outline my own version, which I call “s-vopt” because it “swings” from one level of opt local search to another.
- Convert your solution representation to a bit array.
- Go through each bit, flip it, and see if it improves the solution. If it does, keep the bit flipped and repeat until there are no more bits that can be flipped to reach a local maxima (assuming you’re maximizing a fitness function). You have now reached a local 1-opt maxima.
- Now flip each possible pair of bits, flip them, and see if the fitness rating improves. if it does, keep those bits flipped and go to step 2. If all the pairs have been tried without success continue to the next step.
- Continue in this fashing, first trying to flip all possible triples, then quadruples, then quintuples, etc. until you want to stop. At each, if an improved solution is found, keep it and go to step 2. if not, continue on the next step.