Rescaled Simulated Annealing—Accelerating Convergence of Simulated Annealing by Rescaling the States Energies |
| |
Authors: | L Herault |
| |
Institution: | (1) LETI (CEA), DSYS, CEA-Grenoble, 17 rue des Martyrs, 38054 Grenoble Cedex 9, France |
| |
Abstract: | This paper presents a new metaheuristic, called rescaled simulated annealing (RSA) which is particularly adapted to combinatorial problems where the available computational effort to solve it is limited. Asymptotic convergence on optimal solutions is established and the results are favorably compared to the famous ones due to Mitra, Romeo, and Sangiovanni-Vincentelli (Mitra, Romeo, and Sangiovanni-Vincentelli. (1986). Adv. Appl. Prob. 18, 747–771.) for simulated annealing (SA). It is based on a generalization of the Metropolis procedure used by the SA algorithm. This generalization consists in rescaling the energies of the states candidate for a transition, before applying the Metropolis criterion. The direct consequence is an acceleration of convergence, by avoiding dives and escapes from high energy local minima. Thus, practically speaking, less transitions need to be tested with RSA to obtain a good quality solution. As a corollary, within a limited computational effort, RSA provides better quality solutions than SA and the gain of performance of RSA versus SA is all the more important since the available computational effort is reduced. An illustrative example is detailed on an instance of the Traveling Salesman Problem. |
| |
Keywords: | combinatorial optimization meta-heuristics rescaled simulated annealing simulated annealing Metropolis criterion asymptotic results traveling salesman problem |
本文献已被 SpringerLink 等数据库收录! |
|