Editing Simulated annealing (section)

{{Short description|Probabilistic optimization technique and metaheuristic}}
{{Other uses|Annealing (disambiguation)}}
{{More citations needed|date=December 2009}}
{{Use American English|date=April 2024}}

[[File:Travelling salesman problem solved with simulated annealing.gif|thumb|Simulated annealing can be used to solve combinatorial problems. Here it is applied to the [[travelling salesman problem]] to minimize the length of a route that connects all 125 points.]]

[[File:3D TSP solved with simulated annealing 2.5 MB.gif|thumb|Travelling salesman problem in 3D for 120 points solved with simulated annealing.]]

'''Simulated annealing''' ('''SA''') is a [[probabilistic algorithm|probabilistic technique]] for approximating the [[global optimum]] of a given [[function (mathematics)|function]]. Specifically, it is a [[metaheuristic]] to approximate [[global optimization]] in a large [[solution space|search space]] for an [[optimization problem]]. For large numbers of local optima, SA can find the global optimum.<ref>{{Cite web |title=What is Simulated Annealing? |url=https://www.cs.cmu.edu/afs/cs.cmu.edu/project/learn-43/lib/photoz/.g/web/glossary/anneal.html |access-date=2023-05-13 |website=www.cs.cmu.edu}}</ref> It is often used when the search space is discrete (for example the [[traveling salesman problem]], the [[boolean satisfiability problem]], [[protein structure prediction]], and [[job-shop scheduling]]). For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to exact algorithms such as [[gradient descent]] or [[branch and bound]]. 

The name of the algorithm comes from [[annealing (metallurgy)|annealing in metallurgy]], a technique involving heating and controlled cooling of a material to alter its [[physical properties]]. Both are attributes of the material that depend on their [[thermodynamic free energy]]. Heating and cooling the material affects both the temperature and the thermodynamic free energy or [[Gibbs energy]].
Simulated annealing can be used for very hard computational optimization problems where exact algorithms fail; even though it usually only achieves an approximate solution to the global minimum, this is sufficient for many practical problems.

The problems solved by SA are currently formulated by an [[objective function]] of many variables, subject to several [[mathematical constraints]]. In practice, the constraint can be penalized as part of the objective function.

Similar techniques have been independently introduced on several occasions, including Pincus (1970),<ref>{{Cite journal|last=Pincus|first=Martin|date=Nov–Dec 1970|title=A Monte-Carlo Method for the Approximate Solution of Certain Types of Constrained Optimization Problems|journal=Journal of the Operations Research Society of America|volume=18|issue=6|pages=967–1235|doi=10.1287/opre.18.6.1225|doi-access=}}</ref> Khachaturyan et al (1979,<ref>{{Cite journal|last=Khachaturyan, A.: Semenovskaya, S.: Vainshtein B.|first=Armen|date=1979|title=Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases|journal=Soviet Physics Crystallography|volume=24|issue=5|pages=519–524}}</ref> 1981<ref>{{Cite journal|last=Khachaturyan, A.; Semenovskaya, S.; Vainshtein, B.|date=1981|title=The Thermodynamic Approach to the Structure Analysis of Crystals|url=http://scripts.iucr.org/cgi-bin/paper?S0567739481001630|journal=Acta Crystallographica|volume=A37|issue=5|pages=742–754|doi=10.1107/S0567739481001630|bibcode=1981AcCrA..37..742K|url-access=subscription}}</ref>), Kirkpatrick, Gelatt and Vecchi (1983), and Cerny (1985).<ref>{{Cite book|last=Laarhoven, P. J. M. van (Peter J. M.)|url=https://www.worldcat.org/oclc/15548651|title=Simulated annealing : theory and applications|date=1987|publisher=D. Reidel|others=Aarts, E. H. L. (Emile H. L.)|isbn=90-277-2513-6|location=Dordrecht|oclc=15548651}}</ref> In 1983, this approach was used by Kirkpatrick, Gelatt Jr., and Vecchi<ref name=":2" /> for a solution of the [[traveling salesman problem]]. They also proposed its current name, simulated annealing.

This notion of slow cooling implemented in the simulated annealing algorithm is interpreted as a slow decrease in the probability of accepting worse solutions as the solution space is explored. Accepting worse solutions allows for a more extensive search for the global optimal solution. In general, simulated annealing algorithms work as follows. The temperature progressively decreases from an initial positive value to zero. At each time step, the algorithm randomly selects a solution close to the current one, measures its quality, and moves to it according to the temperature-dependent probabilities of selecting better or worse solutions, which during the search respectively remain at 1 (or positive) and decrease toward zero.

The simulation can be performed either by a solution of [[kinetic equations]] for [[probability density functions]],<ref name=":0">{{cite journal |pages=519–524 |last1=Khachaturyan |first1=A. |last2=Semenovskaya |first2=S. |last3=Vainshtein |first3=B. |title=Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases |journal=Sov.Phys. Crystallography |year=1979 |volume=24 |issue=5 }}</ref><ref name=":1">{{cite journal |pages=742–754 |last1=Khachaturyan |first1=A. |last2=Semenovskaya |first2=S. |last3=Vainshtein |first3=B. |title=The Thermodynamic Approach to the Structure Analysis of Crystals |issue=A37 |journal=Acta Crystallographica |volume=37 |year=1981 |doi=10.1107/S0567739481001630|bibcode=1981AcCrA..37..742K }}</ref> or by using a [[stochastic]] sampling method.<ref name=":2">{{cite journal |jstor=1690046 |pages=671–680 |last1=Kirkpatrick |first1=S. |last2=Gelatt Jr |first2=C. D. |last3=Vecchi |first3=M. P. |title=Optimization by Simulated Annealing |volume=220 |issue=4598 |journal=Science |year=1983 |pmid=17813860 |doi=10.1126/science.220.4598.671|bibcode=1983Sci...220..671K |citeseerx=10.1.1.123.7607 |s2cid=205939 }}</ref><ref>{{cite journal |doi=10.1007/BF00940812 |title=Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm |year=1985 |last1=Černý |first1=V. |journal=Journal of Optimization Theory and Applications |volume=45 |pages=41–51|s2cid=122729427 }}</ref> The method is an adaptation of the [[Metropolis–Hastings algorithm]], a [[Monte Carlo method]] to generate sample states of a thermodynamic system, published by [[N. Metropolis]] et al. in 1953.<ref name=":4">{{cite journal |doi=10.1063/1.1699114 |title=Equation of State Calculations by Fast Computing Machines |year=1953 |last1=Metropolis |first1=Nicholas |last2=Rosenbluth |first2=Arianna W. |last3=Rosenbluth |first3=Marshall N. |last4=Teller |first4=Augusta H. |last5=Teller |first5=Edward |journal=The Journal of Chemical Physics |volume=21 |issue=6 |pages=1087|bibcode=1953JChPh..21.1087M |osti=4390578 |s2cid=1046577 }}</ref>