基于改进禁忌搜索算法求解TSP问题

摘要：

TSP问题作为一个典型的组合优化问题,多年来众多学者都对其展开了深入研究,以期寻找到一个最优算法来应用到实际生活中.由于TSP问题是一个NP难题,因此一般使用目前较为普遍的智能优化算法进行计算其最短路径,禁忌搜索算法便是其中之一.该算法通过引入禁忌表和特赦准则来避免搜索陷入局部最优,在各个行业中均获得了广泛应用.但是,该算法也存在一定的缺陷,比如对初始解的依赖性.因此,本文为了克服该缺点,将传统的禁忌搜索算法进行了改进,借助遗传算法来对初始解进行优化,进而得到更优解.通过案例仿真表明,加入遗传算法后,实验结果有了很大的改善,得到了更优的路线方案,缩短了总旅程的距离,验证了算法改进后的有效性和可行性.

关键词：TSP问题、禁忌搜索算法、遗传算法、组合优化

分类号：TP301(计算技术、计算机技术)

在线出版日期：2022-04-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：154-157