模拟退火算法中的邻居选择

Question

选择邻居时应该考虑算法的温度吗？那么,例如,如果在选择邻居时温度很高,那么应该进行排列吗？或者温度只影响接受概率？

Answer 1

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

来自维基百科的伪代码：

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.

Answer 2

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

高效的候选生成

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

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

关于如何编写邻居函数的更有用的阅读：如何在模拟退火的 1 维和 n 维空间中有效地选择邻居