模拟退火

模拟退火可用于解决组合问题。在这里，它应用于旅行推销员问题最小化连接所有125点的路线的长度。

旅行推销员在3D中有120点的问题，并通过模拟退火解决。

模拟退火（SA）是概率技术用于近似全局最佳给定的功能。具体来说，这是一个元神经近似全局优化大搜索空间为优化问题。当搜索空间离散时，通常会使用它（例如旅行推销员问题， 这布尔可满足性问题，蛋白质结构预测， 和工作店计划）。对于在固定时间内找到近似全球最佳最佳最佳的问题比找到精确的局部最优值更为重要，模拟退火可能比精确的算法（例如梯度下降或者分支和绑定.

该算法的名称来自在冶金中退火，一种涉及材料的加热和控制冷却以改变其物理特性的技术。两者都是取决于其热力学自由能的材料的属性。加热和冷却材料会影响温度和热力学自由能或吉布斯能量。模拟退火可用于精确算法失败的非常硬的计算优化问题；即使它通常可以实现全球最低限度的近似解决方案，但对于许多实际问题来说，它也足够了。

SA解决的问题目前由许多变量的目标函数提出，但受到多个约束。实际上，可以将约束作为目标函数的一部分进行惩罚。

类似的技术已多次独立引入，包括Pincus（1970），^[1]Khachaturyan等人（1979年，^[2]1981^[3]），Kirkpatrick，Gelatt和Vecchi（1983）和Cerny（1985）。^[4]1983年，Kirkpatrick，Gelatt Jr.，Vecchi，使用这种方法，^[5]解决旅行推销员问题的解决方案。他们还提出了当前名称模拟退火。

在模拟退火算法中实现的缓慢冷却的概念被解释为在探索解决方案空间时接受较差的解决方案的概率降低。接受较差的解决方案可以更广泛地搜索全球最佳解决方案。通常，模拟退火算法如下。温度从初始正值逐渐降低到零。在每个时间步骤中，该算法都随机选择接近当前算法的解决方案，测量其质量，并根据选择更好或更差的解决方案的温度依赖性概率移动到它，在搜索过程中分别保持在1（或正面））并降低到零。

模拟可以通过动力学方程的溶液进行密度函数进行^[6][7]或使用随机采样方法。^[5][8]该方法是适应大都市算法， 一个蒙特卡洛法生成热力学系统的样品状态，由N.大都市等。 1953年。^[9]

概述

这状态一些中的物理系统和功能e（s）要最小化，类似于内能在该状态下的系统。目的是从任意中带来系统初始状态，达到最小能量的状态。

模拟退火搜索最大值。这里的目的是达到最高点。在此示例中，使用简单的爬山算法，因为有很多本地最大值。通过慢慢冷却温度，可以发现全局最大。

基本迭代

在每个步骤中，模拟退火启发式都考虑了一些邻近状态S*当前状态s， 和概率决定将系统移至状态之间S*或留在州内s。这些概率最终导致系统转移到较低的能源状态。通常，重复此步骤，直到系统达到足以应用程序的状态，或直到给定的计算预算已经用尽。

国家的邻居

解决方案的优化涉及评估问题状态的邻居，这是通过保守改变给定状态而产生的新状态。例如，在旅行推销员问题每个状态通常定义为排列在要访问的城市中，任何国家的邻居都是通过交换任何两个城市而产生的排列集。改变状态以产生邻近状态的明确定义的方式称为“移动”，不同的举动给出了不同的邻近状态。这些举动通常会导致最后一个状态的改变，以试图通过迭代的零件（例如旅行推销员问题中的城市联系）逐步改善解决方案。

简单的启发式方法喜欢爬山，通过在更好的邻居之后找到更好的邻居并在达到没有更好解决方案的邻居的解决方案时停下来的移动，不能保证导致任何现有的更好的解决方案 - 他们的结果可能很容易只是一个本地最佳，虽然真正的最好的解决方案是全局最佳那可能是不同的。元启发式学使用解决方案的邻居来探索解决方案空间，尽管他们更喜欢更好的邻居，但他们也接受更糟糕的邻居，以避免陷入本地Optima；如果运行足够长的时间，他们可以找到全局最佳。

接受概率

使过渡从当前状态${\ displayStyle s}$到候选人新州${\ displaystyle s _ {\ mathrm {new}}}}$由接受概率函数${\ displayStyle p（e，e _ {\ mathrm {new}}，t）}$，这取决于能量${\ displayStyle e = e（s）}$和${\ displaystyle e _ {\ mathrm {new}} = e（s _ {\ mathrm {new}}}}}}}$在这两个状态中，以及全球时间变化的参数${\ displayStyle t}$叫做温度。能量较小的状态比能量更大的状态更好。概率函数${\ displayStyle p}$即使${\ displaystyle e _ {\ mathrm {new}}}}$大于${\ displayStyle e}$。此功能可防止该方法被卡在局部最低限度上，该方法比全球范围更糟糕。

什么时候${\ displayStyle t}$趋于零，概率${\ displayStyle p（e，e _ {\ mathrm {new}}，t）}$如果${\ displaystyle e _ {\ mathrm {new}}> e}$否则就具有积极价值。对于足够小的值${\ displayStyle t}$然后，该系统将越来越喜欢“下坡”（即降低能量价值）的动作，并避免那些“上坡”。和${\ displayStyle t = 0}$该过程减少到贪婪算法，这只会使下坡过渡。

在模拟退火的原始描述中，概率${\ displayStyle p（e，e _ {\ mathrm {new}}，t）}$等于1${\ displaystyle e _ {\ mathrm {new}} <e}$ - i.e.，当它找到一种方法时，该过程总是下坡，无论温度如何。模拟退火的许多描述和实现仍然是该方法定义的一部分。但是，这种情况对于方法的工作并不是必不可少的。

这${\ displayStyle p}$通常选择功能，以便在差异时接受移动的概率会减少${\ displaystyle e _ {\ mathrm {new}} -e}$增加 - 也就是说，小型上坡动作比大型动作更有可能。但是，只要满足上述要求，就不必需这一要求。

鉴于这些特性，温度${\ displayStyle t}$在控制国家的演变中起着至关重要的作用${\ displayStyle s}$系统对系统能量变化的敏感性。确切地说，很大${\ displayStyle t}$，演变${\ displayStyle s}$对更粗糙的能量变化敏感，而当它对较小的能量变化敏感时${\ displayStyle t}$是小。

退火时间表

快速地

减缓

示例说明了冷却时间表对模拟退火性能的影响。问题是重新排列像素图像以最大程度地减少某个势能功能，导致相似颜色在短范围内吸引并以较大的距离排斥。基本移动交换两个相邻像素。这些图像是通过快速冷却时间表（左）和缓慢的时间表（右）获得的，产生的结果类似于无定形和结晶固体， 分别。

该算法的名称和灵感要求与要嵌入算法的操作特征中的温度变化有关的有趣特征。随着模拟的进行，这需要逐渐降低温度。该算法最初以${\ displayStyle t}$设置为高价值（或无穷大），然后在某些之后的每个步骤中降低它退火时间表 - 用户可以指定的，但必须以${\ displayStyle t = 0}$在分配的时间预算结束时。这样，该系统将最初徘徊在包含良好解决方案的搜索空间的广阔区域，忽略能量功能的小特征。然后向低能区域漂移，这种区域变得越来越狭窄，并根据最陡的下降启发式。

对于任何给定的有限问题，模拟退火算法终止全球最佳解决方案方法1随着退火时间表的扩展。^[10]但是，这种理论结果并不是特别有用，因为确保成功概率所需的时间通常会超过完成搜索的解决方案空间.

伪代码

如上所述，以下伪代码介绍了模拟的退火启发式。它从状态开始s₀并一直持续到最多k_最大限度已经采取了步骤。在此过程中，调用邻居（s）应生成给定状态的随机选择的邻居s;电话随机（0，1）应该在该范围内选择并返回一个值[0，1]，随机均匀。退火时间表由通话定义温度（r）鉴于分数，它应该产生温度r到目前为止已经花费的时间预算。

选择参数

为了将模拟退火方法应用于特定问题，必须指定以下参数：状态空间，能量（目标）函数E()，候选生成器过程neighbour()，接受概率函数P()和退火时间表temperature()和初始温度init_temp。这些选择可能会对该方法的有效性产生重大影响。不幸的是，这些参数没有选择对所有问题都有利的选择，也没有一般方法可以找到给定问题的最佳选择。以下各节提供了一些一般指南。

足够靠近邻居

模拟退火可以在搜索图上建模为随机步行，其顶点都是可能的状态，并且其边缘是候选的移动。对neighbour()功能是，它必须在此图上提供足够的短路径，从初始状态到任何可能是全局最佳的状态 - 搜索图的直径必须很小。例如，在上面的旅行推销员示例中，n = 20个城市的搜索空间有n！= 2,432,902,008,176,640,000（2.4千万亿）；但是每个顶点的邻居数量是${\ displaystyle \ sum _ {k = 1}^{n-1} k = {\ frac {n（n-1）} {2}} = 190}$边缘（来自n选择2），图的直径为${\ displayStyle n-1}$.

过渡概率

为了研究对特定问题的模拟退火行为，考虑到过渡概率这是由于算法实现时做出的各种设计选择所致。对于每个边缘${\ displayStyle（s，s'）}$在搜索图中，过渡概率定义为模拟退火算法的概率${\ displayStyle s'}$当其当前状态为${\ displayStyle s}$。这种概率取决于当前温度，如temperature()，按照候选移动的顺序是由neighbour()功能，以及接受概率功能P()。（请注意，过渡概率是不是简单地${\ displayStyle p（e，e'，t）}$，因为候选人经过串行测试。）

接受概率

规格neighbour()，P()， 和temperature()是部分多余的。在实践中，使用相同的接受函数是常见的P()对于许多问题，并根据特定问题调整其他两个功能。

在Kirkpatrick等人的方法中，接受概率函数${\ displayStyle p（e，e'，t）}$被定义为1${\ displayStyle e'<e}$， 和${\ displaystyle \ exp（ - （e'-e）/t）}$除此以外。该公式通过类比与物理系统的过渡表面上是合理的。它对应于大都市算法在t = 1和大都市 - 持有的提议分布的情况下，是对称的。但是，即使在neighbour()功能类似于大都市 - 主持人中的提议分布，不是对称的，也不是概率。结果，模拟退火算法的过渡概率与类似物理系统的过渡以及状态在恒温下的长期分布不符${\ displayStyle t}$在任何温度下，无需与该物理系统状态的热力学平衡分布有任何相似之处。然而，大多数模拟退火的描述都采用了原始的接受函数，在许多实现的SA实现中可能对此进行了硬编码。

1990年，莫斯托和丰塔纳里，^[11]独立杜克和舒尔，^[12]提出确定性更新（即非基于概率接受规则的更新）可以加快优化过程而不会影响最终质量。Moscato和Fontanari得出结论，从他们的研究中观察到“阈值更新”退火的“特定热量”曲线的类似性，该曲线源自他们的研究，“大都市在模拟退火算法中更新的随机性在接近搜索的搜索中并不重要 - 最佳的最小值。取而代之的是，他们提出“在高温下的成本函数景观的平稳以及在冷却过程中逐渐定义的逐渐定义是成功模拟退火成功的基本要素。”该方法随后在由于杜克（Dueck）和舒尔（Scheuer）的教派而导致的“阈值接受”面额下普及。2001年，弗朗兹（Franz），霍夫曼（Hoffmann）和萨拉蒙（Salamon）表明，确定性更新策略确实是大型算法中的最佳策略，这些算法模拟了成本/能源环境的随机步行。^[13]

有效的候选人生成

选择候选生成器时neighbour()，必须考虑到，在模拟退火算法进行了几次迭代后，当前状态的能量预计将比随机状态低得多。因此，作为一般规则，应该将发电机偏向候选者移动目的地状态的能量${\ displayStyle s'}$可能与当前状态相似。这个启发式（这是大都市算法）倾向于排除“非常好”的候选动作以及“非常糟糕的”动作；但是，前者通常比后者少得多，因此启发式措施通常非常有效。

例如，在上面的旅行推销员问题中，交换两个连续的低能旅行中的城市预计将对其能量（长度）产生适度的影响；而交换两个随意的城市增加长度的可能性要比减少它的长度更大。因此，即使后者可以提供最佳的途径（使用后者，连续S-wap邻域发生器的性能都比任意S-wap One的发电机更好${\ displayStyle n-1}$互换，而不是${\ displayStyle n（n-1）/2}$）。

启发式方法的更精确的陈述是，应该尝试先候选人${\ displayStyle s'}$为此${\ displayStyle p（e（s），e（s'），t）}$很大。对于“标准”接受功能${\ displayStyle p}$上面，这意味着${\ displayStyle e（s'） - e（s）}$是按照${\ displayStyle t}$或更少。因此，在上面的旅行推销员示例中，可以使用neighbour()交换两个随机城市的功能，其中选择城市对随着距离的增加而消失的可能性${\ displayStyle t}$.

避免障碍

选择候选生成器时neighbour()还必须尝试减少具有比所有邻近州的能量要低得多的“深”本地最小值（或连接状态的一组）的数量。这样的“关闭集水能量功能的盆地”可能会以高概率（与盆地中的状态数量大致成正比）和很长一段时间（大致在周围状态和盆地底部的能量差上呈指数呈指数呈指数，这可能会捕获模拟的退火算法。）。

通常，不可能设计一个能够满足这一目标并优先考虑具有相似能量的候选人的候选生成器。另一方面，通过对发电机的相对简单的更改，通常可以极大地提高模拟退火的效率。例如，在旅行推销员问题中，不难展示两个旅行${\ displayStyle a}$，${\ displayStyle b}$，几乎相等的长度，以至于（1）${\ displayStyle a}$最佳${\ displayStyle a}$至${\ displayStyle b}$经历比两者更长的旅行，（3）${\ displayStyle a}$可以转变为${\ displayStyle b}$通过翻转（反向）连续城市。在此示例中${\ displayStyle a}$和${\ displayStyle b}$如果发电机仅执行随机的成对折叠，则位于不同的“深盆地”中；但是，如果发电机执行随机细分流体，它们将处于同一盆地。

冷却时间表

用于证明模拟退火合理的物理类比假设冷却速率足够低，以使当前状态的概率分布接近热力学平衡每时每刻。不幸的是，休息时间 - 温度变化后必须等待恢复平衡的时间 - 毫不及格地取决于能量函数的“地形”和当前温度。在模拟的退火算法中，放松时间也取决于候选者的生成器，这是非常复杂的。请注意，所有这些参数通常以黑匣子功能到模拟退火算法。因此，理想的冷却速率无法事先确定，应针对每个问题进行经验调整。自适应模拟退火算法通过将冷却时间表连接到搜索进度来解决此问题。其他自适应方法作为热力学模拟退火，^[14]根据热力学定律，根据两种状态之间的能量差自动调节每个步骤的温度。

重新启动

有时，最好回到明显更好而不是从当前状态移动的解决方案。这个过程称为重新启动模拟退火。为此，我们设置了s和e至Sbest和ebest也许重新启动退火时间表。重新启动的决定可以基于几个标准。其中值得注意的包括基于固定数量的步骤重新启动，这是基于与到目前为止获得的最佳能量相比，当前能量是否太高，随机重新启动，等等。

相关方法

• 相互作用的大都市算法（又名顺序蒙特卡洛^[15]）结合了模拟退火动作，并对配备有交互回收机制的最佳拟合者接受拒绝。
• 量子退火使用“量子波动”而不是热波动，以通过目标功能中的高而薄的屏障。
• 随机隧道试图克服越来越多的模拟退火运行的尝试，通过通过障碍“隧道”来降低，随着温度降低而逃脱了局部最小值。
• 禁忌搜索通常移至较低能源的邻近状态，但是当发现自己陷入当地最低限度时，它将采取上坡移动。并通过保留已经看到的解决方案的“禁忌列表”来避免周期。
• 双相演变是一个算法和过程（模拟退火属于的算法和过程），通过利用搜索空间中的相位变化来调节本地和全局搜索。
• 反应性搜索优化通过添加内部反馈循环将算法的自由参数添加到问题的特征，实例的特征以及当前解决方案周围的本地情况上，重点侧重于将机器学习与优化相结合。
• 遗传算法维护解决方案池，而不仅仅是一种。新的候选解决方案不仅是通过“突变”（如SA中的）生成的，而且还通过池中两种溶液的“重组”而产生。概率标准（类似于SA中使用的标准）用于选择用于突变或组合的候选物，并从池中丢弃过多的解决方案。
• 模因算法通过采用一组在此过程中合作和竞争的代理来搜索解决方案；有时，代理的策略涉及模拟退火程序，以便在重组它们之前获得高质量解决方案。^[16]还建议退火作为增加搜索多样性的一种机制。^[17]
• 渐变优化优化时，题外“平滑”目标函数。
• 蚂蚁菌落优化（ACO）使用许多蚂蚁（或代理）遍历溶液空间并找到本地生产的区域。
• 这跨凝结法（CE）通过参数化概率分布生成候选解决方案。参数是通过交叉渗透最小化更新的，以便在下一个迭代中生成更好的样品。
• 和谐搜索在即兴创作过程中模仿音乐家，每个音乐家都会扮演一个音符，以便一起寻找最佳和谐。
• 随机优化是一组包括模拟退火和许多其他方法的方法。
• 粒子群优化是一种以群体智能为模型的算法，它可以在搜索空间中找到解决优化问题的解决方案，或者在目标存在下建模并预测社会行为。
• Runner-root算法（RRA）是meta-heuristic优化算法，用于解决受自然界中植物的跑步者和根的启发的单峰和多模式问题。
• 智能水滴算法（IWD）模仿天然水的行为以解决优化问题
• 平行回火是在不同温度下的模型副本的模拟（或哈密​​顿人）克服潜在的障碍。
• 多目标模拟退火算法已在多目标优化.^[18]

也可以看看

参考

进一步阅读

• A. Das和B. K. Chakrabarti（编辑），量子退火和相关优化方法，物理学讲座，第1卷。679，施普林格，海德堡（2005）
• Weinberger，E。（1990）。“相关和不相关的健身景观以及如何告诉差异”。生物控制论.63（5）：325–336。doi：10.1007/bf00202749.S2CID 851736.
• 媒体，WH；Teukolsky，SA；审查，wt;Flannery，BP（2007）。“第10.12节。模拟退火方法”.数值食谱：科学计算的艺术（第三版）。纽约：剑桥大学出版社。ISBN 978-0-521-88068-8.
• Strobl，M.A.R。; Barker，D。（2016）。“系统发育重建中的模拟退火相变”.分子系统发育和进化.101：46–55。doi：10.1016/j.ympev.2016.05.001.PMC 4912009.PMID 27150349.
• V.Vassilev，A.Prahova：“在柔性制造系统控制中使用模拟退火”，国际期刊信息理论和应用，第6/1999卷

外部链接

• 模拟退火JavaScript应用程序，可让您尝试模拟退火。包括源代码。
• “一般模拟退火算法”用于通用模拟退火练习的开源MATLAB程序。
• 关于模拟退火的自助课程Wikiversity项目。
• Google使用使用，而不是使用量子计算机ARS Technica讨论了Google使用的D波计算机实际上可能是有效的模拟退火处理器的可能性。
• [1]基于模拟退火的多物体优化算法：AMOSA。