4

我试图通过将它与爬山算法一起使用来理解禁忌搜索，以解决旅行商问题。

我了解“纯”爬山算法，但禁忌搜索如何更改此算法对我来说不是很清楚。

爬山示范：

假设我们有 6 个城市A,B,C,D,E,F，我们随机选择一个初始状态：(A,B,C,D,E,F)，旅行成本为 120。

然后我将选择一组相邻状态（通过将第一个元素与第二个、第三个、第四个等交换），并计算每个状态的旅行成本：

(B,A,C,D,E,F) = 110   /* <120; mark as optimal */
(C,B,A,D,E,F) = 127
(D,B,C,A,E,F) = 145
(E,B,C,D,A,F) = 102   /* <110; mark as optimal */
(F,B,C,D,E,A) = 80    /* <102; mark as optimal */

现在我们找到了一个局部最优值：(F,B,C,D,E,A)。

禁忌搜索如何改变上述算法？如果您可以演示一两次迭代，我将非常感激。

4

2 回答 2

5

与禁忌搜索 (TS) 的区别在于它保留的禁忌列表。以及它如何影响搜索。生成此类禁忌列表的最简单方法是跟踪最近的搜索并将它们包含在禁忌列表中，以便算法“探索”不同的可能性。禁忌列表启发式的一个示例是：如果您从城市 D 到城市 E 的迭代次数少于“n”次，其中“n”是要存储的先前解决方案的数量，它被添加到禁忌列表中（禁忌中的元素列表有过期）。

它执行的步骤与爬山几乎相同：

  1. 它选择一个初始状态（可能是随机的）并将其设置为最佳选项。

  2. 它进入一个循环，检查是否满足用户给出的中断条件（可以是阈值或此示例的旅行成本）。

  3. 它创建一个空的候选列表。给定邻居中不包含禁忌元素的每个候选者都被添加到这个空的候选者列表中。

  4. 它会在此列表中找到最佳候选者，如果它的成本优于当前最佳，则将其标记为解决方案。

  5. 如果禁忌列表上的禁忌数量已达到最大禁忌数量（您正在定义数字），则禁忌过期。列表中的禁忌按它们输入的顺序过期.. 先进先出。

这个过程会不断重复，直到满足用户定义的阈值。希望这有助于理解它是如何工作的:))

于 2013-12-04T15:02:03.547 回答
4

免责声明：此答案基于链接 [参考-1]Geoffrey De Smet分享的评论中指出这里。学分应该归他所有。

下面显示的两张图片帮助我了解禁忌搜索如何改变爬山算法。

爬山

爬山 （来源：OptaPlanner 用户指南）

禁忌搜索

禁忌搜索 （来源：OptaPlanner 用户指南）

参考：

[Reference-1] JBoss.org 社区文档。OptaPlanner 用户指南。[在线] 位于： http ://docs.jboss.org/drools/release/latest/optaplanner-docs/html_single/index.html 。[访问于 12 月 13 日 07 日]。

于 2013-12-07T09:58:54.283 回答