Optimization by simulated annealing

Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P.

Affiliations

¹IBM Thomas J. Watson Research Center, Yorktown Heights, New York 10598.

²Present address: Instituto Venezolano de Investigaciones Cientificas, Caracas 1010A, Venezuela

Abstract

There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods.

Links

DOI: 10.1126/science.220.4598.6

Cited By (47)

Year	Entry
2010	Hammouche K, Diaf M, Siarry P. A comparative study of various meta-heuristic techniques applied to the multilevel thresholding problem. Eng Appl Artificial Intell. 2010;23(5):676-688.
2016	Liauthor H, Singh S, Kaira S, Mertens JCE, Williams JJ, Chawla N, Jiao Y. Microstructural quantification and property prediction using limited X-ray tomography data. JOM. August 2016;68(8):2288-2295.
2021	Miller M, Perez-Rapela D, Gepner B, Edwards M, Jermakian J, Forman J. A methodology for large-scale parametric evaluation of child booster seats. In: Proceedings of the 2021 International IRCOBI Conference on the Biomechanics of Injury. September 8-10, 2021; Online.593-615.
2004	Bochenek B, Pyrz R. Reconstruction of random microstructures: a stochastic optimization problem. Comp Mater Sci. September 2004;31(1-2):93-112.
2013	Gerus P, Sartori M, Besier TF, Fregly BJ, Delp SL, Banks SA, Pandy MG, D'Lima DD, Lloyd DG. Subject-specific knee joint geometry improves predictions of medial tibiofemoral contact forces. J Biomech. November 15, 2013;46(16):2778-2786.
1999	Neptune RR. Optimization algorithm performance in determining optimal controls in human movement analyses. J Biomech Eng. April 1999;121(2):249-252.
1994	Goffe WL, Ferrier GD, Rogers J. Global optimization of statistical functions with simulated annealing. J Econom. January–February 1994;60:65-99.
2013	Tahmasebi P, Sahimi M. Cross-correlation function for accurate reconstruction of heterogeneous media. Phys Rev Lett. February 15, 2013;110(7):078002.
1991	Fruchterman TMJ, Reingold EM. Graph drawing by force-directed placement. Softw Pract Exp. November 1991;21(11):1129-1164.
2002	Pasini D. A New Theory for Modelling the Mass Efficiency of Material, Shape and Form [PhD thesis]. Bristol, UK: University of Bristol; December 2002.
2002	Li M. Optimal Lot Streaming and Scheduling of Multiple Jobs in Two-Machine No-Wait Flow Shops [Master's thesis]. Concordia University; March 2002.
2006	Defersha FM. An Integrated Approach in the Design of Cellular Manufacturing Systems for Dynamic Production Requirements [PhD thesis]. Concordia University; February 2006.
2007	Agrawal AK. A Dynamic Programming Approach for Economic Optimization of Inspection Strategies in a Multi-Stage Manufacturing System [Master's thesis]. Concordia University; April 2007.
2007	Zhang W. Production Planning in a Multi-Product Manufacturing Environment Using Constant Work-in-Process [PhD thesis]. Concordia University; April 2007.
1996	Ellery A. Systems Design and Control of a Freeflying Space Robotic Manipulator System (ATLAS) for in-Orbit Satellite Servicing Operations [PhD thesis]. Cranfield University; 1996.
2008	Pal S. Explicit Finite Element Modeling of Joint Mechanics [PhD thesis]. University of Denver; August 2008.
2021	Mohseni A. Path Planning for Mobile Robots [Master's thesis]. École de technologie supérieure; June 8, 2021.
2002	Teng C-P. Structural Optomization Under Variable Loading Conditions [PhD thesis]. McGill University; August 2002.
2004	Al-Widyan K. The Robust Design of Robotic Mechanical Systems [PhD thesis]. McGill University; September 2004.
2012	Taghvaeipour A. Contributions to the Structural Analysis of Parallel Manipulators With Reduced Mobility [PhD thesis]. McGill University; April 2012.
1998	Patton JL. Global Modeling of Adaptive, Dynamic Balance Control [PhD thesis]. Evanston, IL: Northwestern University; December 1998.
2016	Ewing JA. The Effect of Patient-Specific Ligament Properties on Knee Mechanics Following Total Knee Arthroplasty [PhD thesis]. The Ohio State University; 2016.
2010	Jiao Y. Characterization of the Structure of Heterogeneous Materials and Particle Packings [PhD thesis]. Princeton, NJ: Princeton University; June 2010.
2003	Chan C-HC. Actuator Hysteresis Modeling and Compensation With an Adaptive Search Space Based Genetic Algorithm [Master's thesis]. Ryerson University; 2003.
2014	Cutbill A. Development of an Interactive Engineering Design Optimization Framework [Master's thesis]. Simon Fraser University; F 2014.
2019	Wu D. Knowledge Assisted Metamodeling and Optimization Method for Large-Scale Engineering Design [PhD thesis]. Simon Fraser University; Summer 2019.
2007	Santos VJ. A Bayesian Approach to Biomechanical Modeling: A Treatise on the Human Thumb [PhD thesis]. Ithaca, NY: Cornell University; May 2007.
2007	Aleman DM. Optimization Methods in Intensity Modulated Radiation Therapy Treatment Planning [PhD thesis]. University of Florida; December 2007.
1994	Nussbaum MA. Artificial Neural Network Models for Analysis of Lumbar Muscle Recruitment During Moderate Static Exertions [PhD thesis]. University of Michigan; 1994.
2019	Lesellier M. Conception, optimisation et commande d’un stablisateur actif pour la compensation des vibrations des robots parallèles à câbles [PhD thesis]. University of Montpellier; 2019.
2011	Contardo C. Models and Algorithms for the Capacitated Location-Routing Problem [PhD thesis]. University of Montreal; July 2011.
2015	Hodiya A. A Mathematical Model and a Simulated Annealing Algorithm for an Integrated Facility Layout and Cell Formation [Master's thesis]. University of Guelph; March 2015.
2015	Shafigh S. Mathematical Models and Solution Procedures in the Design and Scheduling of Manufacturing Systems With Distributed Layouts [PhD thesis]. University of Guelph; August 2015.
2009	Qian J. Design and Analysis of a Three Degrees of Freedom (DOF) Parallel Manipulator With Decoupled Motions [Master's thesis]. University of Ontario Institute of Technology; April 2009.
1997	Zolfaghari S. Design and Planning for Cellular Manufacturing: Application of Neural Networks and Advanced Search Techniques [PhD thesis]. University of Ottawa; 1997.
2023	Sajjadi S. Predictive Visual Servoing: Uncertainty Analysis and Probabilistic Robust Frameworks [PhD thesis]. University of Regina; June 2023.
1999	Beck JC. Texture Measurements as a Basis for Heuristic Commitment Techniques in Constraint-Directed Scheduling [PhD thesis]. University of Toronto; 1999.
2017	Tran TT. Decomposition Models for Complex Scheduling Applications [PhD thesis]. University of Toronto; 2017.
2020	Perez Rapela D. Methodology for the Evaluation of Human Response Variability to Intrinsic and Extrinsic Factors Including Uncertainties [PhD thesis]. Charlottesville, VA: University of Virginia; May 2020.
1999	Wang GG. A Quantitative Concurrent Engineering Design Method Using Virtual Prototyping-Based Global Optimization and Its Application in Transportation Fuel Cells [PhD thesis]. University of Victoria; 1999.
2001	Carretero G. JA. Distance Determination Algorithms for Convex and Concave Objects [PhD thesis]. University of Victoria; 2001.
2002	Zheng R. Rapid Prototype Development of PEM Fuel Cell Gas Delivery Plates [PhD thesis]. University of Victoria; 2002.
2004	Falcão da Luz L. Design of a Magnetorheological Brake System [Master's thesis]. University of Victoria; 2004.
2010	Younis AAH. Space Exploration and Region Elimination Global Optimization Algorithms for Multidisciplinary Design Optimization [PhD thesis]. University of Victoria; 2010.
2011	Carvalho ARD. Design and Development of an Anthropomorphic Hand Prosthesis [PhD thesis]. University of Victoria; 2011.
1995	Janabi-Sharifi F. A Supervisory Intelligent Robot Control System for a Relative Pose-Based Strategy [PhD thesis]. University of Waterloo; 1995.
2014	Vidt ME. Muscle Structure and Function in Older Adults With a Rotator Cuff Tear [PhD thesis]. Winston-Salem, NC: Wake Forest University; April 2014.