分层递进的改进聚类蚁群算法解决TSP问题

来源:用户上传      作者:粱艺琼

　　摘要：现在社会不断的发展和进步，关于旅行商的问题（TSP）规模也在不断地变多，传统的蚁群算法已经不能满足现在的要求，在工作的时候经常会出现一些力不从心的情况出现，在这样的背景下，人们开始慢慢找到一些新的解决办法，分层递进就是这个时候出現的产物。分层递进能够有效地解决TSP的问题。分层递进算法是人们根据分工合作的原理想出来的一种方法。
　　关键词：分层递进;蚁群算法;TSP问题
　　中图分类号：TP393 文献标识码：A
　　文章编号：1009-3044（2020）05-0197-03
　　开放科学（资源服务）标识码（OSID）：
　　TSP问题属于一种NP难问题。分析NP难问题的时候主要依靠的是仿生进化思想，仿生进化思想中主要以蚁群算法为主。蚁群算法最开始的时候是在一个博士论文中提出的结论。从1992年提出到现在，研究的人们一直在不断地分析和改善蚁群算法，争取用最好的让蚁群算法用最好的状态来解决TSP问题。
　　1 蚁群算法的历史
　　传统的蚁群算法虽然也能够解决TSP出现的问题，凡是在解决的时候会花费很多的时间，在运算上也有很大的难度，所以更多的研究者开始希望能够找出一些多种智能的方法来提高运算的性能。有的研究者认为，蚁群算法应该和30pt-起合作使用，通过30pt算法来提高蚁群算法的一个准确度，这样就能减少在计算时候出现的一些误差情况。但是这样合作的算法有一个缺点就是在计算的时候需要大量的仿真设备来支持，这样就会在一定程度上加大工作的成本。还有的研究者认为：可以利用粒子群算法来解决蚁群算法出现的漏洞，进而给蚁群算法找到更多的出路，之后在用30pt算法来优化，这样的算法虽然解决了TSP问题的解经度，但同时也增加了运算的时间，有的时候如果TSP的问题增加规模的时候还会影响运转。还有的人认为可以把融合遗传算法和模拟退火等方法混合在一起解决TSP的问题。具体的办法就是首先用模拟退火优化最开始的路径，通过一段时间之后在用粒子群算法进行优化，优化出来的信息素在进行迭代运行。
　　这样综合的方法虽然能解决TSP出现的问题，但还是不能缩短运算的时间。还有的人认为可以通过改进蚁群算法里面的信息素更新来解决存在的TSP问题，这样除了能够加快运算的速度，还能扩大种群的多样性，让算法的搜索能力变大，但是还是不能解决计算的复杂性问题。在无数次的试验之后最终人们终于找出一种办法就是利用分工合作的方式把一些相对来说比较大的TSP案例进行一个分组归纳在运用蚁群算法来解决TSP问题，这样的方法既能保证解决问题的精准度又能加快算法运算的时间，还能降低算法的时间复杂度，是目前为止最好的解决TSP问题的方法。
　　2 关于TSP问题的内容
　　TSP问题是典型的组合优化问题，通过一些数学计算的方法整编、分组、排序处理一些离散的事情。TSP问题的前提是只给旅行者在特定的城市中拜访一次的机会。给定的城市数量越大就会增加越多的空间复杂度和时间复杂度。在解决TSP问题的时候一般可以通过两种方法：精确算法和启发式的算法。精确算法适合一些小规模的TSP问题，启发式算法适合一些大规模的TSP问题。精确算法包含很多的算法，最常用的就是蚁群算法，蚁群算法的出现给TSP问题提供更多的帮助。
　　3 蚁群算法解决TSP问题的过程
　　1）蚁群算法解决TSP问题的公式为：
　　在根据公式的要求设置一个最大的迭代次数，这样在运行迭代次数达到最大值的时候就可以结束运行，最后获得一个最优解的算法。如果在计算的时候有一些停滞的现象发生，就需要重新开始运行，最后达到想要的要求。
　　2）密度峰聚类算法：
　　密度峰聚类算法就是在一个数据集里面，有一些地局部密度的数据点包围了聚类中心，这些地局部密度的点就会和一些高局部密度的点出现很大的距离。具体的局部密度公式为：与高密度点之间的距离公式为：
　　3） 30pt算法：
　　优化TSP问题的时候还可以使用30pt算法。在运算的时候能够准确地找出和组合出一些节点进行连接，重新组合后的连接情况要及时的记录。在对比重新组合后的数据和最初的数据进行分析，找出一个最合适的线路。
　　4）粒子群算法：
　　要想适应社会可以选择粒子群算法，这种算法在计算的时候会先设置一组种群粒子拜访指定区域，这样就会让每一个位置都有能够计算的适应值。在计算的时候主要的公式为：
　　4 改进算法
　　随着TSP问题在不断扩大，蚁群算法的复杂程度也会相应地进行一定程度的提升。当TSP问题的一个节点数超过100的时候就很难找到蚁群算法的一个平衡点，在TSP问题中城市节点小于40的时候是运行时间最佳和解决问题最佳的时候。
　　1）改进后的密度峰聚类算法：
　　改进后的密度峰聚类算法主要公式为：
　　yi =ρi xδi
　　2）改进的蚁群算法：
　　改进的蚁群算法公式为：
　　τij（t+1） =（l -ρ）τij（t）+p△rij（t）
　　3）改进算法的流程图：
　　如图l是DP-ACS算法解决TSP问题的步骤：
　　从图中可以知道改进算法首先要先设置一个初始的参数值，然后在根据问题制定相应的节点坐标，之后在根据截断距离的定义计算，最后根据改进的密度蜂聚类算法确定一个拐点，之后根据选举出的聚类中心变成簇。因为每个簇包含的节点都不一样，所以要用粒子群的算法来进行设定，最后找出解决问题的方法。 　　之后把所有形成的二类TSP问题进行重组，最后形成全局解路径，之后再把二类的TSP问题还原成初始的TSP问题，解路径在区域连接重新融合。最后将重新连接后的全局路径通过30pt的处理，达到重新连接优化的目的，再看算法辨别有没有达到预先设置的要求，如果达到了就可以退出，如果没有就需要注意如果在运行的时候出现停止的现象，就需要从最开始进行操作。
　　41 DP-ACS算法原理图：
　　如图2是DP-ACS的算法原理图：
　　5）仿真实验结果分析：
　　本次实验采用的是两种数据进行，一种是小规模的，一种是大规模的。如表1所示是通过粒子群算法找到的一些关于不同问题集的蚁群算法的信息素：
　　如表2是设置蚁群算法的初始参数值和算法运行的迭代门限值：
　　6） DP-ACS算法解决小规模的TSP问题：
　　如图3是运行10次之后的一个对比：
　　从图中可以知道：经过密度蜂聚类算法处理之后虽然问题的规模集节点变少，但是还是需要一定的时间。当TSP案例的城市规模小于100的时候，算法之间的运行时间并没有很大程度的差距，现在城市规模慢慢变大，这个时候就能体现出密度峰聚类算法的一个优势。
　　7） DP-ACS算法处理大规模TSP问题：
　　对于大规模的TSP问题，可以通过密度蜂聚类算法来进行处理，之后在通过蚁群算法来进行运算形成一个二类TSP问题的路径图，通过找到两个聚类簇之间的邻节点，切割重组之后形成最优的路径图。在计算的时候如果发现是大规模TSP问题的时候就可以使用密度蜂聚类算法来进行解决。
　　在解决大规模TSP问题的时候，经过改进之后也可以用密度蜂聚类算法来进行计算，这样就能减轻具备自适应信息素里面的更新机制还有蚁群算法运算的复杂度。在解决一些大规模的TSP问题的时候使用蚁群算法能够快速地找到一个问题的解决思路，同时还不会在计算的时候出现局部优化的情况。当所有的全局路径线路都经过处理之后，就能提高解精度。
　　8）算法收敛速度和多样化的分析：
　　在分析算法收敛速度和多样化的时候，可以先选择一些TSP的问题案例进行分析，如图4所示：
　　可以通过图4显示知道：图a能够知道在计算的时候，运行500次的时候是全局最优解的时候，虽然ACS算法的多样性非常强，但是并不是全局最优解的一种计算方法。圖b能够知道在运行前180次的时候路径解都在不断优化，但是从80次的时候就收敛了算法然后找到最优解的方法。从图c能够知道DP-ACS算法表现的时候全局多样性会变得更加的优越，并且算法在收敛的时候也会变慢和真实的结果就会差得非常远。从图d能够知道，如果选择的TSP案例出现增加的时候，DP-ACS算法就是最好的计算方法，在种群的时候也会有更多的多样性，同时也不会出现早收敛的现象。但是ACS算法和MMAS算法在运行300次的时候都会陷入局部最佳的情况，这个时候就不会提高算法解精度。
　　如图5是ACS算法和DP-ACS算法在解决问题的时候的算法多样性的表现。
　　从图5a能够知道，ACS算法在运行前200次的时候会有非常大的上升趋势，这个时候的种群多样性也比较好。但是发现图b表现出来的种群多样性会更好，这个时候DP-ACS算法在前700次运行的时候，前后迭代运算的时候也能一直是不断上升的趋势，这个时候就能够证明DP-ACS算法在一直不断地走在优化解路径的道路上。对于这两图能够发现：DP-ACS算法在每次迭代的时候都比ACS算法的标准值要差很多，在第400次的时候，DP-ACS的标准差数要比ACS算法的标准差相差500，这就说明DP-ACS算法中运行的时候蚂蚁找到的路径解数值会相距非常大，同时还能更好地表现出种群的多样性。
　　9）分析时间复杂度：
　　如表3是改进算法与其他算法运行的时间：
　　从图中的信息能够知道：当案例城市节点数量上升的时候表3中的算法运算时间也在不断上升。但是因为没有经过粒子群的处理，所以运算的时间变短。并且案例规模不断增加的时候更加能够体现改进算法的最大优势。DP-ACS算法需要的运行时间就是衡量算法优化TSP问题性能的指标。
　　5 结论
　　现在TSP问题一直在不断增加，虽然蚁群算法能解决这些问题，但是在解决问题的时候还会有一些不足，这些不足需要时间慢慢进行更新。还可以用密度蜂聚类的算法把这些原始的TSP问题分成一些比较小的簇，这样这些簇就能更好的用蚁群算法来进行计算。同时这些二类的TSP问题还能利用闭合的解路径利用一些近邻点切割断开之后重组之后就变成一些新的原始TSP问题的解路径回路。通过这些实验的数据能够知道：到现在为止解精度和收敛速度最好的一种算法就是DP-ACS算法。特别需要注意的是当TSP问题规模越来越大的时候，算法的优越感就更能体现出来。在以后的日子，还需要把蚁群算法研究得更加深入，除此之外还需要把二类的TSP问题怎么形成的路径进行有效的研究，一起构建一个新型的全局最优路径。
　　参考文献：
　　[1]任珂欣，王兴伟，马连博，等.蚁群分工启发的ICN负载均衡机制[J].计算机科学与探索，2018，12（7）：1109-1116.
　　[2]姜道银，葛洪伟，袁罗.一种动态划分的混合连续域蚁群优化算法[J].计算机工程与应用，2018，54（7）：144-151. [3]刘中强，游晓明，刘升.一种启发式动态信息素更新策略的蚁群算法[J].计算机工程与应用，201 8，54（20）：20-27.
　　[4]高妮，贺毅岳，申元，等.漏洞类型聚类的层次化漏洞修复模型[J].计算机科学与探索，2018，12（2）：274-281.
　　[5]马学森，宫帅，朱建，等.动态凸包引导的偏优规划蚁群算法求解TSP问题[J].通信学报，2018，39（10）：59-71.
　　【通联编辑：唐一东】
转载注明来源:https://www.xzbu.com/8/view-15180327.htm