基于参数组合优化的救援机器人蚁群算法研究

陈文卓，刘 萍，姜 丰，曹春雨

(华北科技学院,北京 东燕郊 065201)

0 引言

随着5G、人工智能算法、无线传感网络的发展，机器人的应用场景更加多样化，例如自然灾害、防爆排爆、医疗健康、公共服务等。其中在高危环境下救援机器人存活能力、运动能力、通讯能力和作业能力等指标成为衡量这一领域性能的关键，尤其是如何在最短时间内确定运动路径以提高工作效率。蚁群算法具有分布式计算、鲁棒性强、强大的全局搜索能力以及易于与其它方法相结合等优点，可广泛应用于组合优化、网络优化、路径规划、机器学习等领域。作为一种启发式的算法，蚁群算法中启发因子等参数极大地影响着算法性能，同时参数初始值的设置对收敛速度至关重要。因此，参数优化问题成为近年来研究蚁群算法方向的热点。

目前，学者对蚁群算法参数优化进行了多方面、多领域的研究，文献[1]提出一种新的信息素更新规则，再对信息残留因子进行实验，找到重要参数在该信息素更新规则下的最佳合理值；文献[2]在基本蚁群算法的基础上对其路径选择策略、启发函数和信息素更新策略进行改进，为地铁疏散人群求解最优疏散路径。文献[3]采用一种依据方向指导信息来优化初始信息素的分布，通过优化信息素的挥发和更新规则来改善算法性能的改进蚁群算法，对机器人在复杂环境下的路径规划具有时效性和适应性；文献[4]运用多目标分配的精英蚁群算法对配送路径进行优化，信息素的规则中参数进行改进，算法在配送路径规划中表现出极高的正确性和可行性；文献[5]中针对中央空调冷冻水系统存在的的问题，提出遗传蚁群算法综合优化控制策略，利用遗传算法对参数进行优化，使冷冻水系统更节能、更稳定。

以上研究均采用改进算法结构的方法优化参数进而提高算法性能，使用时需要广泛搜集各种环境、任务等信息以确定算法中使用的各个参数值，计算复杂度高，不具有高效性和广泛适用性。

因此本文利用单因素法从基本蚁群算法入手，仅针对蚂蚁数目m、救援点数n，信息素挥发因子ρ、信息素启发式因子α、距离启发式因子β、信息素强度Q这些参数分别进行定性数据对比，通过实验仿真验证，最终确定出简单易设的最优参数组合。

1 蚁群算法数学模型

蚁群算法是基于生物的人工智能算法[6]，不需要复杂的数学模型就可以完成随机搜索，因此容易实现。其算法原理是：起初人工蚂蚁进行单独搜索，并分泌信息素在群体间进行信息交流。人工蚂蚁留在路径上的信息素越多，路径被选的概率越大。人工蚂蚁信息传递的行为实际体现了信息的正反馈[7]，每次遍历完，信息素都会进行全局更新，从而保证随机搜索特征。经过多次迭代，最终找到遍历所有点的最短距离的路径，从而提高搜救效率。

本文以m只蚂蚁求解遍历n个救援点最短路径的TSP问题的基础，蚁群算法模型主要包括两部分：蚂蚁在救援点间转移规则和信息素更新规则。在蚁群系统中转移规则如下:

(1)

α为信息素启发因子，表示信息素在蚂蚁选择中的重要程度；τij为边(i,j)上的信息素浓度。β为距离启发因子；ηij为视距函数，表示由救援点i转移到救援点j的可见度，通常η表示救援点i到救援点j的欧式距离dij倒数，即：

(2)

在此基础上设置禁忌列表，用以记录蚂蚁k走过的救援点，避免蚂蚁走回头路，在遍历完所有救援点一周之前不会被清零。此外，为了使蚂蚁的随机搜索能力能够逐步优化改进，每只人工蚂蚁遍历所有救援点一次后进行全局信息素更新，更新公式如下：

τij(t+1)=(1-ρ)τij+Δτij

(3)

式中，Δτij根据蚁周模型表示为：

(4)

式中，Lk表示蚂蚁K在这次遍历中所走过的路径长度，Q为常数，表示信息素强度。

2 蚁群算法参数分析

由文献[8]可知，蚂蚁的数量的增多能够降低蚁群算法搜索的盲目性。在蚁群算法中，蚂蚁数目m与救援点数目n的比例关系的取值，影响算法的全局搜索能力和收敛速度。当m与n的比值过大时,每条路径上的信息素浓度差距很微弱，蚂蚁对于信息素的预判困难从而导致蚁群收敛速度降低；当m与n的比值过小时，不仅导致蚂蚁探索其他路径的能力降低，而且因为各条路上来往的蚂蚁数少，使得各条路上的信息素的差距降低，进而影响蚁群的收敛速度。

信息素启发因子α反映了蚂蚁在运动过程中所积累的信息素的量在指导蚁群搜索中的相对重要程度；由文献[9]可知，α的取值过大导致蚂蚁在选择下一个救援点时，会将该条路上的信息素浓度作为首要考虑因素，蚁群将失去路径探索能力从而陷入局部最优。α的取值过小会导致蚂蚁在选择路径时，信息素浓度的作用降低，虽然加了蚂蚁探索新路径的能力，但是降低了蚁群的收敛速度。

启发函数因子β反映了距离启发信息对于算法搜索的重要程度；β的取值大小影响蚂蚁在选择时对于路径长度的重视程度，从而影响算法的收敛速度。

通过观察自然界的蚂蚁所遗留的信息素可知，信息素浓度会随着时间的推移逐渐挥发，因此在算法中添加了信息素挥发系数ρ来对信息素挥发的程度定性分析。当ρ设置过大时，算法中的信息素挥发较快，导致各条路上的信息素浓度的差距降低，从而降低算法的收敛速度；当ρ设置较小时，信息素的挥发较慢，各条路上的信息素堆积，导致信息素对于路径选择的正反馈性能减弱。

信息素强度Q是蚂蚁在完成一次遍历的过程中遗留的信息素的总量。Q是正反馈机制的重要指标，Q越大，正反馈机制在蚂蚁路径选择中的主导作用越能凸显。

3 最优参数组合的确定

当灾害发生后，根据灾害现场的情况确定出救援机器人执行搜救巡检任务的区域范围，同时结合地理环境信息构建二维平面的运动地图模型。设定救援机器人从救援区域的任意一点作为起始点，利用蚁群算法遍历所有救援点完成执行任务之后返回起点，力图在最短时间内高效完成任务，获得最优的可行路线。

为得到每个参数的最优取值，并对其在救援机器人实行路径规划的精确性进行检验，在此以实际的矿井二维救援点平面图图1为例，利用单因素法进行救援机器人基本蚁群算法的路径规划。

图1 救援点地图二维模型

在进行路径模拟前，根据公式(1)～(4)所示数学模型，并结合上述因素限制，在考虑蚁群算法自身特点的情况下,算法参数范围分别选取为α∈(0,5]，β∈(0,5]，ρ∈(0,0.99]，Q∈[10,1000]，m=(1～5)n。在此范围内以单因素法, 分别对数学模型中提及的蚁群算法参数α、β、ρ和Q以及建立蚁群算法规模的m和n进行多次仿真实验，确定蚁群算法的最优参数组合范围。

每次实验在利用蚁群算法进行路径模拟规划的初始时刻，如图2所示，首先设置初始参数(6个参数中，每次模拟只改变其中一个参数的值)。然后将每个被访问过的救援任务点加入禁忌列表，因此此时蚂蚁将根据当下时刻救援任务地图各救援点信息素浓度选择应该前往的下一个救援点，直到禁忌列表被填满。然后，更新规划路径上的信息素，输出该参数在单因素法中迭代路径长度的最优解，之后清空禁忌列表，作为一次迭代结束。为保证算法的全局规划能力，每次实验进行2000次的迭代。从而获得该参数在此救援地图中的最优取值，重复上述步骤，最终获得所有参数的组合最优解。

图2 单因素蚁群算法流程图

4 实验仿真

根据之前分析，首先设置ρ=0.5，Q=200，m=50，n=50为初始固定参数，控制变量α在0～5范围内以0.25为间距进行变化，每个α的取值都对应β∈[0，0.25，0.5， ... 4.75,5]进行实验仿真，结果如图3所示。

图3 α、β对路径规划算法的影响图

由图3可以看出，当α和β在1～2区间时，在此区域内迭代距离下沉明显且集中，这表明蚁参数取在该范围内，算法能快速迭代出最短距离，算法性能最佳。

蚁群算法中蚂蚁数目m与救援点数目n的比例关系的取值，影响算法的全局搜索能力和收敛速度。当m与n的比值过大时,蚂蚁对于信息素的预判困难从而导致蚁群收敛速度降低；当m与n的比值过小时，使得各条路上的信息素的差距降低，进而影响蚁群的收敛速度。以α=1，β=2，ρ=0.5，Q=200为初始值，该实验分别设置n=50和n=20，结果如图4、图5所示。

图4 n=50时m对路径规划算法的影响曲线

图5 n=20时m对路径规划算法的影响曲线

将图4和图5进行对比可知，蚂蚁数对蚁群算法的搜索性能的影响并不是单一的比较蚂蚁的个数。当蚂蚁数未超过救援点数时，也就是m小于n，即m/n<1时，实验迭代次数多，算法性能相对较差，难以迭代出最短距离；在当蚂蚁数大于或等于救援点数时，即m/n∈[1,3]时，迭代次数最少且实验结果相对稳定，算法性能较好算法均能迭代出最短路径。因此可得出蚂蚁数对算法性能的影响与救援点数n有比例关系，由图5看出，m/n>3时，迭代次数上下波动，算法性能不稳定，而在蚂蚁数时救援点数的一倍到三倍之间迭代次数相对最少，所以推知m与n存在最优比例为m/n∈[1,3]。

同时利用信息素浓度中的信息素挥发系数ρ可以对信息素挥发的程度定性分析。在α=1，β=2，Q=200，m=50,n=50为初始值的条件下，对ρ进行实验仿真，结果如图6所示：

图6 ρ对路径规划算法的影响曲线

由图6可知，随着ρ的不断增大，变化算法迭代次数呈现先降低后增加的趋势，总体来看，算法迭代性能较好的取值集中在0.2～0.7区间内，其中ρ取0.5时迭代次数最少，算法性能最佳，能体现出蚂蚁的全局搜索和快速收敛的能力。

信息素强度Q是蚂蚁在完成一次遍历的过程中遗留的信息素的总量。Q是正反馈机制的重要指标，Q越大，正反馈机制在蚂蚁路径选择中的主导作用越能凸显。在α=1，β=2，ρ=0.5，m=50，n=50为初始值条件下，对Q进行仿真分析。

图7 Q对路径规划算法的影响曲线

由图7可知，Q的取值随着迭代次数的增加而改变，时大时小，但是从整体发展趋势中可以发现，当Q取200时，迭代次数是Q取值范围内的最小值，此时获得最佳性能。

综上，对基于同一环境信息进行路径规划的以上参数，在每条影响曲线图中找到路径最短或迭代次数最少时对应的范围，得到基本蚁群算法参数组合选取范围为α∈[1,2]、β∈[1,2]、ρ∈[0.4,0.6]、Q∈[150,250]且m=(1～3)n。

为验证这一组合范围的性能，选取参数全部优化的组合与未优化做对比，观察其路径长度和迭代次数。如表1所示，在针对采用优化组合参数使得救援机器人进行规划路径时仅需要迭代次数89次，远远少于仅优化蚂蚁数目m和救援点数n的参数组合，且规划距离长度仅取3687M更少，且走过的路径长度更短。因此对于参数组合优化的更为合理，实用性更高。

表1 优化参数组合与部分参数优化组合的路径规划结果对比

5 结论

(1) 针对蚁群算法参数对算法性能的影响问题，基于研究旅行商问题的全局路径规划算法，运用单因素法对蚁群算法参数进行实验对比，分析了各参数对于算法路径寻优效率的影响，并得出在此类问题上各个参数的取值范围。

(2) 通过仿真结果证明了使用优化参数组合后，能够大幅度的提高救援机器人的路径搜索和自主运动能力，节约任务执行时间，提高了救援机器人参与实际作业的效率。同时为机器人优化路径规划提供了有力的理论依据和数据支持。