初始信息素不均匀分布的蚁群算法

薛永才，古姝祺，张均富*

（1.西华大学机械工程学院,四川 成都 610039；2.成都市自来水有限责任公司，四川 成都 610031）

路径规划是移动机器人的一项重要研究内容。机器人路径规划首先利用机载传感器获取机器人位置及环境信息，然后由规划算法自主规划出一条能避开障碍物并到达目标位置的可行安全路径。目前常用的路径规划算法可分为传统规划算法和智能规划算法。传统规划算法包括可视图方法、人工势场方法等；智能规划算法包括遗传算法、蚁群算法等[1]。

蚁群算法是模拟自然界蚂蚁觅食过程而提出的仿生智能优化算法。算法基本思想是蚂蚁在觅食的过程中分泌信息素用以指导后续经过该路径的蚂蚁进行路径选择，路径越短，蚂蚁留下的信息素也越多，蚂蚁选择更短路径的概率也越大，从而可以让蚁群找到一条到食物位置的最短路径[2]。

蚁群算法具有群体智能和正反馈特性，其寻路能力强，但存在收敛性差、易陷入局部最优解等缺点。其初始信息素分布直接影响算法的收敛性及收敛速度。针对该问题，学者们提出了多种改进方法。丁建立等[3]提出了一种遗传算法与蚁群算法相结合的初始信息素分配策略，采用遗传算法得到路径信息，再根据该信息与原始初始信息叠加作为信息素初值，将其应用于旅行商问题，得到了较好效果，但未应用于存在障碍物的地图类路径规划。杨乐[4]依据零点定理提出了一种初始信息素不均衡分配策略，其目的在于增强起始节点与目标节点间的所有节点的初始信息素，这对起点与终点所在直线上障碍物少的情况有较好提升效果。Verdaguer等[5]提出了采用有界信息素来解决搜索最优解失败的情况，其提出的蚁群算法提高了搜索效率，但未应用于存在障碍物的地图类路径规划。Luo 等[6]结合当前节点、下一个节点以及起点与终点之间的距离等因素计算得出初始信息素初值，从而得到不均匀的初始信息素，但没有考虑到障碍物分布对搜索的影响。何雅颖[7]提出了一种初始信息素增强方法，其根据环境障碍占比的多少而调整椭圆区域的大小，并将椭圆形内节点作为初始信息素增强区域，该方法考虑了障碍物的多少，但未考虑实际障碍物分布情况对搜索的影响。

可见，初始信息素的合理分配是提升蚁群算法寻优性能的方法之一。为此，本文提出一种基于双向搜索构建初始信息素增强区域的初始信息素不均匀分配策略，从而改善前期搜索的盲目性，提升蚁群算法前期收敛性。

1 蚁群算法基本原理

1.1 算法基本流程

传统蚁群算法包括参数初始化、禁忌表更新及走向确定、信息素更新等核心步骤。

1）参数初始化。初始化所有节点信息素T、初始禁忌表，设置起点终点位置、蚂蚁数量m、迭代次数L、信息素重要程度 α、启发式信息重要程度 β、信息素蒸发系数 ρ、信息素增强系数Q[8]。

2）禁忌表更新及走向确定。在算法开始时，将蚂蚁放置于起始点，出动蚂蚁开始寻路。蚂蚁寻路时，每只蚂蚁在任意时间t选择下一移动节点时均根据转移概率公式进行移动，其表达式为

式中：i表示当前所在点；j表示下一个可移动点；Jk(i)表示蚂蚁所有的下一个可移动点组成的集合；τij(t)表 示在时间t时 刻从节点i到 节点j该条路径上的信息素浓度；ηij(t)表 示在时间t时刻时所在位置j的启发式信息，在传统算法中，启发式信息为节点到下一可行节点直线距离的倒数。

3）信息素更新。当一次迭代中的所有蚂蚁均完成寻路后，各路径上的信息素按式（2）进行更新。

式中，∆τij表 示在该次迭代中边ij上信息素的增量，其表达式为

其中，∆τijk表示第k只蚂蚁在本次迭代中留在边ij上的信息素。如果蚂蚁k没有经过边ij，则∆τijk的值为0。∆ τijk有3 种模型，分别为ant-cycle 模型、ant-density 模型、ant-quantity 模型。其中，ant-cycle模型具有更好的性能，因为ant-cycle 模型利用全局信息进行信息素的更新，其余2 种采用局部信息进行更新，故蚁群算法通常采用ant-cycle 模型。antcycle 模型表达式为

式（4）重复迭代，输出结果：当一次迭代中的所有蚂蚁完成寻路后，记录下该次迭代的最短路径路线及其长度。重复上述步骤，在达到迭代上限次数后，最终输出本次算法迭代出的最优路径路线。

1.2 算法分析

在蚁群算法中，影响蚂蚁转移的2 个关键因素为信息素与启发信息。当蚂蚁有多个可移动点供选择时，各点的信息素值与启发信息值大小直接影响蚂蚁转移时的移动概率，信息素值高、启发信息值高的点，蚂蚁在概率上会更倾向于往该点移动。

启发信息是根据节点所在位置决定的，当环境地图确定后，各节点的启发信息值也相应确定且不再变化，故其在传统算法中，对蚂蚁寻路过程的影响有限；信息素是根据初始信息素与后续更新确定的，同一节点的信息素会随着多轮迭代中蚂蚁的移动而增加或减少，在同一地图中，各点的信息素会不断地变化，故同一节点在不同时刻对蚂蚁的吸引力也可能不同：因此，在传统算法中，信息素对蚂蚁的影响更大。

蚁群算法中，信息素存在着初始值赋值与后续更新。初始信息素值会影响算法的收敛速度与收敛性。传统蚁群算法中，所有节点的初始信息素值为同一常数，不同节点的信息素在数值上没有差异性，故第一轮的蚂蚁寻路中，各个可转移节点在信息素上对蚂蚁的影响是相同的，此时蚂蚁依靠节点启发信息值的不同进行概率性地移动。传统算法中所有节点相同初值的信息素分布方式，会导致蚁群前期搜索盲目、收敛性不强、收敛速度慢等问题的出现。

2 初始信息素不均匀分布策略

初始信息素不均匀分布是解决上述问题的可行方法。初始信息素不均匀分布的作用在于通过信息素差值引导蚁群更快地找到最短路径。其实现方式是通过对地图进行区域划分，找出可能存在最优路径的区域并增强该区域的初始信息素值，从而使增强区域与其他普通区域产生信息素上的数值差，蚁群在可行节点间移动时，会更倾向于向信息素浓度高的区域移动。因此，合理地构建初始信息素增强区域能够有效地加快算法收敛性能。

对此，文献[4]基于零点定理提出了一种初始信息素不均匀分布策略。该算法的核心思想是：在进行路径规划时，当起点与终点确定后，若起点与终点连线上不存在障碍物，该连线必定为最短路径，故基于零点定理，增强起点与终点间所有节点的信息素值。该算法在起点与终点所在连线上障碍物分布少时，算法的效果提升较佳，但在障碍物较多时，效果较差，原因在于该算法没有考虑到障碍物分布所产生的影响，导致其对不同地图的适应性较差。

对此，本文提出一种基于初始障碍物的初始信息素不均匀分布策略。该策略相较于文献[4]算法的主要差异在于：该策略考虑了由于障碍物分布不同而导致的可能存在最优路径区域的变化。该策略会根据不同地图的初始障碍物的不同而划分出对应的信息素增强区域，故该种算法对不同地图有一定适应性，且该策略基于双向搜索的思想对起点与终点附近的初始障碍物进行了局部路径寻优，进一步提高了增强区域内存在最优路径的可能性。

2.1 基本思想

传统蚁群算法各节点初始信息素等值，会导致前期收敛速度慢、搜索盲目。为此，本文结合双向搜索策略[9]，提出一种基于初始障碍物初始信息素不均匀分布的策略，以提升算法的收敛速度。

该策略的基本思想如下：首先以节点A为起始点、B点为目标点，沿搜索，遇首个障碍则开展绕障局部路径搜索，得到最短路径及其末端节点C，由节点C为起点构造与AB平 行的直线L1，得到L1与边界相交的节点E；然后按照相同原理，以节点B为起始点、沿搜 索，获得节点D和直线L2，以及与边界相交的节点F；最后所构造出的ACEBDFA的 边界及其内部的封闭区域即为初始信息素增强区域，如图1（a）所示，若2 边界所在直线L1与L2重合，则表示得到了一条首尾相连的路径，该路径所穿越的节点ACDB所构造的区域即为初始信息素增强区域，如图1（b）所示。

图1 局部寻优构建信息素增强区域

2.2 实现步骤

搜索策略在算法中具体实现步骤如下。

步骤1，创建记录表。创建节点坐标记录表，用以记录关键节点位置。

步骤2，探寻首个障碍物位置。从起始点开始，以终点为前进方向，找寻第一个不可行节点（即碰到第一个初始障碍物），记录下遇到障碍物前最后一个可行节点位置。

步骤3，对障碍物进行边界判断。对障碍物进行边界搜索，记录下障碍物边界节点。

步骤4，判断障碍物与起点的相对位置。进行数值判断，判断障碍物是否处于某些特殊位置从而导致特殊情况出现，例如初始障碍物上边界与地图上边界重合，导致蚂蚁不能从障碍物上边界经过，若存在这种特殊情况，则搜索策略跳过步骤5 进入步骤6，否则，进入步骤5。

步骤5，判断局部最优路径方向。进行数值判断，判断起点与各障碍物的边界节点直线距离大小，距离小的节点则是绕过障碍物的最短路径，记录下节点位置。

步骤6，连接局部最优路径。连接节点表中的关键节点，得到一条局部最优路径。

步骤7，连接边界。连接节点表中的关键节点，得到一条直线边界。

步骤8，终点方向与之同理，重复上述步骤得到另一局部最优路径及边界。

步骤9，赋值。加强所记录节点及2 条边界内所围成的封闭区域间的节点的初始信息素数值。

步骤10，初始信息素不均匀分布策略结束，进入算法全局路径寻优部分。

步骤11，初始信息素的分布赋值。根据前述搜索得到的增强区域按式（5）进行不均匀赋值。

式中：T代表信息素；P代表信息素具体的数值大小。为了体现不同节点的信息素差异性，增强节点的信息素值会大于普通节点的信息素值。为了避免增强节点的信息素过大造成在节点选择上陷入局部最优情况的出现，同时为了防止增强信息素过低导致增强效果不明显，本文将增强信息素的值限制在普通信息素值的2～5 倍间。

在存在障碍物的地图中，障碍物的分布决定最优路径的长度。初始信息素的不均匀分布可以为蚁群提供方向指导，避免盲目性，其实现原理为增强部分节点的信息素值，从而在提高蚁群在可行节点间转移时增强节点的被选择概率。

改进的初始信息素更新策略考虑了由初始障碍物分布决定的搜索方向，结合双向搜索的思想，对终点所在方向同样进行预搜索。该策略根据地图中的初始障碍物及终点的初始障碍物进行区域的划分，故对障碍物分布情况不同的不同环境地图有适应性。

2.3 改进算法的流程

基于初始信息素不均匀分布策略的改进蚁群算法流程图如图2 所示。

图2 改进蚁群算法流程图

步骤1，对参数进行数值的初始化。

步骤2，按所述的策略进行栅格的初始信息素数值计算，并按式（5）计算得出的数值对信息素进行对应更新，然后开始寻路。

步骤3，寻路时，m只蚂蚁选择起点作为其初始位置。

步骤4，出动第1 只蚂蚁，从所给出的起点位置开始搜索，根据当前位置及下一步的可选栅格位置按式（1）计算出每个可转移栅格的转移概率，再根据概率选择栅格进行移动，直到到达终点或无可移动栅格可选，第1 只蚂蚁寻路结束。记录下该只蚂蚁的行走路线及其长度，再出动下一只位于起点位置的蚂蚁进行寻路。该步骤在一轮迭代中共执行m次。

步骤5，一轮迭代的寻路结束后，对比每只蚂蚁的路径长度，记录下当次迭代的最优路线及其长度。

步骤6，依据此路线按式（4）更新信息素。

步骤7，在达到迭代次数前，重复步骤3 至步骤6，直到达到迭代次数。

步骤8，达到迭代次数后，对每代的最优路径进行长度对比，输出最优路径，算法结束。

3 仿真及分析

3.1 环境地图建模

移动机器人路径规划时的地图建模方法有几何图法、可视图法、栅格法等[10]。其中栅格法因其构图方式简单，便于更新维护而广泛应用于路径规划算法中。为此，本文采用栅格法进行地图构建。在栅格地图中，黑色栅格表示不可行栅格，为障碍物，且所在栅格被编入禁忌表；白色栅格为可行栅格，如图3 所示。

图3 栅格法建图

在向下一栅格运动时，若周围没有障碍物，共有8 个运动方向，每次移动1 个栅格；当某个方向存在障碍物时，则规定不能朝着该方向移动，如图4所示。

图4 栅格法中机器人的可移动方向

3.2 仿真分析

采用MATLAB R2018a 作为仿真环境，所构造的栅格地图如图5 所示，设置起点为节点A，其坐标为（0.5，19.5），终点为节点B，其坐标为（19.5，0.5）。在传统蚁群算法的基础上融入初始信息素不均匀分布策略是本文算法。为验证所提出的信息素不均匀分布策略的有效性，这里将文献[4]所提算法的初始信息素分布策略融入传统蚁群算法作为文献[4]算法用于仿真实验，与传统蚁群算法一同开展对比研究。表1 为3 种算法的主要参数设置。

图5 仿真栅格地图环境

表1 算法的主要参数设置

图6 示出采用本文算法、文献[4]算法、传统算法获得的最优路径。由图可知，3 种算法均可获得一条最优路径。

图6 3 种算法的最优路径

图7 示出3 种算法的蚁群探寻轨迹。由图可知，受初始信息素增强的影响，本文算法在探寻时，蚁群多集中于最优路径附近，没有蚂蚁进入死锁区域，仅有少数蚂蚁进入了右上的较差区域。文献[4]算法及传统算法均存在蚂蚁进入死锁区域的情况。可见，本文提出的初始信息素不均匀分布策略可以有效避免初期搜索的盲目性。

图7 3 种算法的蚁群探寻轨迹

在仿真实验中，笔者对3 种算法均进行了15 次仿真。本文算法收敛成功率为100%，其余2 种算法均存在不收敛及收敛于局部最优解的情况，如表2 所示。表2 同时给出每次仿真算法收敛时的迭代次数的平均值。本文算法相较于传统算法缩短了13.77 次，相较于文献[4]算法缩短了21.27次。可见，本文算法收敛速度均比其他2 种算法快。在最优路径长度方面，3 种算法均迭代出了相同长度的最优路径。在寻优时间上，本文算法相较于文献[4]算法快了0.059 s，相较于传统算法快了0.054 s。

表2 算法性能对比

4 结论

针对蚁群算法在机器人路径规划中存在收敛性差、易陷入局部最优等问题，本文提出了一种基于初始障碍物的初始信息素不均匀分布策略的蚁群算法。通过双向搜索与初始障碍物的分布情况，划分出特定的信息素增强区域，实现初始信息素的不均匀分布，解决蚁群算法前期搜索的盲目性，以此提升蚁群算法的收敛速度。仿真实验结果表明，在同一栅格地图下，本文算法相较于传统蚁群算法和文献[4]算法，在收敛成功率、收敛速度方面均明显提升，并且可有效避免初始搜索的盲目性。