1 引言
随着无人机的快速发展，因其具有低成本、低操作员伤亡等优势，被应用于物流、农业、搜救、军事等多个领域，尤其在军事领域应用更为广泛。为了能够在复杂的战场环境下更高效的完成任务，操作员需要在开展无人机行动之前进行任务分配。
本文中主要对多无人机任务进行分配，在满足无人机性能约束及战场信息的前提下完成对敌方目标的侦察任务，尽可能的取得最大的任务总收益。为贴合战场实际，本文中使用随任务执行序列变化的威胁概率和目标收益代替固定威胁概率和目标收益让任务模型更加真实。
目前，众多学者就任务分配问题已经取得了大量的研究成果。文献[1]使用蚁群算法对任务链进行子集划分，提高了解决医疗资源分配问题的效率。文献[2]在蜂群算法的基础上加入逆向、交叉和变异算子，让其更适合求解火场救援问题。文献[3]通过在粒子群算法中引入死锁检查和修复机制，良好的解决了任务分配中的“死锁”现象。文献[4]细化了遗传算法中交叉变异概率的公式，解决了仓储系统的调度问题。文献[5]在细菌觅食算法中加入动态自适应调节游动参数，提高了算法的收敛能力；文献[6]对传统的合同网算法进行流程优化，提升了算法的分配效率。布谷鸟算法作为一种引入了生物进化论的群智能算法的新型元启发式搜索算法，因其具有参数少、鲁棒性强、通用性好等优点被广泛用于优化模型的求解。文献[7]提出一种结合单纯形的布谷鸟算法增加了解的精度，并在其中融合了粒子群思想增加了局部寻优能力，但过于追求精度使得求解过程消耗了大量时间；文献[8]通过交替及变异的操作改良了布谷鸟算法的早熟问题，但是交替变异操作让算法的随机性增大，导致算法收敛速度下降；文献[9]提出自适应选取交叉操作算子的布谷鸟搜索算法，优化了算法的寻优精度，但步长自适应因子在前期搜索中启动速度缓慢；文献[10]通过对鸟巢位置进行正态随机分布扰动，提高了种群的多样性，正态扰动半径参数δ对寻优搜索结果起到了重要作用，但选取合适的参数较为困难。
针对布谷鸟算法在搜索寻优过程中存在求解速度慢、容易陷入局部最优等不足，本文中引入高斯递减的自适应步长因子加快算法搜索速度，改善算法求解速度慢的问题，同时引入模拟退火机制，增加算法全局搜索能力，避免陷入局部最优解。
2 多无人机任务分配问题
2.1 问题描述
我方通过情报获取到敌方区域的n个重要目标的位置信息、目标价值以及目标威胁等基本信息，为进一步掌握敌方目标的详细信息，我方需要派出无人机对该区域中重要目标进行侦察，我方有m架侦察无人机，无人机均从基地起飞，有序完成对目标的侦察任务使得完成任务效益最大化。
该问题可描述为：无人机集合为UAVi={V1,V2,V3,…,Vm}，无人机位置集合为PVi={PV1,PV2,…,PVm}，侦察目标集合为Tageti={T1,T2,T3,…,Tn}，侦察目标位置集合为PTi={PT1,PT2,…,PTn}，无人机的价值Worthi={WU1,WU2,WU3,…,WUm}，无人机完成侦察任务的概率为Ci={C1,C2,C3,…,Cm}，无人机任务载荷上限Li={L1,L2,L3,…,Lm}，目标的价值Valuei={VT1,VT2,VT3,…,VTn}，目标的威胁系数Threateni={Th1,Th2,Th3,…,Thn},目标的威胁范围的半径为Ri={R1,R2,R3,…,Rn}。
2.2 目标函数
为使多无人机执行侦察任务效益最大化，本文中需要综合考虑威胁代价、航程代价和任务目标收益三者得到最大总收益。
威胁代价主要指侦察无人机在执行任务期间，任务目标(需侦察的地面目标)的防御力量对侦察无人机进行攻击或电磁干扰导致无人机损毁的代价。考虑到实际战场情况，当无人机开始执行任务时，任务目标就会有所警觉，后续的任务目标将在自身原本的防御基础上加强防御力量的部署。如果无人机多分配任务序列为:T1→T2→…→Tk,则第k个目标的威胁概率为：
即无人机i侦察第k个目标的代价为
所以无人机i在连续执行K项任务的威胁代价为：
(1)
航程代价考虑到无人机与目标的距离远大于无人机的最小转弯半径，因此采用直线度量。
(2)
式中: dmax指无人机执行侦察任务的最远距离，Disij指无人机i到目标j的距离。
任务目标收益指无人机完成侦察任务所获得的收益，考虑到实际战场情况，当无人机开始执行任务时，任务目标就会有所警觉，后续的任务目标将对自身重要目标进行遮挡和转移，造成侦察到的任务目标信息减少，降低任务目益，如果无人机多分配任务序列为:T1→T2→…→TK,则第k个目标的实际目标收益为：
则无人机i侦察目标k的收益为
所以无人机i连续完成k项任务目标的收益为：
(3)
总收益适应度函数：
(4)
(5)
式(5)中wi∈(0,1)为权重系数，
2.3 约束条件
(6)
(7)
式(6)表示为所有任务目标都完成；式(7)表示为每一架无人机执行的任务数目不得超过无人机本身的任务载荷数目约束。
3 改进布谷鸟算法
3.1 经典布谷鸟搜索算法
布谷鸟算法(cuckoo search，CS)[11-12]是借鉴布谷鸟寻找鸟窝位置找产卵的行为而提出的一种优化算法。
布谷鸟既不会做巢也不会育雏，它在产卵前会在其他鸟类(宿主鸟)离开鸟巢时，把宿主鸟的卵推出宿主鸟巢，将自己的蛋产在宿主的鸟巢里，让宿主鸟喂养布谷鸟幼崽。而靠宿主鸟养大的幼年布谷鸟，也存在将宿主鸟幼鸟推出鸟巢的习惯，并且会模仿行为来降低被宿主鸟发现的概率。
假设布谷鸟搜索算法满足下列3项理想化的条件：
① 布谷鸟每次随机性的选择合适的鸟巢产下一枚卵；
② 在随机选择的一组鸟窝中，最好的鸟窝将会被保留到下一代；
③ 能使用的鸟窝数目n是固定的，鸟窝的主人能发现外来鸟蛋的概率，也称为Pa∈[0,1]；
算法位置更新公式如下：
(8)
其中:
表示第i个鸟窝在第t代的鸟窝位置，⊗为点乘，α表示步长控制因子，Levy(λ)为Levy随机搜索路径
Levy(λ)～u=t-β, 1<β≤3
(9)
采用下列公式生成Levy随机数：
(10)
其中u、v服从标准正态分布，
为Gamma函数。
更新鸟巢位置后，计算后比较鸟巢的适应度值，选择适应度更优的解。之后按照概率Pa抛弃一部分差解后采用偏好随机游走生成同等数量的新解。
(11)
其中φ∈[0,1]为控制因子，满足均匀分布，
为在第t代里的不相同的随机解。一次种群迭代完成后，保留当代的最优解和对应的适应度值，重复以上过程直到达到最大迭代次数，输出全局最优解。
3.2 布谷鸟算法的改进
经典布谷鸟算法在运算中收敛速度较慢，影响运算速度，而且在运算中容易陷入局部最优从而影响求解结果的精度。
3.2.1 自适应步长因子
在标准布谷鸟算法中，步长控制因子是固定值，如果选取的步长控制因子较大，算法搜索速度变快，但是相应的求解精度降低；如果步长控制因子较小，算法精度变高但是搜索速度变慢。所以本文中在算法搜索的时候采用自适应步长[9-10]调节的方法，在运算前期解的质量不好的时候，采用较大的步长控制因子进行快速搜索，提高搜索速度；在算法搜索后期，算法求得的解比较接近最优解，采用较小的步长控制因子进行精确搜索，提高搜索精度[13]。为增加算法运算时的动态调节能力，这里引入一个自适应步长控制因子α，α随着算法搜索过程的适应度值自动调整步长的大小，从而更快速的获得更精确的优解。
(12)
其中，αmin代表步长因子的最小值，αmax代表步长因子的最大值，
代表第t代最优个体适应度，
代表第t代的最差个体适应度，
第t代的个体i的适应度，Tmax代表最大迭代次数，t代表当前迭代数，k代表常数，用来改变曲线变化率。αmin=0.2，αmax=0.9，k=1，Tmax=200。
3.2.2 模拟退火机制
模拟退火算法[14-15](simulated annealing，SA)是根据固体降温现象提出的一种优化算法，先加热固体让它的温度达到较高水平，加热期间固体粒子随着温度升高而逐渐混乱，能量逐渐变大。再让它缓慢降温，因为温度下降的足够缓慢，整个降温过程一直维持在平衡态，在降至室温后，能量达到最小。SA先选择一个随机的初始高温开始，随着温度参数T下降，算法不断搜索从而得到全局最优解。因为模拟退火机制具有使用灵活、运行效率高且受初始条件限制较小的原因，在布谷鸟算法中引入模拟退火机制，来加强算法的全局寻优能力，防止陷入局部最优。
(13)
Tk=αTk-1
(14)
其中，为第t代的最优解的适应度值，为新解的适应度值，Tk为当前状态温度。α为降温系数取0.8。
3.2.3 编码方式
实验采用实数编码如表1所示，实数的整数部分表示与任务对应的无人机编号,整数部分相同的目标任务分配在同一架无人机的任务序列中；实数的小数部分表示执行任务目标中序列的优先程度。编码与无人机任务序列的关系如表2所示。
表1 编码示意表
Table 1 Code schematic table
目标编码目标编码T12.58T62.98T21.46T71.24T31.88T83.72T42.76T93.91T53.01
表2 解码示意表
Table 2 Decoding schematic table
无人机编号实数列任务序列V11.24<1.46<1.88T7→T2→T3V22.55<2.76<2.98T1→T4→T6V33.01<3.72<3.91T5→T8→T9
3.2.4 算法流程
算法流程如图1所示，具体步骤为：
图1 算法流程框图
Fig.1 Algorithm flow chart
1) 设置算法的温度T、种群数n、发现概率Pa、衰退因子β、种群最大迭代次数Tmax等参数；
2) 初始化鸟巢并计算各个鸟巢的适应度值，留下适应度值最小的鸟巢；
3) 用改进后的Levy飞行更新鸟窝位置，计算当代鸟窝的适应度值并与前一代对比，保留当前最优的鸟窝；
4) 抛弃一部分解。取一组鸟巢将
和随机数R比大小，其中R∈(0,1)。当
时，抛弃取的鸟巢，通过式(11)随机游走生成新的鸟巢；否则保持不变。当前状态温度下降。
5) 保留当前最优解，判断是否满足最大迭代次数的条件，如果达到最大迭代次数则输出最优解；否则返回到第3步继续计算。
4 仿真实验
4.1 仿真实验参数设置
假设现有3架侦察无人机对9个目标进行侦察任务，无人机参数和目标参数分别如表3、表4所示。
表3 无人机参数
Table 3 UAVs parameters
UAViPViWorthiCiLiV1(00,10)500.64V2(00,15)600.75V3(00,20)700.85
表4 目标参数
Table 4 Target parameters
TiPTiWorthiThreateniRiT1(20,25)400.412T2(60,20)500.614T3(55,65)600.915T4(80,60)200.312T5(45,30)300.410T6(30,80)500.614T7(60,90)400.510T8(70,45)300.412T9(90,90)200.310
为了不影响多无人机任务分配结果，这里引入熵权法，对威胁代价函数、航程代价函数和任务目标收益函数中的信息量进行对比，经过多次实验取适应度函数中w1=0.3，w2=0.4，w3=0.3。改进布谷鸟算法、布谷鸟算法、蚁群算法和蜂群算法的仿真结果如图2所示。
图2 算法适应度曲线
Fig.2 Comparison curve of algorithm fitness
改进布谷鸟算法、布谷鸟算法、蚁群算法和蜂群算法的仿真结果分配表如表5—表8所示。
表5 改进布谷鸟算法的任务分配表
Table 5 Task allocation table of improved cuckoo algorithm
无人机任务序列V1T1V2T6-T7-T9V3T5-T2-T8-T4-T3
表6 布谷鸟算法的任务分配表
Table 6 Task allocation table of cuckoo algorithm
无人机任务序列V1T5-T2-T8-T4V2T3-T9-T7-T6V3T1
表7 蚁群算法的任务分配表
Table 7 Task assignment table of ant colony algorithm
无人机任务序列V1T1-T5V2T3-T6-T7V3T2-T8-T4-T9
表8 蜂群算法的任务分配表
Table 8 Task allocation table of bee colony algorithm
无人机任务序列V1T1V2T9-T3-T7-T6V3T5-T2-T8-T4
改进布谷鸟算法、布谷鸟算法、蚁群算法和蜂群算法的仿真结果示意图如图3—图6。
图3 改进布谷鸟算法的任务分配示意图
Fig.3 Task allocation schematic diagram of improved cuckoo algorithm
图4 布谷鸟算法的任务分配示意图
Fig.4 Task allocation schematic diagram of cuckoo algorithm
图5 蚁群算法的任务分配示意图
Fig.5 Task allocation schematic diagram of ant colony algorithm
图6 蜂群算法的任务分配示意图
Fig.6 Task allocation schematic diagram of bee colony algorithm
由图3可知，改进布谷鸟算法在算法迭代前期快速搜索，在算法迭代后期，算法搜索速度变慢。在改进布谷鸟算法迭代到第18次的时候，其适应度值就低于其余3种算法，此时改进布谷鸟算法的适应度值为0.224 16，当算法迭代到32次时，改进后的布谷鸟算法收敛，此时的适应度值为0.170 90。布谷鸟算法在迭代了111代收敛，适应度值为0.204 89。蚁群算法在迭代了75代收敛，适应度值为0.297 00。蜂群算法在迭代了106代收敛，适应度值为0.248 00。
根据表9可知，经过多次的仿真实验结果显示改进布谷鸟算法比布谷鸟算法的求解精度提高了16.41%、速度提高了15.01%；和蚁群算法相比精度提高了39.66%、速度提高了30.55%；和蜂群算法相比精度提高了32.54%、速度提高了13.32%。
表9 算法结果
Table 9 Comparison table of algorithm results
算法名称实验次数平均收敛适应度值平均收敛时间/s改进布谷鸟算法100.183 276.23布谷鸟算法100.219 267.33蚁群算法100.303 758.97蜂群算法100.271 687.18
由此可知改进布谷鸟算法与其他3种算法相比拥有更好的全局寻优能力和更快的收敛速度，改进布谷鸟算法能放弃局部最优解，搜索全局最优解，使得搜索出来的解更符合多无人机任务分配的要求。
5 结论
改进布谷鸟算法应用于多无人机任务分配问题，比原布谷鸟算法、蚁群算法和蜂群算法具有更快的收敛速度；在任务分配过程中也不易陷入局部最优。
[1] 宋薇,高原,沈林勇.一种基于近场子集划分的多机器人任务分配算法[J].机器人，2021,43(05)：629-640.
Wei S,Gao Y,Shen L Y.A multi robot task allocation algorithm based on near-field subset partition[J].Robot,2021,43(05):629-640.
[2] 张小孟,胡永江,李文广.基于改进人工蜂群算法的多无人机灭火任务规划[J].中国惯性技术学报,2020,28(04):528-536.
Zhang X M,Hu Y J,Li W G.Multi UAV fire fighting task planning based on improved artificial bee colony algorithm[J].Journal of Chinese Inertial Technology,2020,28 (04):528-536
[3] 张瑞鹏,冯彦翔,杨宜康.多无人机协同任务分配混合粒子群算法[J/OL].航空学报,2022:1-15.
Zhang R P,Feng Y X,Yang Y K.Hybrid particle swarm optimization algorithm for cooperative task allocation of multiple UAVs[J].ActaAeronautica et Astronautica Sinica,2022:1-15.
[4] 王晓军,王博,晋民杰.改进多种群遗传算法的AutoStore系统多AGV调度优化[J].工业工程,2021,24(04):112-118+167.
Wang X J,Wang B,Jin M J.Multi AGV scheduling optimization of autostore system based on improved multi population genetic algorithm[J].Industrial Engineering Journal,2021,24 (04):112-118,167.
[5] 谷旭平,唐大全.基于细菌觅食算法的多异构无人机任务规划[J].系统工程与电子技术，2021,43(11):3312-3320.
Gu X P,Tang D Q.Multi heterogeneous UAV mission planning based on bacterial foraging algorithm[J].Systems Engineering and Electronics,2021,43 (11):3312-3320.
[6] 廖承城,陶伟,刘韬.基于改进合同网的异构无人机协同对地任务分配[J].现代计算机,2021(15):100-107.
Liao C C,Tao W,Liu T.Heterogeneous UAV cooperative ground mission assignment based on improved contract network[J].Modern Computer,2021 (15):100-107.
[7] 王鹏飞,王书明.改进的布谷鸟MT反演算法[J].石油地球物理勘探,2020,55(01):217-225.
Wang P F,Wang S M.Improved cuckoo MT inversion algorithm[J].Oil Geophysical Prospecting,2020,55(01):217-225.
[8] Kanagaraj G,Ponnambalam S G,Jawahar N.A hybrid cuckoo search and genetic algorithm for reliability-redundancy allocation problems[J].Computers & Industrial Engineering,2013,66(04):1115-1124.
[9] 王天雷,谭南林,张人丰,等.基于ASCP-CS算法的桥式吊车滑模控制器设计[J].湖南大学学报(自然科学版),2020,47(06):87-95.
Wang T L,Tan N L,Zhang R F,et al.Design of bridge crane sliding mode controller based on ASCP-CS algorithm[J].Journal of Hunan University(Natural Sciences),2020,47(06):87-95.
[10] 张珍珍,贺兴时,于青林,等.多阶段动态扰动和动态惯性权重的布谷鸟算法[J].计算机工程与应用,2022,58(01):79-88.
[10] Zhang Z Z,He X S,Yu Q L,et al.Cuckoo algorithm for multi-stage dynamic disturbance and dynamic inertia weight[J].Computer Engineering and Applications,2022,58(01):79-88.
[11] Yang X S,DEBS.Cuckoo search via levy flights[C]//Coimbatore:2009 World Congress on Nature & Biologically Inspired Computing (NaBIC),2009:210-214.
[12] Alssager M,Othman Z A,Ayob M.Hybrid cuckoo search for the capacitated vehicle routing problem[J].Symmetry,2020,12(12):2088.
[13] Wang B,Liu Y H,Ye W.Dual adaptive factors-based integrated navigation performance improvement for airborne POS[J].IEEE Sensors Journal,2019,19(20):9479-9485.
[14] 许雪梅.基于模拟退火算法改进遗传算法的织物智能配色[J].纺织学报,2021,42(07):123-128.
Xu X M.Fabric intelligent color matching based on simulated annealing algorithm and improved genetic algorithm[J].Journal of Textile Research,2021,42 (07):123-128.
[15] Juan F S,Leonor H R,Guadalupe C V,et al.Chaotic multi-objective simulated annealing and threshold accepting for job shop scheduling problem[J].Mathematical and Computational Applications,2021,26(01):8.