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

Solving TSP Problem Based on Improved Tabu Search Algorithm

作　　者：唐文秀 Tang Wenxiu(North China Electric Power University,Beijing 102206,China)

机构地区：[1]华北电力大学,北京102206

出　　处：《科学技术创新》2022年第4期154-157,共4页Scientific and Technological Innovation

摘　　要：TSP问题作为一个典型的组合优化问题,多年来众多学者都对其展开了深入研究,以期寻找到一个最优算法来应用到实际生活中。由于TSP问题是一个NP难题,因此一般使用目前较为普遍的智能优化算法进行计算其最短路径,禁忌搜索算法便是其中之一。该算法通过引入禁忌表和特赦准则来避免搜索陷入局部最优,在各个行业中均获得了广泛应用。但是,该算法也存在一定的缺陷,比如对初始解的依赖性。因此,本文为了克服该缺点,将传统的禁忌搜索算法进行了改进,借助遗传算法来对初始解进行优化,进而得到更优解。通过案例仿真表明,加入遗传算法后,实验结果有了很大的改善,得到了更优的路线方案,缩短了总旅程的距离,验证了算法改进后的有效性和可行性。As a typical combinatorial optimization problem, TSP problem has been deeply studied by many scholars for many years in order to find an optimal algorithm to be applied to real life. Because TSP problem is a NP hard problem,the current common intelligent optimization algorithm is generally used to calculate its shortest path, and tabu search algorithm is one of them. The algorithm avoids the search from falling into local optimization by introducing tabu table and Amnesty criterion, which has been widely used in various industries. However, the algorithm also has some defects,such as the dependence on the initial solution. Therefore, in order to overcome this shortcoming, this paper improves the traditional tabu search algorithm, optimizes the initial solution with the help of genetic algorithm, and then obtains a better solution. The case simulation shows that after adding the genetic algorithm, the experimental results have been greatly improved, a better route scheme is obtained, the total journey distance is shortened, and the effectiveness and feasibility of the improved algorithm are verified.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]