模拟退火 - 直观理解

Question

从csexchange转载：

---

Let s = s0
For k = 0 through kmax (exclusive):
  T ← temperature( 1 - (k+1)/kmax )
  Pick a random neighbour, snew ← neighbour(s)
  If P(E(s), E(snew), T) ≥ random(0, 1):
    s ← snew
Output: the final state s

我很难理解这个算法在温度降低时如何避免被卡在局部最优解中。如果我们在温度较高时跳来跳去，随着温度的降低最终只采取上坡移动，那么所找到的解决方案不是高度依赖于我们在搜索空间中结束时所处的位置吗？我们可能早期找到一个更好的解决方案，在温度高的时候跳出它，然后在温度降低时和我们过渡到爬坡时处于更糟糕的位置。

常见的修改方法之一是记录到目前为止找到的最佳解决方案。我理解这个改变如何减轻了在温度高的探索阶段“抛弃”更好的解决方案的风险，但我不认为这比仅仅执行反复的随机爬坡以对空间进行采样是更好的。

另一种想到的方法是将“迄今为止最好”的跟踪思想与重复的爬山和束搜索相结合。对于每个温度，我们可以执行模拟退火并跟踪最佳的'n'个解决方案。然后对于下一个温度，从这些本地峰值中的每一个开始。

---

更新：

1. 如果不进行修改来跟踪全局最佳解，即使有温度组件，这个算法也会极易陷入局部最优解，是吗？是的，我了解随着温度降低（例如，它转变为纯爬山），采取更差的移动的概率会下降，但可能在开发阶段早期就找到了更好的解决方案，然后从中跳出，随着温度的降低，你没有回头的路，因为你走上了通往新的局部峰值的路径。
2. 通过跟踪全局最优解的添加，我完全可以看出这如何减轻陷入局部峰值的问题，避免了上述问题。但是，这如何改进简单的随机搜索？一个具体的例子是重复的随机爬山。如果你正在跟踪全局最优解，并且在高温部分碰巧达到它，那基本上就是一次随机搜索。
3. 在什么情况下，这个算法比重复的随机爬山之类的算法更可取，为什么？什么样的问题特别适合 SA 而不是其他替代方案。

- Solaxun

---

你有什么具体问题？ - Scott Hunter

@ScottHunter - 我想知道的是：a.) 未经修改的版本如何避免局部最优解，对我来说它似乎与从解决方案空间中的随机点进行爬山没有什么区别，其中该随机点是在温度降低时所处的位置；b.) 在修改后的版本中，它比执行随机重启爬山更有效的原因是什么。 - Solaxun

在冶金学中，像退火一样，并不能保证你会达到最优解，但如果你有正确的材料、正确的操作条件等，通常你能够得到一个好的解决方案（不一定是最佳的，但可以满足你的需求）。 - Jean-Baptiste Yunès

@Solaxun 因为就像在“真实”的退火过程中一样，你的材料的一部分已经处于良好状态，因此再次增加温度不会破坏这种状态，并给你一个机会使更多的零件处于良好状态... - Jean-Baptiste Yunès

我相信，对于模拟退火算法而言，唯一被证明的保证是在冷却进程中步数呈指数级增长（即非常缓慢的冷却），在相当温和的假设下，可以保证收敛到某些函数类别的全局最优解。 - ldog

Answer 1

据我所知，模拟退火算法在极大值问题中不能保证不会陷入局部最优解，尤其是当温度“冷却”时，即在周期后期，k -> kmax的情况下。

因此，正如你所说，我们在开始时会“四处跳跃”，但我们仍然会选择是否接受该跳跃，因为确定接受概率的 P() 函数是目标函数 E() 的函数。在维基百科文章的后面部分，他们稍微描述了一下 P() 函数，并建议如果 e_new > e，那么也许 P=1，总是采取这个移动，如果它是一个改进的话，但如果不是一个改进，也许不总是采取。在周期后期，我们不太愿意随机跳到较差的结果，因此算法倾向于稳定在一个最大值（或最小值），这可能是全局最优解，也可能不是全局最优解。

- AirSquid

---

感谢您的回复。 我想我的观点是，当模拟退火冷却时，我们正在缓慢过渡到爬山，并且当此转换发生时，我们可能处于局部最大值。 假设解决方案空间中有5个最大值。 对我来说，我们最终到达哪一个似乎是完全随机的。 我知道SA不能保证避免局部最大值（除非使用荒谬缓慢的冷却计划），但似乎未经修改的版本实际上只是在掷骰子，看看它最终到达了哪个最大值。 修改它以跟踪全局最佳值可以改善这一点，但那时为什么不只进行随机重复爬山呢？ - Solaxun

与大多数元启发式方法一样，SA背后的概念是在探索和开发之间逐渐过渡。是的，您可以随机重复爬山算法，但您会错过逐渐过渡的过程。此外，请注意“没有免费午餐”定理：永远不会有一种方法比优化所有目标函数的任何其他方法更好。您始终可以找到一个目标函数，其中随机重复爬山算法的效果更好。您始终可以调整参数以适应一堆目标函数，并在其他目标函数上失利。是的，这是随机的！但很可能是“好”的。 - ypnos

也许更好的提问方式是 - 我理解算法的工作原理，但我不明白这种方法如何比随机抽样更容易找到全局最优解。我知道它的转换速度较慢，但我不确定它是否真的有所区别。在什么情况下，模拟退火会胜过随机爬山？这取决于问题本身吗？哪些问题特征更适合使用模拟退火而不是随机爬山？ - Solaxun

@Solaxun：关于“这种方法如何比随机抽样更容易找到全局最优解”的问题，我认为可能让你困惑的是这确实是随机抽样，具体来说，它是Metropolis-Hastings算法。其思想是优化很难，所以SA将事情颠倒过来，说，让我们构建一个采样器，使得我们收敛到基态（全局最优）。这个想法是，我们构建这个采样器，保持不变，并定期退火基础分布，使其在基态周围变得越来越尖峭。 - ldog

在所有这些中，手摆动的部分是当我说我们通过退火温度使概率分布更加尖峰时。您正在进行采样更尖峰与不那么尖峰分布之间的实际经验权衡（需要针对您的问题进行测量和量化）。但是底层算法仍然是Metropolis-Hastings采样器的简单应用：https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm#Intuition - ldog

请阅读此处的最后一段（或整个部分）：https://en.wikipedia.org/wiki/Simulated_annealing#Acceptance_probabilities_2其中描述了在哪些条件下，一些研究人员认为做出确定性选择比随机选择更好。 - ldog

Answer 2

这个问题似乎不太连贯，它似乎询问了香草模拟退火算法提供的保证，然后继续提出多个修改方案，但几乎没有任何理由。

无论如何，我会尽力在这个答案中保持连贯性。

我所知道的唯一一个关于模拟退火的严格证明是描述为：

使用自适应步长的概念对于开发更好的退火算法至关重要。经典模拟退火（CSA）是第一个具有全局收敛严格数学证明的退火算法（Geman和Geman，1984）。如果在GXY（TK）中使用高斯分布，并结合降温时间表S（Tk），其下降速度不快于T = To /（log k），则已被证明可以收敛。整数k是外部退火循环的计数器，将在下一节中详细介绍。但是，对于许多问题而言，对数下降的时间表被认为太慢，需要的迭代次数被认为是“过度杀伤”（Ingber，1993）。

其中可以找到此证明。

Geman, Stuart和Donald Geman在1984年的《IEEE模式分析与机器智能交易》中提出了“随机松弛，吉布斯分布和贝叶斯图像恢复”的理论。就成功修改SA而言，如果您查阅文献，您会发现许多经验性的优越性声明，但很少有证明。过去研究过这个问题后，我可以说，从我当时感兴趣的问题的各种经过实证的SA修改版本中，唯一能够始终比经典模拟退火算法给出更好结果的是被称为并行淬火的SA修改。

并行淬火是SA的修改，其中不是混合一个马尔可夫链（即淬火步骤），而是同时混合多个链，在非常特定的温度下进行，并在动态或静态时间表上进行链之间的交换。

关于并行淬火的原始论文：

Swendsen，Robert H.和Jian-Sheng Wang在1986年的《物理评论快报》57.21中提出了“自旋玻璃的复制蒙特卡罗模拟”。

由于其有效性，有各种免费和专有的并行淬火实现可用；我强烈建议您从高质量的实现开始，而不是自己编写。

注意，平行淬火在各种物理科学领域被广泛用于建模目的，因为它的有效性已经得到证实。但令人困惑的是，在其他文献领域（如计算机科学）中，平行淬火的应用却非常有限。也许计算机科学家对模拟退火算法的修改不太感兴趣，是因为他们认为模拟退火算法很难有所改进。

- ldog

Answer 3

全局函数评估的挑战在于获得良好的效率，即尽可能少地进行函数评估来找到最优解或接近最优解的解决方案。因此，许多“我们可以执行…”的推理在收敛到良好解决方案方面是正确的，但可能无法高效。

现在纯爬山和模拟退火之间的主要区别在于，模拟退火暂时允许目标恶化以避免陷入局部最优解。爬山只搜索函数取值大于迄今为止最佳值的子空间，这可能无法连接到全局最优解。模拟退火添加了一些“隧道”效应。

温度下降并不是关键因素，顺便说一下，像Simplex或Hooke-Jeeves模式这样的爬山方法也可以使用逐渐减小的扰动。温度方案更与目标函数的多尺度分解有关。

- user1196549