I'd be interested to see how a Genetic algorithm with carefully chosen mutation/recombination operators would suit this problem. Mutations could be flips and r

I'd be interested to see how a Genetic algorithm with carefully chosen mutation/recombination operators would suit this problem. Mutations could be flips and random swaps. Recombination would be combining chunks of already partially optimised solutions (breeding). Genetic algorithms do suffer a cost of having to keep a population of solutions in memory so it would be interesting to see how the end results compares in performance to annealing.