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.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aarts and Laarhoven. (1987). Simulated Annealing: Theory and Applications. Kluwer Academic Publishers.
Aarts and Korst. (1989). Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. New York: Wiley Publishers.
Anily and Federgruen. (1987). “Simulated Annealing Methods with General Acceptance Probabilities.” Journal of Applied Probability 24, 657-667.
Azencott. (1992). Simulated Annealing: Parallelization Techniques. New York: Wiley Publishers.
Bilbro et al. (1990). “Extraction of the Parameters of Equivalent Circuits of Microwave Transistors Using Tree Annealing.” I.E.E.E. Transactions on Microwave Theory and Techniques, November.
Bilbro and Snyder. (1991). “Optimization of Functions with Many Local Minima.” I.E.E.E. Transactions on Systems, Man and Cybernetics 21(4).
Cerny. (1985). “A Thermodynamical Approach to the Travelling Salesman Problem: An Efficient Simulated Algorithm.” Journal of Optimization Theory and Applications 45, 41-51.
Dowsland. (1995). “Simulated Annealing.” In C.R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Optimization Problems. McGraw Hill Publishers, pp. 20-69.
Feller. (1950). An Introduction to Probability Theory and its Applications. New York: Wiley Publishers.
Fleisher. (1995). “Cybernetic Optimization by Simulated Annealing: Accelerating Convergence by Parallel Processing and Probabilistic Feedback Control.” Journal of Heuristics 1(2), 225-246.
Hajek. (1988). “Cooling Schedules for Optimal Annealing.” Mathematics of Operations Research 13(2), 311-329.
Hastings. (1970). “Monte Carlo Sampling Methods Using Markov Chains and Their Applications.” Biometrika 57(1), 97-109.
Isaacson and Madsen. (1976). Markov Chains: Theory and Applications. John Wiley Publishers.
Kirkpatrick, Gelatt, and Vecchi. (1983). “Optimization by Simulated Annealing.” Science 220, 671-680.
Kozniewska (1962). “Ergodicité et stationnarité des chaînes de Markov variables à un nombre fini d'états possibles.” Colloq. Math. 9, 333-346.
van Laarhoven and Aarts. (1989). Simulated Annealing: Theory and Applications. Kluwer Academic Publishers.
Lundy and Mees. (1986). “Convergence of an Annealing Algorithm.” Mathematical Programming 34, 111-124.
Metropolis et al. (1953). “Equation of State Calculations by Fast Computing Machines.” Journal of Chemical Physics 21, 1087-1092.
Mitra, Romeo, and Sangiovanni-Vincentelli. (1986). “Convergence and Finite-Time Behavior of Simulated Annealing.” Adv. Appl. Prob. 18, 747-771.
Reinelt. (1994). The Traveling Salesman-Computational Solutions for TSP Applications. Springer Verlag Publishers.
Seneta. (1981). Non-Negative Matrices and Markov Chains. New York: Springer Verlag Publishers.
Snyder et al. (1990). “Optimal Thresholding-A New Approach.” Pattern Recognition Letters 11(12), 803-810.
Verhoeven and Aarts. (1995). “Parallel Local Search.” Journal of Heuristics 1(1), 43-65.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Herault, L. Rescaled Simulated Annealing—Accelerating Convergence of Simulated Annealing by Rescaling the States Energies. Journal of Heuristics 6, 215–252 (2000). https://doi.org/10.1023/A:1009627527067
Issue Date:
DOI: https://doi.org/10.1023/A:1009627527067