Parallel simulated annealing by mixing of states (Q1282439)

Simulated annealing (SA) is an effective method for the optimization of complex cost functions for which heuristic methods do not exist. The authors introduce a new class of algorithms for parallel SA that does not depend on the structure of the optimization problem. The authors show that one particular implementation of this algorithms is scalable for up to 100 processors at nearly 100\% parallel efficiency. The used strategy contains two major elements. The authors monitor and pool performance statistics obtained simultaneously on all processors and mix states at intervals to ensure a Boltzmann distribution of energies. Some tests are presented.