采用改进细菌觅食优化算法的无人机航迹规划*

魏永超a，邓 岚**，李 涛c，邓 毅c，邓春艳

(1.中国民用航空飞行学院 a.学院科研处；b.民航飞行技术与飞行安全科研基地；c.民航安全工程学院，四川 广汉 618307)

0 引 言

基于上述算法的局限性，本文提出一种基于改进细菌觅食优化算法(Improved Bacterial Foraging Optimization,IBFO)的航迹规划算法，且针对基本细菌觅食优化算法(Bacterial Foraging Optimization,BFO)易早熟和收敛速度慢等缺陷，对算法的趋向步长、游动及迁徙操作进行改进。首先，在趋向时，通过赋予细菌自适应的步长来代替细菌的固定趋向步长；其次，嵌入粒子群算法(Partical Swarm Optimization,PSO)的学习因子思想，一个细菌的游动不仅受限于自身的觅食能力，还受到其他细菌的影响；最后，在迁徙时，提出一种自适应的迁徙概率代替固定的迁徙概率。

算法通过比较目标函数，找到代价最小的航迹点，最终得到最优的航迹结果。通过Matlab建立三维环境模型，仿真测试后验证，该算法是可行和有效的，且相比基本的细菌觅食优化算法和粒子群算法提高了收敛速度和求解质量，能够快速安全地实现无人机的航迹规划。

1 IBFO算法原理

将基本的BFO算法通过三个方面的改进得到IBFO，并应用于无人机航迹规划。

1.1 基本BFO理论

细菌觅食优化算法(Bacterial Foraging Optimization，BFO)是由 Passino 基于大肠杆菌的觅食行为，于2002年提出的一种新型仿生类的群体智能优化算法。该算法模仿Eeoli大肠杆菌在人体肠道内吞噬食物的行为，通过模拟细菌迁徙、趋向、聚集、复制四种行为求解问题[9]。

(1)迁徙(Elimination and Dispersal)：当细菌所处的局部环境逐渐发生变化或者突变时(如食物消耗殆尽或温度突然升高)，细菌会随机以给定的迁徙概率Ped迁徙到一个新的区域以应对这种改变。该行为中，细菌中的个体以一定概率死亡并在一个新的区域生成一个新的细菌，从而更有利于算法跳出局部最优解，进而寻找全局最优解[10]。

(2)趋向(Chemotaxis)：细菌将会进行旋转和游动，趋向食物丰富或环境酸碱度适中的区域。旋转是指向一个新的方向，游动指若适应度值得到改善则保持这一方向向前运动，直至适应度值不再改善[11]。趋向行为的数学表达式为

(1)

式中：θi(j,k,l)表示细菌i在第j次趋向、第k次复制、第l次驱散后所处的位置，C(i)为细菌的趋向步长，Δ(i)为细菌在搜索空间内随机方向上的一个单位向量。

(3)聚集(Swarming)：细菌在觅食时，不同个体间存在引力和斥力，引力使细菌更多地聚向食物丰富或环境酸碱度适中的区域，斥力使每个细菌在搜索空间内都有一定的觅食区域，令其能在该位置上获取能量来维持生存[12]。聚集行为的数学表达式为

(2)

(4)复制(Reproduction)：细菌进化服从“适者生存、优胜劣汰”，觅食能力弱的细菌会被淘汰，觅食能力强的细菌进行复制。式(3)被称为细菌i的适应值，该值越小，表明细菌i越健康，觅食能力越强。

(3)

算法中，一个细菌代表一个解，搜索空间中细菌的位置对应着优化问题的解，优化函数的适应度值即目标函数的值，代表解的优良程度。

1.2 IBFO算法

BFO算法中，个体的步长和迁徙概率是固定不变的，步长的不变性会影响最优解的精确度，迁徙概率不变则会导致算法后期的收敛速度变慢。基于上述考虑，本文在研究基本细菌觅食优化算法基础上，进行了以下三个方向的改进，得到了优化能力更好的改进细菌觅食优化算法。

(1)细菌在移动中的固定步长会使收敛速度较慢，因此将固定步长改进为自适应的步长。文献[13]中,采用Cmax为寻优范围最大值的1/4，同时依赖趋向、复制和迁徙的次数j、k、l的乘积来使搜索更加精确，并采用rand函数使运算量减小，最后使得细菌在不同维度前进不同的步长，前期搜索效率高，后期搜索精度高。公式如下所示：

(4)

式中：rand()为从0～1的随机数；Cmax=(MAXd-MINd)/4，MAXd为第d维寻优范围最大值，MINd为第d维寻优范围最小值；j，k，l分别为当前趋向、复制和迁徙次数。

式(4)的改进虽提高了步长递减的变化，但寻优前进的方向较随机。本文的IBFO算法将在此基础上，加入寻优方向的限制，以提高算法的精度。

据细菌和最优点之间的距离来调节步长，若两者距离远，则步长加大；距离近，则步长减小，从而提高收敛速度。将通过下列公式实现：

(5)

式中：Ji为当前细菌i的适应值，Jmax为当前所有细菌最大的适应值。

(2)嵌入粒子群算法的学习因子思想，一个细菌的游动不仅受限于自身的觅食能力，还受到其他细菌的影响。即对于一个细菌，将它的适应度函数值与当前觅食能力最好的细菌进行比较，通过交流学习觅食能力更好的细菌来提高自己的觅食能力。其函数由式(6)给出:

Δ(i)′=Δ(i)+C1rand()×(Jmax-Ji)+

(6)

(3)基本BFO算法中，迁徙概率为一个定值，即所有细菌都以Ped迁徙到一个新的区域，这可能会导致精英个体丢失，算法的收敛速度、精度和稳定性降低[14]。因此，本文将采用自适应的迁徙概率，通过下式实现：

(7)

式中：Jmin为当前所有细菌最小的适应值,Ped为设置的固定迁徙概率。

通过改进，适应度函数值小的细菌迁徙概率大，适应度函数值大的细菌迁徙概率小。这将保证觅食能力最好的细菌一定会被迁移，从而提高了算法的稳定性。

2 IBFO算法航迹规划

2.1 航迹规划目标函数

航迹规划的目的即在确保无人机安全飞行的前提下，规避威胁区域，如陡峭的山峰、恶劣的天气等，最后规划出一条从起点到终点的最短路径。本质上来说，就是一个求解包含众多约束条件的函数最优解问题[15]，其数学形式可由公式(8)表述：

minf=w1×minf1+w2×minf2+…

+wn×minfn。

(8)

式中：f(x)是目标函数，w1、w2…wn是权重系数，f1(x)、f2(x)…fn(x)是约束条件函数。本文中航迹规划模型将采用以下三个约束条件：

(1)路径最短约束

即求从第一个导航点到最后一个导航点的最短总路径长度：

(9)

式中：dx、dy、dz为当前导航点减去前一个导航点的x方向、y方向、z方向的距离差。

(2)飞行高度约束

无人机的飞行高度不能过高也不能过低。若飞行高度过高，会超出无人机机身承受范围，对机体造成损伤；若飞行高度过低，会增加无人机的撞毁概率。因此，需要让无人机在一个合适的高度飞行，且要求飞行过程中尽量保持平稳，以减少油耗以及机器的损耗。由下式表示：

(10)

(3)转弯角约束

转弯角即是无人机从这个导航点到下个导航点转过的角度。在飞行过程中，由于无人机自身的制造工艺约束，不同的无人机具有不同的物理性能，但都不能突然进行大角度的转弯。同时，约束转弯角可以避免无人机迂回前进。由式(11)、(12)所示：

(11)

ai=(xi+1-xi,yi+1-yi,zi+1-zi)T。

(12)

以上三个约束条件通过权重的分配，共同构成了航迹规划的目标函数，从而将搜索一条航迹代价小的路径规划问题巧妙地变为通过智能优化算法求目标函数最小值的数学问题。这样将实际问题进行量化，转化为规划系统能识别的数学符号，是航迹规划技术的发展的一大重要板块。

2.2 IBFO无人机航迹规划流程

如图1所示，将IBFO算法应用在求解无人机航迹规划问题，可分为以下四个步骤：

Step1 读取坐标数据，完成数字地形高程图的建模。设置起点S、终点T的坐标。

Step2 初始化IBFO参数，包括细菌进行迁徙行为的次数、细菌进行趋向行为的次数、细菌进行聚集行为的次数、细菌进行复制行为的次数、细菌的迁徙概率、向前游动的步长、细菌种群大小、引力深度、引力宽度、斥力深度、斥力宽度、局部学习因子、全局学习因子、迭代次数。

Step3 算法迭代。细菌不断进行迁徙、趋向、聚集、复制操作，采用改进的IBFO算法求解航迹规划目标函数最小值，同时，避免飞入天气威胁区和禁飞区，得到从起点到终点的n个导航点。

Step4 迭代结束，规划出最优路径。

此无人机航迹规划优化模型采用改进的细菌觅食优化算法，通过不断迭代寻找目标函数更小的导航点，在设定的迭代次数完成后结束迭代。迭代次数通过经验取得，可以使目标函数达到收敛。最终将得到的n个导航点连接起来，即得到了规划出来的航迹。

图1中，Ned为迁徒行为的次数，Nre为告别行为的次数，S为细菌种群个数，Nc为趋向行为的次数，Ns为趋向行为中单向运动最大步数，最小的适应度函数值存储为Jend。

图1 将IBFO算法应用于航迹规划

3 实验分析

3.1 航迹规划环境建模

环境建模大致可分为两类：基于二维平面建模和基于三维立体建模。目前，全球应用较广的是数字地形高程数据库(Digital Terrain Elevation Data，DTED)。数字地图的种类也有很多，包括数字栅格地图、数字高程模型(Digital Elevation Model，DME)、数字线划地图和数字遥感影像图等[16]。本文采用数字高程模型进行三维立体建模，通过z=z(x,y)表示地形，其中(x,y)为平面二维网格坐标，z为高度。

本文选取了纬度范围从31度22分42.28秒到31度30分02.56秒，经度范围从102度52分23.26秒到102度59分52.05秒的真实地形，如图2所示。

图2 真实地形

随后，通过数字地形高程数据库获取高程点，通过仿真，按照1∶100000的比例均匀离散化为139×139的坐标空间。同时，由于在真实飞行中天气威胁区和政治敏感禁飞区不可忽略，因此将这些区域在航迹规划空间中等效为圆柱型区域，无人机在飞行过程中必须绕过这些障碍。算法经过两个步骤避开障碍：第一步，所有航迹点不会落在圆柱体中；第二步，已得到的两个相邻航迹点之间的连线与圆柱体不能有交点。

本文设置了两个天气威胁区和一个禁飞区。两个天气威胁区为红色圆柱形，平面坐标分别为(70,70)、(80,30)，半径均为10；一个禁飞区为蓝色圆柱形，平面坐标为(100,100)，半径为7，由于离散化坐标空间，无单位。最后的数字地形高程图如图3所示。

图3 数字地形高程图

3.2 算法验证

为了验证本文算法的有效性，采用Matlab R2017b对算法进行仿真。函数变量范围为整个三维空间大小，算法具体参数设置如表1所示。

表1 参数设置

无人机航迹规划仿真结果如图4所示。仿真设置了两个起点，起点1为红色圆型，坐标为(20,20,4.245)；起点2为红色三角形，坐标为(40,20,4.245)。终点为黑色*型，坐标为(90,70,2.7)，坐标中的高度单位为km。仿真采用了三个算法实现无人机航迹规划，分别是改进细菌觅食优化算法、粒子群算法与基本的细菌觅食优化算法，得到的航迹颜色分别为蓝色、绿色、红色，从图中可以清晰地观察到各条航迹。

图4 航迹规划仿真轨迹

为了更好、更直观地进行对比，将航迹投影到纬度坐标，起点1到终点和起点2到终点的两组航迹仿真结果分别如图5和图6所示，可以较为明显地看出采用IBFO算法规划的航迹路径最短，飞行最平稳。

图5 起点1航迹规划仿真轨迹投影图

图6 起点2航迹规划仿真轨迹投影图

同时，起点1到终点和起点2到终点的两组目标函数随迭代次数变化情况分别如图7和图8所示,可以看出迭代次数为40的时候，目标函数基本收敛，因此更改参数MAX为40，并测试算法运行时间来对比收敛速度。

图7 起点1目标函数变化曲线

图8 起点2目标函数变化曲线

各条航迹的长度、高度的均方差、目标函数最终值以及算法运行时间如表2所示。

表2 航迹规划参数结果

由表2的两组数据可清晰得出，相比采用BFO算法和PSO算法进行航迹规划，采用IBFO算法进行航迹规划的航迹长度最短，高度均方差和目标函数最小，算法运行时间最短，因此采用IBFO算法规划出的航迹是更优的。

改进的细菌觅食优化算法相比基本的细菌觅食优化算法和粒子群算法有以下优点：

(1)算法具有更高的全局搜索能力。粒子群算法全局搜索时容易早熟,而改进的细菌觅食优化算法将固定步长改为自适应步长，加入寻优方向的限制以及嵌入学习因子思想，因此全局搜索能力得到很大的提高。

(2)算法具有更好的稳定性。将固定迁徙概率改为自适应迁徙概率，通过改进加快了收敛速度，提高了算法的稳定性，相比粒子群算法容易陷入局部最优而导致的不易收敛，能更好地进行航迹规划。

4 结束语

本文提出了一种基于改进的细菌觅食优化算法，在无人机航迹规划任务中得到应用，同时利用数字地形高程数据库进行三维环境建模仿真，直观展示出了航迹的轨迹。由仿真结果可得，基于改进的细菌觅食优化算法可以规划出路径更短、飞行更平稳、油耗更小更经济的航迹。

本文对工程实际有引导意义，如在实际工程中实现，会大大优化航迹规划。但算法仍存在一些不足，如嵌入学习因子、引入自适应机制改善启发算法，虽带来精度的提高，但同时会增加算法复杂度。下一步计划融合其他人工启发式算法继续进行算法的改进，并考虑用无人机进行真实的实验验证。