复合形引导蜂群寻优的无人机航迹多目标规划

2020-04-28裴红蕾

机械设计与制造 2020年4期

刘刚，裴红蕾

（无锡工艺职业技术学院，江苏宜兴 214200）

1 引言

无人机在军用和民用领域均取得广泛应用，如植保无人机、救援无人机和空中侦查无人机等。植无人机在空中作业时必须躲避障碍物，同时为了达到经济性必须规划出最短路径；军事无人机在执行任务时也必须躲避敌人侦查和打击区域，因此，无人机航迹规划对无人机安全性和经济性意义重大。

无人机航迹规划分为二维规划和三维规划，无人机在定值高度层飞行时为二维航迹，研究对象为无人机在二维空间的航迹规划。基于群智能算法的无人机航迹规划是当前研究的热点[1]，包括遗传算法、人工蜂群算法、粒子群算法、狼群算法、混沌捕食生物地理学算法等。文献[2]将平衡演化策略引入到人工蜂群算法中，平衡了全局开发和局部开发能力，提高了航迹规划速度；文献[3]使用复合形法引导狼群搜索，提高了航迹解算速度；文献[4]使用混沌捕食生物地理学算法规划无人机航迹，此方法时效性更高；文献[5]提出了改进量子遗传算法的无人机航迹规划方法，仿真结果表明此方法规划效率高、稳定性好；文献[6]提出了基于改进智能单粒子优化算法的无人机三维航迹规划，与局部学习粒子群算法相比具有更强的寻优能力。基于智能算法的无人机航迹规划主要问题在于算法原理或算法结构不合理，导致难以搜寻到最优航迹，或航迹不符合航迹要求。

基于人工蜂群算法，研究了无人机的二维航迹规划问题。在传统人工蜂群算法基础上，从初始化方法、蜜源搜索方法、蜜源选择方法、复合形引导寻优等四个方面进行了改进，达到提高航迹规划的精度、速度和稳定性的目的。

2 二维航迹规划问题描述

2.1 二维航迹规划环境建模

设定无人机在定值高度层飞行，雷达、防空导弹、防空火炮等威胁简化为圆模型，如图1所示。圆模型参数包括威胁中心、威胁半径、威胁等级等三个参数。在此需要强调的是，威胁半径为雷达、导弹的威胁半径与无人机外接圆半径之和，这样可以将无人机简化为一个质心。

图1 无人机航迹规划环境模型Fig.1 UAV Route Planning Environment Model

无人机航迹规划的二维环境由给定起始点S、目标定T及若干威胁区域组成，如图1所示。航迹规划描述为在S与T之间规划出一条能够避开威胁区域且长度最短的航迹。为了简化计算，将二维规划问题简化为一维规划问题，建立新坐标系O′X′Y′，坐标原点O′与S点重合，以S→T方向为X′轴正向，Y′轴过O′点与X′垂直。在线段ST间等间距地插入个点，将ST等分为D+1段，在每个等分点上做ST的垂线Li，航迹规划问题就转化为在各垂线Li上确定纵坐标pi，将点pi进行光滑连接就得到了无人机航迹。

记某点在坐标系 OXY 中为（x，y），在坐标系 O′X′Y′中对应为（x′，y′），则两者转换关系为：

式中：θ—X轴与X′轴的夹角；（xs，ys）、（xT，yT）—起点S、目标点T在坐标系OXY中的坐标。

2.2 航迹规划约束条件

为提高航迹规划效率和可行性，从无人机运动规律和硬件性能的角度出发，对航迹进行以下几个方面的约束：

（1）航迹长度约束。无人机执行任务时携带燃料有限，油耗与航迹长度有很强的正相关关系，因此设置一个航迹长度上限Lmax，航迹长度约束公式为：

（2）转向角约束。无人机由子航迹pk-1pk运动到pkpk+1时要经历转弯过程，如图2所示。规定转弯角为ζ。为了保证无人机的飞行安全，必须设定转向角阈值ζmax，则转向角约束可描述为：

图2 子航迹圆滑处理Fig.2 Smooth Processing of Sub Route

转弯点处的航迹需要做平滑处理，做航迹pk-1pk和pkpk+1的共切圆，航迹点pk-1和pk+1之间使用圆弧代替折线，实现航迹的平滑处理。

2.3 航迹规划目标函数

无人机航迹规划目标函数设置了三个方面的代价函数，分别为安全代价、长度代价、转向代价。

（1）安全代价函数。威胁区域是无人机飞行时时刻关注的要素，记无人机到第j个威胁中心距离为dxj，第j个威胁半径为Rj，则无人机受第j个威胁的影响指数为：

式中：a，b＞1—威胁补偿系数；Kj—第j个威胁物的威胁强度等级参数。当 dxj≤Rj时定义为高度危险区域，当 Rj＜dxj＜bRj时定义为一般危险区域，当dxj＞bRj时定义为安全区域。

无人机航迹由D+1个子航迹组成，在此给出第i个子航迹受所有威胁的代价函数。取第i个子航迹9个样本点，分别为1/10～9/10位置节点处受到威胁指数平均数，如图3所示。作为此航迹的平均威胁指数，那么第i个子航迹受到的威胁定义为威胁平均数与长度之积。则第i个子航迹安全代价函数为：

式中：li—第i个子航迹长度；Ni—无人机所受威胁数量。

图3 子航迹威胁采样点Fig.3 Threat Sampling Point of Sub Route

（2）长度代价。无人机航迹由D+1段子航迹组成，虽然在转弯处进行了圆弧平滑处理，但是依然可以使用直线段近似计算，则第个子航迹的长度代价函数为：

（3）转向代价。转向会增加无人机的飞行时间和油耗，在一定程度上也会减少无人机使用寿命，因此转弯次数越少越好，转弯半径越大越好。无人机的转向代价函数为：

其中，转弯角ζi的定义，如图2所示。

综合安全代价函数、长度代价函数、转向代价函数，得到无人机航迹规划的目标函数为：

式中：P=｛p1，p2，L，pD｝—无人机航迹；k1、k2、k3—长度代价因子、威胁代价因子、转向代价因子，通过调节k1、k2、k3可以实现优化中心的调节。

3 传统人工蜂群算法

3.1 算法原理

人工蜂群算法是受蜂群群体采蜜时分工协作启发而提出的，算法通过以下5个步骤实现[7-8]：

（1）初始化。记种群数量为NB，初始时种群中所有个体均为侦查蜂，被随机分配到各蜜源位置，即：

式中：i=1，2，L，NB—蜜蜂个体编号 j=1，2，L；D—解的维度—第 j个位置点的上下界；rand（0，1）—（0，1）间的随机数。

（2）蜜源评价。依据航迹规划的目标函数构造蜜源评价函数，从而对蜜源优劣做出评价。蜜源评价函数为：

式中：fi—第i只蜜蜂的适应度值，这里fi=Ji表示第i只蜜蜂的目标函数。使用蜜源评价函数对蜂群所有个体的蜜源进行评价，蜜源较优的侦查蜂转化为雇佣蜂，蜜源靠后的侦查蜂转化为观察蜂。

（3）雇佣蜂蜜源搜索。雇佣蜂在当前位置附近进行蜜源搜索，当新蜜源适应度优于原蜜源时则选择新蜜源，否则继续进行搜索，雇佣蜂通过这种贪婪规则不断优化蜜源，雇佣蜂的搜索位置更新方法为：

（4）观察蜂选择与邻域搜索。观察蜂依据适应度值计算选择各蜜源的概率，为：

式中：pi—观察蜂选择雇佣蜂的概率；—雇佣蜂数量。

由式（12）可知，依据各蜜源适应度值确定选择概率，可以保证较优蜜源更大的选择概率，确保更优蜜源附近的细致搜索。观察蜂选择雇佣蜂后与雇佣蜂一起进行邻域搜索，观察蜂的位置更新方法和蜜源选择方法与雇佣蜂一致。

（5）侦查蜂的蜜源搜索。若某只蜜蜂在一个蜜源邻域连续搜索次数达到一个上限且适应度值没有明显提高，则此蜜蜂放弃当前蜜源，转化为侦查蜂，在搜索区域内进行随机搜索，其位置更新方式为：

式中：j=1，2，L；D—解的维度。

3.2 算法流程图

根据3.1节的算法原理，给出算法流程图，如图4所示。

图4 人工蜂群算法流程图Fig.4 Flow Chart of Artificial Bee Swarm Algorithm

4 复合形引导蜂群算法及流程

4.1 复合形引导蜂群算法

为了提高人工蜂群算法的寻优能力和寻优速度，从以下4个方面对算法进行改进。

（1）改进蜜源初始化。蜜源初始化的结果是生成一个NB×D的矩阵，每个行相量xi=（xi1，xi2，L xiD）表示一个蜜源位置。如果使用式（9）所示的传统初始化方法，前后航迹点之间没有任何关联，导致初始化的大部分航迹不符合转向要求，也就意味着航迹不可行，不但浪费了搜索时间，还占用了计算资源。为了解决这一问题，如图5所示。依据此图推导出蜜源初始化方法为：

式中：（2xi（j-1）-xi（j-2））—图5中点A的纵坐标；step—由转向角阈值确定的步长。

图5 蜜源初始化方法Fig.5 Honey Source Initialization Method

（2）改进雇佣蜂和观察蜂的蜜源搜索方法。传统算法中，雇佣蜂和观察蜂采用随机位置更新方式搜索蜜源，当前最优蜜源没有起到任何“榜样作用”。为了充分发挥较优蜜源在种群中的优势，提出随机搜索与最优蜜源引导相结合的位置更新方式，设定概率值P1，在（0，1）内产生随机数ϑ，若ϑ＜P1则使用最优蜜源引导的位置更新方法，若ϑ≥P1则使用式（11）给出的位置更新方法。最优蜜源引导的位置更新方法为：

式中：xbext—蜂群搜索到的最优蜜源。

（3）改进蜜源选择方法。传统算法中，依据蜜源适应度值大小决定是否接受蜜源，这种选择方式过早地将有潜力的蜜源淘汰掉，使算法前期收敛较快，算法后期收敛较慢。为了解决这一问题，提出了蜜源选择的Metropolis准则[9]，蜜蜂由当前蜜源转o向新蜜源n的转移概率为：

式中：p（0/n）—由当前蜜源o向新蜜源n转移的概率，下降函数T（t）=T（t-1）·σ；σ—退火系数，取 σ=0.7。

分析式（16）可知，当新蜜源适应度小于原蜜源时，仍有一定的转移概率，有利于保留具有潜力的蜜源；在算法初期，退火温度T（t）较高，适应度差的蜜源转移概率较大，保留有潜力蜜源的概率也大，有利于算法跳出局部最优；算法后期退火温度逐渐减小，算法更加“关注”优质蜜源，更多蜜蜂在优质蜜源邻域内细致搜索，提高寻优精度。

（4）复合形法引导蜂群寻优。为了提高传统算法收敛速度，提出了复合形法引导的人工蜂群算法，复合形法通过不断的反射、延伸和收缩等操作引导蜂群向最优蜜源靠近[10]，在算法迭代一次结束后，选取u个优秀蜜源，按适应度由大到小排序（x1，x2，L，xu），则复合形法对蜂群引导步骤为：

（1）计算复合形形心xc=1/u·

（2）计算反射点 xr=xc+α（xc-xu），式中 α=1.3 为反射系数，若 xr优于xu，则使用xr替换xu，否则转至 Step4；

（3）计算延伸点 xe=xr+β（xr-xc），式中 β=0.6 为延伸系数，若 xe优于 xu，则使用 xe替换 xu，否则转至（4）；

（4）计算收缩点 xs=xu+χ（xc-xu），式中 χ=0.7 为收缩系数，若 xs优于xu，则使用xs替换xu，否则继续；

（5）判断是否达到最大迭代次数，若是则结束，否则转至（1）。

4.2 复合形引导人工蜂群算法流程

根据4.1节对传统人工蜂群算法原理的改进，给出改进人工蜂群算法步骤为：（1）初始化改进算法参数：种群规模NB、单蜜源最大停留次数Limit、最大迭代次数MaxCycle、概率值P1、复合形法最大引导次数MaxGuide，设置trial（i）=0，iter=0；（2）按照式（14）进行种群初始化，依据适应度值将蜜蜂分为雇佣蜂和观察蜂；（3）雇佣蜂进行邻域搜索，使用Metropolis准则判断是否接受新蜜源，而后将蜜源信息传递给观察蜂；（4）观察蜂根据各蜜源适应度值确定选择概率，而后与雇佣蜂一起进行邻域搜索，使用Metropolis准则判断是否接受新蜜源，若蜜源更新则trial（i）=0，若不更新则，trial（i）=trial（i）+1；（5）判断trial（i）＞Limit是否成立，若成立则第i只蜜蜂转化为侦查蜂，使用式（13）进行随机搜索，若不成立则转至下一步；（6）从寻优结果中选出适应度值最大的前u个蜜源，使用复合形法引导寻优次；（7）输出全局最优蜜源，iter=iter+1，判断 iter＞MaxCycle 是否成立，若成立则算法结束，否则转至（3）。

5 仿真验证

为了验证复合形引导人工蜂群算法和建立模型在无人机规划中的有效性，使用Matlab R2014a软件进行仿真验证。无人机工作在（100×100）的区域内，航迹点个数为21，环境中的威胁区域，如表1所示。算法主要参数设置为：最大迭代次数MaxCycle=500、种群规模NB=60、单蜜源最大停留次数Limit=5、复合形使用蜜源数量u=10。

表1 各威胁参数Tab.1 Parameters of Every Threaten

为了形成对比，分别使用改进人工蜂群算法、基于混沌扰动的改进人工蜂群算法[11]、传统人工蜂群算法进行航迹规划，各算法进行仿真20次，每种算法规划的最优航迹，如图6所示。计算各算法在相同迭代次数时目标函数平均值，结果如图7所示。由图6可知，三种算法规划的航迹都能够躲避威胁，顺利完成任务。但是改进人工蜂群算法规划的航迹最为平滑、长度最短且转向角最小。由图7可知，改进人工蜂群算法迭代50次时基本收敛，收敛速度最快且寻优结果也最好。为了更加有力地比较三种算法的性能，统计三种算法的寻优结果，如表2所示。表2中算法耗时为20次寻优的平均耗时，收敛迭代次数为算法基本收敛时的迭代次数，寻优耗时为20次仿真寻找到最优解的平均耗时，收敛值均值与标准差为20次仿真目标函数值的均值与标准差。分析表2可知，提出的改进人工蜂群算法单次循环的耗时略小于另外两种算法，但是改进算法在迭代50次时就收敛，较传统人工蜂群算法与混沌扰动人工蜂群算法分别减少了4倍、6倍；改进算法的寻优耗时为0.82s，比传统人工蜂群算法与混沌扰动人工蜂群算法降低了约一个数量级；改进算法目标函数值均值与标准差均小于传统人工蜂群算法与混沌扰动人工蜂群算法，说明改进算法规划的航迹更优、稳定性更强。