使用禁忌搜索算法解决旅行商问题

Question

我正在尝试使用Tabu搜索与Hill Climbing算法解决旅行商问题，以理解Tabu搜索。

我了解“纯”Hill Climbing算法，但是Tabu搜索如何改变这个算法对我来说不是很清楚。 Hill Climbing演示： 假设我们有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)。

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

- Dilini

---

请注意，有不同类型的禁忌。例如，您可以将解决方案状态 (ABCDEF)、移动 (A在B之前)或涉及的实体 (A) 设为禁忌。然后，简单地不接受任何具有相同禁忌类型的移动（除非它被吸收）。在我的实验中，我通过将实体设置为禁忌获得了最佳结果。而将解决方案状态设为禁忌效果很差：无法扩展。 - Geoffrey De Smet

@GeoffreyDeSmet分享的链接真是太棒了！我现在终于明白禁忌搜索的原理了。非常感谢Geoffrey！希望像我这样拼命寻找简单例子来理解禁忌搜索的人能够从Google搜索中找到那篇文章。 - Dilini

Answer 1

与 Tabu 搜索的区别在于它所保持的禁忌列表，以及它如何影响搜索。生成这样一个禁忌列表的最简单方法是跟踪最近的搜索，并将它们包括到禁忌列表中，以便算法 “探索” 不同的可能性。禁忌列表启发式的一个例子是：如果你从城市 D 去过城市 E 的时间小于 “n” 次迭代，其中 “n” 是要存储的前面解的数量，则会将其添加到禁忌列表中（禁忌列表中的元素有过期时间）。

它执行的步骤与爬山算法非常相似：

1. 选择一个初始状态（可以随机选择）并将其设置为最佳选项。
2. 进入循环，检查用户给定的终止条件是否已满足（对于此示例，可以是阈值或旅行成本）。
3. 创建一个空候选列表。将不包含禁忌元素的每个候选者添加到给定邻域中的此空候选者列表中。
4. 找到此列表上的最佳候选者，如果其成本比当前最佳成本更好，则将其标记为解决方案。
5. 如果禁忌列表上的禁忌数量达到了最大禁忌数（由您定义的数量），则会过期一个禁忌。列表上的禁忌按照先进先出的顺序过期。

该过程重复进行，直到满足用户定义的阈值为止。希望这有助于理解它是如何工作的 :))

- Wald

---

非常感谢您的有益回答，Wald！那么在下一次迭代中，我们会随机选择另一个状态？而且这个状态不应该是禁忌状态...我理解得对吗？ - Dilini

不，初始状态只选择一次，然后根据每个邻居创建候选列表：邻居（B，A，......）他的候选人可以是所有其他城市按顺序移动。如果当前禁忌列表中不存在它，则进入候选列表；如果存在，则跳过它（现在取决于算法的阈值）。 - Wald

它在列表中找到最佳候选项，如果其成本比当前最佳成本更好，则将其标记为解决方案。所以我们不接受更差的解决方案吗？如何避免局部最优解？我认为这个说法是不正确的。 - Kasper Ziemianek

Answer 2

免责声明: 本回答基于链接[参考-1]，由Geoffrey De Smet分享，并在他的评论中指出此处。应该归功于他。

下面的两张图片帮助我理解Tabu Search如何改变山爬算法。

山爬

(来源：OptaPlanner 用户指南)

Tabu Search

(来源：OptaPlanner 用户指南)

参考文献：

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

- Dilini