基于改进萤火虫算法的无人机路径规划

龙舰涵，许湘扬

(泸州职业技术学院 电气与电子工程学院，四川 泸州 646000)

0 引言

无人机(UAV)是一种常见的便携式遥控设备。UAV由于成本低、适用场景多等优点，广泛应用于大气探测行业、电力行业等行业[1-5]。UAV路径规划是UAV飞行领域内的关键技术之一[6-8]。路径规划一般是指确定UAV的起飞位置和目标任务后的一系列优化问题[9-10]。根据UAV的机动性、地理环境威胁和约束条件，规划出最优或次优飞行路径。规划路径的优劣直接影响无人机能否顺利完成任务。因此，无人机路径规划技术已成为无人机发展的关键。

传统路径规划算法包括人工势场法[11]、A*算法[14]等，传统算法需要环境精确建模且运算量较大，存在可行解时可以找到解，但当函数不连续、不可微时，则很难适用。因此在处理解决复杂问题，尤其是离散变量、非连续性问题，智能算法具有更好的适应性。常见的包括蚁群算法[12]、粒子群算法[13]，基本蚁群算法全局搜索能力强，稳定可靠，但信息浓度低，精度不高，搜索速度慢[15]；差分进化算法，这种算法参数较少，易控易实现，但寻优效率不高[16]；鱼群算法，基本鱼群算法面对复杂环境有较高适应性，但经验行为学习能力不够，收敛准确度较低[17]；遗传算法可同时进行多寻优，但后期收敛速度慢，易得局部最优解[18]；深度学习法具有较强的搜索能力，但卷积神经网络较为复杂，三维规划数据量较大[19]。

萤火虫算法(FA)是YANG开发的群体启发算法之一。其受到萤火虫闪烁的灯光照亮启发。萤火虫闪烁是为了寻找配偶或抵抗捕食者的攻击。当萤火虫和光源之间的距离增大时，光吸收导致光变得越来越弱。萤火虫算法作为群体智能算法之一，也容易陷入局部最优。在过去的几年里，许多学者开发了新的FA变体，以避免过早收敛问题[20-23]。尽管这些改进算法已被证明在解决优化问题上是有效的，但仍存在以下缺点：改进方法仅限于算法的部分优化，没有从整体上考虑萤火虫种群的特征。尽管FA算法在个别阶段的优化效果较好，但随着优化问题维数的增加，其性能也会像其他群体智能算法一样下降。然而，在复杂飞行环境下，无人机路径规划问题往往是高维的。另外，通常在路径规划阶段，如果不考虑运动学约束，算法规划的路径在实际情况下无法飞行。

针对以上问题，本文基于多角度改进结合莱维飞行对基本萤火虫算法做出优化。引入Chebyshev映射优化算法初期粒子分布，使得全局搜索能力得以提升；引入logistic混沌函数改进吸引度系数γ，增强算法局部搜索能力，提高后期收敛速度；利用Levy分布改进萤火虫个体的搜索步长，得到新的位置更新公式和新的步长更新公式，提高了种群的搜索范围和有效性。

1 基本萤火虫算法

萤火虫算法是一种智能仿生算法，模拟萤火虫飞向更亮个体的特征。它是基于萤火虫的闪烁模式和行为，这基本上是基于生物发光现象，这是一个过程，负责闪烁的光和交配伙伴被吸引使用这些光。这些灯的潜在优势是，更亮的萤火虫会吸引其他不那么亮的萤火虫，这种现象使得萤火虫可以探索搜索空间，即更新它们的位置。利用目标函数计算每只萤火虫的亮度(适应度)。此外，FA与其他优化算法相比有两个主要优势：自动划分和处理多模态目标函数的能力。这意味着整个萤火虫种群能够自主的分裂成若干子群体，各个群体都能够在局部最优周围进行聚集，从而在所有的这些解之中得到最优的全局解。此外，如果搜索代理的数量适当大于最优的数量，则分割的性质有利于搜索代理同时找到所有的最优。FA基于两个概念，即亮度和吸引力，随着距离的增加而降低。

问题的可行解即萤火虫的位置，萤火虫的亮度即适应度函数。可行解不断接近最优解的过程就是萤火虫飞向更亮个体的过程，直到满足预设条件，即完成任务。将这个过程以数学的形式表述如下：

假设有N只萤火虫，求解问题的维度是D，xi= (xi1，xi2，…，xiD)，(i=1，2，…，N)表示第i只萤火虫的位置，相应的xj= (xj1，xj2，…，xjD)，(j=1，2，…，N)表示第j只萤火虫的位置。

个体i和j之间的距离rij如式(1)计算：

(1)

式中，xid和xjd分别表示d维中，第i只和第j只萤火虫所在的位置。

萤火虫的亮度更新公式如式(2)，吸引度更新公式如式(3)所示：

(2)

(3)

其中：I0表示萤火虫初始亮度，β0代表初始吸引度，γ表示吸引系数。

若萤火虫j更亮，则萤火虫i向j移动时的位置公式如下：

xid(t+1)=xid(t)+β(xjd(t)-xid(t))+αi(t)ε

(4)

其中：xid(t)和xjd(t)表示在d维时萤火虫i和j迭代至第t代时的位置，αi(t)表示萤火虫i第t代时的步长因子，ε服从均匀分布，取值范围为[-0.5，0.5]。

2 改进的萤火虫算法

2.1 Chebyshev混沌映射初始化

混沌在自然界的非线性系统中普遍存在，看似无逻辑的混沌过程却有其规律性。混沌过程的规律性在于其能不重复地遍历所有状态，因此遍历性的优点引入群智能算法，能极大地避免陷入局部极值[24-25]。

通过Chebyshev混沌映射使得萤火虫随机混沌的形成初始种群，与其他诸如logistic、sine等混沌映射相比，以Chebyshev映射方式产生的粒子全局分布更广，信息更加全面，可以更好的避免信息片面带来的种群易得局部最优的问题。本文采用Chebyshev混沌映射生成混沌变量，如式(5)所示：

xn+1=cos(karccosxn)，xn∈[-1，1]

(5)

式中，k为混沌的阶次，当k≥2时，初始值任意设置，经过混沌迭代处理后的序列均不相关，本文取k=4，由公式计算生成彼此互不相关，但所有变量具遍历性质的混沌序列。

利用Chebyshev映射产生初始化种群的步骤如下。

Step 1：若D维空间存在N只萤火虫，随机生成D维向量Y= (y1，y2，…，yd)，yi∈[-1，1]，i∈[1，d]作为第一只萤火虫的初始信息；

Step 2：用式(5)对Y向量的各维度进行迭代N-1次，得到其他N-1只萤火虫信息；

Step 3：将N个经过混沌的个体映射到解空间，具体如式(6)所示；

xid=ld+(1+yid)×(ud-ld)/2

(6)

第d维解空间的上界和下界分别用ud和ld表示，式(5)得出的第i个萤火虫的第d维即yid，xid即经过映射后，第i个萤火虫的第d维坐标值；

Step 4：将N个萤火虫的适应度函数分别进行计算并排序，选M个优质个体作初始种群。

2.2 logistic混沌改进吸引度系数γ

经典的logistic混沌映射是一个动态随机的过程，相比其他方式其具有更好的局部精确性，因此在局部寻优阶段对吸引度衰减系数γ采用混沌逻辑处理，可跳出当前状态逃离局部最优解。混沌序列处理方式如式(7)所示：

xi+1=μxi(1-xi)，μ∈[0，4]，xi∈[0，1]，i=1，2，···，n

(7)

其中：μ是控制参数，本文取μ=4，式(7)此时已进入完全混沌状态。为使吸引度衰减系数γ和算法运行过程相匹配，引入另一变量hs，其值与适应度函数联系紧密，这样处理可以在算法执行初期，当γ的值较小时，I值会很大，此时便可以增强全局搜索能力；算法执行后期，当γ的值较大时，I值会变小，可提高局部搜索能力，hs计算如式(8)所示：

(8)

(9)

其中：Tmax是最大迭代次数，iter是当前迭代次数，通过此公式可调节γ取值，fpi(t)是最佳适应度函数值。

2.3 Levy飞行策略改进步长

Levy flight是法国数学家Levy在20世纪30年代提出的一种随机行走机制，其行走步长满足稳定的重尾分布，在局部位置有较大的跳跃概率。Levy飞行的概率密度分布具有尖峰、非对称和拖尾特征。它的运动模式在频繁的短距离跳跃和偶尔的长距离跳跃之间交替，可以跳出局部最优，扩大种群搜索区域。许多昆虫和动物，如苍蝇和驯鹿，遵循类似自然界Levy飞行的轨迹。

引入Levy飞行的随机搜索策略代替基本算法的步长因子[25，27]。改进的基本思路是利用Levy分布的概率分布特性，改良个体搜索步长的随机性，提高了种群的搜索范围和有效性和全局综合搜索能力。Levy飞行化简后的数学描述为：

Levy(s，γ，μ)=

(10)

引入Levy飞行后位置更新公式为：

(11)

其中：⊕是点对点乘法，Levy(λ)是符合Levy分布的步长随机函数：

Levy(λ)～u=t-λ，1<λ≤3

(12)

改进后步长的计算公式如下所示：

(13)

其中：μ，ν服从正态分布。

(14)

其中：θ取1.5，为方便计算，对该正态分布进行简化：

(15)

(16)

图1 不同标度参数下的Levy分布

2.4 算法实现流程

本文算法的实现具体流程如下：

1)建立3维高空作业环境，设置起终点，生成等高度自适应巡航栅格图。

2)初始化算法中初始亮度I0，初始吸引度β0，最大迭代次数Tmax，萤火虫数目N，混沌映射后选择的优质个体M。

3)引入Chebyshev映射，用式(5)～(6)生成萤火虫初始种群。

4)根据式(7)～(9)计算吸引度系数γ。

5)代入吸引度系数至式(2)～(3)，再通过式(1)计算各萤火虫的相对荧光亮度I，距离rij，吸引度β。

6)根据公式(4)的莱维飞行策略更新位置。

7)对位置更新后的个体重新计算相对荧光亮度I。

8)当前迭代次数iter与最大迭代次数Tmax作比较，若iter>Tmax则退出迭代，若iter

9)算法结束，输出最优结果。

具体流程图如图2所示。

图2 算法流程图

2.5 算法时间复杂度分析

为了更清晰地考察和评价改进萤火虫算法的复杂性，将其与传统萤火虫的复杂性进行了比较。

首先，需要分析了FA的时间复杂度。在FA算法中，假设终止条件为Max，其总体大小为N，问题的维数为D，算法的执行时间是t1，求一个解的时间为t2。FA的时间复杂度为O(Max*N*N*D*(t1+t2))。所以它可以表示为O(N2)。

然后，分析改进FA的时间复杂度。在改进算法中，假设终止条件、总体大小和问题的维数分别与FA相同。生成的组的大小为K。计算时间di、生成组M、对xj的评价、对M的评价、对xgbest的评价的时间分别为t3、t4、t5、t6、t7。改进FA的时间复杂度为O(Max*N*D*(N*t3+N*t4+ 4*N*t5+K*K*t6+t7))。因此，它可以表示O(N2+N*k2)。很明显，改进FA的时间复杂度取决于生成的组的大小。由于自适应多群机制，K的值可以是(0，N)之间的任意值，因此改进FA的时间复杂度在O(N2)和O(N3)之间。

虽然改进FA的时间复杂度比FA要低，但为所提出的自适应多群机制增加计算成本是值得的。原因之一是利用所提出的混沌初始化机制将搜索空间划分为多个子空间，可以在搜索空间中探索出更满意的解。另一种是增加对一些较好的萤火虫的评价，可能有助于FA增加逃脱局部陷阱的概率。

3 无人机飞行环境建模及优化

3.1 飞行空间

UAV在三维空间中执行飞行任务，空间跨度大，环境复杂。此外，无人机受到许多条件的约束。因此，路径规划需要平衡搜索时间、路径代价和计算复杂度，以满足实际工程的要求。路径规划的目标是在复杂环境和各种约束条件下找到到达目标点的可行路径。在环境模型中，轨迹点的位置用三维坐标(xi，yi，zi)(i= 1，2，…，Ns)表示，UAV飞行空间表示为：

(17)

其中：xmin，xmax，ymin，ymax，zmin，zmax分别表示飞行空间边界。

3.2 约束条件

1)距离成本约束：

在UAV执行飞行任务的过程中，距离较短的飞行轨迹(Mfirst，M2，M3，…，Mlast)比距离较远的轨迹具有更好的性价比。通过缩短飞行距离、降低无人机燃油消耗和缩短飞行时间，降低了飞行成本。考虑到无人机自身携带的燃料有限，需要将飞行距离控制在一定限度内，可用以下表达式来表征距离成本约束。

(18)

(19)

式中，G(G≤Gmax)为距离代价，N为构成一条完整飞行轨迹的轨迹段数，fi为轨迹i的距离代价。

2)飞行高度限制：

气压、风速等因素对无人机的飞行有着巨大的影响。考虑到无人机飞行的安全，飞行高度应控制在一定范围内，飞行高度不能过高或过低。设环境模型在航迹点(xMi，yMi，zMi)处的地形高度Tmap为，fh表示最小飞行高度，F定义为最小飞行高度可调信息。

(20)

3)最大偏角约束：

在飞行过程中，无人机需要及时调整飞行姿态，这受到其机动性的限制。只有当偏角小于最大偏角时，无人机才能保持稳定的飞行姿态。设某航迹段与其相邻航迹段的向量为pi=(xMi+1-xMi，yMi+1-yMi，zMi+1-zMi)，最大偏角满足约束条件：

(21)

4)最大俯仰角约束：

影响无人机俯仰角的因素包括风向、气候和自身机动性。此约束限制 UAV在特定角度范围内向上或向下飞行。最大俯仰角可以用数学表达式描述：

(22)

3.3 平滑操作

为满足无人机特殊的飞行机动特性，需要对算法生成的飞行路径进行平滑处理。普遍采用的方法是对生成的航迹曲线进行拟合，增加了工程的工作量。三次样条插值是一种分段的插值方法，它在原轨迹点中利用若干个插值点形成一条平滑的轨迹。三次样条插值法处理过的无人机飞行轨迹更加平滑，无需对算法规划的路径进行曲线拟合。既可以使得无人机在紧急制动或者紧急转向时具有良好的动态性能，又可以减少路径生成过程的冗余度。因此，本文采用三次样条插值曲线来构建和表示无人机飞行路径。

3.3.1 三次样条插值

设Δ为区间[a，b]的一部分，若函数S(x)满足：

1)S(x)∈C2[a，b]；

2)S(xi)=f(xi)i= 0，1，2，…，n；

3)S(x)是每个子区间[xi，xi+1](i= 0，1，2，…，n-1)上的三次多项式，那么S(x)被称为分区Δ的三次样条函数。

如果在节点xi上给定一个函数值，且S(xi)=yi，则S(x)称为三次样条插值函数。为了确定唯一，需要添加3个常见的边界条件：

1)S(a)=y0，S(b)=yn；

2)S(a)=y0，S(b)=yn；

3)S(a+0)=S(b-0)，S(a+0)=S(b-0)，S(a+0)=S(b-0)。

3.3.2 代码设计

三次样条插值是一种分段插值方法。每段之间的样条是不一样的。全部轨迹曲线都是一阶连续，而在轨迹节点是二阶连续的。因此，轨迹节点的数量表示整条飞行轨迹的转弯次数。虽然环境条件很复杂，但一般只需要三至五次就可以躲避全部的障碍。根据环境变化选择飞行轨迹节点的位置。

本文将一条路径上的所有节点视为萤火虫的编码，即一条路径上n个路径节点的三维坐标构成萤火虫个体的n-3维坐标。假设已经确定了n个路径节点的坐标，分别为r1= (xr1，yr1，zr1)，...，rn= (xrn，yrn，zrn)，路径的起点和终点坐标分别为(xs，ys，zs)和(xt，yt，zt)。分别在区间[xs，xr1，xr2，...，xrn，xt]，[ys，yr1，yr2，...，yrn，yt]和[zs，zr1，zr2，…，zrn，zt]，插值点坐标为(xS1，xS2，…，xSm)，(yS1，yS2，…，ySm)，(zS1，zS2，…，zSm)，并通过三次样条插值。那么将轨迹点、插值点以及起终点的连接起来就是UAV规划的飞行路线。

3.3.3 适应度函数与碰撞检测

无人机的飞行轨迹不能与障碍物产生冲突，路径长度要求尽可能短。碰撞检测的目的是检查规划的飞行路线是否穿过障碍物。对三次样条插值后的曲线按路径节点进行分段。每个节点产生{(x，y)| (xri，yri)，(xS1，yS1)，…，(xSm，ySm)}和{z|zri，zS1，zS2，…，zSm}集合，两个集合构成路径曲线上的一点。

本文将障碍定义为三元函数F=aX+bY+cZ。(a，b，c)表示权重插值。对函数F数据进行插值，得到集合{(x，y)}值对应的插值函数值。将函数值与集合{(z)}进行比较，以确定路径是否通过障碍物。本文构造的适应度函数为：

z=L⊗ϖ

(23)

ϖ=ϖ1f1+ϖ2f2+ϖ3f3

(24)

(25)

式中，f1、f2、f3分别为飞行高度、最大偏航角、最大仰角的代价。满足ϖ1+ ϖ2+ ϖ3= 1。

4 仿真及分析

4.1 算法性能实验

为了研究改进FA 的性能，对来自 CEC2013的 28 个测试函数分别利用传统FA和本文算法独立执行30 次实验。在Windows环境下使用MATLAB2018b进行了测试。参数设为随机参数α=0.2，固定光吸收系数-315，初始亮度I0= 1，系数γ=1，r=0，最大的迭代次数为800，问题维数为10。结果如表1所示。

表1 算法性能对比结果

将本文算法的精度与传统FA算法进行比较，其中结果是使用30次运行的平均值得到的。从表中可以看出，结果表明，在CEC2013的28个测试函数中，本文算法在测试函数中精度均优于传统FA算法。从表中的结果可以看出，基于多角度改进策略的萤火虫算法在单峰函数上表现良好，而对于多峰函数以及组合函数，搜索步长的设置会影响本文提出的算法。另外引入Wilcoxon秩检验，在5%的显著水平下进行试验，当P≤0.05时，则存在显著性差异。反之当P>0.05时，则表示差异不显著，用N/A表示，具体结果如表2所示。由其可以看出，改进算法与基本FA算法存在显著差异，改进算法更具优势。

表2 Wilconxon秩检验P值

4.2 环境建立

本文以数学模型建立模拟高空环境，主要研究山地地形的UAV的自适应巡航路径规划问题。以山峰的形式模拟无人机高空工作面临的地形状况，将无人机实际工作环境用三维的山地环境表示，如图3所示。整个模型空间为150×150×250，x∈(0，150)，y∈(0，150)，z∈(0，250)。

图3 高空三维环境建模

4.3 参数设置

为检验改进后萤火虫算法的规划性能，基于Windows11系统、Matlab R2017a平台、内存16 GB等硬件环境，分别利用改进前后FA算法进行规划对比。基于上节中建立的模拟山地环境，并且设置无人机的飞行起始点为(0，0，160)，终点为(150，150，160)，将无人机视为质点，尺寸忽略不计。算法中主要参数初始值需通过多次仿真实验获取，具体如表3所示。

4.4 实例仿真分析

基于模拟山地环境，并按上节参数取值初始化算法中的相关参数，分别利用多角度改进的FA算法和基本FA算法对无人机的航线进行规划。图3为基本FA算法规划的飞行路径，图4为本文算法规划的飞行路径。两种算法各项指标对比如表3所示。

图4 算法改进前规划路径

从图4、图5及表4可以看出，相比于基本FA算法，多角度改进的FA算法规划路线的飞行距离更短，转向次数更少且可以更快寻得最佳飞行路线。具体表现在路径长度减少7.47%，节点减少31.57%，收敛时间减少18.54%。另外飞行轨迹中没有尖锐的急转向角度，整个航线平滑度得以提升，满足无人机在真实环境下的飞行约束。因此在对无人机飞行路线进行规划时，本文算法对无人机真实作业场景具有更强的适应力，能够帮助无人机安全高效的完成飞行作业。而基本萤火虫算法规划的飞行路线中存在一些无用路径，且存在尖锐的转角，这可能导致无人机硬件损耗增加，无法很好适应复杂环境。

表4 指标对比

图5 算法改进后规划路径

为进一步验证改进算法的性能，将改进算法与其他规划算法进行对比，仿真环境与图2保持一致，各算法结果指标对比如表5所示。

表5 指标对比

由表5可知，本文改进算法相较其他对比算法，在路径长度、节点数、收敛时间等指标上，都有不同程度的提升，具体表现为路径长度缩短约为1.14%～7.89%，节点数减少约7.14%～38.10%，收敛时间减少约1.09%～20.53%。因此，验证了本文算法的优良性能。

4.5 算法消融实验

为检验本文提出的改进策略之间的独立性及必要性，对本文算法进行消融实验。基于相同环境，对仅使用Chebyshev映射改进的算法(FA-C)、仅使用logistic映射改进的算法(FA-l)、仅使用Levy飞行策略改进的FA算法(FA-L)与本文改进FA进行比较，结果如表6所示。

表6 消融实验结果

从表6可看出，相较于基本FA算法，单一的改进策略在路径长度及收敛时间上均有不同提升，引入Chebyshev映射可以是扩展寻优空间，logistic映射则可以提升算法局部搜索性能及寻优效率，Levy飞行策略能够扩大搜索范围，使得结果更加精确。结果表明，同时引入3种策略可有效提高算法性能及效率。

5 结束语

本文针对无人机的最优路径规划问题，提出一种多角度改进的萤火虫算法。首先利用Chebyshev混沌特性初始化种群，改善了初始种群不易产生的问题。针对步长因子过于固定的问题，引入Levy飞行算法，利用莱维分布得到新的位置更新公式和新的步长更新公式，提高了种群的搜索范围和有效性。最后针对搜索过程中避免陷入局部极值的问题，引入logistic混沌变异改进吸引度系数，使算法更容易跳出当前状态而逃出局部最优区域，增强了算法局部搜索的能力，保证了算法后期的收敛速度。在模拟高空山地环境仿真后对比数据得出结论，相较改进前萤火虫算法，本文算法路径长度减少7.47%，节点减少31.57%，平顺度优于改进前，收敛速度更快，收敛时间减少18.54%，相较其他对比算法路径长度缩短约为1.14%～7.89%，节点数减少约7.14%～38.10%，收敛时间减少约1.09%～20.53%，因此本文具有良好的规划性能。