ps：作者是很用心写的，如果觉得不错，请给作者一点鼓励噢！（点赞收藏评论噢）

摘要 巡回旅行商问题（TSP）是组合优化中的经典问题。常见的TSP问题求解算法例如穷举法、贪心算法、动态规划算法不适用于求解大量城市或是容易得到局部最优解，所以更多优化算法应运而生。文章将基于遗传算法的原理和传统求解步骤依据具体的TSP问题做出优化改进求解51个城市最短路径规划问题，并借助python语言实现交互功能（用户可从51个城市中自行选择旅游城市，程序将为用户推荐最佳旅行方案）。 关键词 TSP 遗传算法 51个城市 最短路径规划 交互

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，遗传算法从任意一个初始化的群体出发，通过随机选择、交叉和变异等遗传操作，使群体一代一代地进化到搜索空间中越来越好的区域，直至抵达最优解，其基本思想是基于达尔文的进化论和孟德尔的遗传学说。遗传算法的概念最早由Bagley J．D于1967年提出，并于1975年被美国密歇根大学教授HOllan及其学生开始其理论和方法的系统性研究。此后，越来越多的学者参与到遗传算法的研究中，针对遗传算法的缺陷提出解决策略和改进算法。目前，遗传算法的研究主要集中在四个方面：基础理论、遗传策略、编码方式、并行化。由于遗传算法能够被简单编码应用于复杂问题、其启发式搜索特性能够很大概率找到问题的全局最优解，它被广泛应用于各个领域，涉及工业、经济管理、交通运输、工业设计等。但是，尽管遗传算法在解决实际问题中取得了不错的成绩，其基础理论研究至今还未取得突破性进展，数学基础仍然不够完善，尚不能解释清楚参数设置对算法性能的影响、算法收敛性、早熟现象和欺骗问题等[1-4]。

1、遗传算法的编程实现复杂,需要进行编码解码操作； 2、选择、交叉、变异三个算子的实现有许多参数，这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验；’ 3、没有能够及时利用网络的反馈信息,故算法的搜索速度比较慢，要得要较精确的解需要较多的训练时间； 4、算法对初始种群的选择有一定的依赖性； 5、算法的并行机制的潜在能力在目前的研究进展中还没有得到充分的利用。

TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值[9]。迄今为止，TSP问题没有有效算法，研究者猜想NP完全问题(NP-Complete或NPC)和NP难题(NP-Hard或NPH)不存在有效算法，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法，所以研究相应的有效算法寻找其最优或近似最优解具有重要的理论意义。目前求解 TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法或者多个算法相结合的混合算法等[7-8]。随着研究的进行，TSP问题的求解不断突破困难，不断带来令人惊喜的成果。1980年crowder和Padberg求解了318个城市的问题，1987年Padberg和Rinaldi将这个城市数增加到了2392个。1992年，美国Rice大学的CRPC研究小组用50台工作站使用了基于“cutting planes"算法解决T3038个城市的问题，被《发现杂志》评为当年的前50条科学新闻。1994年，Applegate、Bixby、Chvatal等人使用若干台SPARCT作站组成的机群用了3-4年的CPU时间解决了7397个城市的TSP问题。1998年，CRPC研究小组使用三台Digital AlphaServer 4100s(12个处理器) 组成的集群和32台Pentium—11个人计算机解决了美国13，509个城市组成的TSP问题。 2003年2月，Hisao Tamaki使用了路径融合同]Lin-Kernighan启发的变种相结合的方法发现TTSPLIB中pla33810的一个次优解。2004年2月Keld Helsgaun发现了pla85900问题的一个次优解[5-6]。

遗传算法求解TSP问题的实现

初始化数据：读入数据源，将坐标转换为距离矩阵（标准化欧式距离） 初始化对象：种群规模m、运行代数n、变异概率 初始化种群：生成m条路径（编码方式：符号编码） 说明：种群初始化的编码方式有多种，常见的有二进制编码、格雷码编码、实数编码和符号编码。编码方式具有启发性，缺乏理论基础来判断各种编码的好坏，常根据实际问题和经验来确定，本算法采用符号编码。

适应度函数f=1/〖distance(x)〗^15 说明：适应度函数会影响选择压，选择压过大，会造成几个较好的可行解迅速占满整个群体，选择压过小，会让算法变成纯粹的随机行为。本算法对适应度函数进行15次方的尺度变换，就是为了避免选择压太小，轮盘赌的选择失去意义变成等概率随机选择。

计算每个个体适应度占适应度总和的比例并计算累计概率。

1.选择算子：运用轮盘赌选择法，与传统轮盘赌选择法不同的是，本算法不选择重复个体充当父母，即如果选择出来的个体已经被选过一次，下一次再选到它就直接抛弃。这样最后选出来的个体数量m1