DOI：10.3969/j.issn.1672-3872.2025.13.036
作 者：周啟涛（江铃汽车股份有限公司，江西 南昌 330001）
摘 要：【目的】解决基本遗传算法求解TSP问题时存在的局部寻优能力较差、易出现早收敛和局部最小等问题。【方法】提出了一种改进的遗传算法。首先，引入种群大变异策略，有效避免算法“早熟”；其次，进行选择、交叉和变异三大步骤；最后，加入逆转进化操作，改善遗传算法的局部搜索能力。此外，选取TSPLIB测试库中Barma14和Oliver30两种数据对几种遗传算法进行了仿真测试。【结果】改进后的遗传算法求解TSP问题时具有更好的寻优能力，但此算法仍存在一定的局限性，当TSP问题中城市规模进一步扩大时，算法一般只能求解最优解的近似解。【结论】未来研究可尝试运用其他智能算法到改进后的遗传算法中，进一步提高算法的寻优能力。
关键词：遗传算法；TSP；NP完全问题
An Improved Genetic Algorithm for Solving TSP Problem
Author: Zhou Qitao (Jiangling Motors Co., Ltd., Nanchang 330001, China)
Abstract: [Objective] To solve the problems of poor local optimization ability, easy early convergence, and local minima in solving TSP problems using basic genetic algorithms. [Method] An improved genetic algorithm was proposed. Firstly, the introduction of a population wide mutation strategy effectively avoids algorithm “premature convergence”. Secondly, the three major steps of selection, crossover and mutation are carried out. Finally, a reverse evolution operation is added to improve the local search capability of the genetic algorithm. In addition, simulation tests were conducted on several genetic algorithms using Barma14 and Oliver30 data from the TSPLIB test library. [Result] The improved genetic algorithm has better optimization ability when solving the TSP problem, but this algorithm still has certain limitations. When the city size in the TSP problem further expands, the algorithm can generally only solve the approximate solution of the optimal solution. [Conclusion] Future research can attempt to apply other intelligent algorithms to the improved genetic algorithm to further enhance its optimization capability.
Keywords: genetic algorithm; TSP; NP-complete problem
引文信息：[1]周啟涛.求解TSP问题的改进遗传算法[J].南方农机，2025，56(13)：140-142.
查看全文请下载PDF文件↓
