0 引言

蚁群算法作为一种随机搜索寻优方法，其需要解决的问题关键是在“探索”和“利用”之间寻找一个平衡点^[1-3]：既要使算法的搜索空间尽可能大，以寻找全局最优路径，又要利用距离信息、启发式信息和信息素等，使系统以较大概率收敛到全局最优，其本质是解决蚁群算法解的多样性与收敛到全局最优的速度之间的矛盾^[4-6].

移动机器人在进行路径规划之前，需要将工作环境转化成机器人可以识别的二维空间环境模型.环境建模方法有很多，如栅格法、拓扑图、可视图、几何信息法等.栅格法是应用最多的环境建模方法，机器人就是通过创建的栅格地图和真实工作环境对应联系.在栅格环境下，蚂蚁下一步只能选择离自己最近的8个栅格，这8个栅格到达终点距离的差异较小，使得启发函数的作用受到极大的限制，改进启发式函数，对解决路径规划问题^[7-12]至关重要.文[13]提出了距离改变启发式因子，这为算法启发式的设置提供了一种新的思路，从另一个方面考虑了贪婪的设置，但实际上这也是一种方向启发，这种方法没有提供跳出U型障碍物的可能性，值得注意的是该文献提供了一种双种群的方法来跳出凹型障碍物，这样两种方法结合也是一个不错的选择.文[14]提出引入方向夹角启发信息函数，在和当前节点距离相等的可选节点集合中，每个可选节点与终点连线的夹角称之为方向夹角，夹角越小距离终点越近，方向优先.文[15]提出基于距离和方向的启发式概率公式，可以在算法初期通过距离和方向来调节蚂蚁的对路径的选择，减少蚁群算法搜索的盲目性，提高了蚁群寻找优势路径的概率.

蚂蚁会在经过的路上释放一定的信息素，后来的蚂蚁会根据路径上信息素的浓度调整转移概率，进行路径选择，因此信息素的分布对蚂蚁全局路径规划的优劣相当重要.在经典的蚁群算法中，初始信息素的浓度通常为一个相等的值，因而在搜索的初期需要消耗大量的时间来对路径进行筛选，使得算法的收敛速度变慢.文[16]提出了初始信息素分布规则，在终点明确的情况下，对8个方向做优劣区分使蚂蚁在方向选择上有侧重点，越朝向终点位置的地方初始信息素浓度越高，引导蚂蚁朝着正确的大方向行走；文[17]提出动态更新信息素挥发系数，避免陷入局部最优，此外，还提出不可行路径信息更新规则，增大蚂蚁的全局搜索能力，尽可能找到最优路径.

为改善蚁群算法收敛速度慢，容易陷入局部最优解的问题，本文提出基于启发式机制的改进蚁群算法.通过候选节点到目标点的距离动态调整启发函数，即候选节点距离目标点远分配权值小，距离目标点近分配权值大，以提高收敛速度；算法陷入局部最优时，引入惩罚函数，使最优路径上的信息素快速下降而减小蚂蚁下一次搜索正反馈的影响，使算法跳出局部最优.仿真实验结果表明，在复杂障碍物环境中，包括终点处存在凹形障碍物时，本文算法不但可以提高收敛速度，而且明显改善了解的质量.

1 ACS算法

蚁群系统(ACS)是由Dorigo和Gambardella于1996年提出，用于改善蚂蚁系统(AS)的性能.在ACS算法中，蚂蚁选择下一个节点时采用了不同于AS算法的状态转移规则，即由参数q₀控制的伪随机比率规则^[18]，公式为

(1)

其中，q₀为给定常数，q₀是[0, 1]中符合均匀分布的随机数，当q≤q₀时，选择的下一节点为所有可行节点中τ_ij^α(t)η_ij^β(t)值最大的节点；当q>q₀时，V按照式(2)的概率转移公式选择下一个节点：

(2)

其中，allowed_k表示蚂蚁k可以到达的节点；α为信息启发式因子，反映了路径上积累的信息素对后续蚂蚁选择该路径的影响程度，α越大就表示后续蚂蚁选择之前蚂蚁走过路径的可能性越大；τ_ij(t)表示边弧(i，j)的信息素浓度；β为期望启发式因子，反映了启发信息对蚂蚁路径选择的影响程度，β越大就表示该状态转移概率越接近于贪心规则；η_ij(t)为启发函数，表示边弧(i，j)的能见度.

为了避免蚂蚁走过的路径上残留信息素过多，削弱启发信息的作用，从而阻碍算法找到全局最优解，陷入局部最优解，所以需要在每只蚂蚁走完一步或者完成对所有节点的搜索后，对蚂蚁走过路径上的信息素及时更新以提高解的质量和算法的收敛速度.局部和全局信息素的更新规则为：

1) 局部更新规则

每只蚂蚁从某一节点i移动到下一节点j后，按照式(3)更新边弧(i，j)上的信息素.此种信息素更新方式使蚂蚁在路径构建过程中更倾向于选择与上一次路径不同的路径.局部更新规则的公式为

(3)

其中，ξ为局部信息素挥发系数，ξ∈(0，1)；τ₀为各路径上的初始信息素浓度值.

2) 全局更新规则

在ACS中，所有蚂蚁循环完成后才进行全局信息素更新且只更新当前最优路径上的信息素.运用此种更新方式会使蚂蚁的路径搜索更具针对性，蚂蚁更倾向于搜索算法当前迭代为止发现的最优路径.全局更新规则的公式：

(4)

(5)

其中，ρ为全局信息素挥发系数，1-ρ为信息素残留因子；Δτ_ij^k为本次循环中第k只蚂蚁在路径(i，j)上的信息素；L_gb为从路径构建开始到目前搜索到的全局最优路径的长度.

2 基于启发式机制的改进蚁群算法 2.1 目标吸引策略

本文采用栅格法对环境进行划分，起点和目标点分别为S和G，路径规划的目标是寻找一条从起点S到目标点G避开障碍物的最短路径.栅格环境为X行Y列，首先对栅格进行编号(按照从左到右，从上到下的顺序)；然后对候选栅格(可沿左上、上、右上、右下、下、左下、左八个方向到达的相邻栅格)进行编号，如图 1所示；最后每个栅格是否有障碍物用a_i表示：

当前节点i的8个方向，如图 1所示，可表示为D_i={1，2，3，4，5，6，7，8}，D_j∈D_i，D_j代表下一节点j的具体方向.

栅格法以每个栅格为基本单元，将每个栅格看作节点，将各个节点连接形成边.根据欧几里得距离准则，对图 1中当前节点与8个方向上的邻接点构成的每条边赋予权值，可表示为.

传统蚁群算法中的启发函数为当前节点i到下一节点j距离的倒数，会导致蚂蚁在搜索过程中贪图当前最优路径而错过全局最优路径.针对以上问题，本文提出目标吸引策略，启发函数主要分为2步计算：第1步，根据式(6)计算下一可行节点j到目标点G的距离；第2步，通过设置等差数列式(7)作为权值来区分启发式大小，具体规则为：根据计算得出的距离进行排序，距离小则赋予较大的权值，距离大则赋予较小的权值.

目标节点已知，计算出当前点在D_j方向上的下一可行节点j到目标点G的距离：

(6)

其中，j∈allowed_k，allowed_k表示蚂蚁k下一步允许选择的节点j.

(7)

其中，a₁=1，d=1，w为首项为1，公差为1的等差数列. n表示d_j，G中数据从大到小排序后的序号(d_j，G距离相等时，序号相同)，即d_j，G中最大的元素对应系数w=1，排名第2的元素对应系数w=2，因下一节点的选择最多有8个方向，所以d_j，G中的元素最大的对应系数为w=8.蚂蚁在移动过程中会受到目标点的方向信息影响，此影响的大小由权值w调整，改进的启发函数为

(8)

因障碍物环境规模会有不同，对其系数进行归一化处理：

(9)

(10)

其中，X和Y表示栅格有X行Y列.

2.2 信息素更新策略

判断算法陷入局部最优时，引入惩罚函数τ_ij=λτ_ij，λ∈(0，1)：

1) 蚂蚁搜索的过程中，当遇到复杂地形时，很容易形成路径死锁状态(或者说，蚂蚁进入“死亡”状态).为使陷阱周围路径上的信息素快速下降而不影响蚂蚁下一次的搜索，引入惩罚函数.

2) 最优路径的长度连续10代没有改变，引入惩罚函数.

改进的信息素更新公式为

(11)

其中，L_best为当前最优路径.

2.3 改进算法流程

算法的流程为：

算法参数初始化，将m只蚂蚁放置在起点S处；

for NC=1 to NC_max

  for k=1 to m

    初始化禁忌表；

    将起点S移动到禁忌表中；

    判断蚂蚁k的候选节点是否在禁忌表中；

    while(候选节点存在 & & 蚂蚁没有到达目标点G)

        if候选节点为空

            进行下一只蚂蚁；

        end

        利用改进的启发函数式(8)，每只蚂蚁根据式(1)或式(2)选择下一节点；

        if候选节点中包含目标点G

            下一节点选择目标点G；

        end

        更新禁忌表；

    end

    进行局部信息素更新；

    if蚂蚁进入“死亡”状态

        引入惩罚函数式(11)，重新分配信息素；

    end

  end

  进行全局信息素更新；

  当前最优路径长度连续10代没有发生改变，引入惩罚函数式(11)，重新分配信息素；

end

根据以上算法流程进行时间复杂度分析，外层循环为迭代次数NC_max，内层循环为蚂蚁数m，其它影响因素忽略不计，整个算法的时间复杂度为O(NC_maxm). ACS算法的时间复杂度也为O(NC_maxm).由此可见，本文算法的时间复杂度与ACS算法相比并未改变.

3 实验结果及分析

为了验证改进蚁群算法的有效性，在Matlab平台上进行了仿真实验，比较ACS算法和本文改进算法的仿真结果，并对仿真结果进行了分析.

在ACS算法中，启发函数只是当前节点到下一节点距离的倒数，导致蚂蚁因贪图当前最优路径而错过全局最优路径.而本文改进算法引入了启发式机制的思想，将候选节点和目标点的关系考虑到算法中，蚂蚁在移动过程中会受到目标点的方向信息影响，此影响的大小由权值w调整，以提高算法的收敛速度；此外，为避免算法陷入局部最优，引入惩罚函数重新分配路径上的信息素.本文改进算法不仅使得蚂蚁在构建路径过程中更具方向性，加快了算法的收敛速度，还在一定程度上提高了解的质量.

算法参数的设置如表 1所示.

实验结果如图 2~图 7所示，其中，图 2~图 5的对比实验采用了特殊情形的障碍物环境，图 6、图 7则采用一般的障碍物环境.

图 2为3种算法(分别为本文算法、文[19]算法及ACS算法)在遇到起点附近和终点附近都出现凹形障碍物的情形时，进行对比实验的结果(设置起点S=1，终点G=400).传统的ACS算法在遇到起点附近的凹形障碍物和终点附近的凹形障碍物时，均陷入局部最优.而文[19]考虑到启发式对算法初期多样性的影响，设置了一个距离阈值，在蚂蚁路径超过这个阈值时再使用启发式，虽然这样可以使算法跳出初始凹形障碍物的影响，但是如果凹型障碍物出现在终点附近时，仍然较大可能的陷入局部最优解.本文算法在ACS算法的基础上进行改进，通过候选节点到目标点的距离动态调整启发函数，即候选节点距离目标点远分配权值小，距离目标点近分配权值大，同时为了避免算法陷入局部最优，引入惩罚函数，使最优路径上的信息素快速下降从而使蚂蚁下一次搜索受到的影响力降低.实验结果表明，凹型障碍物出现在终点附近时，本文改进算法在解的质量和收敛速度上仍可显示出良好的性能.

图 3为ACS算法和本文算法在Z型障碍物环境中的对比实验结果(设置起点S=1，终点G=400).由此看出，ACS算法并没有得到全局最优路径.为使算法有效的跳出局部最优，本文算法引入了惩罚函数，重新分配当前最优路径上的信息素，会使其对蚂蚁下一次搜索的影响有所减小，增加了算法解的多样性，从而得到全局最优路径.实验结果表明，本文提出的改进算法是可行且有效的.

图 4为两种算法在特殊情形(起点和终点都位于凹形障碍物内)情况下的实验结果，图 5为两种算法在同一栅格环境中起点和目标点互换后的对比实验结果.文[9]中提出根据目标点自适应调整启发函数的思想，虽然算法的收敛速度以及解的质量都得到了提升，但是仅限于目标点在其当前点右下方的情况.本文算法借鉴了文[20]的思路改进启发函数，将候选节点和目标点的关系考虑到算法中，即候选节点距离目标点远分配权值小，距离目标点近分配权值大，改进后的算法可以适用于目标点在当前节点的其它方向.结果表明，本文改进算法在提高收敛速度的同时，也在一定程度上增加了解的多样性，避免算法陷入局部最优.

图 6、图 7为两种算法在栅格环境30×30(设置起点S=1，终点G=900)、栅格环境50×50(设置起点S=1，终点G=2 500)中的对比实验结果，由此可看，本文的改进算法不管是在特殊情形的障碍物环境中，还是在普便的障碍物环境中，都可以达到良好效果.

在每个障碍物环境中运行50次，对各算法的对比实验数据进行统计，得到的结果如表 2所示.

4 总结

传统蚁群算法在机器人路径规划中存在搜索时间较长，容易陷入局部最优等问题.针对这些问题，本文在ACS算法的基础上引入了启发式机制的思想.考虑候选节点和目标点之间距离的关系，蚂蚁在移动过程中会受到目标点的方向信息影响，此影响的大小可由权值w调整，以提高算法的收敛速度.此外，为避免算法陷入局部最优，引入惩罚函数重新分配路径上的信息素.在求解最短路径问题上，本文基于启发式机制的改进算法在收敛速度和解的质量方面有着良好性能，不仅可以用于普遍的障碍物环境，还可用于特殊的障碍物环境.为使本文算法在实际场景中更好地得到应用，下一步探讨路径长度、规划路径上的时耗等多目标路径规划问题.