Abstract
By constructing a master equation for the distribution of outcomes from simulated annealing, we are able to characterize this process exactly for arbitrary annealing schedules on extremely small problems. Two sorts of numerical experiments are reported, using this formalism. First, annealing schedules are found which minimize the cut cost of partitioning a highly symmetric weighted graph, using a fixed number of Monte Carlo search steps. The experiments yield some surprising results, which sharpen our understanding of the problems inherent in trying to optimize a stochastic search. For example, optimal annealing schedules are not monotone decreasing in temperature. Second, we construct configuration spaces of random energies and varying connectivity. These are used to compare different annealing schedules which are common in the literature. The experiments also provide an occasion to contrast annealing schedules derived from asymptotic, worst-case bounds on convergence to the global optimum with adaptive schedules which attempt to maintain the system close to equilibrium throughout the annealing process.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, Optimization by Simulated Annealing,Science, vol. 220, pp. 671–680, May 1983.
D. Jepsen and C. D. Gelatt, Jr., Macro Placement by Monte Carlo Annealing,Proc. ICCAD 83, pp. 495–498, Oct. 1983.
C. Sechen and A. Sangiovanni-Vincentelli, The Timberwolf Placement and Routing Package,IEEE J. Solid-State Circuits, vol. 20, no. 2, pp. 510–522, Apr. 1985.
S. Geman and D. Geman, Stochastic Relaxation, Gibbs Distributions, and Bayesian Restoration of Images,IEEE Trans. Pattern Anal. Mach. Intell. vol. 6, pp. 721–741, Nov. 1984.
P. Carnevali, L. Coletti, and S. Patarnello, Image Processing by Simulated Annealing,IBM J. Res. Develop. vol. 29, no. 6, pp. 569–579, Nov. 1985.
E. D. Sontag and H. J. Sussman, Image Restoration and Segmentation Using the Annealing Algorithm,Proc. 24th Conf. on Decision and Control, pp. 768–773, Dec. 1985.
F. C. Jeng and J. W. Woods, Image Estimation by Stochastic Relaxation in the Compound Gaussian Case,Proc. ICASSP 88, Apr. 1988.
P. Molitor, Layer Assignment by Simulated Annealing,Microprocess. Microprogramm. (Netherlands), vol. 16, no. 4,5, pp. 345–349, Nov./Dec. 1985.
M. Vecchi and S. Kirkpatrick, Global Wiring by Simulated Annealing,IEEE Trans. Computed-Aided Design, vol. 2, no. 4, pp. 215–222, Oct. 1983.
D. Mitra, F. Romeo, and A. Sangiovanni-Vincentelli, Convergence and Finite-Time Behavior of Simulated AnnealingProc. 24th Conf. on Decision and Control, pp. 761–767, Dec. 1985.
S. B. Gelfand and S. K. Mitter, Analysis of Simulated Annealing for Optimization,Proc. 24th Conf. on Decision and Control, pp. 779–786, Dec. 1985.
B. Hajek, A Tutorial Survey of Theory and Applications of Simulated Annealing,Proc. 24th Conf. on Decision and Control, pp. 755–760., Dec. 1985.
S. A. Solla, G. B. Sorkin, and S. R. White, Configuration Space Analysis for Optimization Problems, inDisordered Systems and Biological Organization, E. Bienenstock, F. Fogelman, and G. Weisbuch (eds.), Springer-Verlag, New York, pp. 283, 1986.
S. Kirkpatrick and G. Toulouse, Configuration Space Analysis of Travelling Salesman Problems,J. Physique, vol. 46, pp. 1277–1292, Aug. 1985.
M. Mezard, On the Statistical Physics of Spin Glasses, inDisordered Systems and Biological Organization, E. Bienenstock, F. Fogelman, and G. Weisbuch (eds.), Springer-Verlag, New York, 1986.
M. Mezard, G. Parisi, and M. Virasoro,Spin Glasses and Optimization, World Scientific Press, London, 1988.
E. Aarts and P. van Laarhoven, Statistical Cooling Algorithm: A General Approach to Combinatorial Optimization Problems,Philips J. Res., vol. 40, no. 4, 193–226, 1985.
M. Huang, F. Romeo, and A. Sangiovanni-Vincentelli, An Efficient General Cooling Schedule for Simulated Annealing,Proc. ICCAD 86, pp. 381–384, 1986.
J. Lam and J.-M. Delosme, An Efficient Simulated Annealing Schedule: Derivation, Technical Report 8816, and An Efficient Simulated Annealing Schedule: Implementation and Evaluation, Technical Report 8817, Department of Electrical Engineering, Yale University, New Haven, CT, Sept. 1988.
R. H. J. M. Otten, Floorplan Design Using Simulated Annealing,Proc. ICCAD 84, pp. 96–98, Nov. 1984.
P. N. Strenski, Optimal Annealing Schedules, IBM Research Report RC12923, Yorktown Heights, NY, July 1987.
Harwell Subroutine Library, compiled by M. J. Hopper, AERE-R9185, Computer Science and Systems Division, Atomic Energy Research Establishment, Harwell, Oxfordshire, Dec. 1978.
Author information
Authors and Affiliations
Additional information
Communicated by Alberto Sangiovanni-Vincentelli.
Rights and permissions
About this article
Cite this article
Strenski, P.N., Kirkpatrick, S. Analysis of finite length annealing schedules. Algorithmica 6, 346–366 (1991). https://doi.org/10.1007/BF01759050
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01759050