基于改进布谷鸟算法的多无人机任务分配

纪良杰，赵晓林，魏兆恬，蔺文轩

(1.空军工程大学 研究生院， 西安 710043； 2.空军工程大学 装备管理与无人机工程学院， 西安 710043)

1 引言

随着无人机的快速发展，因其具有低成本、低操作员伤亡等优势，被应用于物流、农业、搜救、军事等多个领域，尤其在军事领域应用更为广泛。为了能够在复杂的战场环境下更高效的完成任务，操作员需要在开展无人机行动之前进行任务分配。

本文中主要对多无人机任务进行分配，在满足无人机性能约束及战场信息的前提下完成对敌方目标的侦察任务，尽可能的取得最大的任务总收益。为贴合战场实际，本文中使用随任务执行序列变化的威胁概率和目标收益代替固定威胁概率和目标收益让任务模型更加真实。

目前，众多学者就任务分配问题已经取得了大量的研究成果。文献[1]使用蚁群算法对任务链进行子集划分，提高了解决医疗资源分配问题的效率。文献[2]在蜂群算法的基础上加入逆向、交叉和变异算子，让其更适合求解火场救援问题。文献[3]通过在粒子群算法中引入死锁检查和修复机制，良好的解决了任务分配中的“死锁”现象。文献[4]细化了遗传算法中交叉变异概率的公式，解决了仓储系统的调度问题。文献[5]在细菌觅食算法中加入动态自适应调节游动参数，提高了算法的收敛能力；文献[6]对传统的合同网算法进行流程优化，提升了算法的分配效率。布谷鸟算法作为一种引入了生物进化论的群智能算法的新型元启发式搜索算法，因其具有参数少、鲁棒性强、通用性好等优点被广泛用于优化模型的求解。文献[7]提出一种结合单纯形的布谷鸟算法增加了解的精度，并在其中融合了粒子群思想增加了局部寻优能力，但过于追求精度使得求解过程消耗了大量时间；文献[8]通过交替及变异的操作改良了布谷鸟算法的早熟问题，但是交替变异操作让算法的随机性增大，导致算法收敛速度下降；文献[9]提出自适应选取交叉操作算子的布谷鸟搜索算法，优化了算法的寻优精度，但步长自适应因子在前期搜索中启动速度缓慢；文献[10]通过对鸟巢位置进行正态随机分布扰动，提高了种群的多样性，正态扰动半径参数对寻优搜索结果起到了重要作用，但选取合适的参数较为困难。

针对布谷鸟算法在搜索寻优过程中存在求解速度慢、容易陷入局部最优等不足，本文中引入高斯递减的自适应步长因子加快算法搜索速度，改善算法求解速度慢的问题，同时引入模拟退火机制，增加算法全局搜索能力，避免陷入局部最优解。

2 多无人机任务分配问题

2.1 问题描述

我方通过情报获取到敌方区域的个重要目标的位置信息、目标价值以及目标威胁等基本信息，为进一步掌握敌方目标的详细信息，我方需要派出无人机对该区域中重要目标进行侦察，我方有架侦察无人机，无人机均从基地起飞，有序完成对目标的侦察任务使得完成任务效益最大化。

该问题可描述为：无人机集合为={,,,…,}，无人机位置集合为={1,2,…,}，侦察目标集合为={,,,…,}，侦察目标位置集合为={1,2,…,}，无人机的价值={1,2,3,…,}，无人机完成侦察任务的概率为={,,,…,}，无人机任务载荷上限={,,,…,}，目标的价值={1,2,3,…,}，目标的威胁系数={,,,…,},目标的威胁范围的半径为={,,,…,}。

2.2 目标函数

为使多无人机执行侦察任务效益最大化，本文中需要综合考虑威胁代价、航程代价和任务目标收益三者得到最大总收益。

(1)

航程代价考虑到无人机与目标的距离远大于无人机的最小转弯半径，因此采用直线度量。

(2)

式中:指无人机执行侦察任务的最远距离，指无人机到目标的距离。

(3)

总收益适应度函数：

(4)

(5)

2.3 约束条件

(6)

(7)

式(6)表示为所有任务目标都完成；式(7)表示为每一架无人机执行的任务数目不得超过无人机本身的任务载荷数目约束。

3 改进布谷鸟算法

3.1 经典布谷鸟搜索算法

布谷鸟算法(cuckoo search，CS)是借鉴布谷鸟寻找鸟窝位置找产卵的行为而提出的一种优化算法。

布谷鸟既不会做巢也不会育雏，它在产卵前会在其他鸟类(宿主鸟)离开鸟巢时，把宿主鸟的卵推出宿主鸟巢，将自己的蛋产在宿主的鸟巢里，让宿主鸟喂养布谷鸟幼崽。而靠宿主鸟养大的幼年布谷鸟，也存在将宿主鸟幼鸟推出鸟巢的习惯，并且会模仿行为来降低被宿主鸟发现的概率。

假设布谷鸟搜索算法满足下列3项理想化的条件：

① 布谷鸟每次随机性的选择合适的鸟巢产下一枚卵；

② 在随机选择的一组鸟窝中，最好的鸟窝将会被保留到下一代；

③ 能使用的鸟窝数目是固定的，鸟窝的主人能发现外来鸟蛋的概率，也称为∈[0,1]；

算法位置更新公式如下：

(8)

()～=-, 1<≤3

(9)

采用下列公式生成随机数：

(10)

更新鸟巢位置后，计算后比较鸟巢的适应度值，选择适应度更优的解。之后按照概率抛弃一部分差解后采用偏好随机游走生成同等数量的新解。

(11)

3.2 布谷鸟算法的改进

经典布谷鸟算法在运算中收敛速度较慢，影响运算速度，而且在运算中容易陷入局部最优从而影响求解结果的精度。

321 自适应步长因子

在标准布谷鸟算法中，步长控制因子是固定值，如果选取的步长控制因子较大，算法搜索速度变快，但是相应的求解精度降低；如果步长控制因子较小，算法精度变高但是搜索速度变慢。所以本文中在算法搜索的时候采用自适应步长调节的方法，在运算前期解的质量不好的时候，采用较大的步长控制因子进行快速搜索，提高搜索速度；在算法搜索后期，算法求得的解比较接近最优解，采用较小的步长控制因子进行精确搜索，提高搜索精度。为增加算法运算时的动态调节能力，这里引入一个自适应步长控制因子，随着算法搜索过程的适应度值自动调整步长的大小，从而更快速的获得更精确的优解。

(12)

3.2.2 模拟退火机制

模拟退火算法(simulated annealing，SA)是根据固体降温现象提出的一种优化算法，先加热固体让它的温度达到较高水平，加热期间固体粒子随着温度升高而逐渐混乱，能量逐渐变大。再让它缓慢降温，因为温度下降的足够缓慢，整个降温过程一直维持在平衡态，在降至室温后，能量达到最小。SA先选择一个随机的初始高温开始，随着温度参数下降，算法不断搜索从而得到全局最优解。因为模拟退火机制具有使用灵活、运行效率高且受初始条件限制较小的原因，在布谷鸟算法中引入模拟退火机制，来加强算法的全局寻优能力，防止陷入局部最优。

(13)

=-1

(14)

3.2.3 编码方式

实验采用实数编码如表1所示，实数的整数部分表示与任务对应的无人机编号,整数部分相同的目标任务分配在同一架无人机的任务序列中；实数的小数部分表示执行任务目标中序列的优先程度。编码与无人机任务序列的关系如表2所示。

表1 编码示意表Table 1 Code schematic table

表2 解码示意表Table 2 Decoding schematic table

3.2.4 算法流程

算法流程如图1所示，具体步骤为：

图1 算法流程框图Fig.1 Algorithm flow chart

1) 设置算法的温度、种群数、发现概率、衰退因子、种群最大迭代次数等参数；

2) 初始化鸟巢并计算各个鸟巢的适应度值，留下适应度值最小的鸟巢；

3) 用改进后的Levy飞行更新鸟窝位置，计算当代鸟窝的适应度值并与前一代对比，保留当前最优的鸟窝；

5) 保留当前最优解，判断是否满足最大迭代次数的条件，如果达到最大迭代次数则输出最优解；否则返回到第3步继续计算。

4 仿真实验

4.1 仿真实验参数设置

假设现有3架侦察无人机对9个目标进行侦察任务，无人机参数和目标参数分别如表3、表4所示。

表3 无人机参数Table 3 UAVs parameters

表4 目标参数Table 4 Target parameters

为了不影响多无人机任务分配结果，这里引入熵权法，对威胁代价函数、航程代价函数和任务目标收益函数中的信息量进行对比，经过多次实验取适应度函数中=03，=04，=03。改进布谷鸟算法、布谷鸟算法、蚁群算法和蜂群算法的仿真结果如图2所示。

图2 算法适应度曲线Fig.2 Comparison curve of algorithm fitness

改进布谷鸟算法、布谷鸟算法、蚁群算法和蜂群算法的仿真结果分配表如表5—表8所示。

表5 改进布谷鸟算法的任务分配表Table 5 Task allocation table of improved cuckoo algorithm

表6 布谷鸟算法的任务分配表Table 6 Task allocation table of cuckoo algorithm

表7 蚁群算法的任务分配表Table 7 Task assignment table of ant colony algorithm

表8 蜂群算法的任务分配表Table 8 Task allocation table of bee colony algorithm

改进布谷鸟算法、布谷鸟算法、蚁群算法和蜂群算法的仿真结果示意图如图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

由此可知改进布谷鸟算法与其他3种算法相比拥有更好的全局寻优能力和更快的收敛速度，改进布谷鸟算法能放弃局部最优解，搜索全局最优解，使得搜索出来的解更符合多无人机任务分配的要求。

5 结论

改进布谷鸟算法应用于多无人机任务分配问题，比原布谷鸟算法、蚁群算法和蜂群算法具有更快的收敛速度；在任务分配过程中也不易陷入局部最优。