基于改进麻雀搜索算法的无人机航路规划研究

王玲玲，孙 磊，丁光平，王加刚，段 誉

(1 盐城工学院机械工程学院，江苏 盐城 224001；2 重庆望江工业有限公司，重庆 400020；3 清华大学精密仪器系，北京 100084)

0 引言

随着航天技术和军事需求的不断增长，航路规划在无人机作战任务过程中发挥着越来越重要的作用。无人机作战时需要根据多个特定的约束条件，搜索出一条从起点到指定终点最安全有效的轨迹[1-3]。

算法设计是解决无人机复杂航路规划的核心环节。近年来，仿生群体智能优化算法层出不穷，研究人员对其开展了深入研究。文献[4]结合了三次样条插值函数和改进的蚁群算法，对无人机飞行路径进行优化，得出了最优的航路。文献[5]以传统粒子群优化算法为基础，引入细菌觅食算法及遗传算法思想，提高算法计算速度与能力。文献[6]提出了一种基于改进的哈里斯鹰群优化的无人机航迹规划算法，引入柯西变异策略和自适应权重以提高其性能。文献[7]提出了一种利用局部信息和相对距离的三维路径规划深度强化学习方法，无人机可在实际场景中获取附近有效的环境信息。但是上述算法仍不能达到理想的效果且存在易陷入局部极值的情况。

为此，文中选用麻雀搜索算法进行无人机的航路规划设计。麻雀搜索(sparrow search algorithm, SSA)算法[8]是由Xue等2020年提出的一种新智能优化方法，是根据麻雀觅食和隐蔽天敌的行为来创建优化模型，该算法具有较好的鲁棒性，可快速有效地规划出无人机航行路径。但该算法和其他群智能算法一样，存在初始化种群的随机性分布不能达到绝对均匀，局部搜索的性能较差，容易忽略最优解的问题。为了改善在三维航路规划中的安全与效率等问题，文中提出了一种基于改进麻雀搜索算法(circle chaos and firefly strategy based sparrow search algorithm, CFSSA)的三维航路规划方法。该方法通过采用 Circle混沌映射对原始麻雀种群进行初始化操作，在初始化的过程中利用萤火虫扰动策略不断对麻雀位置进行迭代优化，从而减少陷入局部最优值的概率，提高全局搜索的能力。实验证明，较其他算法，基于 CFSSA的三维航路规划方法效果更好，能够取得寻优结果。

1 麻雀搜索算法

SSA受到自然界中麻雀觅食和躲避天敌现象的启发，麻雀有很好的飞行能力和很强的警觉性。SSA可以被理解为一个发现者-追随者模型，其中还增加了预警机制。发现者负责发现食物，并把食物位置信息传递给整个群体，而追随者通过发现者的信息获取食物。此外，还有一些个体担任预警者的角色负责在觅食过程中躲避捕食者，并警示种群中的其他麻雀，这时所有麻雀需要向附近麻雀靠近并飞向其他安全区域，以减少被捕食的几率。

麻雀种群中的发现者的位置更新公式为：

(1)

麻雀种群中跟随者的位置更新迭代公式为：

(2)

麻雀种群中预警者的位置迭代更新公式为：

(3)

2 改进的麻雀搜索算法

2.1 Circle混沌映射优化初始种群

在初始化阶段，由于麻雀个体分布不均匀，导致麻雀初始位置过于集中，不利于搜索出全局最优位置。而Circle混沌映射[9]有着随机性、均匀性和有序性等特点，并且不会重复所有的状态，可以用来初始化种群，克服种群初始化时的盲目性，使得个体在搜索空间的初始位置分布更加均匀，提高麻雀种群的多样性，为后期麻雀搜索算法寻优打下基础。Circle映射可表示为[10]：

xk+1=mod(xk+b-(a/2π)sin(2πxk),1)

(4)

式中：mod为取余函数；a，b为系数，分别取值0.5和0.2。

从图1可见，利用Circle映射进行初始化种群，相比于随机初始点，Circle混沌映射值分布更加均匀，麻雀种群在空间中的搜索范围更广，有效改善了原来算法极易陷入局部最优的问题。

图1 Circle混沌映射分布图

2.2 萤火虫扰动策略

萤火虫算法是一种仿生群智能优化算法，仿生群智能优化算法的主要思想是通过研究自然界中模仿生物群体生活的社会行为而构建的一种随机搜索方法[11]。萤火虫算法的优化原理为：将空间中的每一个点看作是萤火虫﹐萤火虫的种群是随机分散的，利用发光度大的萤火虫吸引发光度小的萤火虫的特点，在发光度弱的萤火虫向发光度强的萤火虫移动的过程中，完成位置的更新迭代，从而找到最优位置，该过程也是完成寻找最优解的过程。

群体中每一个萤火虫都对应问题的一个可能解。假设Xk=(xk1,xk2,…,xkd)是一只萤火虫，其中：k表示萤火虫的数量编号;d表示变量的维度。

萤火虫的相对荧光亮度I可表示为：

(5)

式中：I0是每个个体萤火虫的目标函数值，即最大荧光亮度，当I0值越大时萤火虫适应度值越优；γ为光强吸收系数，该系数随着距离的增加、传播媒介的吸收而逐渐变小；rmn=|Xm-Xn|为第m只和第n只各萤火虫间的距离。

萤火虫的吸引度β可表示为：

(6)

式中：β0表示个体光源处的吸引度，一般为常数。

萤火虫扰动位置更新公式为：

xi=xi+β·(xj-xi)+α·(rand(n)-1/2)

(7)

式中：xi和xj为麻雀i和j的空间位置；α为步长因子；rand(n)∈[0,1]为随机因子，可以增加搜索范围，避免在早期阶段进入局部最优。

2.3 改进的麻雀搜索算法流程

综合考虑，改进的麻雀搜索算法流程为：

1)系数初始化。设置种群数量、最大迭代次数、发现者和预警者比例、预警值等。

2)初始化麻雀种群的位置。利用Circle混沌映射进行初始化，使其在解空间中随机分布。

3)计算适应度值函数，比较后得到最优和最差的适应度值的麻雀信息。

4)按比例从群体中选择适应度值高(即路径长度最短)的麻雀作为发现者，并通过式(1)更新发现者的位置。

5)根据式(2)，更新跟随者的位置。

6)根据式(3)，更新预警者的位置。

7)引入萤火虫扰动策略，此时麻雀种群位置等同于萤火虫位置。根据式(5)、式(6)计算出萤火虫群体的相对亮度I0和吸引度β，确定萤火虫的移动方向。

8)并根据式(7)更新萤火虫的位置，并对处于最优位置的萤火虫进行随机扰动，当达到迭代次数或收敛后，移动结束，输出全局的最佳个体位置。

3 无人机三维航路规划建模

3.1 任务环境建模

无人机在执行任务的时候，往往需要考虑复杂多变的三维地形环境，主要受到地形威胁和障碍威胁等因素的影响[12]。具体的三维空间模型为：

(8)

式中：x，y，z2分别为地图模型中点的横纵坐标和高度；a，b，c，d，e，f，g这7个常数用于改变地貌特征粗糙表面的参数。

(9)

式中：n表示地图中山峰的个数；(x,y)表示山峰在平面投影所对应的位置坐标；(x0(u),y0(u))为第u座山的峰顶坐标；h(u)为山峰的高度；ax(u),by(u)表示第u座山峰沿x轴和y轴方向的坡度。

采用式(8)建立基准地形模型来建立粗糙的地面，采用式(9)来模拟基准地形上的山体障碍物。

3.2 约束条件设置

基于无人机的机动性，主要考虑到5个约束条件：

1)最大航程约束。假设路径中有n段，且第q个航路段长度为lq，最大航程为Lmax，约束需满足：

(10)

2)最小航迹段约束。受无人机姿态调整的延迟等限制，最小航迹段距离为Lmin，则航迹中任意一段航迹的距离满足：

lq≥Lmin(q=1,2,…,n)

(11)

3)最大转弯角。无人机的自身性能也受转弯角代价的限制，转弯角度只能在预设的最大拐角范围内完成无人机的姿态调整[13]。转弯代价函数为：

(12)

其中：α表示最大转弯角；aq表示其水平方向的投影。

4)最大爬升/俯冲角。与转弯角相同，无人机爬升和俯冲也存在着最大角度的限制，通常被称为最大爬升/俯冲角即θ[14]，应满足：

(13)

5)飞行高度限制。无人机飞行高度需高于最低高度，防止触地坠落。设最低离地高度为H，则飞行过程中需满足：

H≥Hmin

(14)

3.3 航迹代价指标

航迹代价函数用来计算航路的代价值以便分析航路性能的好坏[15]。综合权衡了燃料消耗代价、高度变化代价和威胁指数3个因素，所采用的航路规划评价函数为：

Jmin=k1L1+k2L2+k3L3

(15)

式中：Jmin表示最小代价航迹；L1，L2和L3分别表示燃料消耗代价、高度变化代价和威胁指数；k1，k2和k3为常数且分别代表各自的权重系数，且满足k1+k2+k3=1。

4 仿真实验与分析

4.1 实验环境与参数设置

为了验证文中CFSSA改进算法的有效性，将其与SSA算法、PSO算法对比。所有算法的种群数量为50，迭代次数为100，空间维度为30。

4.2 测试与分析

4.2.1 算法性能测试

为了测试改进算法的有效性，选取 6个标准测试函数来验证改进算法与SSA算法、粒子群优化(particle swarm optimization,PSO)算法，前4个为单峰函数，后 2个为多峰函数。标准测试函数信息如表1所示。算法优化对比实验结果见表2。

表1 标准函数测试表

从表2可以看出，针对6种测试函数，CFSSA在各函数测试中都能得到不错的收敛精度且更快地趋向于0，整体要优于SSA和PSO，特别是针对前4个单峰函数。由此看出，改进策略的引入是有效的，不仅CFSSA的求解效果和鲁棒性比其他算法好，而且更加稳定，具有较强的寻优能力。

表2 各算法优化对比计算结果

4.2.2 仿真结果及分析

在规格为100 m×100 m×450 m的栅格地图中进行航迹规划仿真实验，设置任务的起点为(15 m,52 m,160 m)，终点为(76 m,89 m,250 m)。

根据给定参数，对CFSSA，SSA和PSO算法分别进行航迹规划测试，独立仿真100次，统计3种算法各自的航迹长度、航迹代价、航迹节点个数和搜索时间如表3所示。各算法的适应度值曲线见图2，各算法的航迹规划图见图3。

图3 各算法最短路径规划对比仿真图

表3 各算法路线统计表

图2 平均适应度值曲线

从表3中可以看出，CFSSA得到的航迹长度最短且搜索时间最快，付出的航迹代价也最小，能够快速稳定地进行航路规划，符合设定的约束并且效果最好。从图2中可看出，SSA算法找到的路线较为复杂且代价最大，PSO算法虽然前期的收敛速度最快，但后期CFSSA 收敛速度最快，也具有较好的收敛精度，在50次迭代之前就已经找到了一条代价最小且时间最短的路径，对比这3种算法CFSSA的寻优值最小且效果最好。

由图3可以看出，CFSSA 与其他群智能算法相比，无人机的航路最为平滑且清晰，且所规划的航迹长度最短。综合来看，CFSSA多种策略的引入使得算法的搜索效果更好、耗时短且稳定，由此证明了算法的合理性。

5 结语

针对麻雀搜索算法在寻优过程中存在陷入局部最优且初始化种群分布不均匀等缺陷，引入了Circle混沌映射来扩大种群初始化，再采用萤火虫扰动策略对麻雀种群的最优位置进行强化更新。为了验证该算法的有效性，利用无人机航路规划进行了仿真。结果表明，提出的算法明显增强了收敛性，能够获得更高质量的导航轨迹和收敛精度，从而更好地避开威胁路径。