A Knee Point Based Coevolution Multi-objective Particle Swarm Optimization Algorithm for Heterogeneous UAV Cooperative Multi-task Allocation
-
摘要: 随着无人机(Unmanned aerial vehicle, UAV)技术的广泛应用和执行任务的日益复杂, 无人机多机协同控制面临着新的挑战. 以无人机总飞行距离和任务完成时间为优化目标, 同时考虑异构无人机类型、任务执行时序等多种实际约束, 构建基于多种约束条件的异构无人机协同多任务分配模型. 该模型不仅包含混合变量, 同时还存在多个复杂的约束条件, 因此, 传统的多目标优化算法并不能有效地处理混合变量及对问题空间进行搜索并生成满足多种约束条件的可行解. 为高效求解上述模型, 提出一种基于拐点的协同多目标粒子群优化算法(Knee point based coevolution multi-objective particle swarm optimization, KnCMPSO), 该算法引入基于拐点的学习策略来更新外部档案集, 在保证收敛性的同时增加种群的多样性, 使算法能搜索到更多可行的任务分配结果; 并基于二进制交叉方法, 引入基于学习的粒子更新策略来提升算法的收敛性及基于区间扰动的局部搜索策略以提升算法的多样性. 最后通过在四组实例上的仿真实验验证了所提算法在求解异构无人机协同多任务分配问题上的有效性.Abstract: With the wide application of unmanned aerial vehicle (UAV) technology and the increasing complexity of UAV tasks, the multi-aircraft cooperative control on UAVs faces new challenges. In this paper, a heterogeneous UAV cooperative multi-task allocation model which takes the UAV total flight distance and task completion time as the optimization objectives is set up. The model includes mixed variables and multiple complex constraints, such as UAV type and task execution time. As a result, traditional multi-objective optimization algorithms cannot effectively search the problem space and generate feasible solutions. In this paper, a knee point based cooperative multi-objective particle swarm optimization algorithm, namely knee point based coevolution multi-objective particle swarm optimization (KnCMPSO), is proposed to solve the above model. In KnCMPSO, a knee point based learning strategy is employed to update the external archive set, which can help get more better solutions. The learning-based particle update strategy is proposed to improve the convergence and the interval disturbance based local search strategy is used to enhance the diversity. The experimental results on four sets of examples show that, the proposed KnCMPSO algorithm can solve the heterogeneous UAVs collaborative multi-task allocation problem more effectively than other existing methods.
-
无人机(Unmanned aerial vehicle, UAV)以其体积轻巧、隐身性能好、续航时间长、可回收重复使用等优势逐渐成为空中作战的主角. 相较于有人机, 无人机能够在偏远、危险或者人员不可达的极端环境中, 自主完成一些重要的诸如监测、搜救、侦察、打击等任务[1]. 无人机协同作战是指在实际的战场中, 多种类型的无人机充分发挥各自优势, 协同完成一项军事任务. 早期的无人机协同作战由于作战场景简单、任务类型单一、任务难度较低, 仅通过人工决策就能确定各无人机的作战序列. 然而随着作战场景逐渐复杂、任务类型逐渐多样化、无人机智能化水平逐渐提高, 仅靠人工决策很难充分挖掘各种无人机的特性并发挥无人机系统的协同作战优势. 现实世界中的无人机往往是异构的, 异构无人机指的是多种类型的无人机(侦察机、战斗机等)[2], 为了提高异构无人机执行任务的效率, 提升异构无人机系统的自主性, 开展异构无人机协同多任务分配问题研究具有十分重要的意义[3].
为了高效地制定无人机的任务分配计划、科学地控制无人机, 需要对无人机协同多任务分配问题建立合适模型.
在模型的约束条件研究方面, 文献[4]充分考虑了无人机执行任务之间的时序和多机协同等约束条件, 将无人机分配问题构建成为协同多任务分配问题模型. 文献[5]提出以无人机自身性能约束、协同约束和实际三维复杂环境构建约束的无人机任务分配模型. 然而上述模型中所考虑的各无人机都具有侦察、打击、评估三种能力, 不属于异构无人机. 在实际问题中, 由于不同无人机的能力有差异, 无法用一类无人机完成所有任务. 因此通常选择采用多架异构无人机组成集群来共同完成任务, 解决不同无人机的能力限制. 一些学者进一步对异构无人机协同任务分配模型提出了新的约束条件, 如文献[6]考虑无人机资源消耗、完成任务资源需求等约束, 文献[7]考虑任务优先级等约束, 文献[8]考虑无人机运动学等约束.
在模型的优化目标研究方面, 目前大部分研究工作建立的都是以最小化无人机飞行距离的单目标模型[9], 也有一些学者尝试构建无人机任务分配的多目标优化模型. 如文献[10]提出同时考虑无人机任务收益、任务执行时间和任务执行代价的多目标模型, 文献[11]以无人机总飞行距离和任务完成时间为优化目标构建了多目标优化模型.
在无人机协同多任务分配模型的求解方面, 近年来也有部分学者进行了深入研究[12], 其中粒子群算法[13]作为群智能算法中的经典算法, 具有操作简单、收敛能力强等特点, 可以很好地求解无人机协同任务分配问题. 文献[14]将多种目标函数进行加权, 利用离散粒子群算法对构建的模型进行求解, 但是采用的交叉变异操作方式较为简单, 求解效率有待进一步提升. 文献[10]利用多目标量子粒子群算法对无人机任务分配问题进行求解, 但是算法编码较为复杂, 计算量比较大. 文献[15]提出采用改进的量子粒子群算法对无人机任务分配问题进行求解, 但是算法需要额外计算平均历史最优位置而且设定的参数较多. 近年来, 随着异构无人机协同多任务分配模型研究的深入, 一些学者针对异构无人机协同多任务分配问题的求解算法进行了探讨. 如文献[11]提出一种基于协同进化的混合变量多目标粒子群优化算法, 但其更新策略过于简单且随机性较大, 随着问题规模的增大, 求解效率将逐渐下降. 文献[16]提出改进的多目标量子粒子群算法, 但其重组方式较复杂, 求解效率不高. 文献[17]提出改进的遗传算法, 但该算法主要针对单目标优化模型, 无法很好地求解多目标异构无人机任务分配模型.
异构无人机协同多任务分配模型有多个复杂的约束条件, 因此, 如何处理不同类型的约束条件, 以提高算法的搜索效率, 是求解异构无人机协同多任务分配模型的重要问题. 近年来, 一些学者针对不同类型的应用问题, 研究采用不同约束处理方法进行求解. 求解方法大致可以分为基于罚函数(Prnalty function, PF)的约束处理方法[18-20]、基于可行性原则的约束处理方法(Stochastic ranking, SR)[21-22]、基于随机排序的约束处理方法 (Feasibility rule, FR)[23]和基于多目标的约束处理方法[24] 4类 . 也有一些学者就约束处理技术理论方面提出了一些新的改进, 如基于分级方式的约束处理准则[25]、基于集成方式的约束处理准则[26]或将约束转化为新的优化目标[27]. 而在异构无人机协同多任务分配模型中, 存在无人机类型约束、任务执行时序约束及多机协同约束等多种复杂约束, 上述方法无法直接用于求解.
为了使构建的模型更加符合现实场景, 现有对无人机任务分配问题的研究工作均在约束条件或目标函数上对模型做出了改进, 但是大部分研究工作均假设无人机的观测时间和一次弹药消耗都是充足的, 然而在实际作战过程中, 当侦察机一次观测时间过长时, 存在被敌方发现乃至击毙的风险, 战斗机一次发射的弹药数量也是有限的. 因此本文在现有研究工作[11]的基础上, 进一步考虑无人机单次任务最大观测时间约束和无人机单次任务最大弹药约束, 建立基于多种约束条件的异构无人机协同多任务分配问题模型.
上述模型不仅包含混合变量, 同时还存在多个复杂的约束条件, 问题的求解难度较大, 传统的多目标优化算法并不能有效地求解上述模型. 同其他智能优化算法相比, 粒子群算法具有计算简单、鲁棒性好、搜索能力强且收敛速度快的特点, 在求解多约束多目标异构无人机协同任务分配问题时, 具有较大优势. 为了高效求解该模型, 本文提出了一种基于拐点的协同多目标粒子群优化算法(Knee point based coevolution multi-objective particle swarm optimization, KnCMPSO). 本文的主要贡献如下:
1)针对模型包含混合变量以及多种约束的特点, 采用基于三维矩阵的混合编码方式以及基于约束处理的初始化方法, 有效避免不可行解的生成, 提高算法的搜索效率.
2)采用协同进化策略, 将多目标优化问题转为多个单目标优化问题, 通过子种群间合作式协同降低求解复杂度, 通过子种群内竞争式协同进化加快算法收敛, 进一步提出基于学习的粒子更新策略来提升算法的收敛性, 粒子不仅学习父代优秀个体, 也学习精英个体或全局最优个体, 可以实现更快收敛.
3)提出基于区间扰动的局部搜索策略来提升算法的多样性, 进一步提出基于拐点的学习策略来更新外部档案集, 加强了算法对帕累托前沿中心面的搜索, 在保证收敛性的同时提升算法的多样性, 使得算法能搜索到更多的可行任务分配结果.
本文首先对无人机协同多任务分配问题建模, 然后介绍基于拐点的协同多目标粒子群优化算法, 接着设计仿真实例来验证算法的有效性, 最后进行总结和展望.
1. 异构无人机协同多任务分配模型
1.1 问题描述
表1展示了模型中涉及的各种符号以及相应说明.
表 1 符号说明Table 1 Symbol description类别 属性 侦察无人机总数$S$ 战斗无人机总数$A$ 初始位置$P_i = (x_i, y_i)$ 飞行速度$V_i$ 无人机$U$ 战斗无人机最大携弹数目$Load_i$ 战斗无人机单次任务最大发射弹药数目$Launch_i$ 侦察无人机单次任务最大侦察时间$T_i$ 无人机最大飞行距离${\rm{Max}}Dis_i$ 无人机$U_i$执行任务$M_k$消耗的资源$C_i^k$ 目标总个数$N_T$ 目标位置坐标$P_j = (x_j, y_j)$ 目标$T$ 目标$j$的任务个数$N_M^j=3$ 任务总个数$N_M=3 \times N_T$ 任务$M$ 任务完成所需资源$CR_k$ 异构无人机协同多任务分配问题描述如下: 假设在某二维已知区域内发现了
$ N_T $ 个敌方目标, 则目标集合$ T $ 可表示为$ T = \{T_1,T_2,\cdots,T_{N_T}\} $ . 无人机系统需要对每个目标依次执行三种不同类型的任务, 分别为观测、打击、打击结果评估, 即三种任务之间存在时序关系. 任务类型集合$ M $ 可以表示为$ M = \{Observe,Attack,Evaluate\} $ , 因此模型中需要调度的总任务数量$ N_M $ 的值为$ N_M = 3 \times N_T $ . 异构无人机系统中的无人机可以被分为侦察机和战斗机两种类型, 其中用于执行观测和打击结果评估任务的侦察无人机有$ S $ 架, 执行打击任务的战斗无人机有$ A $ 架, 则无人机集合表示为$U = \{U_1,U_2,\cdots, U_S,U_{S+1},\cdots,U_{S+A}\}$ . 无人机执行不同的任务需要消耗一定的资源量. 同一个目标上的相同任务可以由多台无人机协同完成. 当所有目标上的所有任务执行完成, 整个军事作战任务顺利完成.1.2 目标函数
为了能够更加合理地对无人机任务分配的结果进行评估, 本文的模型采用无人机总飞行距离和任务完成时间两个目标函数. 无人机的总飞行距离为无人机系统中所有参与任务的无人机飞行距离之和, 任务完成时间为整个作战任务中最后一个完成任务的无人机的总飞行时间. 根据以上定义, 本文模型的计算公式如下:
$$ \left\{ \begin{aligned} f_1 & = \sum_{i = 1}^{S+A} \sum_{k \in M_i} Dis(M_k^i,M_{k+1}^i) \\ f_2 & = \underset{1\le k \le N_M}{{{\rm{max}}}} t_k^{Evaluate} \end{aligned} \right. $$ (1) 式中,
$ Dis(M_k^i,M_{k+1}^i) $ 表示第$ i $ 个无人机执行第$ k $ 个任务到第$ k+1 $ 个任务的飞行距离, 表示完成第$ k $ 个评估任务的时间,$ f_1 $ 代表了所有无人机的总飞行距离,$ f_2 $ 代表了无人机系统中最后一个任务执行完成的时间, 也就是任务的最大完成时间. 由于分配任务时希望无人机尽快完成任务的同时消耗较少的飞行资源, 因此, 本文提出的模型同时考虑了上述两个优化目标, 即同时最小化函数$ f_1 $ 和$ f_2 $ .无人机航程和其消耗资源数紧密相关, 无人机飞行总航程越短, 代表无人机执行任务时消耗的资源越少. 然而, 飞行总航程最短并不一定能保证军事任务的完成时间最短. 例如, 一些无人机可能在同一目标上被分配较多的任务以满足所有无人机飞行总航程最短, 而这会导致该无人机完成所有任务的时间变长, 从而使得整个军事任务完成时间变长. 因此, 无人机飞行总航程和任务完成时间两个指标存在一定的冲突.
1.3 约束条件
为了能够对多台无人机协同完成同一项军事任务进行更有效的刻画, 本文在文献[11]基础上, 进一步考虑无人机单次任务最大观测时间约束和无人机单次任务最大弹药约束来建立异构无人机多任务分配模型, 其所包含的约束条件如下.
1)无人机类型约束. 由于无人机的异构性, 不同类型的任务只能由特定类型的无人机完成.
$$ \begin{equation} X_{i}^{k} = \left\{ \begin{aligned} 1, & \qquad {无人机\;{{i}}\;执行任务\;{{k}}} \\ 0, & \qquad {其他} \end{aligned} \right. \end{equation} $$ (2) 式中,
$ i $ 表示无人机编号,$ j $ 表示目标编号,$ k $ 表示任务编号. 当$ k\in\{Observe, Evaluate\} $ 时,$i\in \{1, 2,\cdots, S\}$ ; 当$ k\in\{Attack\} $ 时,$i \in \{S+1,\cdots, S + A \}$ .2)任务执行时序约束. 对于同一个目标, 无人机系统要先对其执行观测任务, 然后对其执行打击任务, 最后才能够执行打击结果评估任务. 因此对同一个目标上的三种任务需满足如下时序约束.
$$ \begin{equation} T_k^{Observe} \le T_k^{Attack} \le T_k^{Evaluate}, k \in \{ 1,2,\cdots,N_M \} \end{equation} $$ (3) 3)最大携带弹药数目约束. 战斗无人机只能携带一定数目的弹药. 因此战斗无人机执行打击任务消耗的弹药数要小于其最大携带弹药数目.
$$ \begin{equation} \sum_{k = 1}^{N_M}C_i^k X_i^k \le Load_i, \quad i \in \{1,2,\cdots,A\} \end{equation} $$ (4) 4)单次最大侦察时间. 为了避免暴露时间过长以至于被敌方发现, 侦察无人机在执行观测任务和打击结果评估任务时存在最大侦察时间.
$$ \begin{equation} C_i^k \le T_i^k, \quad i \in \{1,2,\cdots,S\} \end{equation} $$ (5) 5)单次最大发射弹药数. 战斗无人机在执行对某一个目标上的打击任务时, 由于自己性能的限制只能发射一定数量的弹药.
$$ \begin{equation} C_i^k \le Launch_i^k, \quad i \in \{1,2,\cdots,A \} \end{equation} $$ (6) 6)多机协同约束. 为了保证军事任务顺利完成, 针对不同目标的不同类型的任务需要分配给不同数量的无人机协同执行. 其中对同一个目标的观测和打击结果评估任务至少需被一架侦察无人机执行, 而打击任务需要分配给至少一架战斗无人机执行.
$$ \begin{equation} \sum\limits_{i = 1}^S X_i^k \wedge \sum\limits_{i = S+1}^{S+A} X_i^{k+1} \wedge \sum\limits_{i = 1}^{S} X_i^{k+2} = 1 \end{equation} $$ (7) 7)完成任务资源需求约束. 执行相同任务的所有无人机资源消耗总量需要大于等于完成当前任务所需要的资源总量.
无人机执行观测任务和打击结果评估任务需要消耗一定的时间资源, 所有执行同一任务的侦察无人机侦察总时间需要满足完成任务所需总时间.
$$ \begin{equation} \sum\limits_{i = 1}^S C_i^k X_i^k \ge CR_k, \quad k \in \{Observe, Evaluate \} \end{equation} $$ (8) 无人机执行打击任务需要消耗一定的弹药资源, 所有执行同一任务的战斗无人机消耗弹药数量需要满足完成任务所需总弹药数量.
$$ \begin{equation} \sum\limits_{i = S+1}^{S+A} C_i^k X_i^k \ge CR_k, \quad k \in \{Attack \} \end{equation} $$ (9) 8)最大航程约束. 假设无人机i执行的任务序列为
$M_i = (M_1,M_2,\cdots,M_m)$ ,$ Dis(M_k,M_{k+1}) $ 表示无人机执行第$ k $ 个任务到第$ k+1 $ 个任务的飞行距离,${\rm{Max}}Dis_i$ 表示无人机最大飞行距离, 则有:$$ \begin{split} &\sum\limits_{k \in M}Dis(M_k, M_{k+1}) \le {\rm{Max}}Dis_i, \\ &\qquad i \in \{1,2,\cdots,S+A \} \end{split} $$ (10) 上述异构无人机协同多任务分配模型所包含的决策变量既有表示任务分配结果的离散变量, 也有表示无人机资源消耗的离散和连续变量, 这些混合变量导致问题解空间变得更加复杂, 难以进行有效搜索. 同时模型还包含多个复杂的约束条件, 既有不等式约束, 也有等式约束, 这些约束条件进一步使得问题对应的解空间变得不规则, 增加了算法搜索到可行解的难度.
由于现有的算法无法对本文提出的多约束多目标异构无人机协同多任务分配模型进行有效求解, 本文提出一种基于拐点的协同多目标粒子群优化算法求解无人机协同多任务分配问题.
2. 基于拐点的协同多目标粒子群算法
本文提出的基于拐点的协同多目标粒子群优化算法KnCMPSO, 主要通过设计基于约束处理的初始化策略、协同进化策略、基于学习的粒子更新策略、基于区间扰动的局部搜索策略及基于拐点的外部档案集更新策略提升算法的求解性能.
算法流程如图1所示. 首先, 采用子种群间合作、子种群内竞争的协同进化策略, 将多目标优化问题转为各个目标维度上的单目标优化问题, 降低了问题的求解复杂度; 其次, 在各个子种群内部, 针对无人机协同多任务分配问题包含混合变量以及多种约束的特点, 以二进制交叉方法为基础, 设计了基于学习的粒子更新策略和基于区间扰动的局部搜索策略, 提升了算法的求解性能; 最后, 引入基于拐点的学习策略来更新外部档案集, 增强了算法对帕累托前沿中心面的搜索, 在保证收敛性的同时增强了算法的多样性.
2.1 编码以及初始化策略
在使用粒子群算法求解无人机协同多任务分配问题时, 首先需要解决的问题就是如何对粒子中个体进行编码操作. 为了处理模型中的混合变量以及各种约束条件, 本文将采用基于三维矩阵的混合编码方式对决策变量进行编码. 如表2所示, 编码矩阵中的第1行是目标编号, 每一个目标编号在粒子的第1行都会出现3次, 按照出现先后顺序分别代表了在此目标上执行的观测任务、打击任务、打击结果评估任务. 第2行是无人机编号, 代表了执行此任务的无人机. 由于目标编号在矩阵出现的先后顺序代表了不同的任务类型, 因此无人机编号(无人机类型) 需要根据目标编号所代表的任务类型来设置. 第3行是无人机执行对应任务的资源消耗, 其中侦察机消耗的资源为时间, 是连续变量, 战斗机消耗的资源为弹药, 是离散变量.
表 2 粒子编码方式Table 2 Particle encoding scheme目标编号$T$ 1 2 2 1 3 1 3 2 3 无人机编号$U$ 1 3 2 3 4 5 6 5 6 1 2 4 1 2 3 资源消耗$C$ 2.4 2.6 1.1 4.9 2.0 1.0 1.0 2.0 1.0 5.0 3.0 2.0 3.0 0.2 1.1 基于三维矩阵的混合编码方式不但能够很好地描述目标、任务、执行任务的无人机以及无人机资源消耗的对应关系, 而且能够直观地表示出各台无人机执行任务的先后顺序, 方便后续初始化操作. 虽然每个个体位置向量编码长度仍然可能不同, 但是所有目标在编码中出现的次数是固定的, 也就是说所有粒子的编码矩阵中第1行目标编号的长度是固定的, 这就大大降低了问题的求解难度.
在上述编码方式的基础上, 本文提出基于约束处理的初始化策略, 具体过程如算法1所示.
表3和表4为初始化策略示例说明, 表3为目标队列集合, 表4为无人机集合. 首先, 建立一个
$ 4 \times N $ 的目标矩阵, 将所有的目标依次放入矩阵中的第1行, 每个目标上的任务按照观测任务、打击任务和打击结果评估任务的顺序依次排列到矩阵的第2、3、4行. 无人机按照侦察机和战斗机类别不同分别放入两个队列当中; 然后, 粒子将按照从左往右的顺序依次初始化位置向量. 每次均从目标矩阵中随机选择一个目标, 并将目标中尚未完成的任务取出进行分配. 根据任务类型选择相应的无人机类型, 并设置无人机对应的资源消耗. 如果此任务上的所有无人机的资源消耗量与完成此任务的资源需求量相等则代表当前任务执行完毕. 当某个目标对应的三种任务全部执行完毕代表此目标的分配全部完成; 最后, 当所有的目标都分配完成之后, 得到的粒子就是一个满足所有约束条件的可行解, 且可以有效避免出现由于某个任务的前置任务未完成而导致的死锁状态[28].表 3 目标队列集合Table 3 Target formation collection1 2 3 $\cdots $ $N$ $T_1^O$ $T_2^O$ $T_3^O$ $\cdots $ $T_N^O$ $T_1^A$ $T_2^A$ $T_3^A$ $\cdots $ $T_N^A$ $T_1^E$ $T_2^E$ $T_3^E$ $\cdots $ $T_N^E$ 表 4 无人机集合Table 4 Drone collection侦察机$U_S$ $U_1,U_2,\cdots,U_S$ 战斗机$U_A$ $U_{S+1},U_{S+2},\cdots,U_{S+A}$ 算法1. 基于约束处理的初始化策略
输入. 目标集合
$ T $ , 任务集合$ TaskSet $ , 无人机集合$ U $ , 位置向量$ P = (M,U,C) $ .输出. 粒子的位置向量
$ P = (M,U,C) $ .1) while
${目标集合}\;T \ne \emptyset ;$ 2)从目标集合
$ T $ 中随机选择一个目标$ T_j $ . 从该目标的任务集合$ TaskSet_j $ 中选择当前需要执行的任务$ M_k $ . 将$ k $ 添加到任务编号向量$ M $ 中;3) if
$ M_k\in\{Observe,Evalute\} $ ;4)从无人机集合
$ U $ 中随机选择一架侦察无人机$ U_i $ ; 随机生成无人机Ui执行任务$ M_k $ 的时间消耗$ C_i^k $ ;5) else;
6)从无人机集合
$ U $ 中随机选择一架战斗无人机$ U_i $ ; 随机生成无人机$ U_i $ 执行打击任务$ M_k $ 的导弹消耗$ C_i^k $ ;7) end if;
8)将
$ T_j $ 添加到无人机编号$U $ 中, 将$ C_i^k $ 添加到资源消耗$ C $ 中; 更新任务$ M_k $ 完成所需资源$ CR_k \gets CR_k - C_i^k $ ;9) if
$ CR_k \le 0 $ ;10)
$ TaskSet_j \gets TaskSet_j - M_k $ ;11) end if;
12) if
$ TaskSet_j $ 为空;13)
$ T \gets T - T_j $ ;14) end if;
15) end while.
2.2 协同进化策略
协同进化是生物学中一种重要的进化机制
$, $ 可促进物种之间的信息交流并提高物种进化效率. 协同进化策略包括了合作式协同进化策略和竞争式协同进化策略两种类型[29]. 已有研究表明, 在优化算法中采用协同进化策略能够降低问题的求解难度, 加快算法的搜索效率, 提升算法的性能[30].KnCMPSO算法采用了子种群间合作式协同进化、子种群内竞争式协同进化的策略来生成新个体. 子种群合作式协同进化采用子问题与子种群一一对应的方式, 将多目标优化问题转为每一个维度上的单目标优化问题. 子种群内竞争式协同进化则采用子种群内的全局最优个体和外部档案集中的精英个体相互竞争的方式来选择较优的个体, 并利用该个体对子种群生成过程进行引导, 避免种群向极端点靠近. 其整体流程如图2所示. 针对一个M维的多目标优化问题, 算法生成M个子种群, 每个子种群分别针对每一个维度上的目标进行优化. 同时利用外部档案集Archive的方式保存迭代过程中寻找到的所有种群的非支配解, 从而实现种群之间搜索信息的共享.
图 2 种群间合作种群内竞争的协同进化策略Fig. 2 Coevolution strategy of inter-population cooperation and intra-population competition子种群间合作式协同进化是指将原始问题分别看作某一个维度上的单目标优化问题, 同时利用外部档案集保存迭代过程中的所有种群的非支配解. 由于子问题与子种群一一对应, 子种群平行且单独地进化, 降低了问题的求解复杂度. 在传统的多目标问题中, 当两个个体互不支配的时候, 无法确定哪一个更优, 导致算法无法选择个体最优粒子和全局最优粒子对当前个体进行更新操作. 采用子种群间合作式协同进化可以有效避免上述问题. 每个子种群根据当前维度目标值的大小来进行个体最优和全局最优的选择, 实现在该维度上的求解. 子种群内竞争式协同进化是指通过各个子种群中的全局最优个体和外部档案集中的精英个体之间竞争, 获取对子种群中的其他个体的引导权, 具体过程如算法2所示.
算法2. 基于竞争的个体更新策略
输入. 外部文档集
$ Archive $ , 全局最优个体$ Gbest $ , 当前个体的位置向量$ cS = (M_{cS},U_{cS},C_{cS}) $ .输出. 新个体的位置向量
$ nS = (M_{nS},U_{nS},C_{nS}) $ .1)在外部文档集中随机选择一个精英个体
$ A $ .2) if
$ \arccos(A,nS) < \arccos(Gbest,nS) $ ;3)将精英个体
$ A $ 作为待学习个体, 使用算法3对当前个体$ cS $ 进行更新, 得到新个体$ nS $ ;4) else;
5)将全局最优个体
$ Gbest $ 作为待学习个体, 使用算法3对当前个体$ cS $ 进行更新, 得到新个体$ nS $ ;6) end if.
如图3所示, 假设子种群1的优化目标为
$ f_1 $ ,$Gbest$ 为子种群1在迭代次数为$ t $ 时候全局最优个体, 待更新的个体为$ S $ . 首先, 在外部档案集中随机选择一个精英个体$ A $ . 计算个体$ A $ 和$ S $ 之间的余弦相似度; 然后, 与$Gbest$ 和$ S $ 之间的余弦相似度进行比较. 当$ A $ 与$ S $ 之间的余弦相似度更小时, 说明个体$ A $ 对个体$ S $ 的引导能力更强, 更有利于算法的收敛, 因此选择$ A $ 作为$ S $ 的全局学习对象; 反之, 选择$Gbest$ 作为$ S $ 的全局学习对象.上述两种协同进化策略不仅能降低问题的求解复杂度, 而且能有效提高算法的收敛速度.
2.3 基于学习的粒子更新策略
在标准粒子群算法中, 种群中的个体通过对个体最优粒子和全局最优个体进行学习来更新速度, 再通过粒子的当前位置和速度来更新粒子的状态. 本文模型中包含了混合变量, 并且约束条件较多, 按照标准粒子群的更新方式将很难生成满足约束的粒子, 所以本文将对粒子的更新方式进行改进, 不再使用粒子速度这一个概念, 粒子在更新的时候只通过向优秀个体学习的方式来更新粒子的状态. 基于此, 在KnCMPSO中提出了一种基于学习的粒子更新策略, 具体过程如算法3所示.
算法3. 基于学习的粒子更新策略
输入. 待学习个体的位置向量
$ lS = (M_{lS},U_{lS},C_{lS}) $ , 当前个体的位置向量$ cS = (M_{cS},U_{cS},C_{cS}) $ , 学习概率$ pro $ .输出. 新个体的位置向量
$ nS = (M_{nS},U_{nS},C_{nS}) $ .1)初始化新个体的位置向量
$ nS = (M_{nS},U_{nS},C_{nS}) $ ;2) for 目标
$ j, 0 \le j \le N_T $ ;3) if
$ random < pro $ ;4)将待学习个体
$ lS $ 位置向量第1行与当前目标j相等的三个位置上的值, 按照其在$ lS $ 位置向量中出现的先后次序依次插入到新个体$ nS $ 位置向量的对应位置;5)将各个任务对应的无人机以及无人机资源消耗量插入到
$ nS $ 位置向量的对应位置;6) end if;
7) end for;
8) for位置向量维度
$s,$ $ 0\le s \le nS $ ;9) if位置向量维度
$ s $ 为空;10)将当前个体
$ cS $ 中的目标、目标对应的无人机以及无人机资源使用量从左到右依次填入到新个体$ nS $ 位置向量中的空位置;11) end if;
12) end for.
图4中的
$ lS $ 表示待学习的个体,$ cS $ 表示当前个体,$ nS $ 代表经过学习方式之后生成的新个体. 整个学习过程如下: 首先, 初始化一个空的个体$ nS $ . 依次选择模型中的目标编号, 以一定的概率选择当前目标编号进行学习操作. 假设当前选中的目标编号为2, 则将待学习个体位置向量第1行与2相等的三个位置上的值, 按照其在$ lS $ 位置向量中出现的先后次序依次插入到新个体$ nS $ 位置向量的对应位置, 同时将各个任务对应的无人机以及无人机资源消耗量插入到位置向量的对应位置. 对目标编号进行一次遍历之后, 新个体$ nS $ 中非空位置保存的就是待学习个体$ lS $ 的信息. 然后, 将原始个体$ cS $ 中的目标、目标对应的无人机以及无人机资源使用量从左到右依次填入到新个体位置向量中的空位置, 跳过新个体$ nS $ 中已存在的目标.通过向优秀个体进行学习, 粒子位置向量将按照式(11)进行更新. 其中
$ X_i(t) $ 代表粒子$ i $ 在第t次迭代中的位置,$Pbest_i$ 为粒子在第t次迭代中的个体最优值,$ A $ 为外部档案集中的个体,$Gbest$ 为第t次迭代中的全局最优,$ w $ 为权重系数,$ competition $ 代表了粒子$ A $ 和$Gbest$ 相互竞争,$ F $ 代表了粒子向较优个体的学习过程.$$\begin{split} X_i(t+1) =\;& (1-w) \otimes F(w \otimes F(X_i(t),Pbest_i), \\ & competition(A,Gbest))\\[-10pt] \end{split} $$ (11) 2.4 基于区间扰动的局部搜索
如前所述, 采用上述基于学习的粒子更新策略对种群中的个体进行更新能够有效地对问题空间进行搜索, 但如果粒子在更新的时候只采用该策略对群体中较优的个体进行学习, 会导致算法在迭代后期陷入局部最优. 为了进一步提升种群的多样性以及算法的搜索能力, 本文进一步提出了一种基于扰动的局部搜索策略, 具体过程如算法4所示.
算法4. 基于区间扰动的局部搜索策略
输入. 当前个体的位置向量
$ cS = (M_{cS},U_{cS},C_{cS}) $ .输出. 新个体的位置向量
$ nS = (M_{nS},U_{nS},C_{nS}) $ .1)初始化新个体的位置向量
$ nS = (M_{nS},U_{nS},C_{nS}) $ ;2)随机选择一个任务
$ M_k $ ;3)根据
$ M_k $ 的任务类型, 找到任务$ M_k $ 可插入的范围$ [startPos, endPos] $ ;4)在
$ [startPos, endPos] $ 范围内随机选择任务插入的位置insertPos;5)将
$ M_k $ 插入位置向量中的$ insertPos $ , 其余位置的任务依次插入到$ nS $ 的$ [startPos, endPos] $ 范围中;6)重新设置完成任务
$ M_k $ 的无人机以及相应的资源消耗.具体实现方式见图5. 图5中
$ cS $ 代表当前个体,$ nS $ 代表执行完局部搜索策略之后生成的新个体. 按照一定的概率在个体$ cS $ 上随机选择某一个目标上的某一个任务$ k $ . 按照任务执行的时序约束找到任务$ k $ 可插入的位置范围$[startPos, endPos]$ . 图5中加下划线的方框表示随机选择的任务k, 两个灰色背景方框的位置从左往右分别为$ startPos $ 和$ endPos $ . 在此范围内随机选择任务插入的位置$ insertPos $ . 将任务k插入位置向量中的$ insertPos $ . 其余位置的任务依次插入到$ nS $ 的$ [startPos, endPos] $ 之中, 并重新设置完成任务$ k $ 的无人机以及相应的资源消耗. 需要指出的是, 任务类型应满足无人机作战类型约束, 即该任务如果是观测和打击结果的评估任务, 则只能选择侦察无人机集合中的无人机, 否则选择战斗无人机集合中的无人机. 此外, 所选择的无人机仍需满足资源约束和最大航程约束.2.5 基于拐点的外部档案集更新策略
将原始问题看作各个目标维度上的单目标优化问题, 虽然降低了问题的求解难度, 但是由于各个子种群分别优化某一个目标, 种群将会向每个目标维度上的极端点靠近. 最后得到的非支配解集也将更多地分布在各个目标维度的附近, 导致算法搜索不到帕累托面的中心部分, 降低算法的多样性. 如图6所示, 以两目标问题为例, 其中矩形点为极端点, 圆形点代表非支配解, 三角形点为支配解, 虚线框所在的区域为中心解集区域. 可以明显看出, 中心区域解集分布较少. 这是由于每一个子种群的全局最优为对应目标维度的极端点, 使得种群在不断迭代过程中大部分的解将向极端点靠近, 导致最后生成的非支配解集多样性不足.
为了使得外部档案集中的解集分布更加均匀, 同时提升算法的收敛性, 本文利用拐点来引导档案集中的其他精英个体的更新. 如图7所示, 点
$ B $ 和点$ C $ 为某个种群内部的边界点, 两者之间的连线为$ L $ , 通过计算种群中其他点到直线$ L $ 的距离, 选择距离最大的那个点作为拐点, 即点$ A $ . 对于三目标或者是超多目标问题, 边界点所构成的是一个平面或是超平面, 则拐点也被定义为距离这个平面或者是超平面最远的点. 本文所提的利用拐点更新外部档案集的方式如式(12)所示, 外部档案集中的个体向拐点学习更新位置向量.式(12)中
$ A_i $ 代表外部档案集$ Archive $ 中任意的一个精英个体,$ kneePt $ 代表拐点,$ F $ 为粒子向优秀个体的学习过程, 具体实现方式见第2.3节.$$ \begin{equation} A_i = F(A_i, kneePt) \end{equation} $$ (12) 3. 实验与结果分析
本文基于不同的任务数量和无人机类型设计了4种不同规模的实例并进行了仿真实验. 实验中的算法均采用Java编程, 运行环境为JDK1.8, 编译器为Eclipse, 处理器为主频3.6 GHz的Intel Core i7-4790.
3.1 仿真实例设计
本文设计了4种不同规模的实例, 其中实例1包含14台无人机和6个军事任务目标, 实例2包含16台无人机和12个军事任务目标, 实例3包含18台无人机和18个军事任务目标, 实例4包含20台无人机和24个军事任务目标. 各个实例中的任务目标被随机地设置在一个固定的位置, 每一个任务目标上包含了三种属性, 分别代表了完成此目标上的某一个军事任务所需要的资源量. 各个实例中的无人机同样的被随机地设置在一个固定的位置, 每一个无人机包括了飞行速度、最大携带弹药数目和最远飞行距离. 实例4中各个目标和无人机的属性设置情况如表5和表6所示, 其他3个实例见附录A. 上述实例包含不同规模、不同分布的无人机任务分配场景, 4个实例的示意图如图8所示. 其中, 实例1和实例2中的目标和无人机在军事区域内分布的相对集中且规模较小, 这意味着在任务分配时可选择的合适的无人机较多, 因此在实例1和实例2的目标空间中存在较多的局部最优解, 算法在实例1和实例2上的实验结果能反映算法求解多峰优化问题时的性能. 而实例3和实例4中目标和无人机的分布相对分散且规模更大, 算法在实例3和实例4上的实验结果能较好地反映算法求解模型的收敛性能. 通过在4个实例上做实验, 可以对算法的探索能力和勘探能力进行较全面的评估.
表 5 实例4中目标属性值Table 5 The target attribute value in example 4目标 坐标
(千米, 千米)观测时间
(秒)打击所需弹药数
(枚)评估时间
(秒)$T1$ (13, 41) 100 2 40 $T2$ (63, 83) 120 1 20 $T3$ (79, 12) 40 3 10 $T4$ (41, 98) 90 4 15 $T5$ (23, 65) 150 2 20 $T6$ (53, 19) 20 2 5 $T7$ (36, 49) 100 2 40 $T8$ (70, 47) 120 1 20 $T9$ (25, 15) 40 3 10 $T10$ (62, 89) 90 4 15 $T11$ (54, 42) 150 2 20 $T12$ (61, 39) 20 2 5 $T13$ (74, 29) 100 2 40 $T14$ (68, 33) 120 1 20 $T15$ (76, 38) 40 3 10 $T16$ (96, 26) 90 4 15 $T17$ (52, 55) 150 2 20 $T18$ (59, 98) 20 2 5 $T19$ (30, 43) 100 2 40 $T20$ (27, 82) 120 1 20 $T21$ (59, 13) 40 3 10 $T22$ (42, 28) 90 4 15 $T23$ (55, 39) 15 2 20 $T24$ (8, 46) 20 2 5 表 6 实例4中无人机属性值Table 6 Attribute value of drone in example 4无人机 坐标
(千米, 千米)无人机类型 携带弹药数
(枚)飞行速度
(千米/秒)$U1$ (57, 5) 侦察机 0 0.10 $U2$ (42, 8) 侦察机 0 0.12 $U3$ (50, 99) 侦察机 0 0.12 $U4$ (62, 25) 侦察机 0 0.11 $U5$ (20, 61) 侦察机 0 0.1 $U6$ (83, 46) 侦察机 0 0.12 $U7$ (56, 90) 侦察机 0 0.11 $U8$ (39, 45) 侦察机 0 0.11 $U9$ (58, 69) 侦察机 0 0.11 $U10$ (13, 86) 侦察机 0 0.1 $U11$ (5, 57) 侦察机 0 0.11 $U12$ (86, 46) 战斗机 11 0.13 $U13$ (89, 34) 战斗机 8 0.09 $U14$ (53, 11) 战斗机 10 0.11 $U15$ (92, 86) 战斗机 9 0.09 $U16$ (96, 18) 战斗机 12 0.11 $U17$ (73, 76) 战斗机 8 0.16 $U18$ (47, 56) 战斗机 7 0.16 $U19$ (56, 80) 战斗机 8 0.12 $U20$ (78, 4) 战斗机 9 0.16 其中军事任务目标和无人机的坐标单位为千米, 无人机飞行速度单位为千米/秒, 无人机最大飞机距离为2000千米. 无人机完成观测任务和打击结果评估任务的最大观测时间为60秒. 无人机完成一次打击任务最大消耗弹药数量为4枚.
3.2 对比算法和评价指标
为了验证KnCMPSO算法性能, 本文选取求解无人机协同任务分配问题的基于协同进化的混合变量多目标粒子群优化算法(Coevolution based mixed-variable multi-objective particle swarm optimization algorithm, C-MOPSO)[11]与3个具有代表性的基于协同进化的多种群粒子群优化算法(Coevolutionary multiswarm particle swarm optimization, CMPSO)[30]、基于协同进化的粒子群优化算法(Coevolutionary particle swarm optimization, CPSO)[31]和基于分解的协同进化多目标局部搜索算法(Coevolutionary multiobjective local search based on decomposition, CoMOLS/D)[32]进行对比实验. 所有算法的种群大小N设置为300, 最大迭代次数为500次, 外部档案集大小均为种群大小的二分之一. 同时采用超体积Hypervolum (HV)指标评价各个算法获得非支配解集的优劣. HV指标是一个综合性评价指标, 能够同时评估算法在收敛性和多样性上的表现. HV指标的数值越大, 表示算法在收敛性和多样性上的表现越好. 本文HV指标参考点设置为(15000, 15000).
3.3 实验结果与分析
为了使选取的各对比算法能够求解本文的模型, 上述对比算法均采用了与KnCMPSO相同的编码策略以及初始化方式. 需要指出的是, 为了保证实验结果的公平性, 除C-MOPSO算法之外, 其他的算法均采用本文所提出的粒子更新方式和局部搜索策略.
在实验过程中, 每个算法均将在上述无人机任务分配实例上执行30次独立实验. 各算法在所有实例上的HV指标数据如表7所示, 其中Mean表示各个算法30次实验计算得到的HV指标的平均值, 其大小反映算法求得的非支配解集的收敛性和多样性. Std表示各个算法30次实验计算得到的HV指标的方差, 其大小反映算法的稳定性. Best表示算法运行30次后得到的最优的HV值. Worst表示算法得到的最差HV值. 表7中各个测试函数上的最优结果加粗标注, 次优结果用下划线标注.
表 7 算法在各个实例上的HV值Table 7 The HV value of the algorithm on each example实例名称 HV CMPSO CoMOLS/D CPSO C-MOPSO KnCMPSO 实例 1 Mean ${\underline{1.941 \times 10^{8}}}$ $1.846\times10^8$ $1.934\times10^8$ $1.873\times10^8$ ${\bf 1.963}\times10^8$ Std ${\underline{1.326\times10^6}}$ $2.035\times10^6$ $1.574\times10^6$ $2.483\times10^6$ ${\bf{1.053\times10^6}}$ Worst ${\underline{1.918\times10^8}}$ $1.799\times10^8$ $1.893\times10^8$ $1.836\times10^8$ ${\bf{1.942\times10^8}}$ Best ${\underline{1.969\times10^8}}$ $1.881\times10^8$ $1.958\times10^8$ $1.937\times10^8$ ${\bf{1.982\times10^8}}$ 实例 2 Mean ${\underline{1.586\times10^8}}$ $1.312\times10^8$ $1.554\times10^8$ $1.371\times10^8$ ${\bf{1.629\times10^8}}$ Std ${\bf{2.916\times10^6}}$ $3.387\times10^6$ $3.158\times10^6$ $3.523\times10^6$ ${\underline{3.114\times10^6}}$ Worst ${\underline{1.525\times10^8}}$ $1.259\times10^8$ $1.494\times10^8$ $1.297\times10^8$ ${\bf{1.544\times10^8}}$ Best ${\underline{1.640\times10^8}}$ $1.371\times10^8$ $1.637\times10^8$ $1.464\times10^8$ ${\bf{1.675\times10^8}}$ 实例 3 Mean ${\underline{1.326\times10^8}}$ $9.365\times10^7$ $1.284\times10^8$ $1.032\times10^8$ ${\bf{1.387\times10^8}}$ Std ${\bf{3.133\times10^6}}$ $4.722\times10^6$ ${\underline{3.174\times10^6}}$ $4.292\times10^6$ $4.271\times10^6$ Worst ${\underline{1.265\times10^8}}$ $8.571\times10^7$ $1.208\times10^8$ $9.782\times10^7$ ${\bf{1.289\times10^8}}$ Best ${\underline{1.383\times10^8}}$ $1.029\times10^8$ $1.365\times10^8$ $1.130\times10^8$ ${\bf{1.487\times10^8}}$ 实例 4 Mean ${\underline{1.103\times10^8}}$ $6.209\times10^7$ $1.027\times10^8$ $7.068\times10^7$ ${\bf{1.151\times10^8}}$ Std $4.482\times10^6$ ${\underline{3.658\times10^6}}$ $4.850\times10^6$ ${\bf{3.056\times10^6}}$ $6.337\times10^6$ Worst ${\underline{9.913\times10^7}}$ $5.582\times10^7$ $9.023\times10^7$ $6.601\times10^7$ ${\bf{1.033\times10^8}}$ Best ${\underline{1.192\times10^8}}$ $6.970\times10^7$ $1.116\times10^8$ $7.631\times10^7$ ${\bf{1.241\times10^8}}$ 由表7可以看出, 相较于其他对比算法, KnCMPSO在4个实例上的HV指标的平均值上都能取得最优结果, 表明了算法在多样性和收敛性上均优于其他对比算法. 另外KnCMPSO算法求得HV指标中Std、Best和Worst值相比较于其他对比算法同样是占优的, 表明了KnCMPSO算法在稳定性上同样优于其他对比算法. 原因如下: 1) KnCMPSO利用协同进化的策略降低了问题的求解难度; 2)通过引入基于拐点的外部档案集更新策略增加了算法对帕累托前沿中心区域的搜索能力. CMPSO算法和CPSO算法虽然同样采用了协同进化策略, 但是在CMPSO和CPSO算法中极端点对个体的引导能力过于强烈, 导致最后生成的解集更多分布在各个目标维度极端解的附近, 算法的多样性受损. CoMOLS/D算法采用的权重和法和反转边界交叉惩罚均是基于权重向量的策略. 由于解集的好坏与权重向量的设置关系十分密切, 在求解帕累托前沿分布不均匀的实际问题上优势不明显. C-MOPSO算法针对无人机任务分配问题设计了基于结构学习的重组方法进行求解, 但是这种重组方法不确定性较大, 尤其是随着问题规模的不断变大, 算法的求解性能逐渐降低, 与C-MOPSO算法的对比证明了本文所提粒子更新方式和局部搜索策略的有效性.
为了更加直观展示算法在各个实例上的结果分布情况, 算法在每个实例上所得解集的分布情况如图9所示. 由图中各实例解集分布情况可以看出, 相比较于其他对比算法, 本文算法求解得到的解集不论是在多样性还是收敛性上都明显占优, 这与上述HV指标的评估结果一致.
图 9 算法在各实例上的解集的分布图Fig. 9 Distribution diagram of the solution set of the algorithm on each example通过上述实验结果中本文算法和其他算法HV指标性能表现, 以及5个算法在各个实例中的解集分布情况可以发现, 相比较于其他4个算法, 本文算法无论在收敛性方面还是多样性方面均明显占优, 充分证明了本文算法求解无人机协同多任务分配问题的有效性.
为了验证KnCMPSO算法所提基于学习的粒子更新策略的有效性, 本文将文献[11]的基于结构学习的生成算子(Structure learning reproduction, SLR)嵌入到KnCMPSO算法框架中, 记该算法为KnCMPSO-SLR, 与现有结果进行了对比, 对比结果见表8. 由表8可以看出, KnCMPSO在实例2上与KnCMPSO-SLR的结果相近, 但在实例1、实例3和实例4上都能取得最优结果, 表明该算法可以保持较好的多样性和收敛性, 其原因在于Kn-CMPSO-SLR采用基于结构学习的粒子更新策略只学习了父代个体的部分基因, 而KnCMPSO采用基于学习的粒子更新策略不仅学习父代个体, 还向精英个体或全局最优个体学习, 因此具有更好的收敛性能.
表 8 算法在各个实例上的HV值Table 8 The HV value of the algorithm on each example实例名称 HV KnCMPSO-SLR KnCMPSO 实例 1 Mean $1.951\times10^8$ ${\bf{1.974\times10^8}}$ Std ${\bf{7.942\times10^5}}$ $1.046\times10^6$ Worst $1.934\times10^8$ ${\bf{1.959\times10^8}}$ Best $1.961\times10^8 $ ${\bf{1.989\times10^8 }}$ 实例 2 Mean ${\bf{1.625\times10^8}}$ $1.622\times10^8$ Std $3.290\times10^6 $ ${\bf{1.632\times10^6}}$ Worst $1.569\times10^8 $ ${\bf{1.598\times10^8 }}$ Best ${\bf{1.690\times10^8}}$ $1.645\times10^8$ 实例 3 Mean $1.347\times10^8 $ ${\bf{1.395\times10^8}}$ Std ${\bf{2.031\times10^6}}$ $3.099\times10^6 $ Worst $1.318\times10^8 $ ${\bf{1.361\times10^8}}$ Best $1.385\times10^8 $ ${\bf{1.449\times10^8}}$ 实例 4 Mean $1.146\times10^8 $ ${\bf{1.184\times10^8}}$ Std ${\bf{2.251\times10^6}}$ $3.492\times10^6 $ Worst $1.087\times10^8$ ${\bf{1.124\times10^8}}$ Best $1.165\times10^8$ ${\bf{1.241\times10^8}}$ 同时, 考虑到本文求解实际问题的特殊性, Kn-CMPSO在解的初始化过程中提出了一种基于约束处理的初始化方法, 为了验证该方法的优越性, 本文选择采用其他3种经典约束处理方法与本文KnCMPSO算法框架结合构成新的算法, 包括与基于罚函数[18]的约束处理方法结合KnCMPSO-PF, 与基于可行性原则的约束处理方法[21]结合Kn-CMPSO-SR和与基于随机排序的约束处理方法结合KnCMPSO-FR[22], 并将这3种算法与本文算法进行实验对比, 实验结果见表9. 由表9可以看出, KnCMPSO在所有实例上均取得了最优结果, 这主要归因于KnCMPSO将约束处理融入到粒子初始化以及更新的过程中, 能有效地解决多种复杂约束, 保证算法迭代过程中生成的解都为可行解, 且在迭代过程中采用基于区间扰动的变异策略来提升种群的多样性, 提高了算法的搜索效率. 而其他算法在迭代过程中生成了部分不可行解, 导致算法搜索效率下降.
表 9 算法在各个实例上的HV值Table 9 The HV value of the algorithm on each example实例名称 HV KnCMPSO-PF KnCMPSO-FR KnCMPSO-SR KnCMPSO 实例 1 Mean ${\underline{1.800\times10^8}}$ $1.782\times10^8 $ $1.786\times10^8 $ ${\bf{1.861\times10^8}}$ Std ${\underline{3.005\times10^6}}$ $3.881\times10^6 $ $ 3.778\times10^6 $ ${\bf{1.948\times10^6 }}$ Worst ${\underline{1.721\times10^8}}$ $1.703\times10^8$ $1.705\times10^8 $ ${\bf{1.800\times10^8}}$ Best ${\underline{1.860\times10^8}}$ $1.837\times10^8$ $1.839\times10^8 $ ${\bf{1.898\times10^8}}$ 实例 2 Mean ${\underline{1.362\times10^8}}$ $1.346\times10^8$ $1.356\times10^8 $ ${\bf{1.449\times10^8}}$ Std ${\underline{4.110\times10^6}}$ ${\bf{3.981\times10^6}}$ $4.166\times10^6 $ $4.562\times10^6 $ Worst $1.275\times10^8 $ $1.257\times10^8$ ${\underline{1.296\times10^8}}$ ${\bf{1.362\times10^8}}$ Best $1.435\times10^8$ $1.426\times10^8$ ${\underline{1.453\times10^8}}$ ${\bf{1.529\times10^8}}$ 实例 3 Mean ${\underline{1.046\times10^8 }}$ $1.036\times10^8$ $1.003\times10^8 $ ${\bf{1.175\times10^8}}$ Std $4.892\times10^6$ $6.045\times10^6$ ${\underline{4.629\times10^6}}$ ${\bf{4.027\times10^6}}$ Worst ${\underline{9.602\times10^7}}$ $8.900\times10^7$ $8.618\times10^7$ ${\bf{1.112\times10^8}}$ Best ${\underline{1.145\times10^8}}$ $1.139\times10^8$ $1.066\times10^8$ ${\bf{1.243\times10^8}}$ 实例 4 Mean ${\underline{7.920\times10^7}}$ $7.851\times10^7$ $7.833\times10^7$ ${\bf{9.603\times10^7}}$ Std $6.365\times10^6$ $6.608\times10^6$ ${\underline{6.008\times10^6}}$ ${\bf{5.376\times10^6}}$ Worst ${\underline{6.537\times10^7}}$ $6.412\times10^7$ $6.007\times10^7 $ ${\bf{8.466\times10^7}}$ Best ${\underline{9.105\times10^7}}$ $8.916\times10^7$ $8.653\times10^7$ ${\bf{1.045\times10^8}}$ 4. 结束语
本文以异构无人机协同作战为背景, 针对无人机协同多任务分配问题建立了包含多种约束条件的异构无人机协同多任务分配问题模型. 为了求解此模型, 本文提出了基于拐点的协同多目标粒子群优化算法KnCMPSO, 并设计了4种不同规模的实例进行仿真实验. 实验结果显示本文所提的算法在多样性和收敛性上均优于其他的对比算法, 表明本文所提算法能够有效求解无人机协同多任务分配问题.
KnCMPSO算法采用混合编码方式以及基于约束处理的初始化方法, 能有效避免不可行解的生成, 采用协同进化策略将多目标优化问题转为各目标维度上的单目标优化问题, 同时设计相应的搜索策略提升算法的收敛性和多样性, 因此可以很好地适用于多目标多约束的无人机任务分配问题. 但由于KnCMPSO算法的编码和搜索策略是根据异构无人机任务分配问题的特性进行设计, 对于其他的多目标多约束混合变量优化问题, 还需研究特定的编码方式和搜索策略来进行求解.
本文提出的模型虽然考虑了更加符合实际情况的约束条件和目标函数, 但是相比于现实作战环境的复杂性还存在一定的差距, 为了更进一步提高任务分配模型的有效性, 未来在构建无人机任务分配模型时将考虑更多符合实际的约束条件和目标函数.
附录A
表A1和表A2分别展示了实例3的目标和无人机的各种属性. 表A3和表A4分别展示了实例2的目标和无人机的各种属性. 表A5和表A6分别展示了实例1的目标和无人机的各种属性.
表 A1 实例3中目标属性值Table A1 The target attribute value in example 3目标 坐标
(千米, 千米)观测时间
(秒)打击所需弹药数
(枚)评估时间
(秒)$T1$ (13, 41) 100 2 40 $T2$ (63, 83) 120 1 20 $T3$ (79, 12) 40 3 10 $T4$ (41, 98) 90 4 15 $T5$ (23, 65) 150 2 20 $T6$ (53, 19) 20 2 5 $T7$ (36, 49) 100 2 40 $T8$ (70, 47) 120 1 20 $T9$ (25, 15) 40 3 10 $T10$ (62, 89) 90 4 15 $T11$ (54, 42) 150 2 20 $T12$ (61, 39) 20 2 5 $T13$ (74, 29) 100 2 40 $T14$ (68, 33) 120 1 20 $T15$ (76, 38) 40 3 10 $T16$ (96, 26) 90 4 15 $T17$ (52, 55) 150 2 20 $T18$ (59, 98) 20 2 5 表 A2 实例3中无人机属性值Table A2 Attribute value of drone in example 3无人机 坐标
(千米, 千米)无人机类型 携带弹药数
(枚)飞行速度
(千米/秒)$U1$ (57, 5) 侦察机 0 0.10 $U2$ (42, 8) 侦察机 0 0.12 $U3$ (50, 99) 侦察机 0 0.12 $U4$ (62, 25) 侦察机 0 0.11 $U5$ (20, 61) 侦察机 0 0.10 $U6$ (83, 46) 侦察机 0 0.12 $U7$ (56, 90) 侦察机 0 0.11 $U8$ (39, 45) 侦察机 0 0.11 $U9$ (58, 69) 侦察机 0 0.11 $U10$ (13, 86) 侦察机 0 0.10 $U11$ (56, 80) 战斗机 8 0.12 $U12$ (86, 46) 战斗机 9 0.13 $U13$ (89, 34) 战斗机 7 0.09 $U14$ (53, 11) 战斗机 9 0.11 $U15$ (92, 86) 战斗机 7 0.09 $U16$ (96, 18) 战斗机 9 0.11 $U17$ (73, 76) 战斗机 7 0.16 $U18$ (47, 56) 战斗机 5 0.16 表 A3 实例2中目标属性值Table A3 The target attribute value in example 2目标 坐标
(千米, 千米)观测时间
(秒)打击所需弹药数
(枚)评估时间
(秒)$T1$ (13, 41) 100 2 40 $T2$ (63, 83) 120 1 20 $T3$ (79, 12) 40 3 10 $T4$ (41, 98) 90 4 15 $T5$ (23, 65) 150 2 20 $T6$ (53, 19) 20 2 5 $T7$ (36, 49) 100 2 40 $T8$ (70, 47) 120 1 20 $T9$ (25, 15) 40 3 10 $T10$ (62, 89) 90 4 15 $T11$ (54, 42) 150 2 20 $T12$ (61, 39) 20 2 5 表 A4 实例2中无人机属性值Table A4 Attribute value of drone in example 2无人机 坐标
(千米, 千米)无人机类型 携带弹药数
(枚)飞行速度
(千米/秒)$U1$ (73, 91) 侦察机 0 0.10 $U2$ (65, 64) 侦察机 0 0.12 $U3$ (56, 37) 侦察机 0 0.12 $U4$ (36, 96) 侦察机 0 0.11 $U5$ (20, 0) 侦察机 0 0.10 $U6$ (1, 68) 侦察机 0 0.12 $U7$ (51, 74) 侦察机 0 0.11 $U8$ (58, 69) 侦察机 0 0.11 $U9$ (13, 86) 侦察机 0 0.10 $U10$ (69, 20) 战斗机 10 0.10 $U11$ (52, 46) 战斗机 6 0.12 $U12$ (46, 98) 战斗机 7 0.13 $U13$ (92, 86) 战斗机 5 0.09 $U14$ (96, 18) 战斗机 7 0.11 $U15$ (73, 76) 战斗机 5 0.16 $U16$ (47, 56) 战斗机 5 0.16 表 A5 实例1中目标属性值Table A5 The target attribute value in example 1目标 坐标
(千米, 千米)观测时间
(秒)打击所需弹药数
(枚)评估时间
(秒)$T1$ (36, 49) 100 2 40 $T2$ (70, 47) 120 1 20 $T3$ (25, 15) 40 3 10 $T4$ (62, 89) 90 4 15 $T5$ (54, 42) 150 2 20 $T6$ (61, 39) 20 2 5 表 A6 实例1中无人机属性值Table A6 Attribute value of drone in example 1无人机 坐标
(千米, 千米)无人机类型 携带弹药数
(枚)飞行速度
(千米/秒)$U1$ (73, 91) 侦察机 0 0.10 $U2$ (94, 92) 侦察机 0 0.12 $U3$ (56, 37) 侦察机 0 0.12 $U4$ (5, 57) 侦察机 0 0.11 $U5$ (20, 0) 侦察机 0 0.10 $U6$ (1, 68) 侦察机 0 0.12 $U7$ (51, 74) 侦察机 0 0.11 $U8$ (11, 90) 侦察机 0 0.11 $U9$ (73, 76) 战斗机 5 0.16 $U10$ (69, 20) 战斗机 10 0.10 $U11$ (52, 46) 战斗机 6 0.12 $U12$ (46, 98) 战斗机 7 0.13 $U13$ (92, 86) 战斗机 5 0.09 $U14$ (79, 4) 战斗机 7 0.11 -
图 2 种群间合作种群内竞争的协同进化策略
Fig. 2 Coevolution strategy of inter-population cooperation and intra-population competition
图 9 算法在各实例上的解集的分布图
Fig. 9 Distribution diagram of the solution set of the algorithm on each example
表 1 符号说明
Table 1 Symbol description
类别 属性 侦察无人机总数$S$ 战斗无人机总数$A$ 初始位置$P_i = (x_i, y_i)$ 飞行速度$V_i$ 无人机$U$ 战斗无人机最大携弹数目$Load_i$ 战斗无人机单次任务最大发射弹药数目$Launch_i$ 侦察无人机单次任务最大侦察时间$T_i$ 无人机最大飞行距离${\rm{Max}}Dis_i$ 无人机$U_i$执行任务$M_k$消耗的资源$C_i^k$ 目标总个数$N_T$ 目标位置坐标$P_j = (x_j, y_j)$ 目标$T$ 目标$j$的任务个数$N_M^j=3$ 任务总个数$N_M=3 \times N_T$ 任务$M$ 任务完成所需资源$CR_k$ 
下载: 导出CSV
表 2 粒子编码方式
Table 2 Particle encoding scheme
目标编号$T$ 1 2 2 1 3 1 3 2 3 无人机编号$U$ 1 3 2 3 4 5 6 5 6 1 2 4 1 2 3 资源消耗$C$ 2.4 2.6 1.1 4.9 2.0 1.0 1.0 2.0 1.0 5.0 3.0 2.0 3.0 0.2 1.1
下载: 导出CSV
表 3 目标队列集合
Table 3 Target formation collection
1 2 3 $\cdots $ $N$ $T_1^O$ $T_2^O$ $T_3^O$ $\cdots $ $T_N^O$ $T_1^A$ $T_2^A$ $T_3^A$ $\cdots $ $T_N^A$ $T_1^E$ $T_2^E$ $T_3^E$ $\cdots $ $T_N^E$
下载: 导出CSV
表 4 无人机集合
Table 4 Drone collection
侦察机$U_S$ $U_1,U_2,\cdots,U_S$ 战斗机$U_A$ $U_{S+1},U_{S+2},\cdots,U_{S+A}$
下载: 导出CSV
表 5 实例4中目标属性值
Table 5 The target attribute value in example 4
目标 坐标
(千米, 千米)观测时间
(秒)打击所需弹药数
(枚)评估时间
(秒)$T1$ (13, 41) 100 2 40 $T2$ (63, 83) 120 1 20 $T3$ (79, 12) 40 3 10 $T4$ (41, 98) 90 4 15 $T5$ (23, 65) 150 2 20 $T6$ (53, 19) 20 2 5 $T7$ (36, 49) 100 2 40 $T8$ (70, 47) 120 1 20 $T9$ (25, 15) 40 3 10 $T10$ (62, 89) 90 4 15 $T11$ (54, 42) 150 2 20 $T12$ (61, 39) 20 2 5 $T13$ (74, 29) 100 2 40 $T14$ (68, 33) 120 1 20 $T15$ (76, 38) 40 3 10 $T16$ (96, 26) 90 4 15 $T17$ (52, 55) 150 2 20 $T18$ (59, 98) 20 2 5 $T19$ (30, 43) 100 2 40 $T20$ (27, 82) 120 1 20 $T21$ (59, 13) 40 3 10 $T22$ (42, 28) 90 4 15 $T23$ (55, 39) 15 2 20 $T24$ (8, 46) 20 2 5
下载: 导出CSV
表 6 实例4中无人机属性值
Table 6 Attribute value of drone in example 4
无人机 坐标
(千米, 千米)无人机类型 携带弹药数
(枚)飞行速度
(千米/秒)$U1$ (57, 5) 侦察机 0 0.10 $U2$ (42, 8) 侦察机 0 0.12 $U3$ (50, 99) 侦察机 0 0.12 $U4$ (62, 25) 侦察机 0 0.11 $U5$ (20, 61) 侦察机 0 0.1 $U6$ (83, 46) 侦察机 0 0.12 $U7$ (56, 90) 侦察机 0 0.11 $U8$ (39, 45) 侦察机 0 0.11 $U9$ (58, 69) 侦察机 0 0.11 $U10$ (13, 86) 侦察机 0 0.1 $U11$ (5, 57) 侦察机 0 0.11 $U12$ (86, 46) 战斗机 11 0.13 $U13$ (89, 34) 战斗机 8 0.09 $U14$ (53, 11) 战斗机 10 0.11 $U15$ (92, 86) 战斗机 9 0.09 $U16$ (96, 18) 战斗机 12 0.11 $U17$ (73, 76) 战斗机 8 0.16 $U18$ (47, 56) 战斗机 7 0.16 $U19$ (56, 80) 战斗机 8 0.12 $U20$ (78, 4) 战斗机 9 0.16
下载: 导出CSV
表 7 算法在各个实例上的HV值
Table 7 The HV value of the algorithm on each example
实例名称 HV CMPSO CoMOLS/D CPSO C-MOPSO KnCMPSO 实例 1 Mean ${\underline{1.941 \times 10^{8}}}$ $1.846\times10^8$ $1.934\times10^8$ $1.873\times10^8$ ${\bf 1.963}\times10^8$ Std ${\underline{1.326\times10^6}}$ $2.035\times10^6$ $1.574\times10^6$ $2.483\times10^6$ ${\bf{1.053\times10^6}}$ Worst ${\underline{1.918\times10^8}}$ $1.799\times10^8$ $1.893\times10^8$ $1.836\times10^8$ ${\bf{1.942\times10^8}}$ Best ${\underline{1.969\times10^8}}$ $1.881\times10^8$ $1.958\times10^8$ $1.937\times10^8$ ${\bf{1.982\times10^8}}$ 实例 2 Mean ${\underline{1.586\times10^8}}$ $1.312\times10^8$ $1.554\times10^8$ $1.371\times10^8$ ${\bf{1.629\times10^8}}$ Std ${\bf{2.916\times10^6}}$ $3.387\times10^6$ $3.158\times10^6$ $3.523\times10^6$ ${\underline{3.114\times10^6}}$ Worst ${\underline{1.525\times10^8}}$ $1.259\times10^8$ $1.494\times10^8$ $1.297\times10^8$ ${\bf{1.544\times10^8}}$ Best ${\underline{1.640\times10^8}}$ $1.371\times10^8$ $1.637\times10^8$ $1.464\times10^8$ ${\bf{1.675\times10^8}}$ 实例 3 Mean ${\underline{1.326\times10^8}}$ $9.365\times10^7$ $1.284\times10^8$ $1.032\times10^8$ ${\bf{1.387\times10^8}}$ Std ${\bf{3.133\times10^6}}$ $4.722\times10^6$ ${\underline{3.174\times10^6}}$ $4.292\times10^6$ $4.271\times10^6$ Worst ${\underline{1.265\times10^8}}$ $8.571\times10^7$ $1.208\times10^8$ $9.782\times10^7$ ${\bf{1.289\times10^8}}$ Best ${\underline{1.383\times10^8}}$ $1.029\times10^8$ $1.365\times10^8$ $1.130\times10^8$ ${\bf{1.487\times10^8}}$ 实例 4 Mean ${\underline{1.103\times10^8}}$ $6.209\times10^7$ $1.027\times10^8$ $7.068\times10^7$ ${\bf{1.151\times10^8}}$ Std $4.482\times10^6$ ${\underline{3.658\times10^6}}$ $4.850\times10^6$ ${\bf{3.056\times10^6}}$ $6.337\times10^6$ Worst ${\underline{9.913\times10^7}}$ $5.582\times10^7$ $9.023\times10^7$ $6.601\times10^7$ ${\bf{1.033\times10^8}}$ Best ${\underline{1.192\times10^8}}$ $6.970\times10^7$ $1.116\times10^8$ $7.631\times10^7$ ${\bf{1.241\times10^8}}$
下载: 导出CSV
表 8 算法在各个实例上的HV值
Table 8 The HV value of the algorithm on each example
实例名称 HV KnCMPSO-SLR KnCMPSO 实例 1 Mean $1.951\times10^8$ ${\bf{1.974\times10^8}}$ Std ${\bf{7.942\times10^5}}$ $1.046\times10^6$ Worst $1.934\times10^8$ ${\bf{1.959\times10^8}}$ Best $1.961\times10^8 $ ${\bf{1.989\times10^8 }}$ 实例 2 Mean ${\bf{1.625\times10^8}}$ $1.622\times10^8$ Std $3.290\times10^6 $ ${\bf{1.632\times10^6}}$ Worst $1.569\times10^8 $ ${\bf{1.598\times10^8 }}$ Best ${\bf{1.690\times10^8}}$ $1.645\times10^8$ 实例 3 Mean $1.347\times10^8 $ ${\bf{1.395\times10^8}}$ Std ${\bf{2.031\times10^6}}$ $3.099\times10^6 $ Worst $1.318\times10^8 $ ${\bf{1.361\times10^8}}$ Best $1.385\times10^8 $ ${\bf{1.449\times10^8}}$ 实例 4 Mean $1.146\times10^8 $ ${\bf{1.184\times10^8}}$ Std ${\bf{2.251\times10^6}}$ $3.492\times10^6 $ Worst $1.087\times10^8$ ${\bf{1.124\times10^8}}$ Best $1.165\times10^8$ ${\bf{1.241\times10^8}}$
下载: 导出CSV
表 9 算法在各个实例上的HV值
Table 9 The HV value of the algorithm on each example
实例名称 HV KnCMPSO-PF KnCMPSO-FR KnCMPSO-SR KnCMPSO 实例 1 Mean ${\underline{1.800\times10^8}}$ $1.782\times10^8 $ $1.786\times10^8 $ ${\bf{1.861\times10^8}}$ Std ${\underline{3.005\times10^6}}$ $3.881\times10^6 $ $ 3.778\times10^6 $ ${\bf{1.948\times10^6 }}$ Worst ${\underline{1.721\times10^8}}$ $1.703\times10^8$ $1.705\times10^8 $ ${\bf{1.800\times10^8}}$ Best ${\underline{1.860\times10^8}}$ $1.837\times10^8$ $1.839\times10^8 $ ${\bf{1.898\times10^8}}$ 实例 2 Mean ${\underline{1.362\times10^8}}$ $1.346\times10^8$ $1.356\times10^8 $ ${\bf{1.449\times10^8}}$ Std ${\underline{4.110\times10^6}}$ ${\bf{3.981\times10^6}}$ $4.166\times10^6 $ $4.562\times10^6 $ Worst $1.275\times10^8 $ $1.257\times10^8$ ${\underline{1.296\times10^8}}$ ${\bf{1.362\times10^8}}$ Best $1.435\times10^8$ $1.426\times10^8$ ${\underline{1.453\times10^8}}$ ${\bf{1.529\times10^8}}$ 实例 3 Mean ${\underline{1.046\times10^8 }}$ $1.036\times10^8$ $1.003\times10^8 $ ${\bf{1.175\times10^8}}$ Std $4.892\times10^6$ $6.045\times10^6$ ${\underline{4.629\times10^6}}$ ${\bf{4.027\times10^6}}$ Worst ${\underline{9.602\times10^7}}$ $8.900\times10^7$ $8.618\times10^7$ ${\bf{1.112\times10^8}}$ Best ${\underline{1.145\times10^8}}$ $1.139\times10^8$ $1.066\times10^8$ ${\bf{1.243\times10^8}}$ 实例 4 Mean ${\underline{7.920\times10^7}}$ $7.851\times10^7$ $7.833\times10^7$ ${\bf{9.603\times10^7}}$ Std $6.365\times10^6$ $6.608\times10^6$ ${\underline{6.008\times10^6}}$ ${\bf{5.376\times10^6}}$ Worst ${\underline{6.537\times10^7}}$ $6.412\times10^7$ $6.007\times10^7 $ ${\bf{8.466\times10^7}}$ Best ${\underline{9.105\times10^7}}$ $8.916\times10^7$ $8.653\times10^7$ ${\bf{1.045\times10^8}}$
下载: 导出CSV
A1 实例3中目标属性值
A1 The target attribute value in example 3
目标 坐标
(千米, 千米)观测时间
(秒)打击所需弹药数
(枚)评估时间
(秒)$T1$ (13, 41) 100 2 40 $T2$ (63, 83) 120 1 20 $T3$ (79, 12) 40 3 10 $T4$ (41, 98) 90 4 15 $T5$ (23, 65) 150 2 20 $T6$ (53, 19) 20 2 5 $T7$ (36, 49) 100 2 40 $T8$ (70, 47) 120 1 20 $T9$ (25, 15) 40 3 10 $T10$ (62, 89) 90 4 15 $T11$ (54, 42) 150 2 20 $T12$ (61, 39) 20 2 5 $T13$ (74, 29) 100 2 40 $T14$ (68, 33) 120 1 20 $T15$ (76, 38) 40 3 10 $T16$ (96, 26) 90 4 15 $T17$ (52, 55) 150 2 20 $T18$ (59, 98) 20 2 5
下载: 导出CSV
A2 实例3中无人机属性值
A2 Attribute value of drone in example 3
无人机 坐标
(千米, 千米)无人机类型 携带弹药数
(枚)飞行速度
(千米/秒)$U1$ (57, 5) 侦察机 0 0.10 $U2$ (42, 8) 侦察机 0 0.12 $U3$ (50, 99) 侦察机 0 0.12 $U4$ (62, 25) 侦察机 0 0.11 $U5$ (20, 61) 侦察机 0 0.10 $U6$ (83, 46) 侦察机 0 0.12 $U7$ (56, 90) 侦察机 0 0.11 $U8$ (39, 45) 侦察机 0 0.11 $U9$ (58, 69) 侦察机 0 0.11 $U10$ (13, 86) 侦察机 0 0.10 $U11$ (56, 80) 战斗机 8 0.12 $U12$ (86, 46) 战斗机 9 0.13 $U13$ (89, 34) 战斗机 7 0.09 $U14$ (53, 11) 战斗机 9 0.11 $U15$ (92, 86) 战斗机 7 0.09 $U16$ (96, 18) 战斗机 9 0.11 $U17$ (73, 76) 战斗机 7 0.16 $U18$ (47, 56) 战斗机 5 0.16
下载: 导出CSV
A3 实例2中目标属性值
A3 The target attribute value in example 2
目标 坐标
(千米, 千米)观测时间
(秒)打击所需弹药数
(枚)评估时间
(秒)$T1$ (13, 41) 100 2 40 $T2$ (63, 83) 120 1 20 $T3$ (79, 12) 40 3 10 $T4$ (41, 98) 90 4 15 $T5$ (23, 65) 150 2 20 $T6$ (53, 19) 20 2 5 $T7$ (36, 49) 100 2 40 $T8$ (70, 47) 120 1 20 $T9$ (25, 15) 40 3 10 $T10$ (62, 89) 90 4 15 $T11$ (54, 42) 150 2 20 $T12$ (61, 39) 20 2 5
下载: 导出CSV
A4 实例2中无人机属性值
A4 Attribute value of drone in example 2
无人机 坐标
(千米, 千米)无人机类型 携带弹药数
(枚)飞行速度
(千米/秒)$U1$ (73, 91) 侦察机 0 0.10 $U2$ (65, 64) 侦察机 0 0.12 $U3$ (56, 37) 侦察机 0 0.12 $U4$ (36, 96) 侦察机 0 0.11 $U5$ (20, 0) 侦察机 0 0.10 $U6$ (1, 68) 侦察机 0 0.12 $U7$ (51, 74) 侦察机 0 0.11 $U8$ (58, 69) 侦察机 0 0.11 $U9$ (13, 86) 侦察机 0 0.10 $U10$ (69, 20) 战斗机 10 0.10 $U11$ (52, 46) 战斗机 6 0.12 $U12$ (46, 98) 战斗机 7 0.13 $U13$ (92, 86) 战斗机 5 0.09 $U14$ (96, 18) 战斗机 7 0.11 $U15$ (73, 76) 战斗机 5 0.16 $U16$ (47, 56) 战斗机 5 0.16
下载: 导出CSV
A5 实例1中目标属性值
A5 The target attribute value in example 1
目标 坐标
(千米, 千米)观测时间
(秒)打击所需弹药数
(枚)评估时间
(秒)$T1$ (36, 49) 100 2 40 $T2$ (70, 47) 120 1 20 $T3$ (25, 15) 40 3 10 $T4$ (62, 89) 90 4 15 $T5$ (54, 42) 150 2 20 $T6$ (61, 39) 20 2 5
下载: 导出CSV
A6 实例1中无人机属性值
A6 Attribute value of drone in example 1
无人机 坐标
(千米, 千米)无人机类型 携带弹药数
(枚)飞行速度
(千米/秒)$U1$ (73, 91) 侦察机 0 0.10 $U2$ (94, 92) 侦察机 0 0.12 $U3$ (56, 37) 侦察机 0 0.12 $U4$ (5, 57) 侦察机 0 0.11 $U5$ (20, 0) 侦察机 0 0.10 $U6$ (1, 68) 侦察机 0 0.12 $U7$ (51, 74) 侦察机 0 0.11 $U8$ (11, 90) 侦察机 0 0.11 $U9$ (73, 76) 战斗机 5 0.16 $U10$ (69, 20) 战斗机 10 0.10 $U11$ (52, 46) 战斗机 6 0.12 $U12$ (46, 98) 战斗机 7 0.13 $U13$ (92, 86) 战斗机 5 0.09 $U14$ (79, 4) 战斗机 7 0.11
下载: 导出CSV
-
[1] 杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述. 自动化学报, 2022, 46(2): 222-241Du Yong-Hao, Xing Li-Ning, Cai Zhao-Quan. Summary of intelligent dispatching technology of unmanned aerial vehicle cluster. Acta Automatica Sinica, 2020, 46(2): 222-241 [2] Deng Q B, Yu J Q, Wang N F. Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes. Chinese Journal of Aeronautics, 2013, 26(5): 1238-1250 doi: 10.1016/j.cja.2013.07.009 [3] 贾高伟, 王建峰. 无人机集群任务规划方法研究综述. 系统工程与电子技术, 2021, 43(1): 99-111 doi: 10.3969/j.issn.1001-506X.2021.01.13Jia Gao-Wei, Wang Jian-Feng. Overview of research on UAV cluster mission planning methods. Systems Engineering and Electronics, 2021, 43(1): 99-111 doi: 10.3969/j.issn.1001-506X.2021.01.13 [4] Shima T, Rasmussen S J, Sparks A G, Passino K M. Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms. Computers & Operations Research, 2006, 33(11): 3252-3269 [5] 黄刚, 李军华. 基于AC-DSDE进化算法多UAVs协同目标分配. 自动化学报, 2021, 47(1): 173-184Huang Gang, Li Jun-Hua. Multi-UAV cooperative target allocation based on AC-DSDE evolutionary algorithm. Acta Automatica Sinica, 2021, 47(1): 173-184 [6] Huang L W, Qu H, Zuo L. Multi-type UAVs cooperative task allocation under resource constraints. IEEE Access, 2013, 6: 17841-17850 [7] Ye F, Chen J, Tian Y, Jiang T. Cooperative task assignment of a heterogeneous multi-UAV system using an adaptive genetic algorithm. Electronics, 2020, 9(4): 687-703 doi: 10.3390/electronics9040687 [8] Xu G T, Liu L, Long T, Wang Z, Cai M. Cooperative multiple task assignment considering precedence constraints using multi-chromosome encoded genetic algorithm. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference. Kissimmee, USA: 2018. 1859−1867 [9] Lei C, He S T, Hui P, Ming C P. Multiple UAVs hierarchical dynamic task allocation based on PSO-FSA and decentralized auction. In: Proceedings of the IEEE International Conference on Robotics and Biomimetics. Bali, Indonesia: IEEE, 2014. 2368−2373 [10] 韩博文, 姚佩阳, 孙昱. 基于多目标MSQPSO算法的UAVS协同任务分配. 电子学报, 2017, 45(8): 1856-1863 doi: 10.3969/j.issn.0372-2112.2017.08.008Han Bo-Wen, Yao Pei-Yang, Sun Yu. UAVS cooperative task allocation based on multi-objective MSQPSO algorithm. Acta Electronica Sinica, 2017, 45(8): 1856-1863 doi: 10.3969/j.issn.0372-2112.2017.08.008 [11] 王峰, 张衡, 韩孟臣, 邢立宁. 基于协同进化的混合变量多目标粒子群优化算法求解无人机协同多任务分配问题. 计算机学报, 2021, 44(10): 1967-1983 doi: 10.11897/SP.J.1016.2021.01967Wang Feng, Zhang Heng, Han Meng-Chen, Xing Li-Ning. Hybrid variable multi-objective particle swarm optimization algorithm based on co-evolution to solve UAV cooperative multi-task assignment problem. Chinese Journal of Computers, 2021, 44(10): 1967-1983 doi: 10.11897/SP.J.1016.2021.01967 [12] 杜永浩, 邢立宁, 姚锋, 陈盈果. 航天器任务调度模型、算法与通用求解技术综述. 自动化学报, 2021, 47(12): 2715-2741Du Yong-Hao, Xing Li-Ning, Yao Feng, Chen Ying-Guo. Survey on models, algorithms and general techniques for spacecraft mission scheduling. Acta Automatica Sinica, 2021, 47(12): 2715-2741 [13] Shi Y, Eberhart R. A modified particle swarm optimizer. In: Proceedings of the IEEE International Conference on Evolutionary Computation. Anchorage, USA: IEEE, 1998. 69−73 [14] 梁国强, 康宇航, 邢志川, 尹高扬. 基于离散粒子群优化的无人机协同多任务分配. 计算机仿真, 2018, 35(02): 22-28 doi: 10.3969/j.issn.1006-9348.2018.02.005Liang Guo-Qiang, Kang Yu-Hang, Xing Zhi-Chuan, Yin Gao-Yang. Cooperative multitask assignment of UAV based on discrete particle swarm optimization. Computer Simulation, 2018, 35(02): 22-28 doi: 10.3969/j.issn.1006-9348.2018.02.005 [15] 邓可, 连振江, 周德云, 李枭扬. 基于改进量子粒子群算法的多无人机任务分配. 指挥控制与仿真, 2018, 40(05): 32-36 doi: 10.3969/j.issn.1673-3819.2018.05.007Deng Ke, Lian Zhen-Jiang, Zhou De-Yun, Li Xiao-Yang. Multi-UAV task allocation based on improved quantum particle swarm algorithm. Command Control and Simulation, 2018, 40(05): 32-36 doi: 10.3969/j.issn.1673-3819.2018.05.007 [16] Wang J F, Jia G W, Lin J C, Hou Z X. Cooperative task allocation for heterogeneous multi-UAV using multi-objective optimization algorithm. Journal of Central South University, 2020, 27(2): 432-448 doi: 10.1007/s11771-020-4307-0 [17] 田震, 王晓芳. 基于多基因遗传算法的异构多无人机协同任务分配. 飞行力学, 2019, 37(01): 39-44Tian Zhen, Wang Xiao-Fang. Cooperative multiple task assignment for heterogeneous multi-UAVs with multi-chromosome genetic algorithm. Flight Dynamics, 2019, 37(01): 39-44 [18] He C, Cheng R, Tian Y, Zhang X Y, Tan K C, Jin Y C. Paired offspring generation for constrained large-scale multiobjective optimization. IEEE Transactions on Evolutionary Computation, 2020, 25(3): 448-462 [19] Wang F, Li Y, Zhou A M, Tang K. An estimation of distribution algorithm for mixed-variable newsvendor problems. IEEE Transactions on Evolutionary Computation, 2019, 24(3): 479-493 [20] Chen W N, Jia Y H, Zhao F, Luo X N, Jia X D, Zhang J. A cooperative co-evolutionary approach to large-scale multisource water distribution network optimization. IEEE Transactions on Evolutionary Computation, 2019, 23(5): 842-857 doi: 10.1109/TEVC.2019.2893447 [21] Menchaca-Méndez A, Montero E, Antonio L M, Zapotecas-Martínez S, Coello C A C, Riff M C. A co-evolutionary scheme for multi-objective evolutionary algorithms based on ϵ-dominance. IEEE Access, 2019, 7: 18267-18283 doi: 10.1109/ACCESS.2019.2896962 [22] Zheng F, Zecchin A C, Simpson A R. Self-adaptive differential evolution algorithm applied to water distribution system optimization. Journal of Computing in Civil Engineering, 2013, 27(2): 148-158 doi: 10.1061/(ASCE)CP.1943-5487.0000208 [23] Cervantes-Culebro H, Cruz-Villar C A, Peñaloza M G M, Mezura-Montes E. Constraint-handling techniques for the concurrent design of a five-bar parallel robot. IEEE Access, 2017, 5: 23010-23021 doi: 10.1109/ACCESS.2017.2764883 [24] He C, Cheng R, Zhang C, Tian Y, Chen Q, Yao X. Evolutionary large-scale multiobjective optimization for ratio error estimation of voltage transformers. IEEE Transactions on Evolutionary Computation, 2020, 24(5): 868-881 doi: 10.1109/TEVC.2020.2967501 [25] Ma Z, Wang Y, Song W. A new fitness function with two rankings for evolutionary constrained multiobjective optimization. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(8): 5005-5016 doi: 10.1109/TSMC.2019.2943973 [26] Wang B C, Li H X, Li J P, Wang Y. Composite differential evolution for constrained evolutionary optimization. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018, 49(7): 1482-1495 [27] Zhou Y L, Zhu M, Wang J H, Zhang Z Z, Xiang Y, Zhang J. Tri-goal evolution framework for constrained many-objective optimization. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018, 50(8): 3086-3099 [28] Edison E, Shima T. Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms. Computers & Operations Research, 2011, 38(1): 340-356 [29] 王凌, 沈婧楠, 王圣尧, 邓瑾. 协同进化算法研究进展. 控制与决策, 2015, 30(02): 193-202Wang Ling, Shen Jing-Nan, Wang Sheng-Yao Deng Jin. Advances in co-evolutionary algorithms. Control and Decision, 2015, 30(02): 193-202 [30] Zhan Z H, Li J J, Cao J N, Zhang J, Chung H S H, Shi Y H. Multiple populations for multiple objectives: a coevolutionary technique for Solving multiobjective optimization problems. IEEE Transactions on Cybernetics, 2013, 43(2): 445-463 doi: 10.1109/TSMCB.2012.2209115 [31] Liu X F, Zhan Z H, Gao Y, Zhang J, Kwong S, Zhang J. Coevolutionary particle swarm optimization with bottleneck objective learning strategy for many-objective optimization. IEEE Transactions on Evolutionary Computation, 2018, 23(4): 587-602 [32] Cai X, Hu M, Gong D W, Guo Y N, Zhang Y, Fan Z, et al. A decomposition-based coevolutionary multiobjective local search for combinatorial multiobjective optimization. Swarm & Evolutionary Computation, 2019, 49: 178-193 期刊类型引用(15)
1. 毕文豪，张梦琦，高飞，杨咪，张安. 无人机集群任务分配技术研究综述. 系统工程与电子技术. 2024(03): 922-934 . 
百度学术2. 段海滨，梅宇，赵彦杰，霍梦真，牛轶峰，王寅，袁莞迈，邓亦敏，范彦铭，朱纪洪，李轩，罗德林. 2023年无人机热点回眸. 科技导报. 2024(01): 217-231 . 百度学术3. 葛泉波，王远亮，李宏. 基于改进舰尾流模型和多层耦合分析的机载雷达测量建模. 自动化学报. 2024(03): 617-639 . 本站查看4. 史晓田，张宏立，董颖超. 基于动态能耗的多无人机协同任务分配. 计算机仿真. 2024(03): 25-32+127 . 百度学术5. 薛健，赵琳，向贤财，吕科，宏晨，张宝琳，岩延，王泳. 非完全信息下无人机集群对抗研究综述. 电子与信息学报. 2024(04): 1157-1172 . 百度学术6. 褚菲. 人防工程档案流程优化管理研究. 华章. 2024(04): 159-161 . 百度学术7. 郑志强，段海滨. 基于有限忍耐度鸽群优化的无人机近距空战机动决策. 计算机应用. 2024(05): 1401-1407 . 百度学术8. 曹成才，黄炎焱，孙鹏耀，吴奎. 面向巡飞弹编队的战前筹划任务分配方法. 指挥控制与仿真. 2024(03): 56-61 . 百度学术9. 王峰，付青坡，韩孟臣，邢立宁，吴虎胜. LeCMPSO算法求解异构无人机协同多任务重分配问题. 控制理论与应用. 2024(06): 1009-1017 . 百度学术10. 丁伟光. 考虑多目标的钢管混凝土拱桥拱肋参数设计优化. 黑龙江交通科技. 2024(08): 125-129 . 百度学术11. 潘成胜，程博，王建伟，施建锋. SCMOPSO算法的陆军合成旅协同多任务分配方法. 火力与指挥控制. 2024(10): 8-18 . 百度学术12. 李敏，包富瑜，王恒. 无人机使能的无线传感网总能耗优化方法. 自动化学报. 2024(11): 2259-2270 . 本站查看13. 周萌，李建宇，王昶，王晶，王力. 多机器人协同围捕方法综述. 自动化学报. 2024(12): 2325-2358 . 本站查看14. 朱润泽，赵静，蒋国平，肖敏，徐丰羽. 基于改进粒子群算法的无人机三维路径规划. 南京邮电大学学报(自然科学版). 2024(06): 120-127 . 百度学术15. 张友安，何子琦，李博宸，宋磊. 基于任务评估反馈的异构无人机动态任务分配. 航空兵器. 2024(06): 78-85 . 百度学术其他类型引用(11)
-
下载:
计量
- 文章访问数: 1133
- HTML全文浏览量: 419
- PDF下载量: 390
- 被引次数: 26
