张瑞星　李秀娟

摘要：为解决蚁群算法（ACO）求解TSP收敛速度缓慢、易陷入局部最优的问题，提出一种基于蚁群的融合算法（APG）。首先在ACO的初始种群中引入精英策略，获得精英路径并构建精英可行解空间；其次引入PSO模型，令精英可行解作为PSO的初始种群，加入GA中的进化策略，使粒子与Gbest进行交叉操作，再使交叉操作后的粒子发生变异，得到第二次优化的可行解空间；最后更新ACO信息素，完成一次ACO优化迭代过程。通过APG在TSPLIB中不同实例的验证，结果表明，APG算法较其它路径优化算法能够得到更优路径。

关键词：TSP；ACO；精英策略；PSO；GA

DOIDOI：10.11907/rjdk.181237

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）009008104

英文标题Application of APG Algorithm in TSP Optimization

--副标题

英文作者ZHANG Ruixing， LI Xiujuan

英文作者单位（College of Electrical Engineering，Henan University of Technology，Zhengzhou 450001，China）

英文摘要Abstract：In order to solve the problem that ACO is of slow convergence and easy to fall into the local optimal when solving TSP problem，an ant colony based fusion algorithm （APG） is proposed.First of all，the elite strategy is introduced into the initial population of ACO to obtain the elite path and build the elite feasible solution space； secondly，the PSO model is introduced to make the elitist feasible solution as the initial population of PSO.The evolutionary strategy of GA is added to cross operation between particles and Gbest，and then the variation of particles after cross operation is achieved，and the second feasible solution space is obtained； finally，the ACO pheromone is updated to complete a ACO optimization iteration process.The verification results of different instances of APG in TSPLIB show that the proposed APG algorithm can get a better path than other path optimization algorithms.

英文关键词Key Words：TSP；ACO；elite strategy；PSO；GA

0引言

商旅问题（Traveling Salesman Problem，TSP）作为多组合优化的NP问题，有着很强的现实意义。很多领域的问题都可以转化为TSP模型进行求解，如点焊机器人的路径规划、物流配送、车间管理调度、城市道路规划等。

随着人工智能的迅猛发展，目前学者们已经提出许多智能算法并应用于求解TSP问题中。宁桂英等[1]提出一种离散型差分进化算法解决 TSP问题。王学武等[2]将莱维飞行策略与粒子群算法结合以优化TSP问题。吴虎胜等[3]采用离散狼群算法解决TSP问题。刘克胜等[4]提出一种免疫框架，利用免疫算法求解TSP问题。文艺等[5]提出一种改进交叉算子和基于种群相似度的更新策略，改进遗传算法以解决TSP问题，克服了“早熟”现象。胡中华等[6]采用不同的动态转移策略改进人工蜂群算法优化TSP問题，提高了算法的收敛速度。杨进等[7]通过引入交换概念和改进猫的行为模式将猫群算法用于求解TSP问题。

蚁群算法（Ant Colony Optimization，ACO）是Marco Dorigo等[8]提出的一种具有正反馈调节能力的群体智能算法。学者们针对算法存在的问题，提出了很多改进方法。张于贤[9]针对蚁群算法信息素更新的时效性问题提出一种改进信息素更新策略，提高了算法的收敛速度。徐金荣等[10]提出一种基于启发式遗传信息的蚁群遗传算法求解TSP问题，提高了算法的收敛速度。潘晓萌等[11]提出一种基于多目标Pareto支配的蚁群优化算法，增强了算法的全局搜索能力。Ratanavilisagul C[12]提出一种基于变异策略的蚁群算法，当蚂蚁陷入局部最优时，使蚂蚁的信息素发生变异，提高了算法的全局搜索能力。Niu Y等[13]提出一种随机蚁群算法，通过优化路径、选择概率更新规则和信息素更新规则，加快了算法的收敛速度。Castillo O等[14]利用分散控制原理改进蚁群算法，其核心是通过α的动态变换避免或减缓完全收敛，提高了算法的全局搜索能力。

根据上文分析可知，提高蚁群算法的收敛速度与全局搜索能力是改进蚁群算法的主要切入点。本文针对蚁群算法和粒子群算法进行分析，提出一种基于蚁群的融合算法（Ant Colony Particle Swarm Genetic Algorithm，APG）求解TSP问题。实验结果表明，APG算法对不同规模的目标优化都能快速进行全局寻优，得到最优解。

1TSP问题描述

已知n个城市之间的相互距离，某个商人从其中一个城市出发，依次访问剩余（n-1）个城市，每个城市只能访问一次，最后返回最初城市。TSP问题即如何安排走访城市的路线，使得路径总长度Td最小。

Td=∑n-1i=1di，i+1+dn，1（1）

其中，di，i+1表示两座城市之间的距离。则：

di，i+1=（xi+1-xi）2+（yi+1-yi）2（2）

式（1）为本文构建的TSP数学模型。

2APG算法

2.1蚁群算法

蚁群算法（ACO）是人工模拟自然界中蚁群觅食行为的一种群体仿生算法[15]。蚂蚁在寻找食物的过程中会在路径上留下信息素，通过信息素彼此交流，从而选择一条离食物源最近的路径。

设蚁群的种群规模为m，需要遍历的城市集为n，任意两座城市之间的路径长度为d，τ为两座城市之间的权值即信息素浓度，η为启发函数，s为任意一座城市，allowk为待访问城市的集合，α、β分别为信息素浓度重要因子与启发函数重要程度因子，p为蚂蚁选择下一个访问城市的概率。概率p计算方法如下：

pkij=[τij（t）]α·[ηij（t）]β∑s∈allowk[τij（t）]α·[ηij（t）]β s∈allowk0 sallowk（3）

蚁群在释放信息素的同时，信息素也会挥发，设挥发率为θ。如果路径短节点的信息素浓度越来越高，而其它路径节点的信息素浓度就会越来越少，则可形成ACO的正反馈调节机制。最后只有一条最优路径上拥有信息素，指导蚁群寻优。信息素更新方法如下：

τij（t+1）=（1-θ）τij+ΔτijΔτij=∑nk=1Δτkij，0<θ<1（4）

2.2粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是模拟自然界鸟群协作捕食行为的一种仿生算法[16]。每个粒子代表一个目标函数的可行解，通过粒子与粒子变化率、粒子的个体极值（Pbest）和群体极值（Gbest）相互作用，不断更新粒子，向最优解逼近。其更新方法如下：

Vk+1i=r0Vki+r1（pki-Xki）+r2（pkg-Xki）（5）Xk+1i=Xki+VK+1i（6）

其中，Vi为粒子更新的速度，Xi为目标函数对应粒子的适应度值，r0、r1、r2均为分布在[0，1]上的任意数，Pi - Xi、Pg - Xi分别为粒子对个体极值与群体极值的影响程度，Xi+Vi表示粒子速度对于粒子的影响程度。

2.3APG算法思想

APG算法的核心思想是令优秀的路径解集合参与信息素更新，在正反馈调节作用下，指导蚁群在下一次优化迭代中建立优秀的可行解空间。分为3步：

（1）利用精英策略思想完成对可行解的第一次优化。用m只蚂蚁构建可行解空间，将其按照路径长短进行排序，选择最短的前n条精英路径作为初始参数。

（2）将n条精英路径作为PSO的初始种群，利用粒子群算法快速收敛性质，为避免“早熟”发生，在PSO优化计算过程中引入遗传算法（Genetic Algorithm，GA）中的进化策略。随机在粒子上选择一个区间fi～fj，用群体极值相应区间位置上的元素代替粒子的元素，完成与群体极值的交叉操作；随机在粒子上选择一个元素fi，将fi与fi+1交换，完成变异操作。通过融合PSO、GA完成对可行解的第二次优化。

（3）令经过二次优化后的路径参与信息素更新，帮助蚁群在迭代中选择优秀路径。

3算法设计与仿真

3.1算法设计

根据上述算法的工作原理，本文算法流程如图1所示。

3.2MATLAB仿真与分析

为验证本文设计APG算法的有效性，选取TSPLIB标准库中的3个实例进行实验，选择ACO、PSO_GA两种算法的优化结果作为对比。

3.2.1Eil51问题

针对Eil51问题，设置参数如下：ACO算法，设m=200，α=0.5，β=10，θ=0.2；PSO_GA算法，设m=200；APG，设m=200，α=0.5，β=10，θ=0.2。设置迭代次数为300，分别进行10次运算，得到最优路径如图2所示。

3.2.2Eil101问题

针对Eil101问题，设置参数如下：ACO算法，m=300，α=0.5，β=10，θ=0.2；PSO_GA算法，m=300；APG算法，m=300，α=0.5，β=10，θ=0.2。設置迭代次数为400，分别进行10次运算，得到最优路径如图3所示。

3.2.3TSP225问题

针对TSP225问题，设置参数如下：ACO算法，m=500，α=0.5，β=10，θ=0.2；PSO_GA算法，m=500；APG算法，m=500，α=0.5，β=10，θ=0.2。设置迭代次数为500，分别进行10次运算，得到最优路径如图4所示。

3.3实验结果

表1列出了ACO算法、PSO_GA算法、APG算法在TSPLIB标准库不同数据样本下10次运算结果的平均值、最优值和收敛迭代次数。在Eil51小样本实验中，无论是最优值、平均值，还是收敛速度，APG算法较其它两种算法都有明显优势。在Eil101、TSP225的大型样本实验中，APG算法的优化结果更加突出。上述实验结果表明，本文设计的APG算法能够较好地进行全局寻优，对TSP问题能够快速收敛得到更佳路径。

4结语

本文提出了一种基于蚁群的融合算法，通过加入精英策略，同时融合PSO、GA算法，利用优秀路径得到优化ACO信息素，有效地解决了ACO求解TSP问题时收敛速度缓慢、易陷入局部最优的问题。通过实验结果可知，本文设计的APG算法与其它优化算法相比，对于求解不同规模的TSP问题，均能得到最优解，提升了求解TSP类型问题的效率。

参考文献参考文献：

[1]宁桂英，曹敦虔，周永权.求解TSP问题的离散型差分进化算法[J].计算机与数字工程，2017，45（11）：21362142.

[2]王学武，严益鑫，顾幸生.基于莱维飞行粒子群算法的焊接机器人路径规划[J].控制与决策，2017， 32（2）：373377.

[3]吴虎胜，张凤鸣，李浩，等.求解TSP问题的离散狼群算法[J].控制与决策，2015（10）：18611867.

[4]刘克胜，曹先彬，郑浩然，等.基于免疫算法的TSP问题求解[J].计算机工程，2000，26（1）：12.

[5]文艺，潘大志.用于求解TSP问题的改进遗传算法[J].计算机科学，2016，43（s1）：9092.

[6]胡中华，赵敏.基于人工蜂群算法的TSP仿真[J].北京理工大学学报，2009，29（11）：978982.

[7]杨进，郑允，马良.改进的猫群算法求解TSP[J].计算机应用研究，2017，34（12）：36073610.

[8]DORIGO M，GAMBARDELLA L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation，1997，1（1）：5366.

[9]张于贤，丁修坤，薛殿春，等.求解旅行商问题的改进蚁群算法研究[J].计算机工程与科学，2017， 39（8）：15761580.

[10]徐金荣，李允，刘海涛，等.一种求解TSP的混合遗传蚁群算法[J].计算机应用，2008，28（8）：20842087.

[11]潘晓萌，李冰.蚁群算法优化和路径规划问题的应用研究[J].科技通报，2016，32（6）：99103.

[12]RATANAVILISAGUL C.Modified ant colony optimization with pheromone mutation for travelling salesman problem[C].International Conference on Electrical Engineering/electronics，Computer，Telecommunications and Information Technology，2017：411414.

[13]NIU Y，ZHANG D.A randomness ant colony algorithm for solving TSP[C].Advanced Science and Industry Research Center：Proceedings of 2017 2nd International Conference on Computer，2017：5.

[14]CASTILLO O，NEYOY H，SORIA J，et al.Dynamic fuzzy logic parameter tuning for ACO and its application in the fuzzy logic control of an autonomous mobile robot[J].International Journal of Advanced Robotic Systems，2013，10（51）：110.

[15]杜鵬桢，唐振民，孙研.一种面向对象的多角色蚁群算法及其TSP问题求解[J].控制与决策，2014（10）：17291736.

[16]李文，伍铁斌，赵全友，等.改进的混沌粒子群算法在TSP中的应用[J].计算机应用研究，2015，32（7）：20652067.

责任编辑（责任编辑：何丽）