基于群体智能算法的无人机协同搜索

蔺文轩， 谢文俊， 张 鹏， 纪良杰

(空军工程大学，西安 710000)

0 引言

无人机参与作战所执行的任务具有高危险性和复杂性的特点，且单体无人机载荷小、执行任务的鲁棒性差，故无人机集群作战成为无人机参与战争的主要作战形式[1]。在无人机集群作战过程中，如何将作战任务适当地分配给每架无人机是保证无人机集群高效、有序完成作战任务的必要保证，所以无人机集群作战任务分配是目前研究的重点和热点。

无人机集群作战任务分配即根据作战环境的各种约束条件为无人机分配任务目标的方案。目前针对无人机集群作战任务分配问题的解决方法主要为建立模型并根据模型寻优求解。传统的多无人机作战任务分配模型有多车辆路由模型(MVRP)[2]、多旅行商模型(MTSP)[3]、混合线性整数规划模型(MILP)[4]和协同任务分配模型(CMTAP)[5]等。智能优化算法在解决任务分配问题时主要通过平衡最短求解时间和最优分配方案进行求解，算法流程简单，且求解质量较高，是解决任务分配问题常用方法之一。粒子群优化(PSO)算法凭借其算法简单、易于实现的特点广泛应用于寻优问题求解，但PSO算法主要适用于连续性问题，在使用PSO算法求解离散型问题时，需要对问题进行连续化处理，在完成寻优求解后将结果离散化，即可完成离散型问题求解[6]。文献[7]以MILP为基础，根据时间、距离、角度等因素构造了目标函数，对PSO算法改进后进行寻优求解，加快了寻优速度，提高了多无人机任务分配的效率，但PSO算法本身存在易陷入局部最优解的缺陷，在解决离散型问题时尤为明显。文献[8]针对离散型寻优问题，借鉴遗传算法中的交叉变异机制，增加了粒子多样性，提高了算法跳出局部最优的能力。天牛须搜索(BAS)算法是一种新提出的寻优算法，具有强大的局部寻优能力。将天牛须搜索算法与粒子群优化算法相融合，可以规避粒子群优化算法的固有缺陷，适用于求解无人机集群任务分配问题。

1 算法原理

1.1 粒子群优化算法

粒子群优化算法通过模拟鸟类运动时个体信息共享的方式实现对目标问题的求解。算法的主要内容为：假设在多维搜索空间中，存在数量为N的粒子群，每个粒子的位置及速度分别表示为Xi={Xi1,Xi2,…,Xin},Vi={Vi1,Vi2,…,Vin}，每一个粒子的最优解表示为Pi={Pi1,Pi2,…,Pin}，n为迭代次数，全局最优解表示为Pg={Pg1,Pg2,…,Pgn},粒子群中的每个粒子根据Pi和Pg更新自己的位置和速度，具体方法为

(1)

(2)

其中:t表示当前迭代次数；Pid表示当前更新粒子最优解;Pgd表示当前全局最优解；ω为权重系数；k1,k2为学习因子，主要控制粒子根据现有信息进行判断，对自身位置进行调整，向潜在最优位置移动；r1,r2为[0,1]上的随机数。

1.2 天牛须搜索算法

(3)

式中，n表示优化参数的维度。

天牛最优位置的更新规则为

(4)

式中,f(x)表示天牛在位置x的适应度值。天牛根据两须探测的适应度差值确定下一步的寻优方向和位置，位置Xt的更新规则为

(5)

式中，σt表示t时刻天牛移动的步长。

天牛两须的位置更新算式为

(6)

每次移动步长和天牛两须之间的距离更新算式为

(7)

式中:φσ,φd分别表示步长和搜索距离的衰减系数;D为距离常数。天牛须搜索算法的流程如图1所示。

图1 天牛须搜索算法流程图

根据算法原理可以看出天牛须搜索算法具有计算过程简单、自主决策性强、灵活性高的特点，满足求解多目标优化的算法需求，即计算快、效果好、稳定性高等。但是在求解无人机集群任务分配问题时仍有如下缺陷。

1) 天牛在寻优的过程中，每一次的位置更新不论结果是否更优都会导致搜索步长的衰减，若天牛初始位置距离最优位置较远，容易导致天牛陷入局部最优点。改进步长更新方式，引入步长最小值σ0，避免步长无限制衰减而陷入局部最优。步长更新算式为

σt=φσ(σt-1-σ0)+σ0

。

(8)

2) 针对多目标优化问题算法初始的衰减步长难以取得合适值、参数调节较为复杂的情况，可以将算式进行简化，共用一个参数c，方便参数调节。改进后搜索步长和两须间距离的算式为

(9)

3) 有实验表明[10],天牛须搜索算法在处理寻优问题时对于约束边界附近的寻优效果较差，针对此问题，引入二阶天牛搜索，在位置更新中加入速度项，即

Xt=Xt-1+vt

(10)

(11)

式中,ω0,ω1表示上个迭代过程中速度和两须适应度差的权重系数。

为防止速度过大对求解产生影响，设定最大速度vmax=ω0·σt，速度的取值约束为

(12)

2 算法改进

2.1 基于天牛须搜索的粒子群优化算法

粒子群优化(PSO)算法作为一种常用的寻优方法，在解决无人机集群任务分配问题时存在搜索精度低、易陷入局部极值的缺点。为弥补算法缺陷，在PSO算法中引入天牛须搜索算法的思想，形成一种基于天牛须搜索的粒子群优化(BSO)算法[11],该算法结合两种算法的优势，克服了PSO算法早熟的缺陷，提高了寻优速度和精度。算法的主要描述如下。

将PSO算法中每个粒子看作天牛，天牛的位置更新算式为

(13)

其速度更新项借鉴PSO算法思想

(14)

步长更新项借鉴BAS算法思想

(15)

并将天牛左、右须位置更新算式进行修正

(16)

以PSO算法中的速度向量代替原始算法的随机方向，步长更新和搜索距离更新算式为

(17)

BSO算法以BAS算法为基础，在天牛个体之间引入信息交互机制，同时借鉴PSO算法中粒子速度对位置更新的影响，使其在每一次的迭代寻优中可以遍历更多的区域，提高了算法的寻优速度。

2.2 天牛须粒子群混合算法

BSO算法能够很好地避免陷入局部最优的问题，但是在解决无人机集群任务分配等离散型问题时的收敛速度较慢，为了加快算法的收敛速度，提出一种天牛须粒子群混合(BSO-BAS)算法，算法分为内外两部分：外层BSO算法负责全局寻优，内层BAS算法负责局部寻优。主要思想为：在一次迭代过程中，先使用BSO算法求解全局最优解，在全局最优解的邻域内使用BAS算法再进行局部最优值的求解，如果发现适应度更高的局部最优值则替换掉原全局最优值，可以加快算法的寻优速度并提高效率，同时增强算法求解问题的实时性。算法流程如图2、图3所示。

图2 内层BAS流程图

图3 外层BSO流程图

为避免算法陷入局部最优解，在内层循环中加入对非最优解的保留原则，设置适应度差值Δf

Δf=f(xk+1)-f(xk)

(18)

式中：xk+1为BAS算法寻优一次后天牛的位置；xk为外层BSO算法给定的全局最优位置。若Δf<0，用xk+1代替xk作为全局最优位置，否则引入随机概率P，即

(19)

若P>0，则接受xk+1，否则不更新全局最优解。

3 无人机集群任务分配模型

设战场环境中存在数量为NU的己方无人机和数量为NT的敌方目标，计划使用无人机对敌方目标执行侦察或打击任务。无人机集合记为U={U1,U2,…,UNU}，无人机Ui在t时刻的位置坐标记为(xi(t),yi(t))；敌方目标集合记为T={T1,T2,…,TNT}，目标Tj的位置坐标记为(xj,yj)；将任务分配过程划分为NS个阶段，用s={1,2,…,NS}表示。使用决策变量xijs来表示无人机Ui在各任务分配阶段对任务Tj的执行情况，其定义为

(20)

无人机集群执行任务的总收益用函数J表示

ω3·PS,i j-ω4·Li j)xijs

(21)

式中:PE,i j表示无人机Ui对目标Tj执行任务的能力；Vj表示目标Tj的价值；PS,i j表示Ui对Tj执行任务后的生存概率；Li j表示Ui对Tj执行任务时的飞行距离;ω2,ω3,ω4为权重系数。

无人机受自身能力约束，执行任务所需消耗不能超过自身最大能力载荷，即

(22)

每一个任务分配阶段都有一架无人机去执行一个任务，即

(23)

4 实验仿真与分析

不同类型的无人机对不同目标执行任务的能力和代价有所差异，为验证所提出算法的可行性和有效性，假设在10 km×10 km的战场环境中存在3架不同类型的己方无人机与7个需执行侦察或打击任务的敌方目标。无人机与敌方目标的位置坐标如表1所示，不同无人机对各目标执行任务的能力和执行任务后的生存概率分别如表2和表3所示。

表1 无人机与目标位置坐标

表2 无人机对各目标执行任务的能力与目标价值

表3 无人机对目标执行任务后的生存概率

在实验仿真中，寻优问题的维数由敌方目标数量确定，执行某一任务的无人机序号由天牛位置确定，对天牛位置通过进一法向上取整。根据战场环境初始化仿真环境大小为10 km×10 km，无人机数量NU=3，敌方目标数量NT=7，算法种群大小为10，最大迭代次数为100，权重系数ω2,ω3,ω4分别为0.2,0.4和0.4。

分别使用第1章中4种算法对无人机集群任务分配问题进行求解，将任务分配给无人机的最优解Xui=[3,2,1,1,2,2,3]，各无人机执行任务最佳的先后顺序Xoi=[1,1,1,2,2,3,2]，即任务分配方案为：U1执行任务T3和T4，执行顺序为T3→T4；U2执行任务T2，T5和T6，执行顺序为T2→T5→T6；U3执行任务T1和T7，执行顺序为T1→T7。任务分配的最大收益为Jmax=0.821。4种算法的任务分配收益变化如图4所示。

图4 4种算法任务分配收益变化

通过实验仿真可以看出，BSO-BAS算法能在较少的迭代次数内求解得到最优的分配方案，没有陷入局部最优解，任务分配收益明显高于其他3种算法。为验证所提出算法的稳定性，对上述实验进行20次重复仿真，仿真结果如表4和图5所示。

表4 仿真20次各算法结果对比

图5 4种算法20次仿真寻优结果

通过20次仿真的结果可以看出，本文提出的BSO-BAS算法相对于其他3种算法稳定性更高，寻优稳定性达90%，且平均收益值与PSO算法相比提高了19.01%，更适用于无人机集群任务分配问题求解。

5 总结

本文设计了一种天牛须粒子群混合(BSO-BAS)算法，增强了天牛的寻优能力，避免其陷入局部极值，提高了搜索效率和算法的实时性，弥补了PSO算法和BAS算法的缺陷。通过实验仿真验证了该算法在解决无人机协同搜索任务分配问题时具有稳定性良好、求解速度更快、精度更高等特点，具有一定的理论和实践意义。