对模拟退火的困惑

Question

模拟退火是一种用于优化的元启发式算法。本质上，它进行爬山，有可能从一座山跳到另一座山--即使是跳到第二座山上更低的地方。

随着“温度”的冷却和系统进入解决方案，这种负跳跃被允许的频率越来越低。参见this pseudo-code。允许跳跃的要点是使系统能够从导致局部最大值的山丘移动到导致全局最大值的山丘。

我的困惑是，系统如何防止自己从导致全局最大值的山丘跳到只导致局部最大值的山丘。

Answer 1

我认为您对模拟退火(SA)的理解有一点缺陷。

当使用SA解决问题时，在任何时间点，您的可行解决方案都将位于解决方案空间中的某个小山中。除非你在你访问的每一座山上都进行标准的爬山(你不是)，否则你没有办法知道你目前所在的山峰通向哪里。你所知道的就是你现在的身高。因此，在任何迭代中，您很可能从通向全局最优的小山跳到通向局部最优的小山。

也就是说，使用SA，你会倾向于登上更高的山丘，因为较低的温度会逐渐驱使你走向山丘，那里仍然有上升的可能性。