改进蚁群算法及其应用

代婷婷, 朱桂玲, 胡晓飞

(昭通学院 数学与统计学院，云南 昭通 657000)

人工智能在科技发展中具有很重要的地位，是科技发展的一大分支。随着理论和技术的不断完善，其应用的范围越来越广，尤其是人工智能在生活中带给人们的方便无处不在，在推动社会的现代化进程中起了非常关键的作用[1]。智能算法的研究在20世纪60年代就已经开始，靠人力无法解决的很多问题，使用智能算法都显得轻而易举。智能算法的种类较多，应用的范围也比较广泛，国防、农业、工业、物流运输等领域都有用到。蚁群算法就是其中常用的一种，诸如输电网规划、车间调度、路径规划、物流配送等方面都经常用到[2-3]。

机器人在当前的生产生活中正在代替人在一些场合发挥着日益重要的作用[4]。为了满足人类的各种需求，必须深入分析复杂多变的环境，设计合理的算法程序，实现自主导航。路径规划是移动机器人实现这一目标的核心技术，是研究的热点[5]。在一定程度上，机器人路径规划水平的高低决定着机器人的智能水平。因此，寻找高效的机器人路径规划方法非常重要[6]。

蚁群算法在智能算法中是常用的一种方法，虽然在收敛速度等方面有不足和局限，但是，它具有的正反馈性、强鲁棒性、并行性等优点在机器人路径规划中有优势。很多学者已经验证了蚁群算法在寻找最优路径方面有较高的速度[7-8]。鉴于此，将文献报道的改进蚁群算法[5-6]进行融合，得出了一种新的改进蚁群算法，并且将此方法应用于解决机器人路径规划问题。

1 相关理论

1.1 基本蚁群算法

蚁群算法的相关思想和计算步骤是由Marco Dorigo[7-9]于1992年在他的博士论文中首次提出来的，蚂蚁在寻找食物的途径中会选择最短的路径，而选择最短路径的关键是信息素浓度的引导作用。随着行走在前面的蚂蚁在路径上留下的信息素浓度的变化，后来者的蚂蚁会选择信息素浓度大的路径作为自己的行走路径，则这条路径上行走的蚂蚁数量会增多。随着分泌信息素的蚂蚁增多，这条路上留下的信息素浓度又会进一步增大，那么后面的蚂蚁选择该条路径的概率越大。按照此机制，以达到寻找最短路径的目的。具体模型：

设i为外出觅食蚂蚁的出发点，则其到达觅食终点j的随机行进概率：

(1)

其中：pijk(t)表示从t时刻开始，蚂蚁k从节点i到节点j的转移概率；α表示蚂蚁在觅食路径上用于剩余信息素交流刺激后来蚂蚁的诱发因子；β为启发式信息对蚂蚁行进方向期望的诱发因子；allowedk表示蚂蚁在觅食路径中尚未访问的节点集合。

将已经访问的节点集合放入tabuk中，tabuk是一个用来记录蚂蚁行进路径的记录表。从式(1)可以看出，信息素浓度高而且距离蚂蚁较近的路径在蚂蚁觅食过程中很容易被选到。每一次每一只蚂蚁经过某一条路径后都会马上按照式(2)和式(3)更新该路径上的信息素[10-11]。

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

(2)

(3)

其中：ρ表示随着时间的变化信息素挥发的变量；1-ρ表示挥发后留下来的信息素变量；m表示蚂蚁的数量；Δτij(t)表示t时间范围内节点i到节点j的信息素量变大小；Δτijk(t)表示在t时间内，蚂蚁k从节点i到j行走中释放的的信息素量大小。

1.2 环境建模方法

机器人的路径规划问题，需要对机器人所处的环境模拟建模，这样才可以更方便地研究其路径的规划问题。模拟环境的建模方法有很多，本文选择最常用的栅格法进行环境建模。

栅格法环境建模的做法是将机器人所处的运行环境划分成大小相同的正方形栅格，一个栅格表示一个单位，每个栅格边长是环境最小行走单元，栅格内的情况可以忽略不计。

首先，规定机器人的栅格坐标由中心点表示，采用坐标法和序号法对每一个栅格进行标记和编号；其次，使用白色表示安全区域，用彩色表示障碍区域。除去曾经走过的栅格，机器人可以向安全区域的任意方向行走。文献[5]中的20×20栅格示例如图1所示。

图1 20×20栅格示意图

2 改进蚁群算法

2.1 改进启发函数

影响最短路径计算结果的主要因素是节点之间的概率转移和行走路径上的信息素浓度的更新。一般情况下，取节点i与下一个节点j之间的欧氏距离的倒数作为转移概率中的启发函数。实际上，在最初搜索的时候，行走路径上的蚂蚁数量较少，释放的信息素较少，造成其他蚂蚁偏离正确寻找路径的概率较大，从而形成局部最优解或无效解[12]。文献[5]在启发函数中引入了下一节点和目标节点之间的欧氏距离，从而加强当前节点与目标节点的联系，数学表达式为：

(4)

其中：dij表示当前节点i与下一个可行节点j之间的欧氏距离;djE是下一可行节点j到目标节点E的欧氏距离。搜索路径的方向性被加强，运行时间也就相应缩短，提高了算法的时间效率。

2.2 更新信息素浓度

信息素浓度的更新方式对蚁群算法的效率也具有较强的影响力[13]。更新信息素浓度的主要原因有以下几方面：第一，信息素浓度与路径的长度有着密切的联系，为了防止积累过多使算法过早局部收敛，对信息素浓度进行更新是必不可少的；第二，随着时间的推移，信息素会因为蒸发使其在蚂蚁行走路径上的浓度降低；第三，经过行走路径的所有蚂蚁都会释放信息素，正因为其正反馈性，最短路径上的蚂蚁最多，信息素也最多，要在全部路径中凸显最优路径[14-15]。文献[6]找到了当次迭代中的最优路径和最差路径，通过加强最优路径上的信息素同时减弱最差路径上的信息素释放量，将信息按照式(5)的方式更新，防止收敛过快而陷入局部最优。

(5)

式中：Lbest表示此次迭代中最优路径长度;Lworst表示此次迭代中的最差路径。

2.3 改进蚁群算法的步骤

针对以上两种改进的优点，本文将启发函数改进和信息素浓度更新的方案结合起来，提出了一种新的改进蚁群算法。通过在启发函数中加入与最终节点的距离，同时增加或减少在信息素更新时找到的最优解和最差解的信息素浓度，提高了算法的性能。具体步骤如下：

Step1:设m为蚂蚁数量，s为起始点，g为目标函数，Nmax为最大的迭代次数，设置α和β的值分别为1和6，将所有的蚂蚁都置于起始点；

Step2:使所有蚂蚁都从s点出发，接着将出发点s加入到禁忌表中；

Step3:依据公式(4)寻找下一个节点，将找到属于可行节点集合的节点作为下一个可行节点，并且将其放入到禁忌表中；

Step4:对当前蚂蚁的行走路径做好标记，判断蚂蚁是否已到终点，如果没有到达终点，返回至Step3；若是蚂到达了终点，接着判断其是否已走完全程，是则执行Step5，否则转至Step2使下一只蚂蚁出发；

Step5:等到全部蚂蚁到达目标节点之后，计算每只蚂蚁的路径长度，找出最优解和最差解，然后按照公式(5)对信息素更新，同时增加迭代次数；

Step6:在迭代次数达到最大的时候，输出最短路径，否则转到Step2。

3 实证分析

为了验证本文提出的改进蚁群算法的可行性和有效性，应用MATLAB2019进行仿真实验。让机器人处在图1的栅格障碍环境中，分别使用普通蚁群算法和改进的蚁群算法，测试机器人寻找无碰撞的最短路径的问题。在实验的过程中设定机器人工作的目的是找到一条从起点到终点的没有碰撞的最短路径，比较两种算法在寻找最短路径过程中用时的长短和路径的优劣。改进蚁群算法在实验中的参数设置如下表1所示。

表1 改进蚁群算法的实验参数设置

两种算法的实验仿真结果如图2和图3所示。

图2表明，普通蚁群算法和改进的蚁群算法寻找到的最优路径一样，最优路径的长度是29.21。图3可以看出，普通蚁群算法迭代18次可以找到最优路径，而改进的蚁群算法跌代3次即可得到最优路径，说明改进的蚁群算法的搜索效率较普通蚁蚁群算法有很大的提升。

图2 两种算法的最优路径

(a)普通蚁群算法 (b)改进蚁群算法

综上所述，改进的蚁群算法收敛速度更快，可以在短时间内搜索到最优解。

4 结 语

在查阅相关文献的基础上，将改进启发因子和改进信息素更新融合在一起，产生了一种新的改进蚁群算法。为了更直观看出改进算法的优势，选用栅格法对机器人的路径环境进行模拟建模，通过建立20×20栅格障碍环境，将改进蚁群算法和普通蚁群算法应用于此环境，利用MATLAB2019进行仿真实验，让机器人找到从起点到终点的一条无碰撞的最短路径。实验仿真的结果表明，虽然改进蚁群算法和普通蚁群算法找到的最优路径相同，长度都是29.21,但是改进的蚁群算法较普通蚁群算法能在更短的时间内找到最优路径，说明本文的算法不但可行，而且搜索效率较高。