基于T-ACO算法的旅行商问题求解优化研究

来源:用户上传      作者:

　　摘  要：为了有效求解旅行商问题，本文提出了一种基于T分布的改进蚁群算法。针对基本蚁群算法易陷入局部最优、寻优精度低等缺陷，在优化过程中，在信息素更新原则上，引入T分布，有益于基本蚁群算法弥补其不足。在基本蚁群算法中增加了信息素的突变，使得蚂蚁群的多样性提高，从而跳出局部最优的限制。与此同时，T-ACO算法在旅行商问题搜寻精度与收敛速度方面也得到了提高。对T-ACO求解旅行商问题的性能进行了实验仿真，实验分析表明，T-ACO算法有更好的寻优能力。
　　关键词：T分布;蚁群算法;旅行商问题;优化
　　中图分类号：TP391.9     文献标识码：A
　　1   引言（Introduction）
　　旅行商问题由Ramser B博士在1959年根据车辆路径的选择问题提出，该问题属于数学领域的经典问题。TSP问题的实质为一个供货商为不同的需求客户送货，要求配送路径不可以重复的情况下，选择路程最短的路径作为最终的配送路径[1]。众多学者已经证明了TSP问题是一个经典的NP-hard问题。因此，近些年来，学者都将研究的重点放在求解TSP问题的算法设计上。目前解决TSP问题的方法大致分为两种，一种是包括分支定界法、线性规划法和动态规划法在内的启发式搜索算法[2]，另外一种是包括模拟退火算法[3]、禁忌搜索算法[4]、遗传算法[5]、蚁群算法[6]、遗传算法[7]，以及粒子群算法[8]等的人工智能优化算法。由于现在有众多实际问题可以转化为TSP模型[9]，因而TSP问题诸如电网规划[10]、网络优化[11]、交通运输[12]、物流配送[13]等重要领域都有着广泛的应用。
　　为了有效求解旅行商問题，本文提出了一种基于T分布的改进蚁群算法。针对基本蚁群算法易陷入局部最优、寻优精度低等缺陷，在优化过程中，在信息素更新原则上，引入T分布，有益于基本蚁群算法弥补其不足。在基本蚁群算法中增加了信息素的突变，使得蚂蚁群的多样性提高，从而跳出局部最优的限制。与此同时，T-ACO算法在旅行商问题搜寻精度与收敛速度方面也得到了提高。对T-ACO求解旅行商问题的性能进行了实验仿真，实验分析表明，T-ACO算法有更好的寻优能力。
　　2   旅行商问题（Traveling salesman problem）
　　旅行商问题可以简单描述为在给定的个城市里，每个城市只经过一次，然后回到出发点，找出使该回路最短的路径的问题。TSP问题的数学模型如下[14]：
　　
　　式中，表示指定的点集;表示边集;表示赋值图;表示点到点的距离;表示点在回路路径上，表示不在回路路径上;表示的子图，对应的约束条件保证没有任何子回路解的产生。旅行商问题的目的是为了获得一个最优回路，在该回路上，除了起点之外的每一个点只能经过一次。
　　3   T-ACO算法（T-ACO algorithm）
　　3.1   T分布
　　T分布又被称为学生分布，威廉·戈塞于1908年[15]首先推导发表，自由度为的T分布的概率密度函数为：
　　
　　根据式（5）可以卡看出，T分布的分布曲线与参数自由度有关。若越小，则T分布曲线就越平坦。若分布曲线中间部分越平坦，则多对应两侧的尾部的曲线就会凸起的越高。这就存在两种特殊的情况，一种情况为时，T分布曲线为柯西分布曲线。另外一种情况为时，T分布曲线为高斯分布曲线。T分布变异恰好融合了柯西分布变异和高斯分布变异的特点，通过不断改变自由度参数的值可以获得不同变异幅度。
　　3.2   基于T分布的蚁群算法
　　基本蚁群算法是对蚂蚁的生物学原理进行模拟后的一种人工智能优化算法。基本蚁群算法根据信息素遗留的多少来判定选择的路径，路径上遗留的信息素越多，则该路径被选择的概率就越大。
　　基本蚁群算法易陷入局部最优、寻优精度低等缺陷，为了克服上述缺陷，将T分布引入信息素更新中。由于T分布具有较好的扰动作用，使得群体多样性增加，因此能够提高算法的收敛速度，且不受局部最优的限制，增加寻得全局最优解概率。
　　为了提高收敛速度，可事先确定一个阈值，以避免蚂蚁周游一次后，较差解所带来的无效搜索。同时，为避免蚁群算法陷入局部最小，在调整信息素时，引入T分布，用以跳出局部最小点。改进后的各条路径上的信息素调整为
　　
　　其中，表示信息素挥发程度，;表示所有蚂蚁在节点与节点间的信息素浓度的总和;表示第只蚂蚁在节点和节点之间路径上释放的信息素浓度;为蚂蚁循环一次释放的信息素总量，的大小对算法的收敛速度有影响;为第只蚂蚁走过的路径长度;为T分布变量。
　　3.3   求解步骤
　　步骤1 参数初始化，包括、、及等蚁群算法参数以及T分布变异的特征参数。
　　步骤2 令，为迭代次数，将只蚂蚁随机放在座城市。
　　步骤3 根据式（9）计算蚂蚁的转移概率，选择并移动到下一个城市，同时将加入到中。
　　
　　其中，为信息素重要程度因子，反映蚂蚁间的协作能力;为启发函数重要程度因子，反映蚂蚁对于启发信息的重视程度;为启发函数表示蚂蚁从节点转移到节点的期望，，表示两点间的距离，为蚂蚁待访问的节点集合。
　　步骤4 是否满。若为否，回到步骤3，否则，继续步骤4。
　　步骤5 按式（6）—式（8）进行T分布信息素的全局更新。
　　步骤6 判断是否，若为是，重复步骤3—步骤6，否则，结束迭代，输出最优解。
　　4   实验仿真（Experimental simulation）
　　为了验证算法的有效性，利用TSPLIB标准库中的berlin52、eil76及RAT99三个测试集进行算法性能测试[16]。设置最大迭代次数，信息素重要程度因子，启发函数重要程度因子，信息素全局挥发因子，信息素释放总量。表1为在重复实验30次的情况下，ACO算法及T-ACO算法在三个测试集所获得最优解、最差解和平均值。表2为ACO算法及T-ACO算法在三个测试集所获得成功率、平均收敛代数及标准差。 　　从上述测试可以看出：在寻优能力方面，T-ACO算法在最优解、最差解及平均值都优于ACO。在收敛速度方面，T-ACO的平均收敛代数少于ACO。在稳定性方面，T-ACO标准差小于ACO。由此可以看出，T-ACO算法相对于ACO算法更有效。
　　5   结论（Conclusion）
　　为了弥补基本蚁群算法的不足，将T分布引入到蚁群算法中，提出改进的蚁群算法（T-ACO）。利用改进的蚁群算法求解旅行商问题，并将其结果与基本蚁群算法进行了对比对比发现，改进的蚁群算法在求解旅行商问题上比基本蚁群算法更具有优越性，具有更好的收敛性和更高的收敛精度。本文的研究仍存在一些不足，解决旅行商问题时，使用的对比算法较少，这是后续研究需要加入的部分。
　　参考文献（References）
　　[1] 王凌.智能优化算法及其应用[M].北京：清华出版社，2001：
　　 218-222.
　　[2] 李军民，林淑飞，高让礼.用混合遗传算法求解多目标问题TSP问题[J].西安科技大学学报，2006，26（4）：515-518.
　　[3] HE Qing，WU Yi-Le，XU Tong-Wei.Application of improved genetic simulated annealing algorithm in TSP optimization[J].Control and Decision，2018（2）：219-225.
　　[4]王宏斌，劉娜.基于优先权编码的改进禁忌搜索算法求解TSP问题[J].物流科技，2017，40（6）：29-32.
　　[5] 施泰龙，郑悠，王蔚，等.引入外来种群的禁忌遗传混合算法求解TSP问题[J].宁波工程学院学报，2017，29（3）：20-25.
　　[6] 许凯波，鲁海燕，程毕芸，等.求解TSP的改进信息素二次更新与局部优化蚁群算法[J].计算机应用，2017，37（6）：1686-1691.
　　[7] 张勇，高鑫鑫，王昱洁.基于SFLA-GA混合算法求解时间最优的旅行商问题[J].电子与信息学报，2018，40（2）：363-370.
　　[8] 裴皓晨，娄渊胜，叶枫，等.一种求解旅行商问题的改进混合粒子群算法[J].计算机与数字工程，2018，46（2）：218-235.
　　[9] Cavdar B，Sokol J.A distribution-free TSP tour length estimation model for random graphs[J].European Journal of Operational Research，2015，243（2）：588-598.
　　[10] 王赛一，王成山.遗传禁忌混合算法及其在电网规划中的应用[J].电力系统自动化，2004，28（20）：43-46.
　　[11] 沐士光.遗传算法在网络优化问题中的研究与应用[J].计算机仿真，2010，27（5）：128-131.
　　[12] 钟石泉，杜纲.基于核心路径禁忌算法的开放式车辆路径问题研究[J].计算机集成制造系统，2007，13（4）：827-832.
　　[13] 王华东，李巍.粒子群算法的物流配送路径优化研究[J].计算机仿真，2012，29（5）：243-246.
　　[14] 邓义成，任声策，殷旅江.基于改进果蝇算法的旅行商问题[J].兰州理工大学学报，2016，42（4）：109-113.
　　[15] 茆诗松.概率论与数理统计教程[M].北京：高等教育出版社，2004：22-28.
　　[16]TSPLIB[EB/OL].http：//comopt.ifi.uni-heidelberg.de/software/TSPLIB95/，2016-12-10.
　　作者简介：
　　费   腾（1983-），女，博士，副教授.研究领域：智能计算与群智能算法.
　　赵   斌（1983-），男，本科，讲师.研究领域：算法研究.
　　黄俊东（1999-），男，本科生.研究领域：自动化设计.
　　刘泽田（1999-），男，本科生.研究领域：智能算法.
转载注明来源:https://www.xzbu.com/1/view-15148679.htm