Metropolis, simulated annealing, and iterated energy transformation algorithms: Theory and experiments

In this paper, we compare from the theoretical and experimental points of view three stochastic optimization algorithms: the Metropolis, simulated annealing, and iterated energy transformation algorithms. We give the optimal exponents for the concentration of the marginal distribution of the final state of these algorithms around the global minima of the virtual energy function. Experiments are performed on an N.P. complete benchmark which tries to retain the main aspects of scheduling problems. They lead to the same qualitative ranking of algorithms as the theory does.