一种求解旅行商问题的交叉禁忌搜索(英文)

摘要

提出一种改进的禁忌搜索(TS)—交叉禁忌搜索(CTS),并用于混合优化问题旅行商问题(TSP)的求解。CTS主要包括集中策略和分散策略。采用选择规律的改变促进移动的混合,集中策略增强了算法的局部搜索能力;分散策略是用于开辟新的搜索空间。在CTS中,采用遗传算法中的交叉算子作为分散策略,优解选择法作为集中策略。CTS、标准TS、带集中策略的TS和蚁群算法用于求解相同的TSP例子,所用例子都是来自TSPLIB例子库和Fogel路径。求解结果显示了CTS的性能优于其它算法。