基于改进蚁群算法的无人船路径规划研究

2021-11-13王成，任佳，张育

海南大学学报（自然科学版） 2021年3期

王成，任佳，张育

（海南大学信息与通信工程学院，海南海口 570228）

作为水面智能体的典型代表，无人船（Unmanned Surface Vehicles，USV）可自主完成水面和水下目标侦察、搜索、探测和监视等任务［1-2］，受到了广泛关注，路径规划［3］是无人船进行水域作业的前提和保障.

目前适用于无人船路径规划的算法主要有遗传算法［4］、粒子群算法［5］、蚁群算法［6-7］和人工势场法［8］等.相较于其他智能优化算法，蚁群算法应用于路径规划时具有并行搜索、鲁棒性强、简单易实现等特点，但存在着初期搜索效率低、收敛速度慢和易陷入局部最优等缺点，因此许多学者从信息素的更新、启发式信息值等方面对蚁群算法进行了改进，提出改进的蚁群算法［9］.曹新亮［10］等针对蚁群算法在路径规划过程中出现的收敛速度慢的缺陷，对各点初始信息素浓度进行差异化设置，避免寻优的盲目性，提高了算法的收敛速度，但该算法仅从一个方向对蚁群算法进行改进，并没有解决蚁群算法陷入死锁路径的问题.朱艳［11］等针对蚁群算法收敛速度慢，容易陷入局部最优的问题，自适应调整启发函数，引入方向信息，提高算法效率，动态调整权重系数改变目标点的方向信息在蚂蚁移动过程中的影响，该算法不仅可以提高收敛速度，而且在改善解的质量方面也取得了较好的效果，但仍然存在算法前期搜索效率低的问题.王晓燕［12］等结合人工势场法构造启发信息，提高了算法的收敛速度，根据起点和终点的编号对初始信息素浓度进行不均匀分配，避免了蚁群算法前期搜索的盲目性，自适应调整信息素挥发系数，提高了全局搜索能力，由于采用人工势场法构建起发信息，增加了算法的运行时间，对于蚁群算法陷入死锁路径的问题没有进行改进.屈鸿［13］等在蚂蚁陷入死锁时，对当前栅格的信息素浓度进行惩罚，再令蚂蚁退到上一个栅格，可以降低蚂蚁进入死锁的概率，但此改进会增加路径长度，无法得到最有解.白建龙［14］等针对易陷入局部最优问题，利用搜索的历史信息改善解的多样性，从而获得最优路径，但该算法未考虑算法前期收敛速度慢的问题.Luo Q［15］等构建分配不均匀的初始信息素，改进全局信息素更新的方法，引入动态惩罚方法解决死锁问题，但该算法降低了每次迭代过程中最优解的正反馈引导作用.

由于上述文献在利用蚁群算法实现全局路径规划时，仍在一些弊端，因此笔者针对蚁群算法存在的前期搜索效率低、收敛速度慢等问题进行了以下改进：对初始信息素进行不均匀分配，避免前期盲目搜素；在信息素浓度更新规则加入权重因子，增强了当前最优解对后代蚂蚁的指导作用，加快了算法的收敛；对死锁点的信息素浓度进行惩罚，减少后续死亡蚂蚁的数量.

1 路径规划模型

1.1 环境建模在进行无人船路径规划前，需要对任务环境进行建模，以便于把任务环境中安全区域及障碍物清晰地表示出来，笔者研究无人船全局路径规划.设定障碍物都是静止不动，因为栅格法表示简单，易于在编程中实现.为了简化无人船的任务环境，采用栅格法对任务环境进行建模，0表示安全区域，1表示障碍物，将任务环境表示为方形地图，栅格法由边长单位为1的小正方形组成，安全区域表示为白色，障碍物表示为黑色，图1为二维电子地图，图2为对应的二维栅格地图.

图1 二维电子地图

图2 二维环境栅格图

为了便于后期对环境信息的表征，对栅格进行编号，顺序从上往下，从左往右.由于蚂蚁所在栅格位置为栅格的序号，而在计算栅格间距离时，利用栅格点中心位置坐标，因此栅格号与坐标之间的关系

其中，a为小栅格的边长，n为小栅格的序号，M M为栅格的总行数，ceil为向上取余函数，mod为余函数，“/”为简单除法，保留小数.图3为图2对应的栅格序号图.

图3 栅格对应序号图

1.2 建立目标函数在保证无人船航行安全的前提下，进行航线的路径规划，需先建立目标函数

其中，L为无人船的航线距离，N为无人船航线所穿过的栅格数，d n（n=1，2，…，N）为所在栅格的中心点，l(d n，d n+1)为无人船从点d n到点d n+1的直线距离.

2 基于改进蚁群算法的路径规划算法

2.1 传统蚁群算法蚁群算法是根据蚂蚁觅食行为所研究出来的一种智能仿生算法.由初始起点，蚂蚁会在觅食经过的路径上留下信息素，当蚂蚁第一次走到一个分岔路口时，会随机选择路径并留下信息素，信息素浓度与路径长短成反比，路径越长信息素浓度越低，蚂蚁会优先选择信息素浓度较高的路径，形成一种正反馈现象，较长路径上的信息素浓度会越来越低，甚至消失，较短路径上的信息素浓度越来越高.最终会找到最优路径.

蚁群算法采用伪随机状态转移规则选择下一个节点的位置，如果蚂蚁k现位于i点，通过式（3）以q0的概率选择蚂蚁k的下一个节点j，否则利用式（4）计算转移到每个点的概率，最后利用轮盘赌去选择下一个节点j，

其中，式（3）中q为（0，1）内的随机数，q0为（0，1）之间的概率系数，在此需根据需求自行设置.C为蚂蚁可以选择的下一个节点j的集合；下一个节点j的选择范围为当前节点周围的8个节点中的可行性点，j为根据式（4）所计算出来的下一个点，τij为蚂蚁从i点移动到j点的信息素浓度；α为信息素激励因子；β为期望启发因子；ηij为蚂蚁从i点移动到j点的启发程度；arg max函数为[τij]α[ηij]β取到最大值的点的集合，d ij为蚂蚁所在的i点到下一点j点的直线距离，d jE为下一点j到终点E的距离.

蚂蚁在追寻信息素寻找路径的同时，会残留新的信息素，因此路径上的信息素会挥发残留叠加，在t+1时刻时，路径上信息素浓度进行更新

其中，ρ为信息素挥发系数，m为蚂蚁的总数量，为蚂蚁k新增的信息素浓度，可得到

其中，Q为信息素强度，L k为蚂蚁k走的路径总长度.

2.2 改进蚁群算法

2.2.1 改进初始信息素由于蚂蚁在进行觅食行为之前，没有经过所搜索的路径，传统蚁群算法的信息素浓度的初始值在每条路径上都为0，蚂蚁在前期进行路径搜素时，存在一定的盲目性，容易造成收敛速度慢，浪费搜索路径的时间，两点之间直线最短.因此起点到终点的最短路径为此两点的之间距离即d SE.在此根据起点S、所在点i、下一个目标点j及终点E之间的距离，由于路径的长度不同，代表着信息素浓度的初始值进行了不均匀的分配，使得对于较短路径上的信息素浓度偏高，避免了算法初期的盲目性，进一步提高了搜索速度，具体实现

其中，d SE为起点S到终点E之间的直线距离，d Si为起点S到所在点i之间的直线距离，d ij为所在点i到下一个节点j的直线距离，d jE为下一个节点j到终点E之间的直线距离，由式（1）可得.

2.2.2 改进信息素更新机制传统蚁群算法中路径上信息素浓度的更新主要是由随时间挥发后剩余的部分和蚂蚁经过后新增的信息素组成，存在搜索效率低的问题.为了提高搜索效率，采用“优胜劣汰”的思想引用权重因子h，当所有蚂蚁进行完一次迭代之后，会对所有路径上的信息素进行更新，此时的路径长短不一，把蚂蚁所走的路径中最优解L best与蚂蚁此次所走的路径长度L k之间的比值作为权重因子h，由式（9）可得，路径越短，权重因子h越大，信息素增加的越多.根据式（10）对所有路径上的信息素浓度进行更新，较短路径上信息素增加越多，会增强较优解对后续迭代的引导作用，较长路径上信息素增加越少，可以减少较差解对后续迭代的误导作用，因此可以加快算法收敛到全局最优的速度.

2.2.3 解决死锁问题死锁问题即在寻找路径的过程中，当前所在节点周围没有可选择的可行节点，且当前节点并非终点.传统蚁群算法在蚂蚁进入死锁之后，仅仅杀死陷入死锁点的蚂蚁，减少蚂蚁数量，并没有对死锁点的信息素进行任何惩罚，这样后续还是会有一定数量的蚂蚁进入此点，蚂蚁数量大量减少，使得解决问题的多样性降低，无法保障算法迭代寻优的后期解的多样性.因此为了避免蚂蚁陷入死锁点，引入惩戒因子μ，对死锁点的信息素浓度进行惩罚，计算死亡蚂蚁的数量mn，进入死锁点的蚂蚁数量越多，μ越大，对该死锁点的惩罚也就越大，后续进入此死锁点的蚂蚁数量就会大大减少，增加了解决问题的多样性，对死锁点信息素的惩罚

2.3 改进蚁群算法流程本文算法具体流程如下：

步骤1根据无人船任务环境的起始点和终点，确定无人船的工作区域；

步骤2初始化各个参数.起始点S的位置，终点E的位置，蚂蚁数量m，信息素激励因子α，期望启发因子β，信息素挥发系数ρ，最大迭代次数K，当前迭代次数k，迭代次数阈值k0，信息素强度Q，死锁时惩戒因子μ等相关参数；

步骤3根据栅格法对无人船的工作区域进行建模；

步骤4计算初始信息素，根据式（8）计算初始信息素τij(0)；

步骤5根据无人船工作区域的起始点，初始化m个蚂蚁的位置为无人船工作区域的起始点；

步骤6规划蚂蚁路径，根据伪随机状态转移规则式（3），结合式（4），确定蚂蚁下一点j的位置；

步骤7然后把节点j添加到禁忌表中，并判断路径点j是否是死锁点，若是则执行步骤8，否则返回步骤6，知道下一个路径点j为无人船执行任务的终点，则执行步骤9；

步骤8蚂蚁进入死锁状态，计算进入死锁状态的蚂蚁数量，根据式（11）对死锁路径的最后两步进行信息素惩罚；

步骤9当所有蚂蚁完成一个循环后，根据式（6）和（10）对搜索路径进行全局信息素更新；

步骤10搜索完成，判断是否达到最大迭代次数，若k≠K，使k=k+1，清空禁忌表，跳转到步骤3，继续循环执行；若k=K，则输出最优解，算法结束.

具体算法流程如图4所示.

图4 算法流程图

3 仿真与分析

3.1 实验环境与条件假设为验证该算法的可行性和有效性，进行了大量的仿真实验，并与传统蚁群算法和文献［15］提出了算法进行了对比，验证了该算法的优越性.仿真环境如下：Windows10 64位，处理器Intel（R）Core（TM）i7-8750U，主频2.2 GHz，内存16 GiB；仿真软件：MatlabR2019b.

无人船的工作环境采用文献［15］的工作环境，障碍物为工作环境中的静态船舶、暗礁以及狭窄水域等，工作环境大小为30×30，起始点坐标为（0.5，0.5），终点坐标为（29.5，29.5），工作环境的栅格图中小栅格的边长为1.

本文算法、传统蚁群算法和文献［15］中提出的算法在仿真时的蚂蚁数量都为50只，最大迭代次数都是100次；

本文算法和文献［15］提出的算法中的惩戒因子取值均为0.2.

3.2 仿真实验与结果分析蚁群算法参数选取合适与否直接关系到算法的效果，目前还没有一种最合适的方法去直接确定参数的最优组合.首先采用文献［15］中设定的参数在文献［15］的仿真环境下进行仿真实验与文献［15］以及传统蚁群算法做对比，图5～7为本次实验3种算法的结果对比，图8中红色虚线为传统蚁群算法的规划路径，蓝色实线为文献［15］的规划路径，黑点为本文算法的规划路径，为了避免偶然情况，重复100次实验，平均结果如表1所示.

图5 最优路径的变化曲线

图8 3种算法规划的最优全局路径

由表1可知，本文算法在采用文献［15］中设定的参数组合时，与文献［15］找到的最优路径都为44.526 9，优于传统蚁群算法找到的最优路径45.112 7.在收敛次数方面，本文算法经过43.8次迭代后才收敛，文献［15］经过30.6次迭代就收敛，文献［15］在损失蚂蚁数量方面也优于本文算法.因此，合适的参数组合对算法的性能有着关键作用.

表1 3种算法在路径规划中的结果比较

为了更加有效地找到合适的参数组合，通过对参数设置不同值进行仿真分析，选择最优的参数组合.

每个参数设置5个数值，同时保持其他参数不变，对每个参数的数值进行100次仿真，对算法结果求平均值进行对比，本文测试的参数为信息素激励因子α、期望启发因子β和信息素挥发系数ρ，进行仿真实验，α，β，ρ的默认值设置为α=1.5，β=8，ρ=0.5，其他参数设置为K=100，m=50，k0=5，Q=10，μ=0.2.经过多次仿真实验，由表2参数仿真结果对比可以看出本文参数最优组合为α=1.5，β=10，ρ=0.3.

表2 本文改进的蚁群算法测试参数仿真结果对比表

图6 最优路径的平均值变化曲线

图7 丢失蚂蚁数量的平均值变化曲线

在经过实验找到适合本文算法的参数组合后，再在文献［15］的仿真环境下进行仿真并于文献［15］及传统蚁群算法进行对比.图9～11为本次实验3种算法的结果对比，图12中红色虚线为传统蚁群算法的规划路径，蓝色实线为文献［15］的规划路径，黑点为本文算法的规划路径，为了避免偶然情况，重复100次实验，平均结果如表3所示.

图9 3种算法最优路径比较

图10 3种算法收敛比较

图11 3种算法丢失蚂蚁数量

图12 3种算法的规划路径

表3 工作环境中3种算法仿真结果对比

由表3可以看出，传统蚁群算法最优路径长度为45.112 7，在仿真100次的情况下，平均迭代51.9次后才能找到最优路径，且在平均迭代92.5次后能收敛，最终收敛路径长度却为46.458 3，极其不稳定且丢失蚂蚁数量多.文献［15］算法和本文算法找到的最优路径均为44.526 9.在仿真100次的情况下，文献［15］算法仅有3次最后收敛到最优路径，初期搜索效率的高低即为首次获得最优航行代价对应的迭代次数的大小，文献［15］算法在迭代16.5次后找到最优路径，本文算法仅迭代5.1次后便找到最优路径，寻优能力提高了近三倍，解决了初期搜索效率低的问题.收敛速度取决于全局收敛到最优解的平均迭代次数，文献［15］算法在迭代30.6次后收敛于45.468 3，本文算法在14.4次迭代后便可收敛，且收敛路径为44.975 4，优于文献［15］算法，提高了算法的收敛速度.文献［15］算法丢失蚂蚁数量为336.2，本文算法丢失蚂蚁数量为122.2，丢失蚂蚁数量仅占文献［15］算法的三分之一，增加了方案的多样性.在运行时间方面，比传统蚁群算法短了1.8 s，比文献［15］算法节省约4 s.

综上所述，本文算法与文献［15］算法和传统蚁群算法在2种环境进行对比.在改变初始信息素浓度之后，加快蚂蚁的寻优速度；对于信息素浓度更新，加入权重因子可以加快蚂蚁的收敛速度.文献［15］算法对于信息素浓度的更新，是对最优解增加信息素浓度、最坏解减少信息素浓度，其他路径上信息素浓度不变，容易导致陷入局部最优，找不到最优解.对于死锁问题，文献［15］算法对锁死路径最后两步的信息素浓度进行惩罚，减少了蚂蚁经过此路径的概率.本文算法将锁死路径最后一步信息素浓度置0，在减少丢失蚂蚁数量方面比文献［15］算法有显著效果，增加解的多样性.因此，本文算法与其他算法相比，具有较大优越性和实用性.