9

选择邻居时应该考虑算法的温度吗？因此，例如，如果在挑选邻居时温度很高，应该进行排列吗？还是温度只影响接受概率？

4

3 回答 3

5

后者是正确的：只有接受概率受温度影响。温度越高，越“坏”的动作被接受以逃避局部最优。如果您预先选择具有低能量值的邻居，您基本上会与模拟退火的想法相矛盾，并将其变成贪婪搜索。

来自维基百科的伪代码：

s ← s0; e ← E(s)                                  // Initial state, energy.
sbest ← s; ebest ← e                              // Initial "best" solution
k ← 0                                             // Energy evaluation count.
while k < kmax and e > emax                       // While time left & not good enough:
  T ← temperature(k/kmax)                         // Temperature calculation.
  snew ← neighbour(s)                             // Pick some neighbour.
  enew ← E(snew)                                  // Compute its energy.
  if P(e, enew, T) > random() then                // Should we move to it?
    s ← snew; e ← enew                            // Yes, change state.
  if enew < ebest then                            // Is this a new best?
    sbest ← snew; ebest ← enew                    // Save 'new neighbour' to 'best found'.
  k ← k + 1                                       // One more evaluation done
return sbest                                      // Return the best solution found.
于 2013-04-06T17:44:04.743 回答
5

这是来自维基百科的描述，其中指出实际上应该针对某些问题计算温度。

高效的候选生成

启发式的更精确的陈述是，应该尝试第一个候选状态 s'，其中 P(E(s), E(s'), T) 很大。对于上面的“标准”接受函数 P，它意味着 E(s') - E(s) 在 T 或更少的数量级上。因此，在上面的旅行推销员示例中，可以使用交换两个随机城市的 neighbour() 函数，其中选择城市对的概率随着距离增加超过 T 而消失。

这确实意味着在确定邻居时温度可能是相关因素。

更多关于如何编写邻域函数的有用读物：How to Effective select neighbor in 1-dimensional and n-dimensional space for Simulated Annealing

于 2015-06-11T20:27:34.330 回答
3

我也有同样的问题，但我认为Python 中模拟退火基础的另一篇文章的答案表明 T 可能与选择邻居有关是非常合理的。

选择邻居也将取决于您的问题。限制邻里的主要原因是，一旦你找到了一个不错的解决方案，即使你后来转向更糟糕的解决方案，你至少也留在附近。直觉是大多数目标函数都有些平滑，因此好的解决方案将靠近其他好的解决方案。因此，您需要一个足够小的社区，让您靠近好的解决方案，但又足够大，让您可以快速找到它们。您可以尝试的一件事是随着时间的推移减少邻域（例如，使其与温度成正比）。– 2013 年 11 月 4 日 20:58

于 2014-10-10T08:39:40.673 回答