改进人工蜂群算法的无人机航迹规划研究*

徐流沙，吴梅，袁志敏

（1.西北工业大学自动化学院，西安710072；2.陕西飞机工业（集团）有限公司设计研究院，陕西汉中723213）

改进人工蜂群算法的无人机航迹规划研究*

徐流沙1，吴梅1，袁志敏2

（1.西北工业大学自动化学院，西安710072；2.陕西飞机工业（集团）有限公司设计研究院，陕西汉中723213）

如何快速地规划出满足约束条件的飞行航迹，是实现无人机自主飞行的关键。将改进的人工蜂群算法应用于求解无人机航迹规划问题，同时在人工蜂群算法的侦察阶段引入差分进化算法的思想。通过仿真实验并与标准人工蜂群算法比较，结果表明此算法能够有效加快收敛速度，提高最优航迹精度，是解决航迹规划和其他高维复杂函数优化的有效方法。

无人机，航迹规划，人工蜂群算法，差分进化算法

0　引言

无人机（UAV）航迹规划（Path Planning）是无人机任务规划系统的核心之一，它一般指在确定无人机起飞位置、目标位置和飞行途中的目标任务后的一系列优化问题，根据无人机的机动性能，飞行的地理环境及威胁等信息规划出一条满足飞行条件的最优或者次优路径。航迹规划对于提高飞机生存率、增强作战效能具有十分重要的意义。

人工蜂群（Artificial Bee Colony，ABC）算法是一种新兴群体智能优化技术，它基于蜂群的智能采蜜行为及自治、分工和自组织，是由土耳其Erciyes大学Dervis Karaboga［1］在2007年提出。ABC算法结合全局搜索和局部搜索的方法来使蜜蜂在食物源的探索和开采两个方面达到很好的平衡。Karaboga与Basturk［2］通过5个常见基准函数测试得出，ABC算法与遗传算法、进化算法和粒子群算法一样具有良好的优化性能，但是，目前ABC算法作为一种新的随机优化算法，在接近全局最优解时，仍存在着搜索速度变慢、过早收敛、个体的多样性减少，甚至陷入局部最优解等难题。然而，ABC算法因有劳动分工和协作机制，算法更灵活，易与其他技术结合以改进原算法。本文首先介绍适用于ABC算法的航迹表示方法，并在这基础上结合约束条件，构造合理的目标函数，再对ABC算法进行一些改进，并将其应用于无人机航迹规划。

1　问题描述

无论针对何种飞行器，航迹规划问题都包含了一些相同的基本要素：规划空间建模、航迹表示、约束条件解析、目标函数确定、规划算法选取［3］。

1.1规划空间与航迹表示

不考虑地形高度信息，认为无人机都是以同一高度飞行，所以航迹规划在二维欧氏空间中进行搜索。威胁和障碍，如地形高度、气象环境、地方防空火力与雷达部署等，可以用封闭图形表示，如圆、多边形等。对于非圆形不规则威胁区可视作若干圆形威胁区的组合，本文用圆表示威胁和障碍。因此，威胁信息可表示为Nthreat×3的矩阵，每行为（Txi，Tyi，Ri），其中Nthreat为威胁个数，（Txi，Tyi）为第i个威胁的坐标，Ri为威胁半径。当然也可以定义各个威胁源的威胁指数，本文认为威胁指数都相等。

确定起点S，终点G后，航迹规划在S，G之中，规划出一条可行且较优的航迹。用空间位置点序列{S，P1，…，PD，G}表示飞行航迹，P1，…，PD为中间节点，D为定值，各相邻航迹节点用直线段连接。为了计算简单，通过坐标平移与变换［4］，将起点S映射到原点，终点G映射到X轴上，SG等分成D+1段，并在等分点上作垂直于X轴的直线，则P1，…，PD分别在各自垂线上，这样只需要保存P1，…，PD的纵坐标x1，x2，…，xD即可，因此，这一航迹可表示为X=（x1，x2，…，xD），对应着ABC算法中的一个蜜源，如图1所示。

图1　航迹点分布

有个缺点就是，这样规划出来的航迹是横坐标的函数，即不能迂回。不过在实际应用中，为了减少导航误差，也不希望无人机迂回行进。

1.2约束条件

为保证规划结果合理可用，需要考虑飞行器自身的物理限制和使用要求。在二维规划空间主要包括以下几个方面［5］。

1.2.1最小航迹段长度

开始改变飞行姿态前必须保持直飞，它有最短距离的限制，也即最短航迹长度。这一限制取决于飞行器的机动能力和导航要求。如图1所示，只需保证等分间隔大于最小航段长度。

1.2.2最大拐弯角

它限制了生成的航迹只能在小于或等于预先确定的最大拐弯角范围内转弯。该约束条件取决于飞行器的机动性能和飞行任务。例如，在紧密编队飞行中，飞行器应避免剧烈转弯，否则将导致很大的碰撞风险。设Pk为第k个中间节点，则最大拐弯角约束为：

式中ak=PkPk-1，‖ai‖为向量ai的长度，默认P0为S，PD+1为G。

1.2.3最大航迹长度

它限制了航迹的长度必须小于或等于一个预先设置的最大距离Lmax。它取决于飞行器所携带的燃料以及特定任务中到达目标所允许的飞行时间，该约束为：

1.2.4端点方向约束

为了保证顺利完成某些任务，要求飞行器按特定方向区间接近目标。按照图1，固定端点方向，则点PD也就确定，规划维数减少。

1.3目标函数

1.3.1威胁代价

无人机在空间中的点x处受第j个威胁的影响指数主要与无人机和威胁间的距离dxj有关，具体计算可采用如下方式：

式中：Kj为一参数，反映第j个威胁的强度，默认都为1；a＞1，b＞1，将规划空间相对于威胁j划成3个区域，威险区、次安全区、安全区。

这样在表达式中，要计算第i段的航迹的威胁指数需要沿第i段进行积分，为了减少计算量，只计算该段航迹的若干个点的威胁指数的平均值，再乘以该航迹段的长度。则：

式中，Nthreat为已知威胁源的个数，li/6表示第i段航迹的1/6处，如图2所示。

图2　威胁代价计算

1.3.2油耗代价

假设无人机飞行速度为常值，则油耗可简单地认为与航迹长度成正比。

1.3.3转弯代价

综合以上，目标函数为：

式中，X=（x1，x2，…，xD），x1，x2，…，xD分别为点P1，P2，…，PD的纵坐标，且

表示规划区域大小，w1，w2，w3为相应权系数。

航迹规划问题的数学描述即是：

2　规划算法

2.1人工蜂群算法

采蜜的群体智能通过不同角色之间的交流、转换及协作来实现。ABC算法模拟实际蜜蜂采蜜机制处理函数优化问题，将人工蜂群分为3类：采蜜蜂、跟随蜂、侦察蜂。优化问题的解及相应的函数值抽象为蜜源的位置和花蜜的数量。每只采蜜蜂都对应一个蜜源，采蜜蜂采蜜过程则抽象为在当前蜜源附近搜索新蜜源，若优于当前蜜源就将其替换。对于航迹规划，X代表某一蜜源，则J（X）为该蜜源质量。

首先侦察蜂在无先验条件下发现初始蜜源并记忆，之后寻找最优蜜源的过程为：侦察蜂转变成采蜜蜂进行采蜜；跟随蜂根据蜜源信息在某种机制下选取合适的蜜源并转换成采蜜蜂采蜜，得到本次循环的最终标记蜜源，这样反复循环寻找最佳蜜源；但是如果在采蜜过程中，蜜源经若干次搜索不变，相应的采蜜蜂变成侦查蜂，重新搜索新的蜜源。具体步骤如下［7］：

1）初始化ABC参数：蜂群总数NP，最大迭代次数Nmax，蜜源放弃阈值limit；

2）按照式（7）随机产生NP/2个初始蜜源Xi=（xi1，xi2，…，xiD），i=1，2，…，NP/2，rand为［0，1］中的随机数，j=1，2，…，D；

3）当前迭代次数为iter=1；

4）若iter＜Nmax，repeat；

5）采蜜蜂在蜜源附近按式（8）搜索新蜜源；

式中，k为随机生成，且不等于i，φij为［-1，1］间的随机数，控制搜索范围。

6）贪婪准则，根据式（6）比较前后蜜源优劣，若搜索后蜜源优于搜索前，则代替先前蜜源；

7）跟随蜂根据处于蜜源处的采蜜蜂释放的花蜜信息，按轮盘赌方式选择蜜源，并在其附近按式（2）搜索新蜜源；

8）贪婪准则，根据式（6）比较跟随蜂及采蜜蜂搜索的蜜源的质量，若优于则替换；

9）若某些蜜源经limit次循环不变，放弃该蜜源，相应采蜜蜂变成侦查蜂，按式（7）随机产生新蜜源；

2.2算法改进

2.2.1初始蜜源

初始解是算法进行搜索的起点，如果生成的初始群体不够合理，对算法的性能有很大影响。

在ABC算法中，初始群体生成是随机的，为此，有必要对初始群体的生成方法进行改进，改进的目的是使得初始群体个体分布较为均匀，所以采取了小区间生成法：先将第j（j=1，2，…，D）个参数的取值范围分成蜜源总数NP/2个等值小区间，分别记作I1，j，I2，j，…，INP/2，j，再生成一个NP/2×D矩阵E={eij}，其中E的每列为1，2，…，NP/2的随机排列，则第i个蜜源的各个参数分别在小区间Ii，ei1，Ii，ei2，…，Ii，eiD中随机生成。这样生成的初始个体将会均匀地分布在整个解空间上，保证了初始群体含有较丰富的模式，增强了搜索收敛于全局最优点的可能。仿真实验证明，这种方法生成的初始群体性质优良，可加快算法的收敛速度，很好地改善算法的收敛性能。

2.2.2选择机制

ABC算法中，跟随蜂是以轮盘赌的形式选择蜜源，形式如下：

式中，fiti为第i个蜜源的适应值。对于第j只跟随蜂，面对第i个蜜源，如果rand≤Pi，则选择该蜜源，若rand＞Pi则放弃，直到第j只跟随蜂找到属于自己的蜜源。

这是一种基于贪婪策略的选择方式，会使种群多样性降低，从而引起过早收敛和提前停滞的现象。在自由搜索算法中，提出了一个重要概念——灵敏度，通过与信息素（与优化问题的适应度值有关）配合选择区域，理论上可以搜索更多区域，这就在很大程度上避免了陷入局部最优；所搜索区域的信息素必须适应其灵敏度，这就使算法有导向作用，决定了目标函数在搜索空间中的收敛和发散。这种区域选择的方式与跟随蜂选择蜜源的方式是类似的，所以可以考虑将灵敏度与信息素配合的方式代替轮盘赌的方式［8］。步骤如下：

1）计算所有蜜源的适应度值fit；

2）计算第i个蜜源的信息素：

3）随机产生第j个跟随蜂的灵敏度S（j）～U［0，1］；

4）找出配合第j个跟随蜂灵敏度的蜜源：随机找出i，满足nf（i）≥S（j），即灵敏度越高的跟随蜂，越能找到质量更高的蜜源。

2.2.3侦察蜂寻找新的蜜源

在标准ABC算法中，当某一蜜源经过limit次采蜜后，仍未得到质量更好的蜜源，说明陷入局部最优，则会在规划空间随机生成新的蜜源代替该蜜源。这样做对提高全局收敛性的帮助有限，同时因为没有综合现有蜜源信息，使得搜索过于盲目，降低收敛速度。对此，可以引入差分进化法中的变异和交叉操作。

差分进化（Differential Evolution，DE）算法是一种采用浮点矢量编码在连续空间中进行随机搜索的优化算法。DE的原理简单，受控参数少，实施随机、并行、直接的全局搜索，易于理解和实现。算法的基本思想是：对当前种群进行变异和交叉操作，产生另一个新种群；然后利用基于贪婪思想的选择操作对这两个种群进行一对一的选择，从而产生最终的新一代种群。

（1）变异操作

对蜜源Xi=（xi1，xi2，…，xiD）进行变异操作，得到相对应的变异个体Vi=（vi1，vi2，…，viD），即：

式中，Xbest为当前全局最佳蜜源，参数r1，r2∈{1，2，…，NP/2}互异且不等于i，Xbest称为父代基向量；（Xr1-Xr2）称作父代差分向量；F为缩放比因子。虽然有时用随机选择的个体作为父代基向量可能更加合适，但对大多数例子，使用Xbest可以加速收敛。如果使用Xbest时导致早熟收敛，则应考虑使用随机个体［9］。

（2）交叉操作

将Xi与Vi交叉产生子代个体，Ui=（ui1，ui2，…，uiD）为保证第i个蜜源的演化，首先通过随机选择，使得Ui至少有一位由Vi贡献，而对其他位，可利用一个交叉概率因子CR∈［0，1］，决定Ui中哪些位由Xi贡献，哪些位由Vi贡献。如果rand＜CR，则该位由Vi贡献，即CR越大，Vi贡献越多。当CR=1时，Ui=Vi，即如下：

式中，rand（j）为［0，1］之间的均匀分布随机数；rand（i）为{1，2，…，D}之间的随机量。

最后，将Ui替代Xi成为第i个蜜源进入下一次循环，并更新相应蜜源质量信息。

在文献［4］中，作者在ABC算法的最后阶段，利用混沌算子对所有个体进行操作得到一序列新个体，再从中选取最优进入下一次迭代。本文也可以基于差分进化算法，采用同样的方式进行迭代［10］。经过实验，这样做可以减少迭代次数，并有可能找到更优解。可是对于航迹规划，目标函数是关于航迹的复杂函数，规划程序运行时间主要花费在航迹代价的计算上，这种方法有可能降低规划效率。

3　仿真实验

在仿真实验中，参数选取如下：

初始条件：起点设为（0，0），终点为（0，310），航迹点数D=30，x1min，x2min，…，xDmin=-150，x1max，x2max，…，xDmax=150，威胁源如下页图3，图4同心圆所示；最小航迹段长度为10，最大拐弯角为π/3，不限最大航迹长度；

ABC控制参数为：NP=60，Nmax=1 000，limit=60，F=0.5，CR=0.8。

也即算法终止条件为迭代次Nmax=1 000，运行过程中输出每一次迭代的最优航迹代价，迭代结束再用图形输出最优航迹，如图3，图4所示。本文同时对标准ABC算法和改进ABC算法进行航迹规划，观察两种算法在何时趋于收敛，并比较两者航迹的优劣。

图3　标准ABC算法

图4改进ABC算法

图3是标准ABC算法所生成的航迹，由图可以看出，算法陷入了局部最优，经多次仿真实验，算法平均大概在600次迭代收敛，平均航迹代价为315。

图4是改进ABC算法所生成的航迹，较之图3有了很大改善，航迹变得平滑且代价大幅减少，收敛速度也加快许多，平均迭代300次左右收敛，平均航迹代价为265。可以看出，改进的ABC算法能够有效地加快收敛速度和收敛精度。

4　结束语

本文用ABC算法求解无人机航迹规划这一多约束、难建模的复杂优化问题。针对ABC算法的不足，提出了几项改进，并在MATLAB环境下对所提方法进行仿真实验，结果表明，所作的改进有效地提高了收敛精度和减少规划时间，同时也验证了ABC算法在航迹规划问题上的可行性。文中假设威胁源已知且固定不变，如果威胁源发生了动态变化，则需要进行实时的动态航迹规划，下一步将对此进行研究。

［1］Karaboga D，Basturk B.A Powerful and Efficient Algorithm for Numerical Function Optimization:Artificial Bee Colony（ABC）algorithm［J］.Journal of Global Optimization，2007，39（3）:459-71.

［2］Karaboga D，Basturk B.On the Performance of Artificial Bee Colony（ABC）Algorithm［J］.Applied Soft Computing，2008，8（1）:687-97.

［3］王维平，刘娟.无人飞行器航迹规划方法综述［J］.飞行力学，2010，28（002）:6-10.

［4］Xu C，Duan H，Liu F.Chaotic Artificial Bee Colony Approach to Uninhabited Combat Air Vehicle（UCAV）Path Planning［J］.Aerospace Science and Technology，2010，14（8）:535-41.

［5］Szczerba R J，Galkowski P，Glicktein I，et al.Robust Algorithm for Real-time Route Planning［J］.Aerospace and Electron ic Systems，IEEE Transactions on，2000，36（3）: 869-78.

［6］李少华，魏海光，周成平，等.一种海上无人飞行器的快速航迹规划方法［J］.四川兵工学报，2011，32（12）：73-76.

［7］胡中华.基于智能优化算法的无人机航迹规划若干关键技术研究［D］.南京：南京航空航天大学，2011.

［8］毕晓君，王艳娇.改进人工蜂群算法［J］.哈尔滨工程大学学报，2012，33（1）:117-23.

［9］谢晓锋，张文俊，张国瑞，等.差异演化的实验研究［J］.控制与决策，2004，19（1）:49-52.

［10］高卫峰，刘三阳，姜飞，等.混合人工蜂群算法［J］.系统工程与电子技术，2011，33（5）:1167-70.

Research on Path Planning of UAV Based on Improved ABC Algorithm

XU Liu-sha1，WU Mei1，Yuan Zhi-min2
（1.College of Automation，Northwestern Polytechnical University，Xi’an 710072，China；
2.Research Institute，Shaanxi Aircraft Industry（Group）Co.Ltd，Hanzhong 723213，China）

It is critical for autonomous planning of Unmanned Aerial Vehicles（UAV）that how to plan the flight path quickly which fulfills some constraints.This paper applies improved Artificial Bee Colony（ABC）algorithm to solve the problem of UAV path planning and introduce the idea of Differential Evolution（DE）algorithm in the scout bee phase of ABC algorithm.Compared with the standard ABC algorithm，it shows that this algorithm can effectively accelerate the convergence speed and improve the accuracy of the optimal path through the simulation experiments，which proves the feasibility，effectiveness and robustness of this method on the path planning and other high-dimensional complex function optimization.

unmanned aerial vehicles，path planning，artificial bee colony algorithm，differential evolution

V279

A

1002-0640（2015）01-0062-05

2013-11-13

：2014-02-17

中国航空科学基金资助项目（20100753007）

徐流沙（1988-），男，湖北通山人，硕士研究生。研究方向：航迹规划。