基于迭代局部搜索的路径规划蚁群算法

许健 许峰

摘要：针对蚁群算法易早熟及局部搜索能力欠佳的缺陷，将迭代局部搜索策略引入蚁群算法。新算法的基本思想是：从初始解出发，用蚁群算法进行局部搜索，如陷入局部最优，则产生一个摄动解作为新的初始解再进行局部搜索，根据接受规则决定进入下一步迭代的局部最优解。将改进算法应用于二维路径规划，数值实验表明，改进算法相比基本蚁群算法有更佳的局部收敛性，可获得比基本蚁群算法结果更优路径。

关键词：蚁群算法；迭代局部搜索；局部收敛性；路径规划

DOIDOI：10.11907/rjdk.173181

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）008-0031-04

英文摘要Abstract：Ant colony algorithm is easy to premature and the ability of local search is poor.The iterative local search strategy is introduced into ant colony algorithm.The basic idea of the new algorithm is that the new algorithm starts from the initial solution and use ant colony algorithm for local search.A perturbation solution is generated as a new initial solution，and then the local search is carried out if it falls into the local optimum，and the local optimal solution of the next iteration is determined according to the acceptance rule.The improved algorithm is applied to two-dimensional path planning，and the numerical experiments show that the improved algorithm has better local convergence than the basic ant colony algorithm，and it can obtain better path than that of the basic ant colony algorithm.

英文关键词Key Words：ant colony algorithm； iterative local search； local convergence； path planning

0 引言

路径规划是指在有障碍物的环境中寻找一条从起点到终点无碰撞地绕过所有障碍物的运动路径。路径规划算法众多，基本可分为局部路径规划和全局路径规划两类。其中，局部路径规划算法主要有人工势场法；全局路径规划算法包括栅格划归法、顶点图像法、广义锥方法和位形空间法。考虑到路径规划往往是包含复杂约束的大规模优化问题，因此启发式智能优化算法目前已成为求解路径规划问题的主流方法，如蚁群算法、粒子群算法、模拟退火算法、遗传算法等。早在1998年，Patcher[1]就讨论了路径规划问题中的关键优化技术及其复杂性；Dong[2]、Zheng[3]和Nikolos等[4]系统研究了路径规划中进化算法的优化原理。

蚁群算法 （Ant Colony Optimization，ACO）是由意大利学者M Dorigo[5]于1992年首先提出的一种新型智能进化算法，其基本思想是通过模拟蚁群在搜索食物过程中的寻优能力解决优化问题。蚁群算法具有正反馈、自组织、分布式等突出优点，缺陷是收敛速度較慢，易陷于局部最优解。

迭代局部搜索（Iterated Local Search，ILS）最早由Lourenco等[6]于2002年提出，是一种简单而有效的元启发式算法，主要通过摄动的方法改善算法局部搜索能力。迭代局部搜索一经提出，立即被用于求解TSP问题[7]和调度问题[8]，并取得了良好的效果。目前，对迭代局部搜索的应用研究已取得了一系列成果。张志强[9]较早将迭代局部搜索策略应用于蚁群算法；王海斌[10]在粒子群优化算法中引入了迭代局部搜索；高超等[11-14]系统地研究了迭代局部搜索，并将其应用于车辆路径规划问题。

本文提出一种基于图论和迭代局部搜索的二维路径规划蚁群算法（ILS-ACO），并根据数值实验对该算法进行性能测试。

1 二维路径规划问题的空间模型与dijkstra算法

1.1 MAKLINK图

本文通过构建MAKLINK图的方法建立二维路径规划空间模型[15]。MAKLINK图是指两个障碍物之间不与障碍物相交顶点之间的连线，以及障碍物顶点与边界相交的连线，主要作用是生成二维路径规划的初始可行空间。图1即为本文实例中的MAKLINK图。

若MAKLINK图中连线的中点依次为v1，v2，…，vl，连接这些中点及起点S与终点T，则构成了二维路径规划的初始可行空间。

1.2 Dijkstra算法

由于二维路径规划初始可行空间中路径众多，为了提高路径搜索效率，采用Dijkstra算法规划一条从起点S到终点T的初始路径。Dijkstra算法是图论中典型的单源最短路径算法，用于计算某节点到其它所有节点的最短路径，其基本思路是将节点分成两组，第1组包括已确定最短路径的节点，第2组为未确定最短路径的节点。按递增次序将第2组中的节点逐个加入第1组，直到从源点出发可到达的所有节点都被包含在第1组中。

Dijkstra算法流程如下：

（1）初始化存储未确定最短路径的节点集合V与已确定最短路径的节点集合S，并利用邻接矩阵初始化最短路径长度D。

（2）在D中选择最小值D[i]，D[i]为源点到点i的最短路径长度，将点i从集合V中取出并放入集合S中。

（3）根据节点i修改更新D中源点到集合V中节点对应的路径长度值。

（4）重复步骤（2）和步骤（3），直到找出源点到所有节点的最短路径为止。

2 蚁群算法与迭代局部搜索

2.1 基本蚁群算法

蚂蚁之所以能找到从巢穴到食物的最短路径，并且能适应性地搜索新的路径，根本原因是蚂蚁能在其走过的路上释放信息素。路径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，后来的蚂蚁选择该路径的概率也越大，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最终可以发现最短路径。蚁群算法的核心步骤为信息素轨迹强度的更新和蚂蚁转移概率的确定。本文采用下列蚂蚁圈模型[5，16]：

2.2 迭代局部搜索

蚁群算法与其它智能优化方法一样，不可避免地存在一些缺陷，如初始信息素生成速度较慢及局部搜索能力较差、易早熟等。

为了提高启发式算法的局部搜索能力，Lourenco[6] 2002年提出了迭代局部搜索的策略，其基本思想是：从一个初始解s出发，应用局部搜索方法，一旦局部搜索陷入停滞状态，局部最优解s^产生摄动，移动到不同于局部搜索使用解的领域中。摄动产生的解s′是局部搜索的新起始解，它将产生新的局部最优s′^。最后，一个接受规则负责决定选择两个局部最优解中的哪一个进入下一阶段的摄动过程。

迭代局部搜索流程如下：

（1）输入参数，生成最初解s。

（2）应用局部搜索，生成局部最优解s^，它是当前最优解sbest。

（3）通过对当前解s^的摄动，生成一个中间解s*。

（4）对中间解s*进行局部搜索，再生成局部最优解s^*。

（5）判断新的局部最优解s^*是否比当前最优解sbest更符合接受规则。若否，输出最优解sbest，程序结束；若是，判断局部最优解s^和s^*中的哪一个进入下一阶段的摄动过程，转入流程（3）。

2.3 基于迭代局部搜索的蚁群算法

一系列研究表明[9，16-18]，将蚁群算法与其它优化策略相融合，可以取长补短，提高优化效果。本文将迭代局部搜索引入蚁群算法，提出了一种改进的路径规划蚁群算法，流程如下：

（1）给定蚁群算法参数。

（2）用dijkstra算法产生一个初始较优解。

（3）利用式（1）更新信息素，并转流程（5），否则转流程（4）。

（4）根据式（2）选择下一节点。

（5）根据梯度阈值原则[16]判定当前解是否陷入局部收敛，若是则转流程（6），否则转流程（7）。

（6）对蚁群算法搜索到的局部最优解进行迭代局部搜索，得到摄动后的最优解。

（7）若算法的整体迭代次数达到最大迭代次数，则输出最优解，算法结束，否则转流程（3）。

3 数值实验结果

3.1 问题描述

在200×200的二维空间区域内寻找一条从起点S到终点T的最优路径，该二维空间区域内有4个障碍物。障碍物1的4个顶点分别为（40，140； 60，160； 100，140； 60，120）；障碍物2的4个顶点分别为（50，30； 30，40； 80，80； 100，40）；障碍物3的4个顶点分别为（120，160； 140，100； 180，170； 165，180）；障碍物4的3个顶点分别为（120，40； 170，40； 140，80）。起点S的坐标为（20，180），终点T的坐标为（160，90）。二维规划空间如图2所示。

3.2 規划结果

在蚁群算法中，取定的初始参数如下：信息素计算参数为2，信息素选择阈值为0.7，信息素更新参数为0.1和0000 3；启发信息参数为0.5和1.1，种群数量为10，进化代数为200；判定是否陷入局部最优的阈值ε=0.01。图3给出了最终的最优规划路径，图4、图5分别给出了ACO和ILS-ACO的典型进化曲线。

对比ACO和ILS-ACO的典型进化曲线可直观地看出，ILS-ACO比ACO有更好的局部收敛性。

为了更进一步定量比较ACO和ILS-ACO的全局收敛性及局部收敛性，表1中给出了ACO和ILS-ACO两种算法的最优值、平均值、标准差、20次仿真中求得最优值（达到理论最优解的95%即视为最优值）的频率及平均最小进化代数。考虑到计算结果的随机性，表1中20次实验结果的平均值更有意义。本文研究的路径规划问题理论最优解为191.5。

从表1中可见，ILS-ACO在解的质量、稳定性和收敛速度方面均优于ACO。

综上，有理由相信，在二维路径规划中若采用ILS-ACO，将获得比基本ACO更优的路径规划。

4 结语

通过分析基本蚁群算法和迭代局部搜索算法，设计了一种用于二维路径规划的新的混合蚁群遗传算法。新算法实现了蚁群算法与迭代局部搜索的优势互补，改善了蚁群算法的局部收敛性。数值实验结果显示，该算法可在很大程度上克服基本蚁群算法的早熟现象，可较好地解决二维路径规划问题。

蚁群算法的收敛性较为复杂，尚未完全解决。目前可以证明的结论是：基于蚂蚁圈模型的蚁群算法与其它优化算法的混合算法是收敛的。因此，本文提出的算法在理论上是收敛的。最后需要指出，蚁群算法与粒子群算法、人工免疫系统、分布估计算法、协同进化算法等均为近年来出现的新型进化范例，理论体系尚不完善，收敛性等关键理论问题有待进一步研究。

参考文献：

[1] PATCHER M，CHANDLER P R.Challenges of autonomous control [J].IEEE Control Systems Magazine，1998，18（4）：93-97.

[2] DONG J，VAGNERS J.Parallel evolutionary algorithms for UAV path planning [C].Chicago：AIAA 1st Intelligent Systems Technical Conference，2004.

[3] ZHANG C，LI L，XU F.Evolutionary route planning for unmanned air vehicles [J].IEEE Transactions on Robotics，2005，21：609-620.

[4] NILOLOS I，VALAVANIS K.Evolutionary algorithm based offline/online path planning for UAV navigation.[J].IEEE Transaction on Systems，Man and Cybernetics-Part B，2003，33：898-912.

[5] DORIGO M，THOMAS S.Ant colony optimization[M].Massachusetts ：MIT Press，2006.

[6] LOURENCO H R， MARTIN O， STUTZLE T. Iterated local search [J].International Series in Operations Research and Management Science，2002，57：321-353.

[7] CONGRAM R K，POTTS C N.An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling program [J].INFORMS Journal on Computing，2002，14（1）：52-67.

[8] APPLEGATE D，COOK W，ROHE A.Chained Lin-Kernighan for large traveling salesman problems [J].INFORMS Journal on Computing，2003，15（1）：82-92.

[9] 張志强，张璟，张翔.基于蚁群优化的混合智能算法研究 [J].西安理工大学学报，2009，25（3）：314-317.

[10] 王海斌，刘维亭，徐卉.基于迭代局部搜索和自适应粒子群优化的SVM短期负荷预测 [J].船舶工程，2013，35（1）：57- 60.

[11] 高超.随机局部搜索算法及其应用研究 [D].合肥：中国科学技术大学，2015.

[12] 温真真.需求可拆分车辆路径问题的迭代局部搜索算法研究 [D].北京：北京交通大学，2015.

[13] 刘万峰.求解车辆路径问题的启发式算法及其在注塑排程问题中的应用 [D].深圳：深圳大学，2015.

[14] 赵轩.求解RCPSP问题的迭代局部搜索算法研究 [D].北京：北京交通大学，2016.

[15] 史峰，王辉.Matlab智能算法30个案例分析 [M].北京：北京航空航天大学出版社，2011.

[16] 刘雪东，许峰.基于目标函数变化率的混合蚁群遗传算法 [J].计算机工程与应用，2013，49（18）：41-44.

[17] 张潇，王江晴.混合蚁群算法在车辆路径问题中的应用[J].计算机工程，2011，37（24）：190-192.

[18] 彭碧涛，周永务.多时间窗车辆路径问题的混合蚁群算法[J].计算机工程与应用，2010，46（31）：28-31.

（责任编辑：何 丽）