Combinatorial optimization by iterative partial transcription
Arnulf Möbius, Bernd Freisleben, P. Merz, Michael Schreiber · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · 1999
A procedure is presented that considerably improves the performance of local search based heuristic algorithms for combinatorial optimization problems. It increases the average ``gain'' of the individual local searches by merging pairs of solutions: certain parts of either solution are transcribed by the related parts of the respective other solution, corresponding to flipping clusters of a spin glass. This iterative partial transcription acts as a local search in the subspace spanned by the differing components of both solutions. Embedding it in the simple multistart-local-search algorithm and in the thermal-cycling method, we demonstrate its effectiveness for several instances of the traveling salesman problem. The obtained results indicate that, for this task, such approaches are far superior to simulated annealing.