使用禁忌搜索如何选择邻居作为旅行推销员?

Question

当试图理解禁忌搜索如何应用于旅行推销员时，我很难理解社区是如何产生的。如果我们看一下维基百科上的这个伪代码：

sNeighborhood ← getNeighbors(bestCandidate)
for (sCandidate in sNeighborhood)
if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) )
bestCandidate ← sCandidate
end
end

我的最佳候选者从最近邻算法生成的路径开始，这条路径的邻居是什么？

假设我的路径是A，B，D，C，A，邻域是每个指数的所有可能性吗？例如[B，D，C]，[A，C，D]等？

然后我们消除每个索引的禁忌列表中的邻居？

如果没有，我的邻居是什么？

同样在伪代码中，禁忌列表只添加新的最佳候选者，那么下次我们如何选择不同的社区呢？

if (fitness(bestCandidate) > fitness(sBest))
sBest ← bestCandidate
end
tabuList.push(bestCandidate)

维基百科源代码：

https://en.wikipedia.org/wiki/Tabu_search

Answer 1

问题 1

is the neighborhood every possibility for each index?

不是每个，在这种情况下，它可以完成，因为总索引是 4，但当索引数量增加时，它会太复杂。

一般来说，可以通过使用一些启发式方法(例如索引之间的直接距离)找到邻域。例如，如果路径为 [A， B， C， F， G， E， D， A]，并且对于每个索引，选择 2 个最接近的索引，例如 [B， C]、[A， F]、[A， D] 等。现在可以使用这些指数生成社区，只采用有效的指数(请记住，每个城市只访问一次，不在禁忌列表中)。

问题2

so then how do we pick a different neighborhood next time?

是的，最佳候选者被推入列表中，而不是它的邻居，所以它会找到新的邻居，不会陷入无限循环。

例如，路径 X 将给出邻居 Y 和 Z，其中(假设)Z 是最好的，因此 Z 将被推入 Tabu 列表中(并且 X 已经在列表中)，所以现在 Z 不会去找 X，因此会寻找新的更好的邻居。