基于遗传算法求解TSP问题（旅游路径规划，Python实现，超详细，可视化， 结果分析）
ps：作者是很⽤⼼写的，如果觉得不错，请给作者⼀点⿎励噢！（点赞收藏评论噢）
基于遗传算法求解TSP问题
铝制工艺品
摘要 巡回旅⾏商问题（TSP）是组合优化中的经典问题。常见的TSP问题求解算法例如穷举法、贪⼼算法、动态规划算法不适⽤于求解⼤量城市或是容易得到局部最优解，所以更多优化算法应运⽽⽣。⽂章将基于遗传算法的原理和传统求解步骤依据具体的TSP问题做出优化改进求解51个城市最短路径规划问题，并借助python语⾔实现交互功能（⽤户可从51个城市中⾃⾏选择旅游城市，程序将为⽤户推荐最佳旅⾏⽅案）。 关键词 TSP 遗传算法 51个城市 最短路径规划 交互
第⼀章绪论
1 遗传算法
1.1 背景介绍
遗传算法是模拟⽣物在⾃然环境中的遗传和进化过程⽽形成的⼀种⾃适应全局优化概率搜索算法，遗传算法从任意⼀个初始化的体出发，通过随机选择、交叉和变异等遗传操作，使体⼀代⼀代地进化到搜索空间中越来越好的区域，直⾄抵达最优解，其基本思想是基于达尔⽂的进化论和孟德尔的遗传学说。遗传算法的概念最早由Bagley J．D于1967年提出，并于1975年被美国密歇根⼤学教授HOllan及其学⽣开始其理论和⽅法的系统性研究。此后，越来越多的学者参与到遗传算法的研究中，针对遗传算法的缺陷提出解决策略和改进算法。⽬前，遗传算法的研究主要集中在四个⽅⾯：基础理论、遗传策略、编码⽅式、并⾏化。由于遗传算法能够被简单编码应⽤于复杂问题、其启发式搜索特性能够很⼤概率到问题的全局最优解，它被⼴泛应⽤于各个领域，涉及⼯业、经济管理、交通运输、⼯业设计等。但是，尽管遗传算法在解决实际问题中取得了不错的成绩，其基础理论研究⾄今还未取得突破性进展，数学基础仍然不够完善，尚不能解释清楚参数设置对算法性能的影响、算法收敛性、早熟现象和欺骗问题等[1-4]。
1.2 优点
1. 对可⾏解表⽰的⼴泛性，⽆论什么结构对象例如矩阵、数列等，遗传算法都能对其进⾏编码得到基因个体；
2. 搜索从体出发，具有潜在的并⾏性，可以进⾏多个个体的同时⽐较；
3. 搜索使⽤评价函数启发，过程简单；
222au
4. 使⽤概率机制进⾏迭代，具有随机性；
5. 具有可扩展性，容易与其他算法结合；
6. 遗传算法在搜索过程中有很⼤概率可以到全局最优解。
1.3缺点
1、遗传算法的编程实现复杂，需要进⾏编码解码操作；
2、选择、交叉、变异三个算⼦的实现有许多参数，这些参数的选择严重影响解的品质,⽽⽬前这些参数的选择⼤部分是依靠经验；’
3、没有能够及时利⽤⽹络的反馈信息，故算法的搜索速度⽐较慢，要得要较精确的解需要较多的训练时间；
4、算法对初始种的选择有⼀定的依赖性；
5、算法的并⾏机制的潜在能⼒在⽬前的研究进展中还没有得到充分的利⽤。
2 TSP问题
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问题的实现
1 问题描述
2 算法实现步骤
2.1 初始化
纸碗
初始化数据：读⼊数据源，将坐标转换为距离矩阵（标准化欧式距离）
初始化对象：种规模m、运⾏代数n、变异概率
初始化种：⽣成m条路径（编码⽅式：符号编码）
说明：种初始化的编码⽅式有多种，常见的有⼆进制编码、格雷码编码、实数编码和符号编码。编
码⽅式具有启发性，缺乏理论基础来判断各种编码的好坏，常根据实际问题和经验来确定，本算法采⽤符号编码。
2.2.计算种适应度
适应度函数f=1/〖distance(x)〗^15
说明：适应度函数会影响选择压，选择压过⼤，会造成⼏个较好的可⾏解迅速占满整个体，选择压过⼩，会让算法变成纯粹的随机⾏为。本算法对适应度函数进⾏15次⽅的尺度变换，就是为了避免选择压太⼩，赌的选择失去意义变成等概率随机选择。
2.3计算累计概率
计算每个个体适应度占适应度总和的⽐例并计算累计概率。
2.4迭代
1.选择算⼦：运⽤赌选择法，与传统赌选择法不同的是，本算法不选择重复个体充当⽗母，即如果选择出来的个体已经被选过⼀次，下⼀次再选到它就直接抛弃。这样最后选出来的个体数量m1<=m。
2.交叉算⼦：从赌选择出来的⽗母中随机选择两个不同个体充当⽗母，随机产⽣两个变异位置，交换两个交叉点之间基因形成两个新的⼦代放⼊种中，直到种数量恢复到初始种数⽬m
3.变异运算：对种中的每⼀个个体来说，产⽣⼀个随机数，若该随机数⼩于变异概率即产⽣变异。变异的⽅法是在染⾊体上产⽣两个变异点，将变异点间的基因⽚段倒序即完成变异。
4.更新最优解。
5.将新种复制到旧种中，准备下⼀代进化（迭代）。
3 实验结果
⽂件：支撑梁
第⼀列为地点名称，第⼆，三列为地点的经纬度
地点名称
ps：程序具有泛化性，将这两个⽂件⾥的内容修改即可得到不同地⽅的旅游路径规划
3.1初始设定
先根据经验值（种⼤⼩：20 ~ 100，迭代次数：500，变异概率：0.0001~0.1）对初始化参数进⾏设定取种⼤⼩100，迭代次数500，变异概率0.1，选择51个城市，设置⽅案数量为1，运⾏20次。
3.2 调参
调整参数，观察实验结果随参数的变化，通过反复尝试获得51个城市路径近似最优解
根据实验规划得到的最优路径为475.1153
具体实验情况如下图所⽰：
运⾏程序，点击需要旅游的城市和需要输出的⽅案数量，这⾥选择了51个城市，输出⼀个⽅案，程序最后运⾏完会给出⼀条路径规划路线。
穿孔塞焊
零时刻
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议