research-article

A theoretical framework for simulated annealing

Authors:

Alberto Sangiovanni-VincentelliAuthors Info & Claims

Algorithmica, Volume 6, Issue 1-6

Pages 302 - 345

https://doi.org/10.1007/BF01759049

Published: 01 June 1991 Publication History

Abstract

Simulated Annealing has been a very successful general algorithm for the solution of large, complex combinatorial optimization problems. Since its introduction, several applications in different fields of engineering, such as integrated circuit placement, optimal encoding, resource allocation, logic synthesis, have been developed. In parallel, theoretical studies have been focusing on the reasons for the excellent behavior of the algorithm. This paper reviews most of the important results on the theory of Simulated Annealing, placing them in a unified framework. New results are reported as well.

References

[1]

Aarts E. H. L. and van Laarhoven P. J. M. Statistical Cooling: A General Approach to Combinatorial Optimization Problems Philips J. Res. 1985 40 193-226

[2]

Aarts E. H. L. and van Laarhoven P. J. M. Simulated Annealing: Theory and Applications 1987 Dordrecht Reidel

[3]

Anily S. and Federgruen A. Probabilistic Analysis of Simulated Annealing Methods Graduate School of Business 1985 New York Columbia University

[4]

Anily S. and Federgruen A. Simulated Annealing Methods with General Acceptance Probabilities J. Appl. Probab. 1987 24 657-667

[5]

C. R. Aragon, D. S. Johnson, L. A. McGeoch, and C. Schevon. Simulated Annealing Performance Studies. Workshop on Statistical Physics in Engineering and Biology, April, 1984.

[6]

P. Banerjee and M. Jones. A Parallel Simulated Annealing Algorithm for Standard Cell Placement on a Hypercube Computer.Proc. ICCAD, pages 34–37, 1986.

[7]

Binder K. Monte Carlo Methods in Statistical Physics 1978 Berlin Springer Verlag

[8]

Bohachevsky I. O., Johnson M. E., and Stein M. L. Generalized Simulated Annealing for Function Optimization Technometrics 1986 28 3 209-217

[9]

Casotto A., Romeo F., and Sangiovanni-Vincentelli A. A Parallel Simulated Annealing Algorithm for the Placement of Macro-Cells IEEE Trans. Computer-Aided Design 1987 6 838-847

[10]

A. Casotto and A. Sangiovanni-Vincentelli. Placement of Standard Cells Using Simulated Annealing on the Connection Machine.Proc. ICCAD, pages 350–353, 1987.

[11]

Connors D. P. and Kumar P. R. Balance of Recurrence Orders in Time-Inhomogeneous Markov Chains with Applications to Simulated Annealing Probab. Engrg. Inform. Sci. 1988 2 2 157-184

[12]

F. Darema-Rogers, S. Kirkpatrick, and V. A. Norton. Simulated Annealing on Shared Memory Parallel Systems.IBM J. Res. Develop., 1987.

[13]

Davenport W. B. Probability and Random Processes: An Introduction for Applied Scientists and Engineers 1970 New York McGraw-Hill

[14]

Faigle U. and Schrader R. On the Convergence of Stationary Distributions in Simulated Annealing Algorithms Inform. Process. Lett. 1988 27 4 189-194

[15]

Freedman D. Markov Chains 1971 San Francisco, CA Holden-Day

[16]

Gelfand S. Analysis of Simulated Annealing Type of Algorithms 1987 Cambridge, MA. Massachusetts Institute of Technology

[17]

S. Gelfand and S. Mitter. Analysis of Simulated Annealing for Optimization.Proc. 24th Conf. on Decision and Control, pages 779–786, December 1985.

[18]

Gelfand S. and Mitter S. Simulated Annealing with Noisy or Imprecise Energy Measurements 1987 Cambridge, MA Massachusetts Institute of Technology

[19]

Geman S. and Geman D. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images IEEE Trans. Pattern Anal. Mach. Intell. 1984 6 721-741

[20]

Gidas B. Non-Stationary Markov Chains and Convergence of the Annealing Algorithm J. Statist. Phys. 1984 39 73-131

[21]

Gnedenko B. V. and Khinchin A. Y. An Elementary Introduction to the Theory of Probability 1961 San Francisco, CA Freeman

[22]

Hajek B. Cooling Schedules for Optimal Annealing Math. Oper. Res. 1985 13 2 311-329

[23]

Hammersley J. M. and Handscomb D. C. Monte Carlo Methods 1964 New York Wiley

[24]

Hastings W. K. Monte Carlo Sampling Methods Using Markov Chains and Their Applications Biometrika 1970 57 1 97-109

[25]

Hillis D. The Connection Machine 1985 Cambridge, MA MIT Press

[26]

Hoel P. G. Introduction to Mathematical Statistics 1962 New York Wiley

[27]

Holley R. and Stroock D. Simulated Annealing via Sobolev Inequalities Comm. Math. Phys. 1988 115 4 553-569

[28]

M. D. Huang, F. Romeo, and A. Sangiovanni-Vincentelli. An Efficient General Cooling Schedule for Simulated Annealing,Proc. ICCAD, pages 381–384, 1986.

[29]

Hustin S. Tim, a New Standard Cell Placement Program Based on the Simulated Annealing Algorithm Master's thesis 1988 Berkeley, CA University of California

[30]

Isaacson D. L. and Madsen R. W. Markov Chains: Theory and Applications 1976 New York Wiley

[31]

Kemeny J. G. and Snell J. L. Finite Markov Chains 1976 New York Springer-Verlag

[32]

Kirkpatrick S., Gelatt C. D., and Vecchi M. P. Optimization by Simulated Annealing Science 1983 220 4598 671-680

[33]

S. A. Kravitz and R. A. Rutenbar. Multiprocessor-based Placement by Simulated Annealing.Proc. 23rd Design Automation Conf., pages 567–573, 1986.

[34]

J. Lam and J-M. Delosme. Logic Minimization Using Simulated Annealing.Proc. ICCAD, pages 348–352, 1986.

[35]

Lam J. and Delosme J.-M. An Adaptive Annealing Schedule 1987 New Haven, C. University of Yale

[36]

J. Lam and J-M. Delosme. Simulated Annealing: A Fast Heuristic for Some Generic Layout Problems.Proc. ICCAD, pages 510–513, 1988.

[37]

Lundy M. and Mees A. Convergence of the Annealing Algorithm Math. Programming 1986 34 111-124

[38]

Madsen R. W. and Isaacson D. L. Strongly Ergodic Behavior for Non-Stationary Markov Processes Ann. Prob. 1973 1 2 329-335

[39]

Metropolis N., Rosenbluth A. W., Rosenbluth M. N., and Teller A. H. Equation of State Calculations by Fast Computer Machines J. Chem. Phys. 1953 21 1087

[40]

D. Mitra, F. Romeo, and A. Sangiovanni-Vincentelli. Convergence and Finite-Time Behavior of Simulated Annealing.Proc. 24th Conf. on Decision and Control, December, 1985.

[41]

Mitra D., Romeo F., and Sangiovanni-Vincentelli A. Convergence and Finite-Time Behavior of Simulated Annealing Adv. Appl. Probab. 1986 18 747-771

[42]

Nulton J. D. and Salamon P. Statistical Mechanics of Combinatorial Optimization Phys. Rev. A 1988 37 4 1351-1356

[43]

R. H. J. M. Otten and L. P. P. P. van Ginneken. Floorplan Design Using Simulated Annealing.Proc. ICCAD, pages 96–98, 1984.

[44]

Otten R. H. and van Ginneken L. P. Simulated Annealing: The Algorithm 1989 Boston, MA Kluwer

[45]

Peskun P. H. Optimum Monte Carlo Sampling Using Markov Chains Biometrika 1973 60 3 607-612

[46]

Ripley B. D. Stochastic Simulation 1987 New York Wiley

[47]

Romeo F. Simulated Annealing: Theory and Applications to Layout Problems Ph. D. thesis 1989 Berkeley, CA University of California

[48]

Rossier Y., Troyon M., and Liebling T. Probabilistic Exchange Algorithms and Euclidean Traveling Salesman Problems Technical Report RO 851125 1985 Lousanne EPF

[49]

Rudin W. Principles of Mathematical Analysis 1976 New York McGraw-Hill

[50]

A. Sangiovanni-Vincentelli. Editor's Foreword.Algorithmica, this issue.

[51]

Seneta E. Non-negative Matrices and Markov Chains 1981 New York Springer-Verlag

[52]

Sorkin G. B. Combinatorial Optimization, Simulated Annealing and Fractals Master's thesis 1987 Berkeley, CA University of California

[53]

G. B. Sorkin. Rapidly Mixing Analysis of Simulated Annealing on Fractals.Proc. of Sixth Annual MIT VLSI Conf., pages 331–351, April, 1990.

[54]

G. B. Sorkin. Efficient Simulated Annealing on Fractal Energy Landscapes.Algorithmica, this issue, pp. 367–418, 1991.

[55]

Strenski P. N. Optimal Annealing Schedules: A Case Study 1987 Yorktown Heights, NY I.B.M. T. J. Watson Research Center

[56]

P. N. Strenski and S. Kirkpatrick. Analysis of Finite Length Annealing Schedules.Algorithmica, this issue, pp. 346–366, 1991.

[57]

Tijms H. C. Stochastic Modeling and Analysis: A Computational Approach 1986 Chichester Wiley

[58]

Tsitsiklis J. N. Markov Chains with Rare Transitions and Simulated Annealing 1985 Cambridge, MA MIT Laboratory for Information and Decision Systems

[59]

Černy V. Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm J. Optim. Theory Appl. 1985 45 41-51

[60]

S. White, Concept of Scale in Simulated Annealing.Proc. ICCD, pages 646–651, 1984.

Cited By

Schwarz THochberger CMitra TYoung EXiong J(2022)Technology Mapping of Genetic CircuitsProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design10.1145/3508352.3549344(1-8)Online publication date: 30-Oct-2022
https://dl.acm.org/doi/10.1145/3508352.3549344
Papastamoulis PNtzoufras I(2022)On the identifiability of Bayesian factor analytic modelsStatistics and Computing10.1007/s11222-022-10084-432:2Online publication date: 15-Apr-2022
https://dl.acm.org/doi/10.1007/s11222-022-10084-4
Ball RBranke JMeisel S(2018)Optimal Sampling for Simulated Annealing Under NoiseINFORMS Journal on Computing10.5555/3215359.321537330:1(200-215)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.5555/3215359.3215373
Show More Cited By

Recommendations

Rescaled Simulated Annealing—Accelerating Convergence of Simulated Annealing by Rescaling the States Energies

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 ...
A Modified Simulated Annealing Algorithm for the Quadratic Assignment Problem

The quadratic assignment problem (QAP) is one of the well-known combinatorial optimization problems and is known for its various applications. In this paper, we propose a modified simulated annealing algorithm for the QAP - M-SA-QAP. The novelty of the ...
Constructing efficient simulated annealing algorithms

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 6, Issue 1-6

Jun 1991

883 pages

ISSN:0178-4617

Issue’s Table of Contents

© Springer-Verlag New York Inc. 1991.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 June 1991

Revision received: 15 January 1990

Received: 15 October 1989

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Schwarz THochberger CMitra TYoung EXiong J(2022)Technology Mapping of Genetic CircuitsProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design10.1145/3508352.3549344(1-8)Online publication date: 30-Oct-2022
https://dl.acm.org/doi/10.1145/3508352.3549344
Papastamoulis PNtzoufras I(2022)On the identifiability of Bayesian factor analytic modelsStatistics and Computing10.1007/s11222-022-10084-432:2Online publication date: 15-Apr-2022
https://dl.acm.org/doi/10.1007/s11222-022-10084-4
Ball RBranke JMeisel S(2018)Optimal Sampling for Simulated Annealing Under NoiseINFORMS Journal on Computing10.5555/3215359.321537330:1(200-215)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.5555/3215359.3215373
Ghezavati VNia N(2015)Development of an optimization model for product returns using genetic algorithms and simulated annealingSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-014-1465-819:11(3055-3069)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/s00500-014-1465-8
Mirsanei HZandieh MMoayed MKhabbazi M(2011)A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup timesJournal of Intelligent Manufacturing10.5555/2070879.207089622:6(965-978)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.5555/2070879.2070896
Hsieh S(2010)Use of GA based approach for engineering design through WWWWSEAS Transactions on Computers10.5555/1852414.18524209:4(372-381)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.5555/1852414.1852420
Bezuglov AVargas J(2006)Simulated annealing algorithm with biased neighborhood distribution for training profile modelsProceedings of the 16th international conference on Foundations of Intelligent Systems10.1007/11875604_71(642-651)Online publication date: 27-Sep-2006
https://dl.acm.org/doi/10.1007/11875604_71
Fanany MKumazawa I(2006)A neural network for simultaneously reconstructing transparent and opaque surfacesProceedings of the Third international conference on Image Analysis and Recognition - Volume Part II10.1007/11867661_15(157-168)Online publication date: 18-Sep-2006
https://dl.acm.org/doi/10.1007/11867661_15
Han CPark J(2006)Simulated annealing based learning approach for the design of cascade architectures of fuzzy neural networksProceedings of the Third international conference on Advances in Neural Networks - Volume Part I10.1007/11759966_117(798-803)Online publication date: 28-May-2006
https://dl.acm.org/doi/10.1007/11759966_117
Han CPark J(2006)Adaptive-Partitioning-Based stochastic optimization algorithm and its application to fuzzy control designProceedings of the 4th Helenic conference on Advances in Artificial Intelligence10.1007/11752912_9(67-76)Online publication date: 18-May-2006
https://dl.acm.org/doi/10.1007/11752912_9
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents