基于优化麻雀搜索算法的水下机器人路径规划研究*

周凯莉 刘从军，2

（1.江苏科技大学计算机学院 镇江 212003）

（2.江苏科大汇峰科技有限公司 镇江 212003）

1 引言

水下机器人（ROV/AUV）是海洋工程、科学调查的载体，工作水深可达4000m，是水下作业的必要工具。考虑使用路径规划［1］为无人船进行深海作业规划最优化的路径，提供便捷服务。

智能算法在求解路径规划问题时对全局探索和局部开发这两个基本流程可以起到很好的平衡作用，因此，无数研究者采用多种不同的智能仿生算法，不断创新改进，推动现实生产运用。王成等［2］优化传统的蚁群算法进行无人船路径规划，针对传统的蚁群算法（ACO）的固有局限性，即前期搜索效率低、早熟性收敛。通过更新信息素浓度时加入权重因子，解决了过快收敛；对算法死锁出现，采取减少死亡的蚂蚁数量对死锁点信息素进行惩罚。但该算法后期未解决种群多样性与收敛速度的矛盾，全局寻优能力仍可提高。刘洋等［3］改进的遗传算法，以较高的成功率规划出可行路径，且产生路径较短。但并未改进遗传算法容易出现过早收敛的问题。虞馥泽等［4］将遗传算法与蚁群算法融合，用遗传算法获得较优路径，并将其用作蚁群算法的初始信息素设置，以引导蚁群算法进行更进一步的优化搜索。其收敛性是要好于传统的单一算法，寻优效果与收敛性仍有提升的空间。

麻雀搜索算法（Sparrow Search Algorithm，SSA）是基于麻雀寻找食物行为的启发式算法，应用于路径规划时具有适用性强、参数少、全局搜索能力强、问题求解的快速性、全局优化特征、早熟性收敛等优点。薛建凯等［5］首次探讨相应规则并构建数学模型，概括算法实施过程。该文实验结论表明麻雀搜索算法具备自适应性、高效性、鲁棒性，对大规模路径规划问题和实时路径规划问题非常可行。汤安迪等［6］在薛建凯［5］的基础上表示算法在迭代后期，由于种群多样性降低，可能导致收敛速度和精度下降，进而陷入局部最优解。采用立方映射混沌算子创建初始种群，为缩小搜索空间，加快收敛。利用反向选择策略生成初始反向解，将其加入初始种群。此外，为减少算法陷入停滞的概率，使用高斯随机游走策略生成新个体有助于避免出局部最优解。

由于上述文献中的群智能仿生算法实现路径规划都存在一些弊端，结合文献［5］和文献［6］，将麻雀算法适当优化：如选择Tent映射初始化麻雀种群，采用自适应调整惯性权重策略［7］，通过增大或减小惯性权重值，最终提高全局搜索能力和收敛速度，提高求解的精度。同时考虑到算法后期的停滞问题，添加柯西变异来增加种群的多样性。

2 路径规划模型

2.1 环境建模

下水机器人在进行水下作业需要实时的进行路径规划，首先需对工作区的环境进行建模［8］。选择栅格法进行环境模拟，建立栅格地图，假设当环境中的元素属于自由区的面积大于障碍区域，则该象元取值为0，否则为1。其中自由栅格为白色，障碍栅格表示为黑色。将黑色象元用数字1 表示，白色象元用0 表示。最后采用序号法对每个栅格进行编号，顺序从前往后，从上到下。图1 为二维电子地图，图2 为二维栅格地图，用栅格法表示的整个环境编号图如图3。

图1 二维电子地图

图2 二维栅格地图

图3 二维栅格地图

图4 ISSA流程图

定义初始栅格坐标为（1，1），g为任意栅格，f为所有栅格集合，记作f=｛g（1，1），g（1，2）…g（x，y）｝。

其中，a为栅格步长，在x，y方向上最大值分别为xmax，ymax，则每行栅格个数Nx与每列栅格数Ny如式（1）所示。

n为栅格的序号，栅格号与序号的关系如式（2）所示。

2.2 建立目标函数

模拟栅格地图，最终目的是使水下机器人在安全的情况下找到最短的线路达到终点，问题转化为求以下函数（3）的最小值。

3 基于优化麻雀搜索算法的路径规划算法

3.1 麻雀搜索算法

麻雀搜索算法（Sparrow-Search-Algorithm，SSA）属于智能仿生算法分支下的粒子群优化算法（Particle Swarm Optimization，PSO）［9～10］，但是能克服PSO 算法中一些局限性，如PSO 算法参数设定通常由实验方法确定，导致方法的优化性能与人的经验关系密切。麻雀搜索算法可以说是一种粒子群算法的改进，为算法性能最优化提供了可能。

麻雀是雀科，一种小型鸟类的统称。属于一种群居杂食性鸟类，每次聚集十几只或几十只。规定由N只麻雀组成的种群，表示形式如式（4），该麻雀种群中的行为可以分为三类：搜索食物的发现者、跟随者和警戒侦查者。发现者负责寻找食物，跟随者会加入发现者的行列并向其移动以觅食，警戒侦查者负责发出危险警报。麻雀的总体比例不变，行为身份根据情况转换。一旦侦查者警报，跟随者会迅速散开到安全区域，而发现者会在群体中间随机移动，靠近安全区域的跟随者。

3.1.1 更新发现者位置

更新发现者位置是指根据当前搜索状态，每个发现者的适应度值的变化更新发现者的位置，更好地搜索目标，说明见式（5）。

上述公式［11］的描述中：当前迭代次数t，最大迭代次数itermax，第t次迭代时的第i个麻雀个体在第j维中的位置信息Xij；随机数α∈（0，1）；每个因子均为1 的l×d矩阵L；方差为1 的正态分布的随机数Q。

预警值R2∈（0，1）；预警安全值ST∈（0.5，1）。若R2＜ST，未发现捕食者，种群状态安全，发现者将按正态分布随机移动到当前位置附近。若R2≥ST，表示部分个体发现或遭遇捕食者。迭代过程中的发现者围绕当前位置移动，移动范围表示如式（6），其中，Y为移动位置值的变化范围。

3.1.2 更新跟随者位置

在SSA 中，跟随者的位置可以根据发现者的位置和行为进行更新。跟随者根据距离和方向来决定跟随者的移动方式，发现者位置在迭代过程中更新如式（7）。

其中，Xbest为发现者所在位置，即当前最佳觅食地区；Xworst为当前糟糕位置。A为一个d×d矩阵，其中每个元素随机分配1或者-1。若i≤n/2时，表示第i个跟随者在附近觅食最佳区域，如果i＞n/2，表示适应度低于第i个跟随者没有找的食物，需要飞到其它地方，提高适应度值。

3.1.3 预警行为

在麻雀群体中，存在一个预警机制。大约有10%～30%的麻雀判断是否需要发出预警信号，以采取某种行动以改变搜索策略。根据式（8）中的位置更新，警戒者的位置会进行相应的调整。

其中，β为随机步长控制系数，服从方差为1，均值为0 的正态分布［12］；K为随机数，且K∈［-1，1］；第i个麻雀个体的适应度值fi；当前最佳适应度值fg；当前最糟糕的适应度值fw；ε表示最小的参数，以避免分母为零。

3.2 优化麻雀搜索算法

麻雀算法SSA 属于启发式算法之一，与人工蚁群算法结构相似，具有良好的鲁棒性和快速收敛性，综合性能较好。它需要解决的问题与人工蚁群算法类似，例如平衡局部搜索和全局搜索，以尽量有效地避免陷入局部最优解。为了进一步提高麻雀搜索算法的能力，采取一些优化策略。

3.2.1 Tent混沌映射

混沌运动的特点可以用来提高算法的寻优效率，在启发式算法中得到广泛应用。优化变量通过混沌映射线性地映射到混沌变量中［13］，然后根据混沌的遍历性和随机性进行优化搜索。最后，将得到的解线性地转化回优化变量空间［14］。

伯努利变换基于伯努利分布进行二值转换，根据某个概率阈值决定转换的结果。将Tent 映射混沌和伯努利变换结合，可以产生一种混沌序列，在一定程度上增加随机性。Tent 混沌映射的式（9），结合伯努利变换产生式（10）。

3.2.2 自适应调整惯性权重策略

定义第i个麻雀在第j维上个体的搜索能力如式（11）所示。

从式（11）可以看出，如果Xij距x*较远，且x*距Xbest较近，则ISA 的值较大。表明此时全局搜索能力较强，应该适当减小惯性权重，增强局部搜索能力。如果Xij距x*较近，x*距Xbest较远，则ISA的值较小，说明局部搜索能力较强，应该增大惯性权重以提高全局搜索能力。

通过自适应地调整惯性权重，算法可以在搜索的不同阶段灵活地调整搜索行为，公式如式（12）所示。参数α∈（0，1］，本文将α设为常量0.3。在式（3）中引入自适应惯量，重新更新发现者的位置，得到式（13）。

3.2.3 解决算法停滞问题

采用柯西变异［15］来增加种群的多样性和搜索空间。选择当前适应度最佳的个体进行突变，并比较突变前后的位置，选择较好的位置进行下一次迭代，表达式如式（14）。

3.3 优化麻雀搜索算法流程

步骤1 根据工作环境的起始点与终点，确定水下机器人的工作区域；

步骤2 根据栅格法对水下机器人工作区域进行环境建模；

步骤3 随机初始化麻雀种群，同时定义最大迭代次数，设置安全阈值；

步骤4 根据机器人工作的起始点，初始化种群，包括设定麻雀发现者和跟随者的数量，以及预警侦查麻雀的占比。然后计算初始种群的适应度，并对其进行排序，以选择当前的最优值与最差值；

步骤5 规划麻雀搜索的路径，根据式（11），更新发现者的位置；根据式（7），更新跟随者的位置；根据式（8），更新警戒者的位置；

步骤6 更新路径，如果本次结果优于之前，则重新构建新的路径得到最佳情况；

步骤7 判断算法是否进入停滞，重新将最优个体进行柯西变异，重新初始化，循环；

步骤8 判断是否达到最大迭代次数，若没有，跳转到步骤5；否则继续下一步；

步骤9 搜索完成，输出最优结果，算法结束。

4 仿真与实验

4.1 实验环境与条件假设

为验证该算法的具有实践的可行性，选择传统的麻雀搜索SSA 文献［5］进行对比仿真实验，实验结果验证了优化的麻雀算法ISSA的优越性。

工作环境描述如下：障碍物为海面上的静态其他船舶、深海暗礁、沉积物以及浅滩等。作业环境一：大小为20*20，起始点坐标为（0.5，0.5），终点坐标为（19.5，19.5），作业环境的栅格图中栅格边长为1。作业环境二：大小为30*30，起始点坐标为（0.5，0.5），终点坐标为（29.5，29.5），作业环境的栅格图中栅格边长为1。

设置本文算法与文献［5］提出的算法，种群数量为50，安全值为0.8，发现者与跟随者的比例分别的0.3，0.2。遵循公平性原则，最大迭代次数都是100次，如表1所示。

表1 麻雀搜索算法参数设置

4.2 实验过程

4.2.1 作业环境一下的规划对比

采用大小为20*20，起始点坐标为（0.5，0.5），终点坐标为（19.5，19.5），栅格图中栅格边长为1，深色的方格代表障碍区域，白色的方格代表自有可行区域。保持两种算法的参数不变，进行100 次实验，与文献［5］SSA进行对比。图5为SSA的路径最佳规划方案，图6 为ISSA 的路径最佳规划方案，具体数据如表2所示。

表2 两种算法在环境一中路径规划的结果比较

图5 环境一SSA规划方案

图6 环境一ISSA规划方案

由表2得出，本文优化的ISSA的平均最短路径为29.4587，优于传统SSA 平均最短路径29.7915，降低了1.11%。在收敛次数方面，本文算法经过15.367次迭代后就趋于收敛，且收敛路径平均值为29.636；而文献［5］经过22.965 次才开始收敛，收敛路径平均值为29.965，收敛路径平均值降低了1.09 %，收敛迭代次数下降了33.1%。

4.2.2 作业环境二下的规划对比

采用大小为30*30，起始点坐标为（0.5，0.5），终点坐标为（29.5，29.5），栅格图中栅格边长依然为1，深色的方格代表障碍区域，白色的方格代表自有可行区域。保持两种算法的参数不变，进行100 次实验，与文献［5］SSA进行对比。图7为SSA的路径最佳规划方案，图8 为ISSA 的路径最佳规划方案，具体数据如表3所示。

表3 两种算法在环境二中路径规划的结果比较

图7 环境二SSA规划方案

图8 环境二SSA规划方案

由表3得出，本文优化的ISSA的平均最短路径为45.7705，优于传统的SSA 平均最短路径47.0178降低了2.65%。在平均收敛迭代次数方面，本文算法经18.3741 次迭代后就趋于收敛，收敛路径平均值47.0631；文献［5］经过26.2365 次才开始收敛，收敛路径平均值48.5698。收敛路径平均值降低了3.10%，平均收敛迭代次数下降了36.07%。

4.3 结果分析

综上所述，本文优化的麻雀搜索算法ISSA 与文献［5］SSA 算法在两种环境下进行100 次实验比对，结果显示ISSA 算法在在程序运行耗时，最短路径、平均最短路径、收敛路径平均迭代次数、收敛路径平均值等方面相较于SSA 算法优势明显。并随着环境的复杂程度增加，本文算法在上述方面的优势相对文献［5］的SSA算法优势更加明显。

5 结语

规划出一条从初始点到终点的最优路径是解决水下机器人工作的先行问题，路径的选择，确保作业的效率。在分析群智能仿生算法的基础上，针对群智能仿生算法搜索效率低、收敛速度慢等问题，本文提出了一种优化的麻雀算法，该算法具有以下优点：

1）新颖简单，麻雀算法通过麻雀搜索食物与反捕食的过程，进行各类种群的更新。

2）引入Tent映射初始化麻雀种群，以此保证初始种群个体自随机性，增加多样性，提高ISSA 算法的收敛速度。

3）通过自适应调整惯性权重策略平衡麻雀个体的局部搜索能力和全局搜索能力。同时增大或减小惯性权重值调整收敛速度，改善算法的精度。

4）添加柯西变异来增加种群的多样性，提高算法的稳定性。

通过实验，将文本算法ISSA 与传统SSA 进行了比较，实验结果验证了ISSA 在寻优过程中拥有一定的优越性，表明具有实际应用的可行性。下一步的工作重点为研究麻雀算法运用在三维路径规划方面，并考虑对动态避障的可操作性。