algorithm - 使用禁忌搜索解决旅行商问题

Question

我试图通过将禁忌搜索与爬山算法结合使用来理解旅行商问题。

我了解“纯”爬山算法，但我不太清楚禁忌搜索如何改变该算法。

爬山示范:

假设，我们有 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)。

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

Answer 1

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

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

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

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

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

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

5. 如果禁忌列表中的禁忌数已达到最大禁忌数(您定义的数量)，则禁忌到期。列表中的禁忌按照输入的顺序过期。先进先出。

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