Metropolis, Simulated Annealing, and Iterated Energy Transformation Algorithms: Theory and Experiments |
| |
Authors: | Olivier Catoni |
| |
Institution: | DIAM—Laboratoire de Mathématiques, URA 762 du CNRS, Département de Mathématiques et d'Informatique, Ecole Normale Supérieure, 45 rue d'Ulm, 75 230, Paris Cedex 5, France |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|