Editing Simulated annealing (section)

===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|neighbour()}} 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>