基于折射麻雀搜索算法的无人机路径规划

欧阳城添， 朱东林， 王丰奇， 邱亚娴

(江西理工大学信息工程学院，江西 赣州 341000)

0 引言

无人机技术的飞速发展，使其在多个领域具有重要作用。无人机的路径规划是一个典型的复杂多目标优化问题，在综合考虑各种环境条件下，找到一条从起始点到目标点的可行或最优的飞行轨迹。进化算法因较好的鲁棒性被广泛用于解决路径规划这类问题。

为了更好地实现进化算法对无人机的路径规划，学者们提出了各种应对方案。文献[1]在灰狼优化算法中引入了遗传算法的交叉和变异算子，使无人机在复杂环境中的路径选择具有较好的判断能力；文献[2]提出了基于相位角编码和突变自适应机制的果蝇优化算法，在不同的测试环境下，证明了改进算法的有效性；文献[3]在麻雀搜索算法(SSA)中引入了混沌策略增强种群的多样性，并使用自适应惯性权重及柯西-高斯突变策略来增强算法的寻优能力，使得改进的麻雀搜索算法具有较强的搜索能力，规划的路线较为安全；文献[4]将天牛须算法融合粒子群算法，使得改进的粒子群算法在路径规划中的代价更小；文献[5]提出一种混沌麻雀搜索算法，采用立方映射初始化种群，并引入精英反向学习及正余弦算法，增强局部与全局能力,最后采用非线性递减及高斯游走策略防止算法出现早熟,在无人机路径规划中取得较好的效果。以上文献虽取得不错的成效，但在寻优过程中缺乏判断能力且没有从根本上改善原算法的寻优机制，例如：变异策略在实际环境中仅对原位置做出局部变化，没有从根本上平衡算法的全局与局部能力；混沌理论本身具有不确定性，因此在高维复杂环境中仍然存在陷入局部最优的概率，导致稳定性不足。

针对以上问题，本文提出一种折射麻雀搜索算法(Refracted Sparrow Search Algorithm,RSSA)来改善路径规划中的安全与稳定等问题，麻雀搜索算法(SSA)是2020年提出的新型进化算法[6]，在函数优化上具有较强的寻优能力，但局部搜索能力不足，因此，本文采用折射反向学习(ROBL)增大算法的搜索范围，开拓未知区域的搜索，再引入疯狂算子提高算法的局部开发能力，最后利用模拟退火(SA)算法提升算法跳出局部最优的能力,来综合提升麻雀搜索算法的寻优能力，使其在路径规划中具有较好的寻优手段。

1 麻雀搜索算法

麻雀搜索算法在寻优过程中分为发现者、追随者和侦察者3个行为阶段。发现者为种群内的其他个体提供觅食的方向，具有较好的全局搜索能力。发现者的位置更新算式为

(1)

式中：i为当前迭代次数；M为最大迭代次数；Xi,j为第i只麻雀在第j维中的位置信息；α′为随机数，α′∈(0,1]；R2和ST分别表示预警值和安全值，R2∈[0,1]，ST∈[0.5,1]；Q为随机数且服从正态分布；L′表示元素为1的1×d矩阵。当R2

追随者在发现者的带领下进行局部搜索，适应度较好的个体会优先获得食物。追随者的位置更新算式为

(2)

式中：XP为当前的发现者所占据的最优位置；Xworst为当前全局最差的位置；A是1×d矩阵且随机赋值为1或-1，A+=AT(AAT)-1。i>n/2，表示没有获取食物或没有足够食物，需要飞往他处进行觅食。

现实中麻雀也存在被天敌捕捉的危险，因此麻雀种群中存在侦察的个体，发现危险时会发出信号，使得发现者带领其他个体飞向安全的地方。其具体行为算式为

(3)

式中：Xbest表示目前全局最佳的位置；β′为步长控制参数，是服从均值为0且方差为1的正态分布的随机数；K∈[-1,1]，是一个随机数，表示麻雀移动的方向同时也是步长控制参数；fi为当前麻雀个体的适应度值；fg和fw分别为当前全局最优和最差的适应度值；ε为最小的常数，以避免分母出现零；fi>fg，表示极其容易受到捕食者的攻击，fi≤fg，表示部分麻雀意识到了危险，需要通过离开当前位置尽量减少它们被捕食的风险。

2 折射麻雀搜索算法

2.1 折射反向学习

反向学习(OBL)[7]是改善智能优化算法的常用手段，通过计算当前位置的反向解来提升算法的搜索范围，这种方式在前期能够使得算法的寻优性能得到提高，但手段单一且缺乏灵活性，在后期寻优中同样存在陷入局部最优的概率。为进一步改善这种缺陷，本文采用折射反向学习(Refracted Oppposite-Based Learning,ROBL)[8-9]更新发现者位置，其原理是在反向学习的基础之上引入光的折射定律，利用折射定律来开发更深度的解。具体原理如图1所示。

图1 折射反向学习原理图

图1中，X轴上解的搜索区间为[lb,ub],Y轴表示法线，l与l′分别为入射光线与折射光线的长度，α和β分别为入射角和折射角,O为[lb,ub]的中点，由图中的几何关系及折射率的定义可知

(4)

令h=l/l′,代入式(4)可得

(5)

将算式变形，得到折射反向解为

(6)

显然，h=n=1时，ROBL可转换为一般的OBL，由此可看出，一般的OBL得到的解较固定，手段单一，而ROBL则可以通过调整参数动态获取新解，降低算法陷入局部最优的概率。当优化的问题维度上升，ROBL算式为

(7)

式中：x′i,j为折射反向解；lbj与ubj分别为第j维空间的最小值和最大值。

2.2 疯狂算子

在麻雀搜索算法中，追随者的位置受发现者的牵制，仅在其附近进行随机搜索，若遇到局部极值点，追随者无力跳出局部状态，因此采用“疯狂”的思想来降低个体出现早熟的现象。本文在追随者位置更新算式中引入疯狂算子[10-11]，使得追随者的寻优手段较为丰富，维持个体的多样性。新的追随者的更新算式为

(8)

式中：xcraziness通常取较小的常数，一般为0.000 1；P′与Q′分别定义为

(9)

(10)

其中：c4是服从[0,1]的均匀分布随机数；Pcr是设定的疯狂概率，若太小，P值为0的概率增加，因此在多次实验下，取0.5较为适宜。

2.3 模拟退火算法

模拟退火(Simulated Annealing,SA)算法[12]来源于固体退火原理，是一种基于概率的经典算法。SA算法与进化算法相结合，用于提炼进化算法每次找到的解，利用模拟退火的退温操作摆脱局部最优的干扰，使得每次获得解的质量提高，趋向全局性[13-14]。

2.4 算法实现步骤

麻雀搜索算法虽有较快的收敛速度，但易出现早熟现象，为此，本文提出了一种折射麻雀搜索算法(RSSA)，引入ROBL提升算法全局视野，再使用疯狂算子使算法的搜索变得更加细致，最后通过模拟退火算法提炼每次得到的解，使得最优解的质量提高。具体实现步骤如下。

1)初始化种群位置、数量以及迭代次数等相应参数。

2)计算各种群的适应度函数，得到相应的最大值和最小值，确定最好及最差位置。

3)计算预警值，根据预警值更新发现者的位置。

4)根据式(7)与式(1)更新发现者的位置。

5)根据式(8)与式(2)更新追随者的位置。

6)根据式(3)更新意识到危险的麻雀位置。

7)执行模拟退火操作，即

Tk+1=λTk

(11)

式中：T为温度系数；λ为退火过程中的衰减参数。

8)增加了当前温度下麻雀个体pi被选择为全局最优的概率算式，即

(12)

式中：Tfit表示新的适应度值；N为麻雀个体总数。

9)从当前麻雀个体pi中确定新的全局最优值fg。

10)若未达到迭代次数，则回到2)；若达到，则进行下一步。

11)输出最佳位置和最小代价。

3 算法性能测试

为测试改进算法的寻优能力，本文选取6个标准测试函数来验证，前2个为单峰函数，中间3个为复杂多峰函数，最后1个为固定维度函数，具体测试函数信息如表1所示。同时，将SSA算法、粒子群优化(PSO)算法和灰狼优化(GWO)算法进行对比，为验证算法的可行性与新颖性，将文献[15]中的混沌麻雀搜索算法(CSSA)与文献[16]中的改进麻雀搜索算法(ISSA)进行对比。所有算法的种群数量为100，迭代次数为500，PSO算法中学习因子c1=c2=2，权重w=0.728，实验环境为Matlab 2018b，Windows10操作系统，运行内存为8 GiB。分别统计各算法的最优值(Best)、平均值(Ave)及方差(Std)3项指标，用来综合衡量算法的寻优能力。

表1 测试函数表

各算法寻优结果见表2。由表2可看出，RSSA算法在各函数中均展现出较好的寻优能力，尤其在F3～F6函数中，RSSA算法的寻优效果与其他算法差异较大，从F1函数中可看出，RSSA算法并没有削弱SSA算法本身的寻优能力，由此证明了该算法的合理性。

表2 各算法寻优结果

仅凭3项指标确定改进算法的性能具有片面性，为体现其合理性及公平性，通过统计检验对改进算法相比于其他算法的优越性进行评估。本文采用Wilcoxon秩检验显示每种算法是否存在显著性差异，在5%的显著水平下进行实验，当P<0.05时，可认为拒绝零假设，即存在显著性差异；当P>0.05时，两种算法之间的差异性不明显，则用N/A表示。具体结果如表3所示。

表3 Wilcoxon秩和检验P值

由表3中看出，RSSA算法与各算法均存在显著性差异，仅个别算法存在性能相当的情况，因此进一步验证了RSSA算法的有效性。

4 无人机路径规划

4.1 任务环境的建模

4.1.1 地形威胁区域

当无人机执行任务时，应考虑地形起伏变化的特点。本文主要采取复杂函数模拟地形起伏变化的建模，具体数学模型如下

(13)

式中：x,y是地形投影在水平面上的点坐标，z为水平面点坐标对应的高程；a，b，c，d，e，f，g为常系数，对数字地图中的地表特征进行控制。

4.1.2 障碍区域建模

为了使无人机在躲避障碍区域中能够更直观地在三维模型中进行观测，障碍区域建模主要是建立山峰模型，山峰模型采用的数学表达式为

(14)

式中：i为第i座山；hi为山的高度；z为其高程；(xi,yi)是第i座山的地理中心坐标；xsi,ysi为控制山峰的坡度。

4.2 约束条件

无人机在实际运行中要考虑多方面的因素，因此其约束条件主要有以下几个方面。

4.2.1 最大长度约束

无人机在任务飞行的过程中，自身燃油携带量是有限的，因此每次飞行总长度需要受到限制。若一条路径中有n个点，且最大航程为Lmax，在路径节点的第i段长度可表示为Li。因此整条路线的总长度表示为

(15)

4.2.2 最低高度约束

在飞行过程中，低飞行高度确实能带来许多益处，但机身不能与地面距离太近，太近也同样存在着安全隐患，因此需选择合适的最低高度限制。如果第i段路径轨迹的离地最低高度为Hi，无人机最低飞行高度约束为Hmin，那么无人机飞行过程中将被要求始终满足

H≥Hmin。

(16)

4.2.3 最大爬升角约束

爬升角度是现实环境中无人机进行路径规划需要考虑的约束之一，因为，无人机在遇到障碍物时需要提前做好爬升准备，但是爬升角度有一个最大限制，超过此约束限制会造成无人机失速从而发生危险。角度γ满足

(17)

4.2.4 最大转弯角约束

在将算法用于无人机路径规划时，有必要考虑最大转向角约束，转弯角也是影响机身安全的因素之一。如果特定旋转角度超出了无人机应有的最大承受性能范围，则此可选节点将被直接舍弃。假如旋转角度可以满足无人机的机动性，则判断其他指标因素。最大转弯角约束如图2所示，其中，θ是无人机在水平面上的最大转弯角。假设飞行路径段i的水平面投影为Ai=(xi-xi-1,yi-yi-1)，并且其在路径段i+1上的投影为Ai+1=(xi+1-xi,yi+1-yi)，那么无人机的最大转弯角约束可以通过矢量Ai和Ai+1之间的角度表示。θ的计算方法如下

图2 最大转弯角约束示意图

(18)

式中，‖Ai‖表示向量的模。

4.2.5 威胁区域约束

无人机在飞行过程中也会受到诸多因素的威胁，因此本文使用不同大小的圆柱体来表示威胁区域，如图3所示。

图3 威胁模型示意图

无人机航迹规划是在绕过几个威胁区域的前提下，使无人机在最短的距离内到达目的地。假定无人机与威胁中心之间的距离为dT，威胁区域对无人机造成的损坏概率PT(dT)可以表示为

(19)

式中：dTmax表示受威胁区域影响的最大半径区域；dTmin表示无人机飞行发生碰撞坠毁的可能性为1的半径区域。

4.3 代价函数设计

对路径规划使用各算法时，代价函数被用来评价生成路径的优劣程度，也可作为算法种群迭代进化好坏的依据，算法执行的效率与质量取决于代价函数的优劣程度，同时也是评判路径规划水平的性能指标。为了更好地对路径质量进行考核，本文综合考虑路径的高度代价、长度代价以及偏转角大小这3个方面来构造适应度函数，即

Jcost=ω1Jlength+ω2Jheight+ω3Jsmooth

(20)

式中：Jcost表示路径的总代价；Jlength，Jheight，Jsmooth分别为路径的总长度代价、总高度代价以及平滑度代价；w1，w2，w3分别为对应权值。

4.3.1 路径长度代价

路径长度是评价路径优劣最重要的指标之一，路径越短，无人机飞行时耗能和耗时就越少。本文引入路径长度代价如下

(21)

4.3.2 高度代价

无人机的稳定飞行高度同样是无人机航迹规划过程中的重要环节。相对于大多数飞行器来说，飞行高度不应该有大幅度的波动。稳定飞行高度有助于减轻控制系统的负担，节省更多的燃料。故引入航迹高程代价函数如下

(22)

4.3.3 光滑度代价

无人机在转弯时受到空气阻力的影响，需要消耗一部分能量，同时也对机体产生一定的压力，转角越小，产生的压力越大且耗能越多，同时飞行效率低，因此飞行的平滑度也是飞行代价的关键因素。算式为

(23)

φj=(xj+1-xj,yj+1-yj,zj+1-zj)。

(24)

4.4 实验结果与分析

为验证融合算法优化无人机效果的可行性与实用性，将其与模拟退火粒子群算法(SAPSO),PSO,SSA优化效果进行对比，各算法参数设置如下：种群数量统一为100，迭代次数统一为400，初始温度T为25，λ=0.99，θ=45°，β=30°，Hmin=0.3 km,实验环境参数设置见表4。

表4 模型仿真参数

为增强实验说服力及减小偶然事件的干扰，每种算法独立运行10次，统计各算法每次规划路线的最小值、平均值、最差值这3项指标，各算法最优路线见图4，各算法的性能指标见表5，平均代价函数收敛图见图5。

图4 各算法最短路径规划图

图5 各算法平均代价收敛图

由图4及表5可看出，RSSA与SAPSO算法优化无人机的路径最为简单且清晰，从各算法性能指标表来看，RSSA算法比SAPSO算法具有更好的收敛精度与稳定性，其他算法的稳定性较差，最差代价值超过61；从图5中可看出，RSSA算法具有较好的收敛精度，在50次迭代之前找到了一条代价最小的路径，SSA算法找到的路线较差，复杂且代价最大。同时也验证了改进算法的有效性与实用性。综合来看，RSSA算法虽增加了内部循环的计算代价，但没有根本改变算法的总体结构，且极大地改善了算法寻优能力，因此增加的代价是值得的。

表5 各算法的性能指标

5 结束语

本文针对麻雀搜索算法在寻优过程中存在陷入局部最优且依赖于初始化种群的缺陷，引入了基于折射原理的反向学习策略与疯狂算子，使得搜索方式更加灵活、仔细，再融合模拟退火算法，提炼每次得到的最优解，通过标准测试函数及无人机路径规划实验验证了RSSA算法的有效性及实用性，下一步需要考虑更多的约束条件，实现精准的路线规划。