我刚刚被介绍到模拟退火，并希望在再次深入研究代码之前更好地理解它，因为尽管从我目前拥有的资源中阅读了代码，但我觉得我不太明白它。所以请随时纠正我目前对算法的理解：
模拟退火算法的总体目标是基于一些预定义的计算方法（如 TSP 中的行进距离或生物信息学中的密码子对分布）获得最小（或最大）分数。然而，为了避免陷入局部最优，暂时接受较低（或较高）的分数，以获得更好的全局解决方案。
另一个问题：如何克服局部最优？是通过基于某种概率接受更高的分数吗？（从这里开始很朦胧）
非常感谢你调查这个..
问问题
1454 次
1 回答
3
您的描述是正确的，但可能会产生误导，因为“以实现更好的全局解决方案”表明算法以某种方式知道暂时较差的分数会有所帮助。它没有（它不能！），而且实际上大多数时候暂时较差的分数只是暂时的较差分数。
这是想法。你在黑暗中跌跌撞撞，寻找一个深洞。如果你只是继续下坡，那么你最终会进入离你开始的地方最近的洞，这个洞可能不是很深。所以你故意随意地四处走动，如果你进入浅洞，就让自己爬出来。因此，您几乎看不到浅孔；但如果你碰巧掉进了一个很深的洞，你很可能会留在里面。
现在，当然最终你确实想找到你所在的洞的底部。所以你从很多随机性开始并逐渐减少它，所以最初你只是几乎完全随机地四处游荡（除非你有幸掉进一个非常深的洞），但后来——一旦你希望你找到了最深的洞——你可以更准确地找到它的底部。
物理类比是液体冷却时晶体形成的过程。通过缓慢冷却，您可以获得更大的（更低的总能量，更接近全局最优值）晶体。温度 = 随机性，其基本过程与模拟退火的过程非常相似。或者，更确切地说，模拟退火非常类似于缓慢晶体生长的过程。
就机制而言：通常的设置是您随机尝试步骤，如果它们使事情变得更好，则始终接受它们，如果它们变得更糟，则以看起来像 exp(-d/T) 的概率接受它们，其中 d 是如何更糟糕的是，这一步使事情变得更糟，而“温度”T 是衡量您目前为了更多地探索解决方案空间而准备忍受多少随机废话的量度。你逐渐减少 T。当 T->0 时，接受使事情变得更糟的步骤的概率变为零。
您如何生成随机步骤以及如何降低“温度”的详细信息是大多数实际工作进行的地方:-)。
于 2011-03-24T00:11:23.093 回答