基于优化蚁群算法的智能机器人路径规划研究

樊啸宇

摘 要：由于利用蚁群算法实现人工智能机器人路径规划领域中的算法自身缺陷问题，本文提出一种用于人工智能机器人路径规划的改进式蚁群算法。在人工智能机器人路径规划方面，采用基于栅格的技术实现路径量化工作；在获取全局路径最优解方面，基于排序的精英蚂蚁策略，提高全局最优解的搜索能力并提高算法的收敛速度。通过验证，基于人工智能的思想，在蚁群算法改良环节中成功引入了集成式算法创新模式，不仅实现了机器人路径规划自主选择性，而且提高路径寻优准确性和快速响应性。

关键词：人工智能；路径规划；蚁群算法；栅格；精英蚂蚁策略

中图分类号：TP242 文献标识码：A 文章编号：1671-2064（2018）20-0034-03

1 引言

在人工智能的研究领域中，路径规划是至关重要的一项研究分支。基于此，智能机器人的路径规划是指在给定的环境模型中，寻找一条从起始点到目标点的最优无碰撞路径的人工智能式自主择优过程。

其中蚁群算法是一种经典的启发式优化算法[1]，模拟了蚂蚁觅食的行为，通过释放信息素标记路径，之后经过的蚂蚁会根据遗留的信息素浓度选择较优的路径，经过一定次数的迭代后，能得到全局最优路径。蚁群算法虽然具有较强的鲁棒性、并行性和正反馈机制，具有很强的发现较好路径解的能力，但是也存在一些明显的缺陷：（1）每次迭代搜索后仅保留本次最优解，对历史信息利用率较低，导致算法的收敛速度相对较低；（2）易陷入局部最优解而使算法迭代停滞，不利于更好解的发现。针对蚁群算法的以上缺陷，目前大致有两种改进方案：一种是在经典蚁群算法的基础上进行改进[2]，另一种是将蚁群算法与其他智能算法结合，如遗传算法[3]、免疫算法[4]等。

为了提高蚁群算法的路径量化分析和获取全局最优解的能力，本文在路径规划构建方面，采用了基于栅格的思想；在获取全局最优解方面，采用了基于排序的精英蚂蚁策略。基于以上人工智能的算法集成创新，实现人工智能机器人路径规划获取全局最优解的过程。

2 基于栅格思想规划路径的蚁群算法构建

2.1 构建用于路径规划的蚁群算法

在蚂蚁k（k=1，2，…，m）的运动过程中，各条路径上的信息素浓度决定其移动方向。表示在t时刻蚂蚁k由栅格i（xi，yi）转移到栅格j（xj，yj）的状态转移概率，由各条路径上残留的信息素浓度及路径的启发信息计算，蚂蚁在选择路径时会尽量选择离自己距离较近且信息素浓度较大的方向。状态转移公式为：

（2-1）

其中表示蚂蚁k下一步可以选择的节点，C为全部节点集合；

（k=1，2，…，m）表示禁忌表，记录蚂蚁k当前已走过的城市；

α表示信息启发因子，反映了信息素浓度的相对重要程度；

β表示期望启发因子，反映了期望值的相对重要程度；

表示边（i，j）上的信息素浓度；

表示边（i，j）上的启发信息，一般取栅格i到栅格j距离dij的倒数，即。

为了防止残留信息素浓度过大导致启发信息的作用不明显，在蚂蚁完成一次迭代后，对信息素浓度进行更新处理。信息素更新规则为：

， （2-2）

（2-3）

其中ρ表示信息素挥发系数，则表示信息素残留系数；

表示边（i，j）上的信息素增量；

表示蚂蚁k在边（i，j）上的信息素增量。

2.2 信息素增量的计算

根据信息素增量的不同，M.Dorigo提出三种蚁群算法模型[5-6]：蚁周模型、蚁量模型、蚁密模型。蚁周模型的原理是利用蚂蚁经过路径的总长度（整体信息）计算信息素增量；蚁量模型的原理是利用蚂蚁经过的节点间的距离（局部信息）计算信息素增量；蚁密模型的原理是将信息素增量取为恒值，没有考虑不同蚂蚁经过路径的长短。

鉴于信息素增量计算的普遍适用性和非特定条件约束的前提下，蚁周模型的性能优于其他两种模型[7]，因此本文采用蚁周模型：

（2-4）

其中Q为常量，表示蚂蚁在一次迭代中释放的信息素总量。

Lk表示第k只蚂蚁在本次迭代中经过路径的总长度。

3 基于排序的精英蚂蚁策略改进的蚁群算法设计

由于蚁群算法存在收敛速度慢和容易出现停滞现象等缺陷，本文将采用基于排序的精英蚂蚁策略并对之优化，修正蚁群算法的上述缺陷，进而优化蚁群算法获取全局最优解的过程。

基于排序的精英蚂蚁策略改进蚁群算法的具体思路：通过信息素更新，实现蚂蚁的解的多种可能性，为最大—最小蚂蚁策略突破蚁群算法过早收敛于局部最优解的局面做铺垫；同时，引入自适应特性的信息素挥发系数更新机制，完善全局解的搜索能力并提高算法自身的收敛速度。

3.1 信息素更新设计

传统的精英蚁群系统[8]为了使当前找到的最优解在下一次迭代中对蚂蚁更有吸引力，在每次迭代結束后给予所有已经找到的最优解额外的信息素增量。这些获得额外信息素增量的路径视为被精英蚂蚁走过，这些路径上的某些边可能属于全局最优解。

然而精英蚂蚁对应的路径上的额外信息素增量，使得某一条路径上的信息素浓度急剧增加，降低了后续蚂蚁选择其他最优解的概率，影响了后续蚂蚁的解的多样性，容易造成算法的早熟，使得算法收敛于某一局部最优解。因此，本文在精英蚂蚁策略中加入排序策略[9]，将不同的路径根据信息素浓度进行排序，分别给予不同程度的信息素增量（赋予精英蚂蚁的优秀程度越高，给予的信息素增量越大），同时对于每一次迭代中的最优解给予一定的额外信息素增量。这样提高了后续蚂蚁的解的多样性，解决了因收敛过快而停滞于局部最优解的问题。

具体方法如下：每次迭代完成后，蚂蚁按路径长度排序，即L1≤L2≤……≤L3，根据蚂蚁的排名μ对信息素增量进行加权。设ω为当前最优路径上信息素的权重，ω必然大于等于其它权重。第μ个最优路径的权重为max{0，ω-μ}。同时，给予当前最优路径额外的信息素增量。基于排序的精英蚂蚁策略下的信息素更新设计则为：

， （3-1）

其中表示只蚂蚁在边（i，j）上根据排名的信息素增量：

（3-2）

（3-3）

（3-4）

其中μ为最优蚂蚁排名，为第μ只最优蚂蚁在边（i，j）上的信息素增量，为第μ只最优蚂蚁的路径总长度，为精英蚂蚁在边（i，j）上的信息素增量，为当前最优路径的总长度。

3.2 最大—最小蚂蚁策略

在基于排序的精英蚂蚁策略的基础上，为了进一步避免算法过早收敛于局部最优解，可以引入最大—最小蚂蚁策略[10]，即在每次迭代后将各条路径可能的信息素浓度限制在区间内，超出这个范围的值被强制设为或者是。这样可以有效地避免某条路径上的信息素浓度远大于其余路径，使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩散。

在此基础上增加信息素浓度平滑机制可以提高性能，即当信息素浓度收敛或接近收敛于最大值时，通过增加选择低强度信息素浓度路径的概率以提高发现新解的能力。

， （3-5）

其中和分别为平滑化之前和之后的信息素浓度。

3.3 信息素挥发系数自適应

在基于排序的精英蚂蚁策略的基础上，信息素挥发系数ρ直接影响算法的全局搜索能力及收敛速度[11]。为了既使算法拥有较强的全局搜索能力，又避免其出现停滞状态，引入信息素挥发系数自适应策略：

， （3-6）

其中为ρ的最小值，γ为挥发系数衰减常数，取0.95。

算法运行初期ρ较大，信息的正反馈作用占主导，从未搜索过的路径上的信息素浓度趋近于0，再次选择已搜索过的路径的可能性较大，收敛速度比较快，易出现局部收敛。后期ρ逐渐减小，信息的正反馈作用逐渐减弱，从未搜索过的路径信息素浓度增大，搜索的随机性能增强，全局搜索能力提高，但会降低蚁群算法收敛速度，所以设置一个最小值，防止ρ过小而使算法停滞。

信息素挥发系数自适应更新规则为：

（3-7）

4 技术路线流程设计（图1）

步骤1：构建栅格模型，初始化改进蚁群算法中的原始参数，设置蚂蚁数量m、信息启发因子α、期望启发因子β、信息素挥发系数ρ、信息素总量Q、最大迭代次数NCmax。初始化禁忌表，迭代次数NC=1。

步骤2：蚂蚁k（k=1，2，…，m）开始遍历。更新蚂蚁k当前位置的禁忌表，根据状态转移公式（2-1）计算每个可行栅格的转移概率，使用轮盘赌的方法选择下一个栅格。

步骤3：一次迭代完成后，蚂蚁按路径长度排序，根据排名μ对信息素增量进行加权，同时根据信息素挥发系数自适应策略更新信息素挥发系数ρ，共同作用对信息素浓度进行更新。

步骤4：使用最大—最小蚂蚁策略，进一步更新信息素浓度。

步骤5：令迭代次数。若，则清空禁忌表，跳转至步骤2，直到为止；否则输出全局最优解。

5 仿真和说明

本文以实际真实路径作为参考，分别采用常规的蚁群算法和改进的蚁群算法在逼近真实路径方面进行对比。具体仿真参数设定如表1所示。

通过上述参数数值设定，常规的蚁群算法和改进的蚁群算法分别对路径进行规划，其路径规划效果对比如图2所示。

从图2可知，纵坐标代表与理想真实路径的吻合度，横坐标表示路径规划的耗时。由于改进的蚁群算法较正常的蚁群算法复杂，故路径规划前期效果较差；但是，随着路径规划过程不断迭代，最终采用改进的蚁群算法路径规划吻合度高达98.7%，高于采用蚁群算法的路径规划吻合度89.4%；同时，在路径规划效果达到稳定状态的过程中，改进的蚁群算法耗时257.4ms小于蚁群算法耗时329.2ms。

仿真结果表明：在路径规划吻合度方面，改进的蚁群算法搜索全局最优解的能力得到提升；在节约时间成本方面，改进的蚁群算法收敛速度更快。

6 结语

本文针对人工智能路径规划领域的蚁群算法进行改进，设计基于排序的精英蚂蚁策略改进的蚁群算法模型，采用排序策略、信息素挥发系数自适应策略和最大—最小蚂蚁策略改进信息素更新规则，以完善对全局最优解的搜索能力并提高算法的收敛速度。通过仿真，证明本设计具有理论优势和实际应用价值，并为后续的人工智能机器人路径规划研究提供了参考方案。

参考文献

[1]Colorni A， Dorigo M， Maniezzo V. Distributed Optimization by Ant Colonies[C]// Ecal91-European Conference on Artificial Life. 1991：134-142.

[2]喻环.改进蚁群算法在机器人路径规划上的应用研究[D].安徽大学，2017.

[3]赵凯，李声晋，孙娟，赵锋.改进蚁群算法在移动机器人路径规划中的研究[J].微型机与应用，2013，32（04）：67-70.

[4]邱莉莉.基于改进蚁群算法的机器人路径规划[D].东华大学，2015.

[5]Gambardella M，Dorigo M. Solving symmetricand asymmetric TSPs by ant colonies[C]//Proc of the IEEE Conf on Evol Compu， 1996：622-627.

[6]Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a colony of cooperating agents[J]. IEEE Transaction on System， Man and Cybernetics： Part B， 1996， 26（1）： 29-41.

[7]胡小兵.蚁群优化原理、理论及其应用研究[D].重庆大学，2004.

[8]B.Bullnheimer， R.F.Hart， C.Strauss. Applying the ant System to the Vehicle Routing Problem. Meta-Heuristics： Advances and Trends in Local Search Paradigms for Optimization. Kluwer， Boston， 1998：109-120.

[9]任瑞春.基于排序加权的蚁群算法[D].大连海事大学，2006.

[10]王鸿豪.基于蚁群算法的机器人路径规划及其在港口上的应用探讨[D].武汉理工大学，2007.

[11]申铉京，刘阳阳，黄永平，徐铁，何习文.求解TSP问题的快速蚁群算法[J].吉林大学学报（工学版），2013，43（01）：147-151.