模拟退火算法可用于求解组合问题。此处将模拟退火算法应用于求解旅行商问题 ，求出连接125个点的最小路线长度 使用模拟退火算法求解120个点的三维旅行商问题 模擬退火 （英語：Simulated annealing ，缩写作SA）是一種逼近给定函数 全局最优 的通用概率演算法 ，具体来说，它是一种元启发算法 ，常用來在一定時間內，尋找在一個很大搜尋空間 中的近似全局最優 解。在有大量局部最优解时，模拟退火算法可以找到全局最优解。[ 1] 旅行推销员问题 、布尔可满足性问题 、蛋白质结构预测 、作业车间调度问题 等）。对于在固定时间内找到近似全局最优优先于找到精确局部最优的问题，模拟退火算法可能优于梯度下降法 或分支定界 等精确方法。
模拟退火算法解决的问题包含多元目标函数 与若干约束 。实践中，约束可作为目标函数的一部分进行惩罚。
Pincus (1970)、[ 2] [ 3] [ 4] [ 5] 旅行推销员问题 所發明[ 6] 演算法 。
模拟退火算法中的慢冷却是指在探索解空间的过程中，接受较差解的概率会缓慢下降。接受较差解可以更广泛地搜索全局最优解。总的来说，模拟退火算法的工作原理如下：温度从初始值逐渐降低到0，每个时间步长内，算法随机选择一个与当前解接近的解，并根据与温度相关的概率选择更优的。搜索过程中，这概率会趋近于1。
可通过求解概率密度函数 的动力方程[ 7] [ 8] 随机 采样法进行模拟。[ 6] [ 9] N. Metropolis et al. (1953)发表的梅特罗波利斯-黑斯廷斯算法 的改进版，是一种生成热力学系统样本状态的蒙特卡罗方法 。[ 10]
“模拟退火”來自冶金學 术语退火 ，是將材料加熱後再經特定速率冷卻的技术，目的是增大晶粒 的體積，並且減少晶格中的缺陷，以改变材料的物理性质。材料中的原子原來會停留在使內能 有局部最小值的位置，加熱使能量變大，原子會離開原來位置，而隨機在其他位置中移動。退火冷卻時速度較慢，使得原子有較多可能可以找到內能比原先更低的位置。
模擬退火的原理也和金屬退火的原理近似：我們將熱力學的理論套用到統計學上，將搜尋空間內每一點想像成空氣內的分子；分子的能量，就是它本身的動能；而搜尋空間內的每一點，也像空氣分子一樣帶有“能量”，以表示該點對命題的合適程度。演算法先以搜尋空間內一個任意點作起始：每一步先選擇一個“鄰居”，然後再計算從現有位置到達“鄰居”的概率。
可以证明，模拟退火算法所得解依概率收敛 到全局最优解。
模拟退火法可用于精确算法失效的高难度计算优化问题，虽然通常只能获得全局最优的近似，但对很多实际问题已经足够。
物理系统 的热力学状态 s ，以及要最小化的函数
E
(
s
)
{\displaystyle E(s)}
内能 ）。目标是将系统从任意初始状态带到内能尽可能小的状态。
运用模拟退火算法搜索最大值，目标是达到最大值点。本例中，简单的爬山算法 是不够的，因为有许多局部最值。缓慢降温可以找到全局最值。
模拟退火启发式在每一步都会考虑当前状态s 的某邻态
s
∗
{\displaystyle s^{*}}
概率 决定是否移动到状态
s
∗
{\displaystyle s^{*}}
解的优化包括计算问题状态的邻域，即由保守改变现状态产生的新状态。例如，在旅行推销员问题 中，状态是待访问城市的排列 ，状态的邻域是交换任意两城市产生的排列集合。良定义的到邻态的方法称为移动，不同移动会产生不同的邻态集。
爬山算法 之类启发法 逐个寻找更好的邻态来移动，并在无更好邻态时停止，显然这很容易陷入局部最优 。元启发算法 利用解的邻域作为探索解空间的一种方式，虽然更喜欢较好的邻态，但也接受较差的邻态，以免陷入局部最优。若运行时间够长，则可以找到全局最优。
从现状态s 转移 到候选的新状态
s
n
e
w
{\displaystyle s_{\mathrm {new} }}
P
(
e
,
e
n
e
w
,
T
)
{\displaystyle P(e,e_{\mathrm {new} },T)}
e
=
E
(
s
)
,
e
n
e
w
=
E
(
s
n
e
w
)
{\displaystyle e=E(s),\ e_{\mathrm {new} }=E(s_{\mathrm {new} })}
T 。转移到能量更小的状态的概率更大。概率函数P 在
e
n
e
w
<
e
{\displaystyle e_{\mathrm {new} }<e}
T 趋近于0时，若
e
n
e
w
>
e
{\displaystyle e_{\mathrm {new} }>e}
P
(
e
,
e
n
e
w
,
T
)
{\displaystyle P(e,e_{\mathrm {new} },T)}
T ，系统会越来越倾向于“下山”（向低能值移动）而避免“上山”。
T
=
0
{\displaystyle T=0}
贪心算法 ，只进行下山转移。
在模拟退火的原始描述中，
e
n
e
w
<
e
{\displaystyle e_{\mathrm {new} }<e}
P
(
e
,
e
n
e
w
,
T
)
=
1
{\displaystyle P(e,e_{\mathrm {new} },T)=1}
P 函数通常是这样选择的：当差值
e
n
e
w
−
e
{\displaystyle e_{\mathrm {new} }-e}
鉴于这些特性，温度T 在控制系统状态s 演化方面起到关键作用，因为它对系统能量变化非常敏感。确切地说，T 的大小决定着s 演化敏感的“粒度”。
冷却时间对模拟退火性能的影响。待解决问题是重新排列一幅图像的像素，使某
势能 函数最小，它会使较近的相似颜色相互吸引，较远的则相斥，基本移动是像素交换位置。快速冷却（左）与较慢冷却（右）时，结果分别类似于
无定形体 与
晶体 。
算法名称与灵感要求嵌入一个与温度有关的有趣特征。开始时，温度T 被设为一个较大值（或无穷大），按用户指定的退火历程，每次迭代降温，但必须在一定时间预算内结束为
T
=
0
{\displaystyle T=0}
梯度下降法 启发式向下移动。
对任意给定的有限问题，随着退火历程延长，模拟退火算法以全局最优解终止的概率趋近于1。[ 11] 暴力搜索 整个解空间 的耗时。[ 12]
尋找能量
E
(
s
)
{\displaystyle E(s)}
s
{\displaystyle s}
s : = s0 ; e := E ( s ) // 设定目前状态为 s0，其能量 E(s0)
k : = 0 // 评估次数 k
while k < kmax and e > emin // 若还有时间（评估次数 k 还不到 kmax）且结果还不够好（能量 e 不够低）则：
sn : = neighbour ( s ) // 随机选取一邻近状态 sn
en : = E ( sn ) // sn 的能量为 E(sn)
if random () < P ( e , en , temp ( k / kmax )) // 决定是否移至邻近状态 sn
s : = sn ; e := en // 移至邻近状态 sn
k : = k + 1 // 评估完成，次数 k 加一
return s // 返回状态 s
下面以自然语言解说模拟退火算法的演算步骤。
由一个产生函数从当前解产生一个位于解空间的新解，并定义一个足够大的数值作为初始温度。
迭代过程是模拟退火算法的核心步骤，分为新解的产生和接受新解两部分：
由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则：若Δt′<0则接受S′作为新的当前解S，否则以概率exp（-Δt′/T）接受S′作为新的当前解S。
当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关，算法求得的解与初始解状态S（是算法迭代的起点）无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。
迭代过程的一般停止准则：温度T降低至某阈值时，或连续若干次迭代均未接受新解时，停止迭代，接受当前寻找的最优解为最终解。
在某个温度状态T下，当一定数量的迭代操作完成后，降低温度T，在新的温度状态下执行下一个批次的迭代操作。
将模拟退火算法用于实际问题，需要指定状态空间、能量（目标）函数E()、候选解生成器neighbour()、接受概率函数P()、退火历程temperature()以及初始温度init_temp。这些选择会对算法效率产生重大影响，遗憾的是它们的选择不适合所有问题，也没有针对特定问题找到最佳选择的通用方法。下面几节将给出一些通用指导。
模拟退火可建模为搜索图上的随机游走，其顶点是所有状态，边为候选的移动。neighbour()的基本要求是提供从初态到任何可能是全局最优态的足够短路径，这要求搜索图的直径足够小。以上面的旅行推销员问题为例，n = 20个城市的搜索空间有n! = 2,432,902,008,176,640,000（243亿亿）个状态，而每个顶点有
∑
k
=
1
n
−
1
k
=
n
(
n
−
1
)
2
=
190
{\displaystyle \sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}=190}
n
−
1
{\displaystyle n-1}
要研究模拟退火算法在特定问题上的行为，可考虑算法实施过程中各种设计选择产生的转移概率。对搜索图中的每条边
(
s
,
s
′
)
{\displaystyle (s,s')}
s 时转移到
s
′
{\displaystyle s'}
temperature()指定的当前温度、neighbour()生成的候选移动的顺序及接受概率函数P()（注意转移概率不是简单的
P
(
e
,
e
′
,
T
)
{\displaystyle P(e,e',T)}
neighbour()、P()、temperature()的指定是多余的，因为实践中通常会使用相同的接受函数P()，并根据具体问题调整其他函数。
在Kirkpatrick et al.的方法中，若
e
′
<
e
{\displaystyle e'<e}
P
(
e
,
e
′
,
T
)
=
1
{\displaystyle P(e,e',T)=1}
exp
(
−
(
e
′
−
e
)
/
T
)
{\displaystyle \exp(-(e'-e)/T)}
T
=
1
{\displaystyle T=1}
梅特罗波利斯-黑斯廷斯算法 。即使与梅特罗波利斯-黑斯廷斯算法中的提议分布类似的neighbour()函数不对称或根本不是概率分布，也常用于模拟退火。因此，转移概率同类似物理系统的转移概率并不对应，恒定温度T 下的长期状态分布也不必同物理系统在任何温度下的热力平衡态分布有任何相似处。尽管如此，大多数模拟退火的描述都会假定原接受函数，而这种函数可能在许多模拟退火的实现中都是硬编码（hard-coded）的。
Moscato and Fontanari (1990)[ 13] [ 14] [ 15]
选择候选生成器neighbour()时，必须考虑到算法迭代几次后，现态的能量将低于随机状态。因此一般来说，生成器应偏向更接近目标状态
s
′
{\displaystyle s'}
启发式 （也是梅特罗波利斯-黑斯廷斯算法 的主要原理）往往会排除“非常好”与“非常坏”的转移，不过前者通常更少见，所以启发式往往相当有效。
例如，在上述旅行商问题中，低能旅行中交换两连续城市对能量（总距离）影响不大，而交换两任意城市更可能增加能量。因此，连续交换优于随机交换，尽管后者能提供更优路径（
n
−
1
{\displaystyle n-1}
n
(
n
−
1
)
/
2
{\displaystyle n(n-1)/2}
启发式一个更准确的诠释是，应先尝试
P
(
E
(
s
)
,
E
(
s
′
)
,
T
)
{\displaystyle P(E(s),E(s'),T)}
s
′
{\displaystyle s'}
P 来说，这意味着
E
(
s
′
)
−
E
(
s
)
{\displaystyle E(s')-E(s)}
T 或更小的数量级上因此在上述旅行商问题中，可用交换两随机城市的neighbour()，并设置两城市距离超过T 时不予选择。
选择候选生成器neighbour()时，还必须尽量减少能量远低于所有邻态的“深”局部最优（或相连状态集）数，这种“能量函数盆地”可能会以较高概率（与盆地中状态数大致呈正比）与较长时间（与周围状态同盆地底部的能量差大致呈指数关系）困住模拟退火算法。
一般来说设计不出既能满足这一目标，又能优先处理能量相近的候选粒子的候选发生器。另一方面，往往可对生成器进行相对简单的修改，大大提高模拟退火的效率。例如，在旅行商问题中，不难找到两条长度几乎相等的路线
A
,
B
{\displaystyle A,\ B}
A
{\displaystyle A}
A
{\displaystyle A}
B
{\displaystyle B}
A
{\displaystyle A}
B
{\displaystyle B}
A
,
B
{\displaystyle A,\ B}
模拟退火的物理类比假设冷却速率足够低，当前状态的概率分布比任意时刻都接近热力平衡 。 然而，弛豫时间（relaxation time，温度变化后恢复平衡耗时）很大程度上取决于能量函数的“地形”和当前温度。模拟退火算法中，弛豫时间还以非常复杂的方式取决于候选生成器。注意所有参数通常作为黑盒函数 提供给模拟退火算法。因此，理想的冷却速度无法事先确定，只能根据经验分析具体问题。自适应模拟退火 算法将冷却历程同搜索进度联系起来，解决了这一问题。其他自适应法有热力学模拟退火，[ 16]
有时，从现态出发不如回到明显更优的解，这一过程称作模拟退火的重启（restarting）。为此，置s、e为sbest、ebest，然后重启退火历程。重启的决定可基于多个标准，其中值得注意的是包括基于固定步数、基于当前能量与迄今最优的能量、随机重启等等。
交互式梅特罗波利斯-黑斯廷斯算法 （或顺序蒙特卡洛[ 17]
量子退火 用“量子扰动”而非热波动来穿越目标函数中较薄的障碍。随机隧道法 试图以隧道穿越障碍，克服了随温度降低，模拟退火越来越难以摆脱局部最优的问题。禁忌搜索 通常会移动到能量较低的邻态，发现陷入局部最优时，就会采取上坡转移，并会保留已知解列表（即“禁忌表”）以避免循环。双相演化 是一组算法与过程（SA属于其中），利用搜索空间的相变，在局部搜索与全局搜索之间进行调节。反应式搜索优化将机器学习与优化相结合，增加内部反馈回路，根据问题、实例与当前解周围的情形，对算法的自由参数进行自我调整。
遗传算法 保留一组解（“池”，pool），而非一个解。新的候选解可由突变（如SA）和“重组”从池中产生。概率标准和SA中所用的类似，用于选择突变或重组的解，并剔除多余解。文化基因算法 使用一组既合作又竞争的搜索器（agent）搜索解。有时搜索器的策略设计模拟退火，以便在重组之前获得高质量解。[ 18] [ 19] 渐进优化 在优化过程中对目标函数进行“平滑化”处理。蚁群算法 （ACO）用许多搜索器遍历解空间，并找到局部较优的区域。交叉熵法 （CE）通过参数化概率分布生成候选解。参数通过交叉熵最小化进行更新，以便在下次迭代中生成更好的样本。和声搜索模拟音乐家即兴演奏的过程，每个音乐家演奏一个音符，共同寻找最佳的和声。
随机优化 是一系列方法的总称，包括模拟退火等很多方法。粒子群优化 是一种以群体智能为模型的算法，能在搜索空间中找到优化问题的解，或在有目标的情形下模拟、预测群体行为。茎根算法（runner-root algorithm，RRA）是一种元启发 优化算法，用于解决单模态和多模态问题，灵感来自植物的茎与叶的关系。
智能水滴算法（Intelligent water drops algorithm，IWD）模仿自然水滴的行为解决优化问题。
并行退火 在不同温度（或哈密顿量 ）下模拟模型副本，以克服潜在障碍。多目标模拟退火用于多目标优化 。[ 20]
^ What is Simulated Annealing? . www.cs.cmu.edu. [2023-05-13 ] . （原始内容存档 于2024-08-29）. ^ Pincus, Martin. A Monte-Carlo Method for the Approximate Solution of Certain Types of Constrained Optimization Problems. Journal of the Operations Research Society of America. Nov–Dec 1970, 18 (6): 967–1235. doi:10.1287/opre.18.6.1225 ^ Khachaturyan, A.: Semenovskaya, S.: Vainshtein B., Armen. Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases. Soviet Physics, Crystallography. 1979, 24 (5): 519–524. ^ Khachaturyan, A.; Semenovskaya, S.; Vainshtein, B. The Thermodynamic Approach to the Structure Analysis of Crystals . Acta Crystallographica. 1981, A37 (5): 742–754. Bibcode:1981AcCrA..37..742K doi:10.1107/S0567739481001630 ^ Laarhoven, P. J. M. van (Peter J. M.). Simulated annealing : theory and applications . Aarts, E. H. L. (Emile H. L.). Dordrecht: D. Reidel. 1987. ISBN 90-277-2513-6OCLC 15548651 ^ 6.0 6.1 Kirkpatrick, S.; Gelatt Jr, C. D.; Vecchi, M. P. Optimization by Simulated Annealing. Science. 1983, 220 (4598): 671–680. Bibcode:1983Sci...220..671K CiteSeerX 10.1.1.123.7607 JSTOR 1690046 PMID 17813860 S2CID 205939 doi:10.1126/science.220.4598.671 ^ Khachaturyan, A.; Semenovskaya, S.; Vainshtein, B. Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases. Sov.Phys. Crystallography. 1979, 24 (5): 519–524. ^ Khachaturyan, A.; Semenovskaya, S.; Vainshtein, B. The Thermodynamic Approach to the Structure Analysis of Crystals. Acta Crystallographica. 1981, 37 (A37): 742–754. Bibcode:1981AcCrA..37..742K doi:10.1107/S0567739481001630 ^ Černý, V. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm . Journal of Optimization Theory and Applications. 1985, 45 : 41–51. S2CID 122729427 doi:10.1007/BF00940812 ^ Metropolis, Nicholas; Rosenbluth, Arianna W.; Rosenbluth, Marshall N.; Teller, Augusta H.; Teller, Edward. Equation of State Calculations by Fast Computing Machines . The Journal of Chemical Physics. 1953, 21 (6): 1087. Bibcode:1953JChPh..21.1087M OSTI 4390578 S2CID 1046577 doi:10.1063/1.1699114 ^ Granville, V.; Krivanek, M.; Rasson, J.-P. Simulated annealing: A proof of convergence. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1994, 16 (6): 652–656. doi:10.1109/34.295910 ^ Nolte, Andreas; Schrader, Rainer, A Note on the Finite Time Behaviour of Simulated Annealing , Operations Research Proceedings 1996 1996 (Berlin, Heidelberg: Springer Berlin Heidelberg), 1997, 1996 : 175–180 [2023-02-06 ] , ISBN 978-3-540-62630-5doi:10.1007/978-3-642-60744-8_32 ^ Moscato, P.; Fontanari, J.F., Stochastic versus deterministic update in simulated annealing, Physics Letters A, 1990, 146 (4): 204–208, Bibcode:1990PhLA..146..204M doi:10.1016/0375-9601(90)90166-L ^ Dueck, G.; Scheuer, T., Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, 1990, 90 (1): 161–175, Bibcode:1990JCoPh..90..161D ISSN 0021-9991 doi:10.1016/0021-9991(90)90201-B ^ Franz, A.; Hoffmann, K.H.; Salamon, P, Best optimal strategy for finding ground states, Physical Review Letters, 2001, 86 (3): 5219–5222, PMID 11384462 doi:10.1103/PhysRevLett.86.5219 ^ De Vicente, Juan; Lanchares, Juan; Hermida, Román. Placement by thermodynamic simulated annealing. Physics Letters A. 2003, 317 (5–6): 415–423. Bibcode:2003PhLA..317..415D doi:10.1016/j.physleta.2003.08.070 ^ Del Moral, Pierre; Doucet, Arnaud; Jasra, Ajay. Sequential Monte Carlo samplers. Journal of the Royal Statistical Society, Series B. 2006, 68 (3): 411–436. S2CID 12074789 arXiv:cond-mat/0212648 doi:10.1111/j.1467-9868.2006.00553.x ^ Moscato, Pablo. An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search. Annals of Operations Research. June 1993, 41 (2): 85–121. S2CID 35382644 doi:10.1007/BF02022564 ^ Moscato, P. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. Caltech Concurrent Computation Program. 1989, (report 826). ^ Deb, Bandyopadhyay. A Simulated Annealing-Based Multiobjective Optimization Algorithm: AMOSA. IEEE Transactions on Evolutionary Computation. June 2008, 12 (3): 269–283. S2CID 12107321 doi:10.1109/TEVC.2007.900837
A. Das and B. K. Chakrabarti (Eds.), Quantum Annealing and Related Optimization Methods [失效連結
Weinberger, E. Correlated and uncorrelated fitness landscapes and how to tell the difference. Biological Cybernetics. 1990, 63 (5): 325–336. S2CID 851736 doi:10.1007/BF00202749 Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP. Section 10.12. Simulated Annealing Methods . Numerical Recipes: The Art of Scientific Computing 3rd. New York: Cambridge University Press. 2007 [2021-09-02 ] . ISBN 978-0-521-88068-8存档 于2011-08-11）. Strobl, M.A.R.; Barker, D. On simulated annealing phase transitions in phylogeny reconstruction . Molecular Phylogenetics and Evolution. 2016, 101 : 46–55. PMC 4912009 PMID 27150349 doi:10.1016/j.ympev.2016.05.001 V.Vassilev, A.Prahova: "The Use of Simulated Annealing in the Control of Flexible Manufacturing Systems", International Journal INFORMATION THEORIES & APPLICATIONS, VOLUME 6/1999 （页面存档备份 ，存于互联网档案馆 ）
