朱宏伟，游晓明，刘 升

(1.上海工程技术大学 电子电气工程学院，上海 201620；2.上海工程技术大学 管理学院，上海 201620)

蚁群算法(Ant Colony Optimization，ACO)是一种群智能优化算法。它基于自然界蚁群集体觅食行为，模拟真实蚁群的协作过程。1991年，Dorigo提出蚂蚁系统(Ant System，AS)［1］用于解决TSP等复杂难问题。1996年，Dorigo等人为了限制信息素的正反馈作用，提出蚁群系统(Ant Colony System，ACS)［2］，通过两种信息素更新方式，平衡每条边之间的信息素差异，提高蚁群算法性能。同理，T.Stutzle等人提出了最大-最小蚂蚁系统(MAX-MIN Ant System，MMAS)［3］，通过限制信息素最大值和最小值，保证算法的多样性。后来专家学者在这两者基础不断改进［4-7］，使算法不断向前方展。同时还将蚁群算法延展于机器人路径规划、调度等一系列优化问题上，使算法向多方向发展［8-9］。

粒子群优化算法(Particle Swarm Optimization，PSO)最早是由Kennedy和Eberhart提出的，最初是模拟鸟群的捕食行为，逐渐发展成为群体智能算法。在寻优过程中，每个潜在的最优解都与粒子运动速度相关，根据粒子的历史经验以及邻居们的经验来调整其速度大小和方向，朝着最优解的方向逼近。粒子群优化算法已经广泛应用于连续优化问题和离散优化问题，特别是其天然的实数编码特点适合于处理实优化问题并可以有效地对系统参数进行优化。

虽然使用粒子群优化的参数会提高解的质量，但是找到全局最优解还有一定的困难，故本文提出一种基于粒子群参数优化的同构双种群蚁群算法(Homogeneous Dual Ant Colony Algorithm Based on Particle Swarm Optimization，HDAP)来提高找到全局最优解的概率。以ACS作为框架基础，算法开始时，将蚂蚁均分为两个子种群，分别命名Population1和Population2。Population1引入单位距离信息素路径构造算子，将距离因素和信息素因子相统一，提高算法遍历整个地图的能力。Population2引入粒子群优化算法对蚁群算法中的多个参数进行优化，减小蚁群算法中参数的影响，实现对解空间高效、快速的全面寻优。Population1中由于未使用α和β等参数，与Population2的参数优化形成优势互补关系，两个种群相隔一定迭代次数进行协同交流，提高发现全局最优解的概率。仿真实验表明，针对TSP问题，本文算法提高了解的质量，增强了算法的种群多样性。

1 相关工作

1.1 基本蚁群算法的TSP问题

以NP-难问题中最常用的TSP问题为例说明基本蚁群算法的模型。

设蚂蚁的数量为m，城市的数量为n，dij(i，j=1，2，…)代表两两城市之间的距离，τij(t)代表t时刻i城市和j城市之间的信息素的浓度大小。在ACS算法中，每条边上的起始浓度都是相同的，记为τ0。

1.1.1 路径构建

首先每个蚂蚁被随机分配到城市中，然后根据状态转移概率寻找下一个要到达的城市。ACS算法中，每只蚂蚁从i城市到j城市的选择方式为

式中，ηij为 i，j城市之间距离的倒数，即 1/dij；q0为一个人为设置的固定值；q为一个随机生成的随机数；S为将要被选择的下一个城市；s为另一种轮盘赌的选择方式。当不符合上述条件，采用轮盘赌进行路径构建。

式中，allowed为蚂蚁当前可行城市集。

1.1.2 信息素更新

ACS算法中分为全局信息素更新以及局部信息素更新部分。

①全局信息素更新：当所有的蚂蚁都完成一次周游以后，算法只允许每一代的最优蚂蚁释放信息素。

式中，

其中，ρ为全局信息素挥发率；Δτij为信息素增量；Lgb为当前最优路径长度。

②局部信息素更新：当所有的蚂蚁都完成一次周游后，算法允许每只蚂蚁都对其走过的路径进行信息素的更新。

全局信息素和局部信息素之间相互配合是ACS算法最重要的特点。

1.2 粒子群算法

粒子群优化算法的基本原理为：一个由m个粒子组成的群体在d维搜索空间中，以一定的速度飞行，每个粒子在搜索时，既考虑自己搜索到的历史最好点，又考虑群体内其他粒子的历史最好点，在此基础上进行位置更新。

设第 i个粒子的位置表示为 xi=(xi1，xi2，…，xid)，其速度表示为vi=(vi1，vi2，…，vid)，其经历过的历史最好点表示为pi=(pi1，pi2，…，pid)。群体内所有粒子所经历的最好的点表示为Gg=(Gg1，Gg2，…，Gpd)。一般来说，粒子的位置和速度分别根据式(5)和式(6)进行更新。

式中，w为惯性权重，其大小决定了粒子对当前速度继承的多少；c1和c2为学习因子，通常在0～2之间取值；rand()是在［0，1］区间内均匀分布的伪随机数，即rand()∈U［0，1］。

2 改进的蚁群算法

本文提出一种基于粒子群参数优化的双种群蚁群算法，通过加强蚁群间的合作，使算法更加符合自然界中蚂蚁种群间相互协同、相互竞争的特点，进一步减少种群陷入局部最优的概率，增强解的质量。将送蚂蚁均分为两种类型，命名为Population1和Populatin2，分别按照式(8)和使用粒子群优化的参数ACS进行路径构建，独立地进行最优解的搜寻，每隔w次迭代后交流最优解，加强种群之间相互学习，相互合作，从而使每个种群皆获得更优解。

2.1 单位距离信息素算子

本文提出一种改进的路径构建策略，即单位距离路径构造算子(Unit Distance of Path Constructor，UD-PC)，将距离因素与信息素因子相结合，增加种群的多样性。本文的路径构建公式如下：

式中，τirn为i城市到 rn城市之间的信息素；dirn为i城市到rn城市之间的距离值。

式(7)与式(1)对比可知，式(1)中由于ηij的β的次方使距离因素对路径构建影响较多，减少了信息素的引导的作用，而式(7)则很好地平衡了这两个因素，其减少了距离因子在路径构建中的权重，增加其他城市被选择的概率，跳出局部最优。

Population1采用式(8)进行路径构建，增强算法搜索整个地图的能力，同时增加算法多样性，使算法更易跳出局部最优，找到最优解。

式中，s为轮盘赌选择方式；q0为一固定常数；q为一个随机数。

2.2 粒子群对于蚁群算法参数的优化

本文提出一种使用粒子群算法优化蚁群算法参数的方法，将ACS中β、q0和ρ放在三维空间坐标系中，进一步优化这3个参数，提升了算法的性能。

设一个三维坐标xi=(xi0，xi1，xi2)来对应一组β、q0和ρ参数，用于表现粒子的位置。同时，与位置相对应的，每个粒子在解空间中的移动有3个方向的速度，记为 vi=(vi0，vi1，vi2)。

算法开始，初始化粒子P0，P1，…，PN的位置参数xi=(xi0，xi1，xi2) ，一个粒子对应一组三维坐标，即参数β、q0和ρ，并将每个粒子所对应的参数值反馈回蚁群算法。蚁群根据不同的参数的值，进行TSP最优解的寻找。每个粒子当前找到的最优粒子位置为Pi，整个种群当前所找到的最优粒子位置为Gg，按照式(5)和式(6)更新粒子的速度和位置。

Population2克服了蚁群算法参数的影响，减少了大量盲目的实验，实现了对搜索空间高效、快速的全面寻优。

2.3 交流策略

根据文献［10］和文献［11］，使用粒子群优化的参数虽然可以找出全局最优解，但是概率偏低，故本文采用两个种群协同交流的策略，提高了算法多样性，同时提高了获得全局最优解的概率。在本算法中，Population1未使用α和β等参数和Population2的参数优化形成路径构造算子之间的互补关系，每隔w次迭代后，两个种群进行交互学习，即比较每个种群中的当前最优解，将其中最好的解保存下来，同时替换掉另一个种群中相对较差的最优解，从而促使两个种群向更好的解的方向发展。式(9)描述了两个种群的学习机制。

2.4 改进算法(HDAP)伪代码

用HDAP算法解决TSP问题的代码如下。

1.Procedure HDAP()

2.Begin：

3.Initialize the parameters and the pheromone

4.Divide m into part #m as ants’number

5. for iter1←1 to T do

6. #Algorithm：Population1

6. for i←1 to m1 do#m as ants’number

7. for j←2 to n do#n as cities’number

8. Unit Distance of Path Constructor

9. end-for

10. end-for

11. Update pheromones

12. #Algorithm：Population2

13. Initialize parameters of P0，P1…PN

14. for i←1 to m2 do#m as ants’number

15. Transfer parameters of PSO to ACO

16. for j←2 to n do#n as cities’number

17. Construct ant solutions

18. Calulation GgandPi

19. Update viand xi

20. end-for

21. Update pheromones

22. end-for

23. if(mod(T，w)= =0) #T is the current iter

24. Collaborative communication

25. end-if

26. end-for

2.5 时间复杂度

通过分析上述算法流程，HDAP时间复杂度为 O((m1×(n-1)+m2×(n-1))×T)，由于 m1+m2=m，故HDAP算法最大时间复杂度为O(m×n×T)，ACS最 大 时 间 复 杂 度O(m×n×T)。由此可以看出，所提出的HDAP蚁群算法虽然产生了部分计算负担，但是没有改变算法的最大时间复杂度。

3 实验分析

本实验在Matlab R2014a的环境下仿真运行。为了检测改进算法的有效性，选取eil51、eil76、KroA100、KroA150、KroB150等TSP算例来进行算法验证，并与ACS、MMAS等经典ACO算法以及多个多种群算法相对比，结果显示所提出的HDAP有着更好的实验结果。同时eil51、eil76、KroA100都比较容易找到最优解，从熵值看出改进的HDAP算法的多样性有着明显的提升。

3.1 eil51问题的实验分析

在eil51问题上，Population1和Population2的公共参数为：蚂蚁数量m=50，信息素作用度α=1，最大迭代次数iter=2000。非公共参数为：Population1的实验参数，包括局部挥发率ζ=0.1，全局挥发率ρ=0.4，参数q0=0.8；Population2实验参数取值范围，包括β=［2，10］，q0=［0.5，0.9］，ρ=［0.2，0.7］。

每组参数不同，ACO算法都进行了连续20次测试，采用控制变量的方法，逐渐改变β的值，来观察其对实验的影响。设到算法所找到的最优长度为Lbest，算法20次实验的平均路径长度为Lave。

式中，n为实验次数；V为与平均解的误差；J为误差率。

式(10)与式(11)可以共同反映每个ACO算法的稳定性，波动情况以及找到最优解的概率。标准差可以反映20次试验每一次找出的解与平均值的线性程度，标准差越大，这个算法的波动程度就越大。而J可以反映出最优值和平均值的离散的关系，用于判断每个ACO算法找出最优值的概率，概率与数值J大小成反比，即J的值越大，算法找到最优解的概率就相对越小。

eil51实例的实验结果如表1。表1显示了不同的β取值对最优解、标准差V、误差率J等实验结果的影响。从表1可以看出，β从2开始依次变化到5，ACS算法平均长度的结果变化类似于一个二次函数。而粒子群优化得到的参数β为4.2311，证明了粒子群优化算法的有效性。同时由于Population1增加了蚂蚁探索整个TSP测试集的能力，提高了解的质量，从算法开始到结束，熵值都一直处于略微上升的状态，表明算法的多样性提升明显，使算法容易跳出局部最优。图1为某次路径长度为426(最优解)时的熵值。

表1 不同β对ACO路径长度的影响

图1 HDAP多样性分析

3.2 中大规模TSP问题分析

下面针对 ch130、KroB150、KroA150等中大规模TSP问题进行实验仿真。每种算法都进行了20次的仿真实验，平均长度四舍五入，具体比较结果如表2所示。

下面举例说明3种ACO算法的收敛情况。图3为KroB150测试集的3种算法的最优解迭代变化。由图可看出，ACS算法收敛的速度最快，在第216代时，相比较其他两种算法，其结果最优，但同时陷入局部最优，而无法跳出；MMAS和HDAP收敛速度相对较慢，MMAS算法在1737和2000次迭代陷入局部最优后，通过信息素的重新初始化，跳出局部最优，但依然没有找到全局最优解。由于HDAP的两个种群之间的学习交流策略，共同处理最优解的寻找，其收敛的速度要更优于MMAS，在1737次迭代中跳出局部最优，同时找到全局最优解。

表 2 反映了在 eil76、KroA100、ch130、KroB150、KroA150等大规模测试集上，3种ACO算法的最优长度、最差长度、平均长度、标准差V等一系列数据比较分析。从仿真实验结果可以看出，HDAP各方面的实验结果都是优于其他两种ACO算法的，尤其是最优解、平均解、平均熵值等方面提升更加明显。结合3.1节中的实验分析，表明HDAP无论在小规模和大规模TSP问题上，都有着比较优的实验结果。

同时，比较了3种算法的J(式(11))的值，3种蚁群算法在不同的测试集中误差率的变化曲线如图3所示。J值越小，说明算法的稳定性越高，其解的质量也相对较高。由图3的实验结果可以看出HDAP在多个测试集中的误差率J都要小于ACS和MMAS算法，说明HDAP在3种算法中有着最高的稳定性。

表2 不同算法性能对比

图3 不同TSP测试集误差率分析

由表2和图3可知，改进的HDAP算法提升是比较明显的。为了证明本文算法的优越性，与一些其他多种群蚁群算法也进行了比较分析，如表3所示。其中HHACO算法的数据都来自于文献［12］(SCI)，AHMACAS算法中数据来自于文献［13］(CSCD)，HMACSF算法中数据来自于文献［14］(CSCD)。从表3可以看出，在与其他多种群蚁群算法对比中，本文算法有着一定的优势，特别是在eil51和eil76测试集上，HDAP找到的最优解要好于其他3种多种群算法。

表3 多种群之间的对比

3.3 HDAP的最优解仿真图

图4给出了HDAP的最优解仿真图。

3.4 收敛速度对比

为了更加直观地对比各个算法的性能，在几个TSP实例中选取不同规模的城市，如 eil51、eil76、ch130、KroA150，用于比较算法的收敛速度，如图5所示。从图中可以看出，HDAP无论在小规模还是在中大规模的问题上，最优解都要好于其他两种算法，且收敛速度要优于MMAS。

图4 HDAP的最优解仿真图

图5 不同测试集的收敛速度

4 结束语

提出一种基于粒子群参数优化的同构双种群蚁群算法，将蚂蚁均分为两个子种群，即 Population1和Population2。Population1引入单位距离信息素路径构造算子，将距离因素和信息素因相统一，增加算法遍历整个地图的能力，增加算法多样性。Population2引入粒子群优化算法对蚁群算法中的多个参数进行优化，克服了蚁群算法参数的影响，实现了对搜索空间高效、快速的全面寻优。Population1中由于未使用α和β等参数，与Population2的参数优化形成优势互补关系，两个种群相隔w次迭代进行协同交流，提高发现全局最优解的概率。接下来，将继续研究如何在更大的测试集中找出最优解和使算法更快的收敛。