应用混沌萤火虫算法的无人机航迹规划

余胜东 ，吴洪涛 ，马金玉

1 引言

随着自动化、计算机与信息技术的发展，无人机应用的领域与范围也越来越广，飞行任务也变得愈加复杂多变[1]。无人机作为作战与侦察的重要手段，为了保证其安全飞行，航迹规划成了无人机实现自主飞行和自主攻击的关键性技术之一[2-4]。然而，航迹规划是个多约束条件的优化问题，如何更快更好地进行航线寻优极具挑战。

近几年来，国内外很多学者采用人工智能算法来解决无人机的航迹规划问题。例如，文献[5]采用遗传算法对无人机进行了实时在线航迹规划，但算法的效率不高；文献[6]利用人工蜂群算法的优势对无人机进行了航迹规划，但仍未克服算法陷入局部最优的问题；文献[7]提出了一种A*算法，有效地去除了规划空间中的无效节点，提高了无人机航迹规划的效率，但规划的精度不高；文献[8]将B样条曲线与粒子群算法（Particleswarmoptimization，简称PSO）相结合为无人机规划出光滑可飞的航线，但计算量太大。萤火虫算法（Glowworm swarm optimization，简称 GSO）是由文献[9]提出的一种新兴元启发式优化算法，已被成功应用于很多领域，但用于无人机航迹规划的研究却不多。GSO算法通过萤火虫个体间的相互吸引进行寻优迭代，具有需要调整参数少、收敛速度快、计算简单等优点。但和其他智能算法一样，基本的GSO法也易于陷入局部最优值导致出现早熟现象、种群多样性较低等的问题。

为了改进基本GSO的性能，提高其局部搜索能力，将立方映射混沌算子引入到GSO中，并提出了一种新颖的混沌萤火虫算法（Chaotic glowworm swarm optimization，简称 CGSO）来解决无人机的航迹规划问题。CGSO在对萤火虫位置初始化过程中使用混沌序列，有效保证了种群多样性和避免了算法早熟现象。同时，对无人机的规划空间与航迹代价模型进行了描述，并给出了威胁代价计算方法。最后，通过标准函数测试与航迹规划仿真对CGSO性能的优越性进行了验证与分析。

2 航迹规划问题描述

2.1 规划空间模型

无人机的航迹规划是在已探知的飞行区域内寻找一条从给定起始点到目标点的满足优化指标的可飞航线[10]。

图1 规划空间模型Fig.1 Model of Planned Space

无人机的起始点为S，目标点为T，如图1所示。需要在S点与T点之间找到一条既短又安全的航线。为了提高计算效率，以S点为坐标系原点，ST作为新的横坐标，垂直于ST的直线作为新的纵坐标。新旧坐标系的转换公式如式所示，θ为旋转角度。

将x轴N等分，节点横坐标为x（n）=ST·n（/N+1），n=1，2，…，N。过每个节点做 ST 的垂线，记作 L1，L2，…，LN。因此，从起始点S到目标点T的航线可以表示为｛S，L（1x（1），y（1）），…，L（Dx（D），y（D）），T｝，这样就把无人机航迹规划问题转换为一个维函数优化问题。

2.2 航迹代价模型

无人机的航迹代价由最小威胁代价minJt与最少油耗代价minJf组成：

式中：ωt—航线上各点的障碍物威胁代价；ωf—航线上各点的飞行油耗代价；L—总航线的长度；ε∈（0，1）—权重系数，若ε越接近0，表示航迹规划越重视油耗；反之，—航迹规划越重视安全，取ε=0.5。

2.3 威胁代价模型

为了计算ωt，如图2所示。把相邻两航迹点间的子航线等分成10份，取其中的5个分点来计算这条子航线的威胁代价。若该航线到威胁物中心的距离小于威胁半径，则根据下式来计算其威胁代价：

式中：Nt—威胁物数量；Li，j+1—子航线长度；tk—威胁物的威胁等级；da，k（a=0.1～0.9）—子航线上各分点到第 k 个威胁物中心的距离。

图2 威胁代价模型Fig.2 Model of Threat Cost

另外，由于无人机的油耗代价与航线有关，故将总油耗代价minJf近似等于总航线长度L。

3 基本的GSO算法

GSO算法是对萤火虫之间互相吸引和位置更新的模拟。算法主要分为4个部分：初始化萤火虫、荧光素更新、位置更新和决策域更新[11]。在算法中，分别定义每只萤火虫i的位置和该处的荧光素值为，并且每个位置对应一个目标函数值f（xi（t）），也就是航迹代价。

算法初始时，萤火虫i（i=1，…，M）的位置由式随机产生：

式中：M—萤火虫种群总数；L—xij取值的下限；U—xij取值的上限。

当每只萤火虫在其区域决策范围内向其邻域个体传递信息时，决策范围根据式更新。

萤火虫i决策范围内的个体数量由式决定：

萤火虫i的运动方向由其邻域内各萤火虫的荧光素数量来决定。而萤火虫i向其邻域内萤火虫j移动的概率由式计算：

移动后，萤火虫i的新位置由式计算：

式中：s—移动步长。

当萤火虫i其更新位置后，新的荧光素值按式重新计算：

式中：ρ∈（0，1）—常数，与荧光素挥发有关；γ—常数，辨识荧光素更新率。

在邻域集合中，当萤火虫i找到具有更高荧光素值的萤火虫j时，且若此时两个体间的距离小于感知半径，则萤火虫i以概率pij（t）选择萤火虫j，并向该方向移动；然后按式更新位置，并计算新位置的目标函数值；最后，按式对荧光素值进行更新。

4 混沌GSO算法

在GSO算法中，随机产生萤火虫的初始位置有可能会导致位置分布不均匀。考虑到混沌算子具有随机性与规律性的特点，且能在一定范围内不重复遍历所有状态。根据文献[12]，在混沌模型中，立方映射比常用的Logistic映射产生的序列更均匀，故采用立方映射混沌算子来改进萤火虫位置的初始化。根据式产生混沌序列：

式中：y（n）∈［-1，1］。

将混沌序列映射到优化变量的取值空间内，利用混沌特性来实现对萤火虫初始位置的搜索。具体步骤为：

（1）对于D维空间内的M个个体，随机产生一个D维向量Y=（y1，…，yd）作为第一个萤火虫个体，其中：yi（n）∈［-1，1］，1≤i≤d。

（2）利用式对Y逐维进行（M-1）次迭代，这就产生了其余（M-1）个个体。

（3）将产生的混沌变量根据式映射到解的搜索空间内：

式中：xid—萤火虫i在第d维的位置；yid—利用式产生的萤火虫i的第d维值。

5 仿真算例

5.1 算法测试

采用文献[13]中提出的4个标准测试函数对CGSO、GSO和PSO的性能进行测试比较。为了公平比较算法性能，各算法的种群规模都设为40，迭代总数为1000，各个测试函数的维数为20。分别对各个函数进行10次实验，统计10次实验最终得到的平均值、标准差、最差值和最优值，如表1所示。

表1 算法测试结果比较Tab.1 Comparison of Results of Algorithms Test

从表中可以看出，CGSO在四个标准测试函数上的寻优值要明显优于PSO与GSO，而且求解质量提升了较高的数量级。这表明所提算法具有更强的全局搜索能力。

5.2 航迹规划仿真

在不考虑姿态变化和地形高度的前提下，设无人机的整个飞行区域为（200×200）km，起始点 S（20，30），目标点 T（180，160），飞行环境，如表2所示。其中威胁物的威胁等级分为1～5五个等级。

表2 飞行环境设置Tab.2 Set of Flight Environment

设置GSO与CGSO三种算法的种群总数均为40，最大迭代次数为 100，ρ=0.4，γ=0.6，β=0.1，nt=8，s=0.03。另外，将这两种算法进行航迹规划的效果与文献[14]中提出的基于PSO算法的航迹规划效果进行比较。航迹规划的维数分别为15和30，分别用这三种算法进行航迹规划30次，取其中最好的一次结果，如图3～图4所示。

图3 三种算法航迹规划的结果对比Fig.3 Comparison of Results of Path Planning Based on Three Algorithms

GSO与PSO进行航线寻优的质量较差且均陷入了局部最优，如图3所示。而CGSO能够很好地跳出局部最优束缚并找到了全局最优的航线；随着求解维数的增加，相比其他两种算法，CGSO依然能够稳定获得较优航线。在图4中，CGSO的迭代速度要快于其他两种算法；在维数为15时，CGSO在20代左右便开始收敛，而GSO要在30代才开始收敛，PSO甚至到60代时还未收敛。表3为三种算法航迹规划的代价值，可以看出CGSO的航迹代价值最小；以维数15为例，所提新算法的搜索效率要比GSO与PSO提高了3.54%和5.83%。以上分析均表明CGSO算法的鲁棒性、快速性和精确性要比其他两种算法好，更适合对无人机进行航迹规划。

图4 三种算法迭代曲线对比Fig.4 Comparison of Iteration Curves Based on Three Algorithms

表3 航迹代价值Tab.3 Path Cost Value

6 结论

提出了利用混沌萤火虫算法来解决无人机在复杂飞行环境下的航迹规划问题。该算法通过萤火虫相互吸引及位置更新来搜索最优解，并引入混沌算子的遍历性与随机性来避免GSO陷入局部最优，从而快速找到全局最优解。标准函数测试表明与其他算法相比，CGSO在求解质量上有显著提高。航迹规划仿真证明了所提算法能够有效解决算法陷入局部最优的问题，并提高了算法收敛速度。另外，随着规划维数的增加，CGSO也表现出较好的稳定性。因此，CGSO能够快速、高效地为无人机规划出一条安全可飞的航线。