标签: tabu-search

能帮助我理解这个禁忌搜索页面7示例:

TS是一种数学优化方法,属于基于轨迹的技术类.禁忌搜索通过使用描述访问过的解决方案的内存结构来增强本地搜索方法的性能:一旦确定了潜在的解决方案,就会将其标记为"禁忌"("禁忌"是同一单词的不同拼写),以便算法不会反复访问该可能性.禁忌搜索归功于Fred W. Glover

我不明白为什么使用上三角形,为什么这样:

禁忌结构现在显示交换模块4和5的位置被禁止3次迭代.在这一步中最有进步的举措是交换3和1以获得2的增益.

你能解释为什么三角形和为什么是上面的陈述？

???

我试图通过使用Hill Climbing算法来理解禁忌搜索,以解决旅行商问题.

我理解'纯' 爬山算法,但Tabu搜索如何改变这个算法对我来说不是很清楚.

爬山示范:

让我们说,我们给了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).

Tabu搜索如何改变上述算法？如果你能展示一两次迭代,我将非常感谢.