python - 模拟退火 - 直觉

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

我无法理解该算法如何在温度降低时不会陷入局部最优。如果我们在开始时温度很高时跳来跳去，最终只在温度冷却时采取上坡 Action ，那么找到的解决方案是否高度依赖于温度开始时我们恰好在搜索空间中结束的位置冷却？我们可能早就找到了更好的解决方案，在温度高的时候跳下，然后在温度变冷时处于更糟糕的位置，我们过渡到爬山。

此方法的一个经常列出的修改是跟踪迄今为止找到的最佳解决方案。我看到这种变化如何降低在温度较高时“丢弃”在探索阶段找到的更好解决方案的风险，但我看不出这比简单地重复随机爬山来对空间进行采样有什么好处，没有温度戏剧。

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

---

更新:有人正确地指出我并没有真正问一个具体的问题，我已经在评论中更新但想在这里反射(reflect)出来:

我不需要将伪代码转录成论文形式，我了解它是如何工作的——温度如何平衡探索与开发，以及这(理论上)如何帮助避免局部最优。

我的具体问题是:

1. 无需修改即可跟踪全局最佳解决方案，尽管有温度分量？是的，我知道随着温度降低(例如，它过渡到纯粹的爬山)，采取更糟糕的行动的可能性会下降，但是您可能在开发部分的早期找到了更好的解决方案(温度高)，从上面跳下来，然后随着温度的降低，您将无路可退，因为您正走在通向新的局部峰值的路径上。
2. 加上跟踪全局最优值，我绝对可以看看这如何减轻卡在局部峰值的情况，从而避免上述问题。但是如何这改进了简单的随机搜索？一个具体的例子是反复随机爬山。如果您正在跟踪全局最优值并且碰巧在高温部分遇到了它，那么这本质上是随机搜索。
3. 在什么情况下此算法比重复随机爬山之类的算法更可取？为什么？问题具有哪些属性使其特别适合 SA 与替代方案。

Answer 1

据我了解，模拟退火不能保证不会陷入局部最大值(对于最大化问题)，尤其是当它在循环后期“冷却”为 k -> kmax 时。

所以正如你所说，我们一开始就“到处跳”，但我们仍然选择是否接受该跳转，因为 P() 函数决定了接受概率是目标 E() 的函数。在同一篇维基百科文章的后面，他们稍微描述了 P() 函数，并建议如果 e_new > e，那么可能 P=1，如果它是一个改进，总是采取行动，但也许如果不是改善，则并非总是如此。在周期的后期，我们不太愿意随机跳跃以获得较小的结果，因此算法倾向于稳定在最大值(或最小值)中，这可能是也可能不是全局的。