0

当试图了解禁忌搜索如何应用于旅行推销员时，我很难理解邻域是如何生成的。如果我们从维基百科看这个伪代码：

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

4

1 回答 1

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 将被推入禁忌列表（并且 X 已经在列表中），所以现在 Z 不会去找到 X，因此会寻找新的更好的邻居。

于 2019-03-27T12:11:01.363 回答