参数α、β和ρ自适应调整的快速蚁群算法

尤海龙，鲁照权

（合肥工业大学 智能制造研究院，合肥 230009）

0 引言

蚁群算法是由意大利学者Dorigo M等于1991年在法国巴黎召开的第一届欧洲人工生命会议（European Conference on Artificial Lif，ECAL）上最早提出的[1]。蚁群算法遵循蚂蚁搜寻食物的过程，蚂蚁在寻找食物的路程中留下信息素，随着时间的累计，最短路径上的信息素浓度高于其他路径，这使得后来的蚂蚁有更大的概率选择该条路径，是一个正反馈过程。蚁群算法的优点包括分布式并行计算机制、易与其他方法相结合、具有较强的鲁棒性等[2]。随着智能机器人的兴起，蚁群算法也被大量使用在机器人路径寻优中。由于机器人行走的实时性，使得要在尽可能短的时间内寻找到最优路径，蚁群算法收敛速度慢的问题显得尤为突出。针对此问题，国内外很多学者对蚁群算法做出了多次改进。改进的方法主要有改变信息素更新策略，仅更新最优路径上的信息素[3]。在全局信息素的基础上加入局部信息素更新[4]避免局部最优。将蚁群算法与其他算法相结合，如与遗传算法相结合[5]加入交叉算子和变异算子，增加了解的全局性；与免疫算法相结合，加入免疫算子，加快了算法的收敛性[6]。对蚁群算法中的参数进行改进，使其成为自适应参数[7]。

文中首先引入一般蚁群算法的数学模型，对蚁群算法的各个参数所起的作用进行介绍，之后根据其作用提出相应的自适应模型。接着使用MATLAB对传统蚁群算法与改进后的蚁群算法进行对比，通过实验结果验证了改进蚁群算法相对于传统蚁群算法收敛速度有了显著提高。最后，进行进一步总结与分析。

1 传统蚁群算法

蚂蚁k（k=1,2,3...,m）在移动过程中，选择从初始点下一步可以到达的节点，根据每个节点路径上的信息素求出前往每个节点的概率，并使用轮盘赌法[8]选取下一步的初始点。以表示蚂蚁从i节点到j节点的概率：

其中τij（t）表示弧（i，j）上信息素的浓度，ηij（i，j）表示与弧（i，j）相关联的启发式信息；tabuk为禁忌表，用来记录蚂蚁已走过的节点，避免蚂蚁“回头”；N为能够选择的所有节点；α为信息素启发因子，反映了τij（t）在蚁群搜索中的重要性；β为期望启发因子，反映了下一节点的位置在蚁群搜索中的重要性，且β越大，状态转移概率越接近贪心规则[9]。

一般情况下， ηij（i，j）按式(2)计算：

dij表示i节点到j节点的距离。由式(2)可知，dij越小，则ηij（i，j）越大，也就越大，被蚂蚁选择的概率就越大。在蚂蚁k到达目的地后，要对路径上残留信息素进行更新，这种更新类似人类的记忆功能，在新的信息素增加的同时，旧的信息素也在不断挥发，被“忘记”。根据此原理，τij(t+1)时刻信息素的浓度相对于τij(t)时刻信息素的更新按照式(3)、式(4)处理：

ρ表示信息素挥发系数， 则（1-ρ）表示信息素残留因子，为了防止路径上信息素无限积累，ρ的取值范围为ρ∈[0，1]；Δτij(t)表示本次循环中路径(i，j)上的信息素增量，初始时刻表示第 k只蚂蚁在本次循环中留在路径（i，j）上的信息量，由式(5)求得：

Lk为第k只蚂蚁在本次循环中所走过的路径长度，Q为信息素强度。

2 改进蚁群算法

与传统蚁群算法相比，文中在两个方面对蚁群算法进行了改进：1）将α（信息启发因子）和β（期望启发因子）改为动态自适应参数，随着迭代次数的改变相应的做出变化。2）将ρ（信息素挥发系数）设置为阈值函数。

2.1 α和β的自适应变化

传统蚁群算法中α和β通常取值为[1，9]中某个固定值。α过大，会使路径上信息素影响权值过大，使得蚂蚁易进入局部最优解。α过小，则蚂蚁行走的随机性又太强，收敛速度太慢。β的取值影响与α相似[10]。α和β过大或者过小都容易导致蚁群算法的搜索陷入局部最优或者陷入随机而无法找到最优解[11]。取最短路径下的运行时间为研究对象，对α和β的最佳取值进行研究。蚁群算法中的其他参数分别取值为：迭代总数K=50，每代出动蚂蚁总数M=80，信息素挥发系数ρ=0.7。多次改变α和β的取值，得到路径长度、运算时间与迭代次数的变化如表1和表2所示。观察变化趋势，可以得出在求取最短路径的问题上，α和β的最佳取值范围分别为[2～4]和[7～9]。

通过分析和多次仿真实验可知，在迭代初期，各条路径信息素浓度差别不大，此时与弧相关联的启发式信息η为影响蚂蚁选择路径的主要因素，因此α的值应较小，β的值应较大。随着迭代的不断进行，最短路径上的信息素浓度逐渐高于其他路径，此时信息素浓度在路径选择中占据主导地位，α的值应相应增加，β的值则较小。到了迭代的后期，部分路径上信息素浓度已远高于其他路径，为了防止由于信息素积累陷入局部最优，此时应减小信息素浓度在路径选择中所占的比重，即α再次变小，β的值则相应增加[12]。同时，适当增大α和β的取值范围，可使蚁群寻得路径解空间范围变大，有助于寻找全局最优解[13]。因此本文中α取值为[1～4]，β取值为[6～9]。

表1 α取值对性能的影响

表2 β取值对性能的影响

通过以上分析可知，α和β随着迭代次数的改变呈现阶梯型变化，为了能够更平滑的完成权重系数的改变，本文分别对α和β的取值采用正弦函数和余弦函数的方式，如式(6)、式(7)所示：

式中，k表示当前迭代次数，K表示迭代总次数；本文取式(6)中A=3、B=1、ε=1而式(7)中C=3、D=6、θ=1。也可按需求适当调整。

2.2 ρ信息素挥发系数函数

在信息素的积累过程中，信息素挥发系数占有重要作用。若ρ过大，会降低算法的全局搜索能力；若ρ过小，则收敛速度会降低[14]。将蚁群算法中的其他参数分别取值为：迭代总数K=50，每代出动蚂蚁总数M=80，α=1，β=7。ρ的取值变化与算法性能的关系如表3所示。

表3 ρ的取值与算法性能的关系

根据分析可知，算法开始时路径上信息素浓度较低，此时ρ应相应取大，使得蚂蚁可以更快的找到较优路径，加快算法收敛速度；随着路径上信息素浓度的不断积累，为了避免陷入局部最优丢失算法的全局搜索能力，ρ的取值应相应减小。为了使算法的全局搜索能力和收敛速度在动态平衡中得到最大程度的优化，本文选用阈值函数对ρ进行动态调整，使其随着迭代次数的改变而改变，ρ的取值为[0.5,0.9]，取式(8)：

式中ψ为常数项，λ为改变因子，k为当前迭代次数，K为总迭代次数。选择合适的值，使ρ的取值在[0.5,0.9]中随着迭代的进行而动态减小。本文中ψ=1.82，λ=1。

3 实验

3.1 二维地图的建立及相关参数设置

为了验证本文中算法的有效性，使用matlab2014创建二维静态栅格地图如图1所示。图中黑色栅格表示障碍物，白色栅格表示可选择的节点。

图1 栅格法静态二维地图

栅格的编号首先通过序号法从第一行依次编号，如第一行和第二行的障碍物的序号为N={2，14，15，19，20}。蚂蚁所取的节点为每个栅格的中心，可通过式(9)换算为直角坐标系坐标：

其中N为序列号，M是地图中栅格的列数，mod( )为求余函数，ceil( )为取整函数。

3.2 算法步骤

1）使用栅格法建立机器人寻找最优路径的地图。

2）输入初始的信息素矩阵，选择初始点和终点并且设置各种参数。算法的相关参数设置为：迭代总次数K=100，每代蚂蚁总数M=80，信息素强度系数Q=1。改进前α、β与ρ分别取1、7和0.7，改进后根据式(6)、式(7)、式(8)设置。文献[15]中的ρ按式(9)设置。

ξ∈(0,1)为挥发因子调节系数；ρmin为ρ的最小值。

3）选择从初始点下一步可以到达的节点，根据每个节点的信息素求出前往每个节点的概率，并利用式(1)的轮盘赌法选取下一步初始点。

4）更新路径及路径长度。

5）重复步骤3）、4），直到蚂蚁到达终点或因进入陷阱而死亡。

6）重复步骤3）、4）、5），直到这一代的M只蚂蚁全部遍历。

7）根据式(3)、式(4)更新信息素矩阵。

8）重复步骤3）～7），直到第K代蚂蚁迭代结束。

3.3 算法实现与比较

建立一个20×20的二维静态地图，多次改变障碍物位置，统计传统蚁群算法和本文改进后蚁群算法找到最优路径所需的迭代次数。如图2所示，某次实验下传统蚁法。

图2 蚁群算法下的最优路径

文献[15]蚁群算法和本文改进后的蚁群算法找到的最优路径相同。在此前提下，三种蚁群算法所需的迭代次数则分布如图3、图4、图5所示。

图3 改进前的迭代次数

图4 文献[15]的迭代次数

图5 本文的迭代次数

改变障碍物位置，迭代总次数选为各算法求得最优路径所需迭代数的次数五倍以保证结果稳定。进行多次实验，在所得最优路径相同的前提下，三种蚁群算法的迭代次数及运算时间如图6、图7所示。

图6 各算法迭代数

图7 各算法运算时间

由图可知，本文改进后的蚁群算法在得到相同最优解的前提下，能够有效的减少迭代次数。由于求得最优

【】【】解所需迭代次数的减小，使得算法在设定总迭代数时可以大幅减小，从而使得算法的总运行时间相应减小，实现了蚁群算法的快速寻路。

4 结论

蚁群算法作为机器人路径避障中的重要方法，如何解决其收敛速度慢的问题以应对实时路况一直是蚁群算法研究的重要方向。本文提出的改进蚁群算法，是对蚁群算法的三个主要参数做了改进，使得它们在算法的不同过程中所做出的影响发生最合适的变化，在避免陷入局部最优的同时加快了收敛速度，并经过仿真实验完成了验证。

[1]T Stützle,M López-Ibáez.Parameter Adaptation in Ant Colony Optimization[M].Springer Be-rlin Heidelberg,2011,6(1):23-8.

[2]李士勇.蚁群算法及其应用[M].哈尔滨工业大学出版社.2004,28(1):42-45.

[3]HH Hoos,MAX-MIN Ant system[M].Elsevier Science Publishers B. V.,2000,16(9):889-914.

[4]孟祥萍,片兆宇.基于方向信息素协调的蚁群算法[J].控制与决策.2013(5):782-786.

[5]李冬妮,贾晓宇.基于蚁群算法和遗传规划的跨单元调度方法[J].北京理工大学学报,2017,37(7):704-7102.

[6]周文明.基于智能算法的移动机器人路径规划研究[D].南京理工大学.2016.

[7]ZM Lai，GD Guo.Ant Colony Optimization Based on Self-Adaption Threshold for Path Planning[J].Computer Systems &Applications,2014.

[8]郁磊.matlab智能算法30个案例分析[M].北京航空航天大学出版社.2015.

[9]DP Du,YR Zu Greedy. Strategy Based Self-adaption Ant Colony Algorithm for 0/1 Knapsack Problem[M].Springer Netherlands.2015,331:663-670.

[10]魏星,李燕.蚁群算法中参数优化及其仿真研究[J].制造业自动化,2015(10):33-35.

[11]王越,叶秋冬.蚁群算法在求解最短路径问题上的改进策略[J].计算机工程与应用,2012,48(13):35-38.

[12]T Zhu,G Dong.Research for the Path Planning of the Agricultural Robot Based on the Improved Ant Colony Algorithm[J].Journal of Agricultural Mechanization Research,2016.

[13]DE JACKSON,M HOLCMBE,FLW RA-TNIEKS.Trail geometry gives polarity to ant foraging networks[J].Nature,2004,432(7019):907-909.

[14]钟娟,赵彦强,孙富康,等.基于混合蚁群算法的物流配送路径问题[J].合肥工业大学学报(自然科学版),2009,32(5):686-688.

[15]申铉京,刘阳阳,等.求解TSP问题的快速蚁群算法[J].吉林大学学报（工学版）2013,43(1):147-151.