You do not have permission to edit this page, for the following reasons:

This IP address has been blocked from editing Wikipedia.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

The IP address or range 52.91.0.0/16 has been blocked (disabled) by ‪JJMC89‬ for the following reason(s):

The IP address that you are currently using has been blocked because it is believed to be a web host provider or colocation provider. To prevent abuse, web hosts and colocation providers may be blocked from editing Wikipedia.
You will not be able to edit Wikipedia using a web host or colocation provider because it hides your IP address, much like a proxy or VPN.
We recommend that you attempt to use another connection to edit. For example, if you use a proxy or VPN to connect to the internet, turn it off when editing Wikipedia. If you edit using a mobile connection, try using a Wi-Fi connection, and vice versa. If you are using a corporate internet connection, switch to a different Wi-Fi network. If you have a Wikipedia account, please log in.
If you do not have any other way to edit Wikipedia, you will need to request an IP block exemption.

How to appeal if you are confident that your connection does not use a colocation provider's IP address:
If you are confident that you are not using a web host, you may appeal this block by adding the following text on your talk page: ((unblock|reason=Caught by a colocation web host block but this host or IP is not a web host. My IP address is _______. Place any further information here. ~~~~)). You must fill in the blank with your IP address for this block to be investigated. Your IP address can be determined here. Alternatively, if you wish to keep your IP address private you can use the unblock ticket request system. There are several reasons you might be editing using the IP address of a web host or colocation provider (such as if you are using VPN software or a business network); please use this method of appeal only if you think your IP address is in fact not a web host or colocation provider.

Administrators: The IP block exemption user right should only be applied to allow users to edit using web host in exceptional circumstances, and requests should usually be directed to the functionaries team via email. If you intend to give the IPBE user right, a CheckUser needs to take a look at the account. This can be requested most easily at SPI Quick Checkuser Requests. Unblocking an IP or IP range with this template is highly discouraged without at least contacting the blocking administrator.

This block will expire on 05:26, 2 September 2024.

Even when blocked, you will usually still be able to edit your user talk page, as well as email administrators and other editors.

For information on how to proceed, please read the FAQ for blocked users and the guideline on block appeals. The guide to appealing blocks may also be helpful.

Other useful links: Blocking policy · Help:I have been blocked
Your IP address is in a range that has been blocked on all Wikimedia Foundation wikis. The block was made by ‪Jon Kolbert‬. The reason given is Open proxy/Webhost: See the help page if you are affected .
- Start of block: 04:57, 27 November 2021
- Expiry of block: 04:57, 27 November 2024
Your current IP address is 52.91.194.66. The blocked range is 52.91.0.0/16. Please include all above details in any queries you make. If you believe you were blocked by mistake, you can find additional information and instructions in the No open proxies global policy. Otherwise, to discuss the block please post a request for review on Meta-Wiki. You could also send an email to the stewards VRT queue at stewards@wikimedia.org including all above details.

You can view and copy the source of this page:

((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 optima.<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|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 achieves an approximate solution to the global minimum, it could be enough 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))</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., 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 [[Nicholas Metropolis|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>

==Overview==
The [[thermodynamic state|state]] ''s'' of some [[physical system]]s, and the function ''E''(''s'') to be minimized, is analogous to the [[internal energy]] of the system in that state. The goal is to bring the system, from an arbitrary ''initial state'', to a state with the minimum possible energy.

[[File:Hill Climbing with Simulated Annealing.gif|center|thumb|Simulated annealing searching for a maximum. The objective here is to get to the highest point. In this example, it is not enough to use a simple [[hill climbing|hill climb algorithm]], as there are many [[Hill climbing algorithm#Local maxima|local maxima]]. By cooling the temperature slowly the global maximum is found.|500px]]

===The basic iteration===
At each step, the simulated annealing heuristic considers some neighboring state ''s*'' of the current state ''s'', and [[probabilistic]]ally decides between moving the system to state ''s*'' or staying in-state ''s''.  These probabilities ultimately lead the system to move to states of lower energy.  Typically this step is repeated until the system reaches a state that is good enough for the application, or until a given computation budget has been exhausted.

===The neighbors of a state===
Optimization of a solution involves evaluating the neighbors of a state of the problem, which are new states produced through conservatively altering a given state. For example, in the [[traveling salesman problem]] each state is typically defined as a [[permutation]] of the cities to be visited, and the neighbors of any state are the set of permutations produced by swapping any two of these cities. The well-defined way in which the states are altered to produce neighboring states is called a "move", and different moves give different sets of neighboring states. These moves usually result in minimal alterations of the last state, in an attempt to progressively improve the solution through iteratively improving its parts (such as the city connections in the traveling salesman problem).

Simple [[heuristic]]s like [[hill climbing]], which move by finding better neighbor after better neighbor and stop when they have reached a solution which has no neighbors that are better solutions, cannot guarantee to lead to any of the existing better solutions((snd)) their outcome may easily be just a [[local optimum]], while the actual best solution would be a [[global optimum]] that could be different. [[Metaheuristic]]s use the neighbors of a solution as a way to explore the solution space, and although they prefer better neighbors, they also accept worse neighbors in order to avoid getting stuck in local optima; they can find the global optimum if run for a long enough amount of time.

===Acceptance probabilities===
The probability of making the [[state transition|transition]] from the current state <math>s</math> to a candidate new state <math>s_\mathrm{new}</math> is specified by an ''acceptance probability function'' <math>P(e, e_\mathrm{new}, T)</math>, that depends on the energies <math>e = E(s)</math> and <math>e_\mathrm{new}= E(s_\mathrm{new})</math> of the two states, and on a global time-varying parameter <math>T</math> called the ''temperature''.  States with a smaller energy are better than those with a greater energy.  The probability function <math>P</math> must be positive even when <math>e_\mathrm{new}</math> is greater than <math>e</math>.  This feature prevents the method from becoming stuck at a local minimum that is worse than the global one.

When <math>T</math> tends to zero, the probability <math>P(e, e_\mathrm{new}, T)</math> must tend to zero if <math>e_\mathrm{new} > e</math> and to a positive value otherwise. For sufficiently small values of <math>T</math>, the system will then increasingly favor moves that go "downhill" (i.e., to lower energy values), and avoid those that go "uphill."  With <math>T=0</math> the procedure reduces to the [[greedy algorithm]], which makes only the downhill transitions.

In the original description of simulated annealing, the probability <math>P(e, e_\mathrm{new}, T)</math> was equal to 1 when <math>e_\mathrm{new} < e</math>—i.e., the procedure always moved downhill when it found a way to do so, irrespective of the temperature.  Many descriptions and implementations of simulated annealing still take this condition as part of the method's definition.  However, this condition is not essential for the method to work.

The <math>P</math> function is usually chosen so that the probability of accepting a move decreases when the difference
<math>e_\mathrm{new}-e</math> increases—that is, small uphill moves are more likely than large ones.  However, this requirement is not strictly necessary, provided that the above requirements are met.

Given these properties, the temperature <math>T</math> plays a crucial role in controlling the evolution of the state <math>s</math> of the system with regard to its sensitivity to the variations of system energies. To be precise, for a large <math>T</math>, the evolution of <math>s</math> is sensitive to coarser energy variations, while it is sensitive to finer energy variations when <math>T</math> is small.

===The annealing schedule===
((multiple image
 | align = right
 | total_width = 400
 | image_gap = 1

 | image1 = SimulatedAnnealingFast.jpg
 | alt1 = Fast
 | caption1 = Fast

 | image2 = SimulatedAnnealingSlow.jpg
 | alt2 = Slow
 | caption2 = Slow

| footer= Example illustrating the effect of cooling schedule on the performance of simulated annealing.  The problem is to rearrange the [[pixel]]s of an image so as to minimize a certain [[potential energy]] function, which causes similar [[color]]s to attract at short range and repel at a slightly larger distance.  The elementary moves swap two adjacent pixels.  These images were obtained with a fast cooling schedule (left) and a slow cooling schedule (right), producing results similar to [[amorphous solid|amorphous]] and [[crystalline solid]]s, respectively.
))
The name and inspiration of the algorithm demand an interesting feature related to the temperature variation to be embedded in the operational characteristics of the algorithm. This necessitates a gradual reduction of the temperature as the simulation proceeds. The algorithm starts initially with <math>T</math> set to a high value (or infinity), and then it is decreased at each step following some ''annealing schedule''—which may be specified by the user but must end with <math>T=0</math> towards the end of the allotted time budget.  In this way, the system is expected to wander initially towards a broad region of the search space containing good solutions, ignoring small features of the energy function; then drift towards low-energy regions that become narrower and narrower, and finally move downhill according to the [[steepest descent]] heuristic.

For any given finite problem, the probability that the simulated annealing algorithm terminates with a [[global optimum|global optimal]] solution approaches 1 as the annealing schedule is extended.<ref>((cite journal |doi=10.1109/34.295910 |title=Simulated annealing: A proof of convergence |year=1994 |last1=Granville |first1=V. |last2=Krivanek |first2=M. |last3=Rasson |first3=J.-P. |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=16 |issue=6 |pages=652–656))</ref> This theoretical result, however, is not particularly helpful, since the time required to ensure a significant probability of success will usually exceed the time required for a [[Brute-force search|complete search]] of the [[solution space]].<ref>((Citation |last1=Nolte |first1=Andreas |title=A Note on the Finite Time Behaviour of Simulated Annealing |date=1997 |url=http://link.springer.com/10.1007/978-3-642-60744-8_32 |work=Operations Research Proceedings 1996 |volume=1996 |pages=175–180 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/978-3-642-60744-8_32 |isbn=978-3-540-62630-5 |access-date=2023-02-06 |last2=Schrader |first2=Rainer))</ref>

==Pseudocode==
The following pseudocode presents the simulated annealing heuristic as described above. It starts from a state ((math|''s''<sub>0</sub>)) and continues until a maximum of ((math|''k''<sub>max</sub>)) steps have been taken. In the process, the call ((math|neighbour(''s''))) should generate a randomly chosen neighbour of a given state ((mvar|s)); the call ((math|random(0, 1))) should pick and return a value in the range ((math|[0, 1])), [[Uniform distribution (continuous)|uniformly at random]]. The annealing schedule is defined by the call ((math|temperature(''r''))), which should yield the temperature to use, given the fraction ((mvar|r)) of the time budget that has been expended so far.

<div style="margin-left: 35px; width: 600px">
((framebox|blue))
* Let ((math|''s'' ((=)) ''s''<sub>0</sub>))
* For ((math|''k'' ((=)) 0)) through ((math|''k''<sub>max</sub>)) (exclusive):
** ((math|''T'' ← temperature( 1 - ''(k+''1'')''/''k''<sub>max</sub> )))
** Pick a random neighbour, ((math|''s''<sub>new</sub> ← neighbour(''s'')))
** If ((math|''P''(''E''(''s''), ''E''(''s''<sub>new</sub>), ''T'') ≥ random(0, 1))):
*** ((math|''s'' ← ''s''<sub>new</sub>))
* Output: the final state ((mvar|s))
((frame-footer))
</div>

==Selecting the parameters==
In order to apply the simulated annealing method to a specific problem, one must specify the following parameters: the state space, the energy (goal) function ((code|E())), the candidate generator procedure ((code| neighbor ())), the acceptance probability function ((code|P())), and the annealing schedule ((code|temperature())) AND initial temperature ((code|init_temp)). These choices can have a significant impact on the method's effectiveness.  Unfortunately, there are no choices of these parameters that will be good for all problems, and there is no general way to find the best choices for a given problem.  The following sections give some general guidelines.

===Sufficiently near neighbour===
Simulated annealing may be modeled as a random walk on a search graph, whose vertices are all possible states, and whose edges are the candidate moves. An essential requirement for the ((code| neighbor ())) function is that it must provide a sufficiently short path on this graph from the initial state to any state which may be the global optimum((snd)) the diameter of the search graph must be small. In the traveling salesman example above, for instance, the search space for n = 20 cities has n! = 2,432,902,008,176,640,000 (2.4 quintillion) states; yet the number of neighbors of each vertex is <math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math> edges (coming from n choose 20), and the diameter of the graph is <math>n-1</math>.

===Transition probabilities===
To investigate the behavior of simulated annealing on a particular problem, it can be useful to consider the ''transition probabilities'' that result from the various design choices made in the implementation of the algorithm.  For each edge <math>(s,s')</math> of the search graph, the transition probability is defined as the probability that the simulated annealing algorithm will move to state  <math>s'</math> when its current state is <math>s</math>.  This probability depends on the current temperature as specified by ((code|temperature())), on the order in which the candidate moves are generated by the ((code| neighbor ())) function, and on the acceptance probability function ((code|P())). (Note that the transition probability is '''not''' simply <math>P(e, e', T)</math>, because the candidates are tested serially.)

===Acceptance probabilities===
The specification of ((code|neighbour())), ((code|P())), and ((code|temperature())) is partially redundant.  In practice, it's common to use the same acceptance function ((code|P())) for many problems and adjust the other two functions according to the specific problem.

In the formulation of the method by Kirkpatrick et al., the acceptance probability function <math>P(e, e', T)</math> was defined as 1 if <math>e' < e</math>, and <math>\exp(-(e'-e)/T)</math> otherwise. This formula was superficially justified by analogy with the transitions of a physical system; it corresponds to the [[Metropolis–Hastings algorithm]], in the case where T=1 and the proposal distribution of Metropolis–Hastings is symmetric. However, this acceptance probability is often used for simulated annealing even when the ((code| neighbor ())) function, which is analogous to the proposal distribution in Metropolis–Hastings, is not symmetric, or not probabilistic at all. As a result, the transition probabilities of the simulated annealing algorithm do not correspond to the transitions of the analogous physical system, and the long-term distribution of states at a constant temperature <math>T</math> need not bear any resemblance to the thermodynamic equilibrium distribution over states of that physical system, at any temperature. Nevertheless, most descriptions of simulated annealing assume the original acceptance function, which is probably hard-coded in many implementations of SA.

In 1990, Moscato and Fontanari,<ref>((citation |journal=Physics Letters A |pages= 204–208 |last1=Moscato |first1=P. |last2=Fontanari |first2=J.F.| title=Stochastic versus deterministic update in simulated annealing |volume=146 |issue=4 |year=1990|doi=10.1016/0375-9601(90)90166-L|bibcode= 1990PhLA..146..204M ))</ref> and independently Dueck and Scheuer,<ref>((citation |journal=Journal of Computational Physics| pages=161–175 | last1=Dueck |first1=G.| last2=Scheuer| first2=T.| title=Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing| volume=90 | issue=1 | year=1990 | issn=0021-9991 | 
doi=10.1016/0021-9991(90)90201-B| bibcode=1990JCoPh..90..161D ))</ref> proposed that a deterministic update (i.e. one that is not based on the probabilistic acceptance rule) could speed-up the optimization process without impacting on the final quality. Moscato and Fontanari conclude from observing the analogous of the "specific heat" curve of the "threshold updating" annealing originating from their study that "the stochasticity of the Metropolis updating in the simulated annealing algorithm does not play a major role in the search of near-optimal minima". Instead, they proposed that "the smoothening of the cost function landscape at high temperature and the gradual definition of the minima during the cooling process are the fundamental ingredients for the success of simulated annealing." The method subsequently popularized under the denomination of "threshold accepting" due to Dueck and Scheuer's denomination. In 2001, Franz, Hoffmann and Salamon showed that the deterministic update strategy is indeed the optimal one within the large class of algorithms that simulate a random walk on the cost/energy landscape.<ref>((citation |journal=Physical Review Letters| pages=5219–5222 | volume=86 | issue=3 | title= Best optimal strategy for finding ground states | last1=Franz | first1=A. | last2=Hoffmann | first2=K.H. | last3=Salamon | first3= P | doi=10.1103/PhysRevLett.86.5219 | year=2001| pmid=11384462 ))</ref>

===Efficient candidate generation===
When choosing the candidate generator ((code| neighbor ())), one must consider that after a few iterations of the simulated annealing algorithm, the current state is expected to have much lower energy than a random state. Therefore, as a general rule, one should skew the generator towards candidate moves where the energy of the destination state <math>s'</math> is likely to be similar to that of the current state. This [[heuristic]] (which is the main principle of the [[Metropolis–Hastings algorithm]]) tends to exclude ''very good'' candidate moves as well as ''very bad'' ones; however, the former are usually much less common than the latter, so the heuristic is generally quite effective.

In the traveling salesman problem above, for example, swapping two ''consecutive'' cities in a low-energy tour is expected to have a modest effect on its energy (length); whereas swapping two ''arbitrary'' cities is far more likely to increase its length than to decrease it. Thus, the consecutive-swap neighbor generator is expected to perform better than the arbitrary-swap one, even though the latter could provide a somewhat shorter path to the optimum (with <math>n-1</math> swaps, instead of <math>n(n-1)/2</math>).

A more precise statement of the heuristic is that one should try the first candidate states <math>s'</math> for which <math>P(E(s), E(s'), T)</math> is large. For the "standard" acceptance function <math>P</math> above, it means that <math>E(s') - E(s)</math> is on the order of <math>T</math> or less. Thus, in the traveling salesman example above, one could use a ((code| neighbor ())) function that swaps two random cities, where the probability of choosing a city-pair vanishes as their distance increases beyond <math>T</math>.

===Barrier avoidance===
When choosing the candidate generator ((code| neighbor ())) one must also try to reduce the number of "deep" local minima—states (or sets of connected states) that have much lower energy than all its neighboring states. Such "closed [[drainage basin|catchment]] basins" of the energy function may trap the simulated annealing algorithm with high probability (roughly proportional to the number of states in the basin) and for a very long time (roughly exponential on the energy difference between the surrounding states and the bottom of the basin).

As a rule, it is impossible to design a candidate generator that will satisfy this goal and also prioritize candidates with similar energy. On the other hand, one can often vastly improve the efficiency of simulated annealing by relatively simple changes to the generator. In the traveling salesman problem, for instance, it is not hard to exhibit two tours <math>A</math>, <math>B</math>, with nearly equal lengths, such that (1) <math>A</math> is optimal, (2) every sequence of city-pair swaps that converts <math>A</math> to <math>B</math> goes through tours that are much longer than both, and (3) <math>A</math> can be transformed into <math>B</math> by flipping (reversing the order of) a set of consecutive cities. In this example, <math>A</math> and <math>B</math> lie in different "deep basins" if the generator performs only random pair-swaps; but they will be in the same basin if the generator performs random segment-flips.

===Cooling schedule===
The physical analogy that is used to justify simulated annealing assumes that the cooling rate is low enough for the probability distribution of the current state to be near [[thermodynamic equilibrium]] at all times.  Unfortunately, the ''relaxation time''—the time one must wait for the equilibrium to be restored after a change in temperature—strongly depends on the "topography" of the energy function and on the current temperature.  In the simulated annealing algorithm, the relaxation time also depends on the candidate generator, in a very complicated way.  Note that all these parameters are usually provided as [[procedural parameter|black box functions]] to the simulated annealing algorithm. Therefore, the ideal cooling rate cannot be determined beforehand and should be empirically adjusted for each problem. [[Adaptive simulated annealing]] algorithms address this problem by connecting the cooling schedule to the search progress. Other adaptive approaches such as Thermodynamic Simulated Annealing,<ref>((cite journal |doi=10.1016/j.physleta.2003.08.070 |title=Placement by thermodynamic simulated annealing |year=2003 |last1=De Vicente |first1=Juan |last2=Lanchares |first2=Juan |last3=Hermida |first3=Román |journal=Physics Letters A |volume=317 |issue=5–6 |pages=415–423|bibcode=2003PhLA..317..415D ))</ref> automatically adjusts the temperature at each step based on the energy difference between the two states, according to the laws of thermodynamics.

==Restarts==
Sometimes it is better to move back to a solution that was significantly better rather than always moving from the current state.  This process is called ''restarting'' of simulated annealing.  To do this we set <code>s</code> and <code>e</code> to <code>sbest</code> and <code>ebest</code> and perhaps restart the annealing schedule.  The decision to restart could be based on several criteria. Notable among these include restarting based on a fixed number of steps, based on whether the current energy is too high compared to the best energy obtained so far, restarting randomly, etc.

==Related methods==
* [[Metropolis–Hastings algorithm|Interacting Metropolis–Hasting algorithms]] (a.k.a. [[Sequential Monte Carlo method|sequential Monte Carlo]]<ref name=":3">((Cite journal|title = Sequential Monte Carlo samplers| doi=10.1111/j.1467-9868.2006.00553.x|volume=68| issue=3|journal=Journal of the Royal Statistical Society, Series B|pages=411–436|arxiv=cond-mat/0212648|year = 2006|last1 = Del Moral|first1 = Pierre| last2=Doucet| first2=Arnaud| last3=Jasra| first3=Ajay| s2cid=12074789))</ref>) combines simulated annealing moves with an acceptance-rejection of the best-fitted individuals equipped with an interacting recycling mechanism.
* [[Quantum annealing]] uses "quantum fluctuations" instead of thermal fluctuations to get through high but thin barriers in the target function.
* [[Stochastic tunneling]] attempts to overcome the increasing difficulty simulated annealing runs have in escaping from local minima as the temperature decreases, by 'tunneling' through barriers.
* [[Tabu search]] normally moves to neighbouring states of lower energy, but will take uphill moves when it finds itself stuck in a local minimum; and avoids cycles by keeping a "taboo list" of solutions already seen.
* [[Dual-phase evolution]] is a family of algorithms and processes (to which simulated annealing belongs) that mediate between local and global search by exploiting phase changes in the search space.
* [[LIONsolver|Reactive search optimization]] focuses on combining machine learning with optimization, by adding an internal feedback loop to self-tune the free parameters of an algorithm to the characteristics of the problem, of the instance, and of the local situation around the current solution.
* [[Genetic algorithms]] maintain a pool of solutions rather than just one. New candidate solutions are generated not only by "mutation" (as in SA), but also by "recombination" of two solutions from the pool. Probabilistic criteria, similar to those used in SA, are used to select the candidates for mutation or combination, and for discarding excess solutions from the pool.
* [[Memetic algorithms]] search for solutions by employing a set of agents that both cooperate and compete in the process; sometimes the agents' strategies involve simulated annealing procedures for obtaining high-quality solutions before recombining them.<ref>((cite journal |last1=Moscato |first1=Pablo |title=An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search |journal=Annals of Operations Research |date=June 1993 |volume=41 |issue=2 |pages=85–121 |doi=10.1007/BF02022564 |s2cid=35382644 ))</ref> Annealing has also been suggested as a mechanism for increasing the diversity of the search.<ref name=martial_arts>((cite journal|last=Moscato|first=P.|year=1989|title=On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms|journal=Caltech Concurrent Computation Program|issue=report 826))</ref> 
* [[Graduated optimization]] digressively "smooths" the target function while optimizing.
* [[Ant colony optimization]] (ACO) uses many ants (or agents) to traverse the solution space and find locally productive areas.
* The [[cross-entropy method]] (CE) generates candidate solutions via a parameterized probability distribution. The parameters are updated via cross-entropy minimization, so as to generate better samples in the next iteration.
* [[Harmony search]] mimics musicians in improvisation where each musician plays a note to find the best harmony together.
* [[Stochastic optimization]] is an umbrella set of methods that includes simulated annealing and numerous other approaches.
* [[Particle swarm optimization]] is an algorithm modeled on swarm intelligence that finds a solution to an optimization problem in a search space, or models and predicts social behavior in the presence of objectives.
* The [[runner-root algorithm]] (RRA) is a [[Metaheuristic|meta-heuristic]] optimization algorithm for solving unimodal and multimodal problems inspired by the runners and roots of plants in nature.
* [[Intelligent water drops algorithm]] (IWD) which mimics the behavior of natural water drops to solve optimization problems
* [[Parallel tempering]] is a simulation of model copies at different temperatures (or [[Hamiltonian (quantum mechanics)|Hamiltonian]]s) to overcome the potential barriers.
* Multi-objective simulated annealing algorithms have been used in [[multi-objective optimization]].<ref>((cite journal |last1=Deb |first1=Bandyopadhyay |title=A Simulated Annealing-Based Multiobjective Optimization Algorithm: AMOSA |journal=IEEE Transactions on Evolutionary Computation|date=June 2008 |volume=12 |issue=3 |pages=269–283 |doi=10.1109/TEVC.2007.900837 |s2cid=12107321 ))</ref>

==See also==
((columns-list|colwidth=30em|
* [[Adaptive simulated annealing]]
* [[Automatic label placement]]
* [[Combinatorial optimization]]
* [[Dual-phase evolution]]
* [[Graph cuts in computer vision]]
* [[Intelligent water drops algorithm]]
* [[Markov chain]]
* [[Molecular dynamics]]
* [[Multidisciplinary optimization]]
* [[Particle swarm optimization]]
* [[Place and route]]
* [[Quantum annealing]]
* [[Traveling salesman problem]]
))

==References==
((Reflist))

==Further reading==
*A. Das and B. K. Chakrabarti (Eds.), ''[ftp://nozdr.ru/biblio/kolxoz/M/MP/Das%20A.,%20Chakrabarti%20B.K.%20(eds.)%20Quantum%20Annealing%20and%20Related%20Optimization%20Methods%20(LNP0679,%20Springer,%202005)(384s)_MP_.pdf Quantum Annealing and Related Optimization Methods]((Dead link|date=March 2024 |bot=InternetArchiveBot |fix-attempted=yes )),'' Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)
*((cite journal |doi=10.1007/BF00202749 |title=Correlated and uncorrelated fitness landscapes and how to tell the difference |year=1990 |last1=Weinberger |first1=E. |journal=Biological Cybernetics |volume=63 |issue=5 |pages=325–336|s2cid=851736 ))
*((Cite book | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | location=New York | isbn=978-0-521-88068-8 | chapter=Section 10.12. Simulated Annealing Methods | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=549 | access-date=2011-08-13 | archive-date=2011-08-11 | archive-url=https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=549 | url-status=dead ))
*((cite journal |doi=10.1016/j.ympev.2016.05.001 |title=On simulated annealing phase transitions in phylogeny reconstruction |year=2016 |last1=Strobl |first1=M.A.R. |last2=Barker |first2=D. |journal=Molecular Phylogenetics and Evolution |volume=101 |pages=46–55 |pmid=27150349 |pmc=4912009))
*V.Vassilev, A.Prahova: "The Use of Simulated Annealing in the Control of Flexible Manufacturing Systems", International Journal INFORMATION THEORIES & APPLICATIONS, [http://www.foibg.com/ijita/vol01-09/ijita-fv06.htm VOLUME 6/1999]

==External links==
* [http://www.heatonresearch.com/aifh/vol1/tsp_anneal.html Simulated Annealing] A Javascript app that allows you to experiment with simulated annealing. Source code included.
* [http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=10548&objectType=file "General Simulated Annealing Algorithm"] ((Webarchive|url=https://web.archive.org/web/20080923163834/http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=10548&objectType=file |date=2008-09-23 )) An open-source MATLAB program for general simulated annealing exercises.
* [[Wikiversity:Simulated Annealing Project|Self-Guided Lesson on Simulated Annealing]] A Wikiversity project.
* [https://arstechnica.com/science/news/2009/12/uncertainty-hovers-over-claim-googles-using-quantum-computer.ars Google in superposition of using, not using quantum computer] Ars Technica discusses the possibility that the D-Wave computer being used by Google may, in fact, be an efficient simulated annealing co-processor.
* [https://ieeexplore.ieee.org/document/4358775] A Simulated Annealing-Based Multiobjective Optimization Algorithm: AMOSA.

((Major subfields of optimization))

((DEFAULTSORT:Simulated Annealing))
[[Category:Metaheuristics]]
[[Category:Optimization algorithms and methods]]
[[Category:Monte Carlo methods]]

Pages transcluded onto the current version of this page (help):

Simulated annealing (edit)
Template:Ambox (view source) (template editor protected)
Template:Category handler (view source) (protected)
Template:Citation (view source) (protected)
Template:Cite book (view source) (protected)
Template:Cite journal (view source) (protected)
Template:Cite web (view source) (protected)
Template:Code (view source) (template editor protected)
Template:Columns-list (view source) (template editor protected)
Template:DMCA (view source) (template editor protected)
Template:Dated maintenance category (view source) (template editor protected)
Template:Dated maintenance category (articles) (view source) (template editor protected)
Template:Dead link (view source) (template editor protected)
Template:Div col (view source) (template editor protected)
Template:Div col/styles.css (view source) (template editor protected)
Template:FULLROOTPAGENAME (view source) (template editor protected)
Template:Find sources mainspace (view source) (template editor protected)
Template:Fix (view source) (protected)
Template:Fix/category (view source) (protected)
Template:Frame-footer (view source) (semi-protected)
Template:Framebox (view source) (semi-protected)
Template:Hlist/styles.css (view source) (protected)
Template:Main other (view source) (protected)
Template:Major subfields of optimization (edit)
Template:Math (view source) (template editor protected)
Template:More citations needed (view source) (template editor protected)
Template:Multiple image (view source) (template editor protected)
Template:Multiple image/styles.css (view source) (template editor protected)
Template:Mvar (view source) (template editor protected)
Template:Navbox (view source) (template editor protected)
Template:Ns has subpages (view source) (protected)
Template:Other uses (view source) (template editor protected)
Template:Pagetype (view source) (protected)
Template:Reflist (view source) (protected)
Template:Reflist/styles.css (view source) (protected)
Template:SDcat (view source) (protected)
Template:Short description (view source) (protected)
Template:Short description/lowercasecheck (view source) (protected)
Template:Snd (view source) (template editor protected)
Template:Spaced en dash (view source) (template editor protected)
Template:Use American English (view source) (template editor protected)
Template:Webarchive (view source) (template editor protected)
Module:Arguments (view source) (protected)
Module:Category handler (view source) (protected)
Module:Category handler/blacklist (view source) (protected)
Module:Category handler/config (view source) (protected)
Module:Category handler/data (view source) (protected)
Module:Category handler/shared (view source) (protected)
Module:Check for unknown parameters (view source) (protected)
Module:Citation/CS1 (view source) (protected)
Module:Citation/CS1/COinS (view source) (protected)
Module:Citation/CS1/Configuration (view source) (protected)
Module:Citation/CS1/Date validation (view source) (protected)
Module:Citation/CS1/Identifiers (view source) (protected)
Module:Citation/CS1/Utilities (view source) (protected)
Module:Citation/CS1/Whitelist (view source) (protected)
Module:Citation/CS1/styles.css (view source) (protected)
Module:Disambiguation/templates (view source) (protected)
Module:Find sources (view source) (template editor protected)
Module:Find sources/config (view source) (template editor protected)
Module:Find sources/links (view source) (template editor protected)
Module:Find sources/templates/Find sources mainspace (view source) (template editor protected)
Module:Format link (view source) (template editor protected)
Module:Hatnote (view source) (template editor protected)
Module:Hatnote/styles.css (view source) (template editor protected)
Module:Hatnote list (view source) (template editor protected)
Module:Message box (view source) (protected)
Module:Message box/ambox.css (view source) (protected)
Module:Message box/configuration (view source) (protected)
Module:Multiple image (view source) (template editor protected)
Module:Namespace detect/config (view source) (protected)
Module:Namespace detect/data (view source) (protected)
Module:Navbar (view source) (protected)
Module:Navbar/configuration (view source) (protected)
Module:Navbar/styles.css (view source) (protected)
Module:Navbox (view source) (template editor protected)
Module:Navbox/configuration (view source) (template editor protected)
Module:Navbox/styles.css (view source) (template editor protected)
Module:Ns has subpages (view source) (protected)
Module:Other uses (view source) (template editor protected)
Module:Pagetype (view source) (protected)
Module:Pagetype/config (view source) (protected)
Module:Pagetype/disambiguation (view source) (protected)
Module:Pagetype/setindex (view source) (protected)
Module:Pagetype/softredirect (view source) (protected)
Module:SDcat (view source) (protected)
Module:String (view source) (protected)
Module:TableTools (view source) (protected)
Module:Template wrapper (view source) (template editor protected)
Module:Unsubst (view source) (protected)
Module:Webarchive (view source) (template editor protected)
Module:Webarchive/data (view source) (template editor protected)
Module:Wikitext Parsing (view source) (protected)
Module:Yesno (view source) (protected)

Return to Simulated annealing.

Retrieved from "https://en.wikipedia.org/wiki/Simulated_annealing"