基于改进麻雀搜索算法的多无人机任务分配

刘夏婷，傅 强

（中国民用航空飞行学院飞行技术学院，广汉 618307）

0 引言

无人机（unmanned aerial vehicle，UAV）拥有成本低、自主程度高、机动灵活等优点，被广泛应用于服务、农业、军事等领域［1-3］。在复杂环境下为了完成多样变化的无人机任务，使用携带不同功能的集群无人机执行任务已成为重要方式。对于多无人机任务分配问题，构建的问题模型和使用的智能算法是至关重要的。

文献［4］提出一种混合粒子群算法，创新性地提出对多攻击任务死锁检测和修复算法，对任务重分配使用匹配策略思想，可有效解决协同攻击任务重分配问题。文献［5］对多无人机的侦察任务分配问题进行研究，使用蚁群算法模拟多种不同载荷情况，其求解的分配方案更加贴合实际情况。文献［6］使用量子遗传算法进行全局任务分配，同时加入混合蛙跳优化策略，跳出局部极值并减少了算法的整体迭代次数。文献［7］使用改进蚁群算法对任务分配和路径规划联合优化，新增加无人机编队数量约束，并引入信息素更新以保证资源的充分利用。文献［8］提出基于并行机制的多目标灰狼算法，在算法中引入分层编码和档案室共享策略，可有效提高求解速度和收敛能力。文献［9］在基础的布谷鸟算法中通过调整自适应步长以及加入模拟退火算法，使算法不容易陷入局部最优。

针对多无人机任务分配问题，本文提出基于Logistics混沌的多目标麻雀搜索算法，构建任务分配目标函数，对麻雀搜索算法进行改进并优化，可高效快速地求解任务分配目标函数。

1 模型建立

1.1 问题描述

本文主要研究在模拟的二维战场空间内，我方多无人机对地面目标完成评估、侦察、攻击三项任务。无人机均从同一确定基地起飞。假设无人机数量NV，其集合为V={V1,V2,V3,…,VNV}，移动的空中目标数量为NT， 集合为T={T1,T1,T3,…,TNT}，每个目标需完成三项任务，即评估、侦察和攻击，其任务数量为NU，任务集合为U={reconnoitre,attack,estimate} ，NU=3。在模拟的二维平面内，无人机i对应的位置为（xi,y）i，目标j对应的位置为（xj,y）j。其相对距离可表示为分别考虑无人机执行任务时的威胁代价，执行侦察、评估、攻击任务带来的收益，完成任务的航行距离，以这三个评价指标为基础综合建立多无人机任务分配目标函数。

1.2 评价指标

1.2.1 威胁代价

威胁代价是指无人机在执行任务时，任务目标对无人机造成无人机损毁付出的代价。假设无人机i的价值为valuei，目标j对无人机i的威胁概率为Sij，即无人机执行任务后的生存概率为(1 -Sij)。经过所有目标后，无人机产生的执行代价计算如下：

1.2.2 任务收益

当无人机依次完成侦察、攻击、评估三项任务时，根据无人机的侦察能力指数、对目标的毁伤概率、评估能力分别得到收益P1ij、P2ij、P3ij。

因此，无人机完成任务的总收益为

1.2.3 航行代价

航程代价是指无人机到达执行任务位置时所需的距离代价，本文采用直线度量。

Dis（Tij）指无人机i到目标j的距离，dmax指无人机执行侦察任务的最远距离。

1.3 总收益适应度目标函数

式（8）中Wi为权重系数，且W1+W2+W3= 1。

1.4 约束条件

1.4.1 任务时序约束

1.4.2 无人机执行任务约束

（1）目标的三种任务可被不同无人机执行，且一架无人机只能执行该点的一种任务。

（2）所有任务均被完成。

2 改进多目标麻雀搜索算法

2.1 经典麻雀搜索算法

在麻雀搜索算法中，有发现者、跟随者和警戒者三类。警戒者所占种群比例10%～20%，发现者和跟随者所占比例是不确定的。其中发现者的主要职责是寻找食物所在的方向和位置，跟随者是跟随发现者进行觅食，警戒者负责对觅食区域的监视。为获得生存的资源，该算法通过在寻找食物过程中不断更新三者的位置完成。发现者的位置更新方式如下：

其中，表示在第t代中第i只麻雀在第j维的位置，R2表示报警值。

跟随者的位置更新：

其中，表示第t代适应度最差的个体位置，表示第t+1 代中适应度最佳的个体位置。A+=AT(AAT)-1。

警戒者位置更新方式如下：

其中，表示第t代中全局最优位置，β为控制步长。fi表示当前个体的适应度值，fg和fw表示目前全局最优和最差个体的适应度值。

2.2 改进多目标麻雀搜索算法

2.2.1 利用Logistic映射初始化种群

麻雀搜索算法寻优能力较好，但其结果具有较大的随机性，且初始化种群麻雀个体的位置会影响算法结果的稳定性，因此在初始化种群阶段利用Logistic 映射，在初期阶段进行个体分类，随着迭代次数变化提高了种群的多样性，在一定程度上减小了算法陷入局部最优的概率。其数学表达公式如下：

其中，μ为Logistic 参数。为了保证映射得到的Xn始终位于［0,1］内，则μ∈［0,4］。x（t）为在t时刻种群占最大可能种群规模的比例。

2.2.2 利用Pareto最优解求解多目标优化问题

利用Pareto 多目标优化问题的主要思想是首先对不同目标优先级或权重进行明确，然后试图找到优化条件在不同权重下各为最优解的一组解，然后根据决策者的偏好或应用场景决定选择哪个解。

多目标优化定义如下：

其中，u∈Ω 为决策向量，Ω 为决策空间；y∈Y，为目标向量，Y为目标函数空间。

3 算法流程

具体算法流程如下：

步骤一：利用Logistic映射策略初始化种群、迭代次数，以及初始化捕食者和加入者比例；

步骤二：计算适应度值，并对结果排序；

步骤三：麻雀更新捕食者位置；

步骤四：麻雀更新加入者位置；

步骤五：麻雀更新警戒者位置；

步骤六：计算适应度值并更新麻雀位置；

步骤七：是否满足停止条件，若满足条件则结束，输出结果；否则，重复执行步骤二至步骤六。

4 仿真实验

4.1 实验参数设置

本文对实验场景构想如下：在多无人机任务分配过程中不考虑能源消耗、通信约束以及载荷约束。为方便计算，将无人机和目标均视为具有速度、角度、价值、概率等属性的质点。仿真环境的区域设置为5 km×5 km的平面。无人机的初始位置从固定点（1.1）开始。

假设现有7 架无人机对4 个目标进行侦察、评估、攻击任务，无人机的基本参数和目标参数及毁伤概率分别见表1、表2和表3。

表1 无人机的基本参数

表2 目标参数设置

经多次实验数据对比，取适应度函数W1= 0.3,W2= 0.3,W3= 0.4。

4.2 实验结果与分析

4.2.1 结果分析

无人机任务目标分配结果见表4所示。

从任务分配结果可以看出，无人机V1完成了T4与T2的评估任务，无人机V2完成了T2的侦察任务与T4的攻击任务，无人机V3完成了T1的侦察任务，无人机V4完成了T2的攻击任务与T3的评估任务，无人机V5完成了T1与T3的侦察任务，无人机V6完成了T1的评估任务与T3的攻击任务，无人机V7完成了T4的侦察任务。每个无人机的任务均为唯一，且每个目标的侦察、攻击、评估任务均被完成。

总收益适应度目标函数结果如图1所示。

图1 算法适应度曲线

由图1 可知，改进麻雀搜索算法利用Pareto最优解求解多目标优化问题，获得了更快的收敛速度，利用Logistic 映射在初期阶段进行个体分类，随着迭代次数变化的同时提高了种群的多样性，一定程度上减小了算法陷入局部最优的概率。

4.2.2 不同场景下实验结果及分析

为验证算法的有效性，使用ISSA、SSA 和GA 三种算法求解不同场景下的多无人机任务分配问题。三种算法的最大迭代次数均设置为100，其他参数的设置均一样。其目标迭代收敛曲线如图2、图3和图4所示。

图2 10无人机对5个目标的收敛曲线

图3 13无人机对6个目标的收敛曲线

图4 16无人机对7个目标的收敛曲线

从总体上看，三种算法迭代收敛的目标函数最终都会趋于一个稳定值。ISSA 算法的收敛值均小于其他两种算法。从图2可以看出，在目标数量较少的情况下，相比其他两种算法，随迭代次数增加，ISSA 算法可以在较短时间内经过较少的迭代次数达到稳定的目标函数值。在图3 和图4 中，当目标数量增加时，迭代初期三种算法目标函数值较为不稳定，上下波动，优化算法的搜索操作呈现不稳定的状态；在迭代后期，各算法的搜索能力较为平稳，目标函数值也趋于稳定。因此，与GA 与SSA 相比，ISSA具有良好的收敛性能。

5 结语

本文以麻雀搜索算法为基础，加入了Logistic映射策略来建立无人机任务分配模型，利用Pareto 多目标优化问题的主要思想对目标的威胁代价、航程代价、任务收益进行权重分配，多次试验找到最优解。仿真结果表明，本文研究的模型合理有效，且应用在不同的场景下也有较大优势，通过算法的改进不仅加强了种群多样性，同时提高了算法的收敛精度以及搜索效率。