从概念上理解模拟退火
我刚刚被介绍了模拟退火，并且想在再次深入研究代码之前更好地理解它，因为尽管我从迄今为止的资源中阅读了代码，但我觉得我不太明白它。所以请随意纠正我目前对算法的理解：
模拟退火算法有一个 实现的总体目标 最低（或最高）分数基于 一些预定义的计算方法 （例如 TSP 中行驶的距离或 密码子对分布 生物信息学）。然而，为了避免 陷入局部最优， 暂时较低（或较高）分数是 接受，以达到更好的效果 全球解决方案。
附加问题：如何克服局部最优？是基于某种概率接受更高的分数吗？ （从这里开始很模糊）
非常感谢您对此进行调查。
i have just been introduced to simulated annealing and would like to understand it better before delving into the code again as I feel like I dont quite get it despite reading the code from the resources I have so far. So please feel free to correct my current understanding of the algorithm:
Simulated annealing algorithm has an
overall goal of achieving the
minimum(or maximum) score based on
some predefined method of computation
(like distance travelled in TSP or
codon pair distribution in
bioinformatics). However, to avoid
being trapped in a local optima, a
temporary lower (or higher) score is
accepted so as to achieve a better
global solution.
An additional question: How is the local optima overcome? Is it by accepting a higher score based on some probability? (quite hazy from here on)
Thank you very much for looking into this..
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您的描述是正确的，但可能会产生误导，因为“以便实现更好的全局解决方案”表明算法以某种方式知道暂时较差的分数会有所帮助。事实并非如此（不可能！），事实上，大多数时候，暂时的更差分数只是暂时的更差分数。
这是我的想法。你在黑暗中跌跌撞撞，寻找一个深洞。如果你继续下坡，那么你最终会进入距离起点最近的洞，这个洞可能不是很深。所以你故意随意地移动，如果你掉进浅洞里，就让自己爬出来。所以浅洞对你来说大多是看不见的；但如果你碰巧掉进一个很深的洞里，你很可能会留在里面。
现在，当然，最终你确实想找到你所在的洞的底部。所以你一开始有很多随机性，然后逐渐减少它，所以最初你只是几乎完全随机地徘徊（除非你有幸掉进一个很深的洞），但稍后——一旦你希望找到了你能找到的最深的洞——你就可以更准确地找到它的底部。
物理类比是液体冷却时晶体形成的过程。通过缓慢冷却，您可以获得更大的晶体（总体能量更低，更接近全局最佳值）。温度=随机性，其底层过程与模拟退火非常相似。或者更确切地说，模拟退火与缓慢晶体生长的过程非常相似。
就机制而言：通常的设置是随机尝试步骤，如果它们使事情变得更好，则始终接受它们，如果它们使事情变得更糟，则以类似于 exp(-d/T) 的概率接受它们，其中 d 是如何更糟糕的是，这个步骤会让事情变得更糟，T（“温度”）是衡量你为了更多地探索解决方案空间而准备忍受多少随机废话的指标。你逐渐减少 T。当 T->0 时，接受使事情变得更糟的步骤的概率将为零。
如何生成随机步骤以及如何降低“温度”的详细信息是大部分实际工作的所在:-)。
Your description is right but might be misleading, because "so as to achieve a better global solution" suggests that somehow the algorithm knows that the temporary worse score is going to help. It doesn't (it couldn't!), and indeed most of the time the temporary worse score is simply a temporary worse score.
Here's the idea. You're stumbling around in the dark, looking for a deep hole. If you just keep going downhill then you'll end up in the nearest hole to where you start, which may not be very deep. So you deliberately move around somewhat at random, letting yourself climb out of shallow holes if you get into them. So shallow holes are mostly invisible to you; but if you happen to fall into a really deep hole you'll likely stay in it.
Now, of course eventually you do want to find the bottom of whatever hole you're in. So you start off with a lot of randomness and gradually reduce it, so that initially you're just wandering around almost completely at random (unless you have the good fortune to fall into a really deep hole), but later on -- once you hope you've found the deepest hole you can -- you can locate its bottom more accurately.
The physical analogy is with the process of crystal formation as a liquid cools. You get bigger (lower overall energy, nearer to a global optimum) crystals by cooling slowly. Temperature = randomness, and the underlying process is rather similar to that of simulated annealing. Or, rather, simulated annealing is rather similar to a process of slow crystal growth.
As far as mechanism goes: the usual setup is that you try steps at random, always accept them if they make things better, and if they're worse accept them with probability that looks like exp(-d/T) where d is how much worse the step makes things and T, the "temperature", is a measure of how much random nonsense you're prepared to put up with at the moment for the sake of exploring the solution space more. You gradually reduce T. As T->0 the probability of accepting a step that makes things worse at all goes to zero.
The details of how you generate your random steps and how you reduce the "temperature" are where most of the actual work goes :-).