Two physically motivated algorithms for combinatorial optimization: thermal cycling and iterative partial transcription Original Research Article

Among the various heuristic approaches to combinatorial optimization, local-search-based evolutionary algorithms have been particularly successful for the last years. We present two algorithms developed for jumping from local minimum to local minimum: Thermal cycling consists of cyclically heating and quenching by Metropolis and local search procedures, respectively, where the amplitude decreases during the process. Iterative partial transcription acts as a local search in the subspace spanned by the differing components of two approximate solutions corresponding to the relaxation of a spin glass by flipping clusters. The high efficiency of the proposed procedures is illustrated for the traveling salesman problem.