我试图通过使用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搜索如何改变上述算法?如果你能展示一两次迭代,我将非常感激。
与Tabu搜索(TS)的不同之处在于它保留的禁忌列表。以及它如何影响搜索。生成此类禁忌列表的最简单方法是跟踪最近的搜索并将其包含在禁忌列表中,以便算法“探索”不同的可能性。禁忌列表启发式的一个例子是:如果来自城市D你去过城市E少于'n'迭代前,其中'n'是先前存储的解决方案的数量,它被添加到禁忌列表中(禁忌中的元素)列表已到期)。
它执行的步骤与爬山的步骤非常相似:
并且该过程重复直到满足用户定义的阈值。希望这有助于理解它是如何工作的:))
免责声明:这个答案基于link [参考文献1],Geoffrey De Smet在他的评论中指出here。积分应归他所有。
下面显示的两个图像帮助我理解Tabu搜索如何改变Hill Climbing算法。
参考:
[参考文献-1] JBoss.org社区文档。 OptaPlanner用户指南。 [在线]可在:http://docs.jboss.org/drools/release/latest/optaplanner-docs/html_single/index.html。 [于12月7日访问]。