Multi-UAV Cooperative Target Allocation Based on AC-DSDE Evolutionary Algorithm
-
摘要:
多无人机协同目标分配最优问题(Multi-UAV cooperative target allocation optimal problem, MUCTAOP), 旨在求解组合分配问题的最小代价值, 是最具有挑战性的多约束组合优化问题之一. 结合进化算法解决MUCTAOP需要考虑两个关键因素: 1) 在进化过程中保持覆盖问题空间的“探索性”和“开发性”平衡; 2) 建立符合实际战场复杂环境的多约束条件. 为解决这两个关键因素, 本文提出一种新的近似聚类混合双策略差分进化算法(Approximate clustering dual-strategy differential evolution algorithm, AC-DSDE). 首先, 根据父代种群适应度值将个体分成“探索类个体”与“开发类个体”; 然后根据混合双策略变异方案平衡后代多样性与收敛性; 最后, 结合无人机自身性能约束、协同约束和实际三维复杂环境构建约束函数. 实验结果表明, 本文所提出的AC-DSDE算法能够快速地找到合理的分配方案.
-
关键词:
- AC-DSDE /
- 混合双策略 /
- 差分进化算法 /
- 多无人机协同目标分配最优问题
Abstract:Multi-UAV cooperative target assignment optimization problem (MUCTAOP), aimed at solving the minimum cost value portfolio allocation problem is one of the most challenging multi-constrained combinatorial optimization problem. Combining evolutionary algorithms to solve MUCTAOP needs to consider two key factors: first, in the process of evolution, we should keep the balance of “exploratory” and “exploitative” covering the problem space; Second, the establishment of a variety of constraints in line with the actual battlefield complex environment. In order to solve the two key factors, this paper proposes a new approximate clustering dual-strategy differential evolution algorithm (AC-DSDE). Firstly, according to the fitness value of the father, the population is divided into sub-populations of “exploration type individual” and “development type individual”; Then the diversity and convergence of the offspring are balanced according to the mixed double strategy variation scheme; Finally, this paper combines the UAVs' own performance constraints, collaborative constraints and the actual three-dimensional complex environment to build the constraint function. The experimental results show that the AC-DSDE algorithm proposed in this paper can quickly find a reasonable allocation scheme.
-
多无人机协同目标分配优化问题(Multi-UAV cooperative target allocation optimal problem, MUCTAOP)是指在复杂任务环境中, 为无人机编队分配一个或一组有序任务, 即对有限的UAVs资源进行合理的分配, 同时编队整体效率达到最优[1]. 文献[2-4]指出多机协同目标分配优化问题具有协同性较高、计算难度大、复杂度高等特点. 在目标分配过程中, 既要考虑飞行器的性能差异、战场势态的复杂性、任务执行权重等因素; 还需要考虑可行的飞行代价、合理的分配算法及各种协同约束条件.
近年来, 为了解决多机协同目标分配问题, 研究者们提出了很多优秀算法. 这些协同目标分配算法主要可以分为三类:
1) 基于数学规划法的协同目标分配
数学规划法是解决集中式分配问题的经典方法; 在处理维数较低的分配情况时, 该方法简单灵活, 求解速度较快; 但在处理维数较高的情况时, 求解的难度呈指数级增长, 且要求已知研究对象所有的信息, 将复杂作战环境信息过度简化, 因此仅适合低维的简单任务环境问题求解. 例如匈牙利算法[5]、混合整数线性规划法(Mixed integer linear programming, MILP)[6]、动态规划法[7].
2) 基于协商法的协同目标分配
协商法能够有效解决分布式目标分配问题, 该类算法计算灵活, 可以将不同层次的分配问题, 在各个节点上进行分布处理. 但在复杂任务环境中, 随着分配规模的增大, 系统的鲁棒性较差; 同时, 对协同约束的处理能力较差, 致使其实现效果偏差较大. 例如基于合同网的协商算法(Contract net based negotiation algorithm, CNBNA)[8], 基于共识捆绑算法(Consensus-based bundle algorithm, CBBA)[9].
3) 基于进化算法的协同目标分配
该类算法是建立在自然选择与群体遗传基础上的寻优算法, 实质上遵循“优胜劣汰”和“适者生存”的思想, 具有较高鲁棒性和广泛适用性. 但是该类算法容易出现局部最优解, 收敛速度较慢, 以及停滞等现象[10-13]. 例如遗传算法[14]、粒子群算法[15]、蚁群算法[16]、差分进化算法[17]等.
由于人们对无人机系统需求不断提高, 尤其是三维真实环境和异构多无人机体系构建, 使该领域的研究更注重复杂高精, 密切贴合实际等要求. 数学规划法与协商法在目标分配过程中都简化了三维真实环境. 进化算法灵活的编码结构适合复杂三维问题的建模和求解[18]. 因此, 进化算法逐渐成为多机协同目标分配研究方法之一. 其中差分进化算法(Differential evolution algorithm, DE)运行稳定、收敛速度较快、空间复杂度较低, 在处理高维问题中显示出较好的结果. 因此, 本文重点研究基于DE 的多无人机协同目标分配.
尽管DE算法已经很好地处理多无人机协同目标分配问题, 但在处理高维复杂环境下多机协同目标分配仍然存在如下难点:
1) 现用的进化策略进行目标分配求解时, 往往只关注优化的某一个方面, 选择适合探索(寻找更多全局最优区域)和开发(加速收敛到最优区域速度)的适当繁衍方案是一个两难选择. 例如, 具有高随机性的变异方案侧重于探索, 而贪婪的变异方案侧重于开发, 这就导致了在解决组合优化问题时存在不足. 针对不同策略的改进和混合, 以平衡探索性与开发性也是目前的一个难点.
2) 如何构建符合实际问题约束函数, 文献[14, 17-18]采用了大量的约束, 但文献中仍假设无人机具有相同航程, 不变的速度; 虽然简化了问题的复杂度, 但忽略了实际战场中异构UAV自身不同的性能. 因此构建合理实际的约束函数才更符合真实优化目标的需要.
为解决这些难点, 本文提出适用于三维环境下多无人机协同目标分配的近似聚类混合双策略差分进化算法(Approximate clustering dual-strategy differential evolution algorithm, AC-DSDE). 该方法有助于平衡种群的多样性与收敛性; 然后, 结合归档技术的代间变异方法取代原来的随机灭绝, 以增加搜索覆盖范围的可控性; 最后, 构建加权混合适应度函数, 在文献[22]的基础上, 限制无人机载弹量, 即限制无人机可执行的任务数. 其方法的主要特征和优点描述如下:
1) 首先, 根据父代种群适应度值将个体分成“开发性个体”与“探索性个体”两个子种群, “探索性个体”能够有效识别问题空间中的最优解区域; “开发性个体”能够加速优化收敛的速度. 通过这种方式, 在进化过程中可以根据不同性质的个体指导种群的进化. 其次, 采用混合双策略变异方案, 使每个个体根据搜索进程, 动态调整变异策略, 有助于探索性与开发性达到平衡. 然后, 结合归档技术与代间变异率来储存一定数量的较优收敛的个体, 避免进化过程中种群的随机变异, 导致已经搜索到的优解变得无效; 同时建立选择概率函数, 选择一定数量的“探索性个体”与“开发性个体”, 有助于收敛的过程中跳出局部最优解.
2) 构建加权混合适应度函数, 将估计航程代价、航程时间和约束违背量之和作为适应度函数; 加入载弹量约束, 限制无人机巡游模式中执行目标数, 将问题的约束作为惩罚函数应用于进化算法的重要评价阶段, 使得运行过程更加符合真实的战争环境.
1. 相关工作
1.1 差分进化算法
差分进化(Differential evolution algorithm, DE)算法[17]类似于很多经典的进化算法, 是一种高效的全局优化算法. 种群中每个个体对应一个解向量, 通过不同的突变策略产生新的个体, 交叉算子根据个体与目标个体进行混合, 生成实验个体; 选择算子根据实验个体的适应度值与目标个体的适应度值相比较, 决定下一代个体. 在算法终止前, 变异、交叉和选择构成了DE的主循环.
1.1.1 初始化种群
在解空间中随机均匀生成NP个个体:
$$\begin{split} \left\{ {X(0)|x_{j,i}^L \le {x_{j,i}}(0) \le x_{j,i}^U;} \right. &i = 1,2,\cdots,NP;\\ &\left. {j = 1,2,\cdots,D}\right\} \end{split}$$ (1) $${x_{j,i}}(0) = x_{j,i}^L + rand(0,1) \cdot \left(x_{j,i}^U - x_{j,i}^L\right)$$ (2) 式(1)与式(2)中NP代表种群的大小, D表示解空间的维度,
$ x_{j,i}^{L} $ 表示种群中第i个“个体”的第j个“基因”的下界,$ x_{j,i}^{U} $ 表示种群中第i个“个体”的第j个“基因”的上界,$ x_{j,i}(0) $ 表示第0代中第i个“个体”的第j个“基因”, rand(0, 1)表示在(0, 1)区间内均匀分布的随机数.1.1.2 变异
初始化种群后, DE算法通过变异算子从种群中随机选取两个个体作差, 所得的差向量加权后与第三个个体求和产生变异个体; 其中, 针对不同的问题有不同的变异策略, 这些变异策略影响着种群的进化. 下面列出了5种常用的变异策略:
1) DE/rand/1
$${v_{j,i}}(g + 1) = {x_{j,r1}}(g) + F \times ({x_{j,r2}}(g) - {x_{j,r3}}(g))$$ (3) 2) DE/best/1
$${v_{j,i}}(g + 1) = {x_{j,best}}(g) + F \times ({x_{j,r1}}(g) - {x_{j,r2}}(g))$$ (4) 3) DE/current-to-best/1
$$\begin{array}{*{20}{r}} {{v_{j,i}}(g + 1) = {x_{j,i}}(g) + F \times ({x_{j,best}}(g) - {x_{j,i}}(g)}+\\ { {x_{j,r1}}(g) - {x_{j,r2}}(g))} \end{array}$$ (5) 4) DE/rand/2
$$\begin{array}{*{20}{r}} {{v_{j,i}}(g + 1) = {x_{j,r1}}(g) + F \times ({x_{j,r2}}(g) - {x_{j,r3}}(g)}+\\ { {x_{j,r4}}(g) - {x_{j,r5}}(g))} \end{array}$$ (6) 5) DE/best/2
$$\begin{array}{*{20}{r}} {{v_{j,i}}(g + 1) = {x_{j,best}}(g) + F \times ({x_{j,r1}}(g) - {x_{j,r2}}(g)}+\\ { {x_{j,r3}}(g) - {x_{j,r4}}(g))} \end{array}$$ (7) 式(3) ~ 式(7)中,
$ r1,r2,r3,r4,r5 $ 是在[1, N]中随机选取的5个整数且$ i \neq r1 \neq r2 \neq r3 \neq r4 \neq $ $ r5 $ ,$ x_{i}(g) $ 表示第g代种群中第i个个体,$ x_{j,best}(g) $ 表示第g代种群中最好的个体,$ v_{j,i}(g + 1) $ 表示变异个体. 参数F是缩放因子, F值的大小直接影响算法的全局寻优能力. F越小, 算法对覆盖问题空间精细搜索能力更好, 但收敛速度会变慢. F越大, 收敛速度更快, 算法能够跳出局部最优, 但可能出现丢解的情况; 同时F值的大小影响种群的多样性[17].1.1.3 交叉
在变异之后, DE通常执行二项式交叉操作, 交叉是由交叉率CR决定, 其从
$ x_{j,i}(g) $ 和$ v_{j}{}_{,i}(g + 1) $ 进行部分交换以形成新的试验向量$ u_{j,i}(g + 1) $ :$${u_{j,i}}(g + 1) = \left\{ {\begin{aligned} & {{v_{j,i}}(g + 1), \;\;\; rand(0,1) \le CR}\\ & {{x_{j,i}}(g), }\;\;\;\;\;\;\;\;\; {\text{否则}} \end{aligned}} \right.$$ (8) 式(8)中, CR是交叉率, 决定子代、父代与中间变异体之间交换个体基因大小程度. CR的值越大, 种群的多样性随之增加; CR的值越小, 种群的多样性也会减少, 不利于全局寻优.
1.1.4 选择
DE采用贪婪算法来选择进入下一代种群的个体, 该算子从试验向量
$ u_{j,}{}_{i}(g + 1) $ 和原始向量$ x_{j,i}(g) $ 中选择更好的个体进入下一代:$${x_{j,i}}(g + 1) = \left\{ {\begin{aligned} &{{u_{j,}}_i(g + 1),}\\ &\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{f({u_{j,i}}(g + 1)) \ge f({x_{j,i}}(g))}\\ &{{x_{j,}}_i(g),\;\;\; {\text{否则}}} \end{aligned}} \right.$$ (9) 式(9)中,
$ f(x) $ 是根据具体问题构建的适应度函数. 例如, 构建目标函数, 对于求最大化问题时, 具有较高适应值的向量被选择到下一代.算法1. 基本DE算法框架
输入. NP (种群大小); D (空间维度大小); T (迭代次数)
输出. 最优解
1. t = 1
2. For i = 1 to NP
3. For j = 1 to D
4.
$ {x_{j,i} = x_{j,i}^{L} + rand(0,1) \cdot \left(x_{j,i}^{U} - x_{j,i}^{L}\right) } $ ;5. End For
6. End For
7. while
${ t \leq T} $ 8. For i = 1 to NP
9. ( Mutation and Crossover)
10. For j = 1 to D
11.
$ {v_{j,i}(g + 1) = Mutation(x_{j,i}(g))} $ ;12.
$ {u_{j,i}(g + 1) = Crossover(v_{j,}{}_{i}(g + 1),x_{j,}{}_{i}(g))} $ ;13. End For
14. (Greedy Selection)
15. If
${ f(u_{j,i}(g + 1)) \geq f(x_{j,i}(g)) } $ Then16.
${ x_{j,i}(g + 1) = u_{j,i}(g + 1)} $ ;17. Else
18.
${ x_{j,i}(g + 1) = x_{j,i}(g)} \normalsize $ ;19. End If
20. End For
21. t = t + 1;
22. End While
1.2 MUCTAOP
多无人机协同目标分配最优问题, 旨在多任务分配过程中求解最小的航程代价. 文献[18]指出多机协同目标分配是一个多模式、多约束、计算难度大, 杂度呈几何级增长的最优化NP问题. 这就要求必须对目标分配问题进行统一建模, 明确飞行器执行的层次和阶段, 才能获得较好的分配结果.
Ramirez等[2]提出了加权随机策略生成突变的新个体, 该策略将搜索的重点放在找到解空间中最好的解, 虽然提高了收敛速度, 但忽略了种群的多样性. Ramirez-Atencia等[19]提出多目标遗传算法解决协同分配问题, 该方法通过变量两两组合(飞行距离、 飞行时间、飞行数量、 燃料消耗), 根据评级的方式, 获得了较好的分配方案. Wang等[20]以智能体加速度作为控制输入, 考虑了限制加速度和速度的物理约束, 提出了基于梯度的算法以最小化性能度量并确定最佳轨迹. 魏政磊等[21]采用了灰狼优化(GWO)算法对多无人机任务分配模型进行求解, 该方法在二维仿真场景中取得了较好的效果, 但未考虑三维复杂场景. Zhao等[22]研究了三维环境中多机协同统一分配方法. 建立仿真战场环境, 在研究三维环境中多无人机协同目标分配具有较好的指导作用; 因此本文在该建模的基础上进行扩展, 加入了无人机载弹约束, 即限定了无人机可执行目标点的个数.
MUCTAOP的场景具体描述为在复杂的三维环境中攻击一组目标的一组无人机
$N = \{ U_{1}, U_{2},\cdots,$ $\left. U_{n} \right\} $ . 该问题的目的是找到一组分配序列$\normalsize M = $ $\left\{ T_{1},T_{2},\cdots,T_{m} \right\},$ 其具有最短的估计航程代价、最短的飞行时间和最小的约束违背. 其典型的场景和仿真环境如图1所示.
图 1 MUCTA在三维任务环境中的场景Fig. 1 Simulation diagram of MUCTA in athree-dimensional environment图1中三维仿真场景包含10架UAVs和10个目标点, 圆圈代表无人机的位置坐标, 五角星代表目标点的位置坐标, 威胁障碍物包括山地形与雷达辐射区(半球型)的结合. 无人机与目标点的对应关系由垂直切面与山地形的交线和可飞行航迹组成, 即为图中显示的实线部分.
2. AC-DSDE For MUCTAOP
2.1 随机分组和自选分组
在解决多机协同目标分配时, 种群中的个体即为备选解, 备选解的优劣直接影响搜索算法寻优效率的高低. 因此在进化之前需要对种群进行有效地划分. 划分方法有两种: 随机分组和自选分组; 种群中个体随机分组, 旨在种群中的个体尽可能探索到种群的未知区域, 对空间有较大的覆盖性. 但是该方法不能快速搜索到最优解, 甚至出现不收敛的现象. 例如Crowding聚类小生境方法[24], 该方法引入了新的参数CS (聚类大小), 设置参考点R, 在种群中找到最近的个体X到R, X及其最近的CS−1个体形成新的子种群, 流程如算法2所示:
算法2. Crowding算法框架
输入. NP (种群大小), CS (聚类大小)
输出. NP/CS个新的子种群;
1. 在搜索空间中随机生成参考点R;
2. For
${ i = 1} $ to$\small {{NP}/{CS}} $ 3. 在种群中找到邻近的个体X到R;
4. X及其最近的CS−1个体形成新的子种群;
5. 从种群中移除CS个个体;
6.
$ {i = i + 1} \normalsize$ ;7. End For
自选分组方法如Speciation聚类小生境方法[24-25]. 本文结合该方法引入父代种群的适应度值, 从每一代中, 选取整数作为聚类大小CS, 小生境数为NP/CS. 将父代种群适应度值进行排序, 最好的个体定义为参考点, 参考点及其近邻CS−1个个体形成新的子种群, 流程如算法3所示:
算法3. Speciation算法框架
输入. NP (种群大小), CS (聚类大小),
$ \small{F} $ (父代种群适应度值)输出. CP个新的子种群;
1.
${ \lbrack F_{n},I\rbrack = {\rm{sort}}(F)} $ ; /将父代种群适应度值进行排序/2. For
${ i = 1} $ to$ {{{NP}/{CS}}} $ 3.
${ S_{best} = F_{n}{}_{(best)}} $ ; /最好的个体定义为参考点/4.
$ {S_{best}} $ 及其近邻的CS−1个体形成新的子种群${S_{n}};$ 5. 从种群中移出新的子种群
$\small{S_{n}};$ 6.
${ i = i + 1}; \normalsize$ 7. End For
从“探索性”子种群中挑选个体可以帮助保持种群的多样性, 从“开发性”子种群中选择个体可以帮助快速收敛到最优个体. 具体操作方法如下: 将整个种群划分为若干个子种群, 然后根据个体的适应度将每个子种群细分为数量相等的部分. 如图2所示, 父代种群中包含“探索性个体”和“开发性个体”, 首先将父代种群进行排序, 设定聚类大小为CS = 2, 形成两个子种群.
2.2 动态混合进化策略
上节已经将种群划分成“探索性”与“开发性”两种不同的子种群. 探索初期, 随机搜索的探索性应该比精细化搜索的开发性比重大, 选用DE/rand/2快速识别空间中最优解的区域, 然后选用DE/best/2优化收敛的速度, 确保在搜索的最后阶段, 精细搜索趋于主导地位. 因此, 探索性与开发性得到了平衡, 算法的整体性能得到了提高. 混合策略产生新个体如式(10)所示:
$$\normalsize {v_i} = \left\{ {\begin{aligned} {{x_{r1}} + {F_d} \times ({x_{r2}} - {x_{r3}} + {x_{r4}} - {x_{r5}})} {\text{,}}\\ {CR(t) \ge \frac{{fitness(i)}}{{fitnes{s_{{\rm{max}}}}}}}\\ {{x_{best}} + {F_d} \times ({x_{r1}} - {x_{r2}} + {x_{r3}} - {x_{r4}})} {\text{,}}\\ {CR(t) < \frac{{fitness(i)}}{{fitnes{s_{{\rm{max}}}}}}} \end{aligned}} \right.$$ (10) 此外, 之前曾分析过缩放因子F值的大小直接影响算法的全局寻优能力. F越小, 算法对覆盖问题空间精细搜索能力更好, 但收敛速度会变慢. F越大, 收敛速度更快, 算法能够跳出局部最优; 因此, 在产生新个体的过程中, 设定动态缩放因子
$\normalsize F_{d} $ 代替静态缩放因子F非常重要.$\normalsize F_{d} $ 设置如式(11)所示:$${F_d} = \left\{ \begin{aligned} &1.5CR(t) {\text{,}}\;\;\;\;\;\;\;\;CR(t) \ge \frac{{fitness(i)}}{{fitness{\rm{max}}}}\\ &1 - 0.5CR(t){\text{,}}\;\;CR(t) < \frac{{fitness(i)}}{{fitness{\rm{max}}}} \end{aligned} \right.$$ (11) 2.3 归档技术
本节结合了代间变异率与归档技术取代了原先的随机重置, 以增加搜索范围的可控性. 在进化过程中, 最优解在整个种群中反映的信息量较低, 随着迭代次数的增加而极可能被覆盖, 使之前的搜索变得无效, 导致信息的不连贯和资源浪费. 因此在世代间灭绝操作时, 建立合理的选择算子概率模型与使用归档技术非常有必要. 在存档中保存当前种群中一定数量的较优个体, 将其它的普通个体全部重置, 直到搜索结束. 保存收敛的个体和代间变异可能找到的最优解, 避免种群突变带来的资源浪费.
$$\normalsize p(i) = \frac{{fitness(i) - fitnes{s_{{\rm{min}}}}}}{{fitnes{s_{{\rm{max}}}} - fitnes{s_{{\rm{min}}}}}}$$ (12) 选择算子概率如式(12)所示, 适应度越大的个体被选中的概率越大, 同时设置代间变异率(Intergenerational mutation rate, IGMR)为0.3. 该方法能避免进化过程中优秀个体的彻底消亡, 在保持种群多样性的同时, 也加速了收敛速度.
图3 (a)表示每代计算的个体适应度值, 经过选择算子计算后得出较好的收敛个体存储在归档库图3 (b)中.
2.4 完整AC-DSDE算法框架如下:
算法4. AC-DSDE算法
输入. NP (种群大小), CS (聚类大小),
$ \small{F} $ (父代种群适应度值)输出. NP/CS个新的子种群;
1. 随机初始化种群;
2. 随机生成一个整数作为簇的大小;
3. 使用算法3将种群划分为几个种群;
4. For 每个种群
5. For 种群中的个体
$\small {x_{i} }$ 6. If
$ {x_{i}} $ 是适合“探索性”个体7.
${ v_{i} = x_{r1} + F_{d} \times (x_{r2} - x_{r3} + x_{r4} - x_{r5})};$ 8. Else
9.
${v_{i} = x_{best} + F_{d} \times (x_{r1} - x_{r2} + x_{r3} - x_{r4})};$ 10. End if
11. End For
12. End For
13. For each individual P(i)
14.
${p(i) = \frac{fitness(i) - fitness_{\text{min}}}{fitness_{\text{max}} - fitness_{\text{min}}}}; \normalsize$ 15. 保存适应度好的种群个体, 重置其他个体;
16. End For
17. 重复步骤2 ~ 15, 直至满足终止条件;
18. End
2.5 目标分配模式
多机协同目标分配可按UAVs和目标点对应数量进行分类. 本文中取N, M分别代表无人机的数量与目标点的数量, 按数量对应关系可分成以下三种不同的模式[22]:
1) 模式1: 当N = M时, 该模式任务分配关系较为简单, 每架UAV分配一个目标点, 每个目标点分配一架UAV, UAV与目标点是一一对应的关系; 该模式计算复杂度较低, 求解的关键在于分配过程中如何避免目标竞争引发的冲突, 如何利用协同降低毁伤概率, 使总的适应度值最大.
2) 模式2: 当N>M时, 该模式任务分配关系较为复杂, 每一个目标点可以分配多架无人机, 每架无人必须执行一个目标点, UAVs与目标点是多对一的关系; 该模式对应关系不平衡, 导致计算复杂度较高, 问题求解的关键在于严格的时间约束导致多机协同困难.
3) 模式3: 当N < M时, 每架UAV可执行多个目标, 每个目标必须分配一架UAV, UAV与目标点是一对多的关系. 其中N<M情况最为复杂, 可以看作三种模式的组合问题. 问题求解的关键在于如何利用较少的资源完成较复杂的任务, 并能有效的处理时序关系, 求解难度较大.
2.5.1 分配模式统一建模
多机协同目标分配等同于运筹学中的指派问题. 现假设有N架无人机, 打击M个分布在不同位置的目标. 要求构建目标函数考虑航程距离最短、总飞行时间最少和约束违背最小, 并且能够统一处理N = M、N > M和N < M三种不同的模式. 因此13, 构建的目标函数如下:
$$ \begin{array}{*{20}{l}} {{\rm{min}}f(x) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {{w_j}{d_{(i,j)}}{D_{(i,j)}}} } }+\\ \;\;\;\;\;\;\;\;\;\;\;\;\; {\; \alpha \left({\rm{max}}\left(\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {{t_{(i,j)}}{D_{(i,j)}}} } \right)\right) + \beta \sum\limits_{k = 1}^K {{c_k}} } \end{array}$$ (13) 其中,
${ d_{(i,j)}} $ 是无人机$ i $ 到目标点$ j $ 的距离, 该距离利用垂直切面法估算航程代替直线, 该方法虽然不是最短的航程, 但是充分考虑了三维地形信息, 比直线距离更接近最优航程;$ w_{j} $ 是目标j 的权重且$0 < $ $ w_{j} \leq 1 $ ,$ w_{j} $ 的值越大, 表示目标$ j $ 越重要;$ t_{(i,j)} $ 是无人机$ i $ 到目标点$ j $ 的时间;$ c_{k} $ 是与约束相对应的惩罚;$ \alpha $ 和$ \beta $ 是用于保持目标函数中多项式的平衡的比例因子, 该因子使得航程代价、航程时间、约束违背保持在同一个量级;$ D_{(i,j)} $ 是决策变量, 决定UAV和目标的对应. 具有不同表达式:$$ {D_{(i,j)}} = \left\{ {\begin{aligned} &{{D_{(i,j)\;}},\;\;\;\;\;\;\;\;\;\;\;N = M}\\ &{{D_{([{i_s},\cdots,{i_l}],j)}},\;\;s,l \in N,\;N > M}\\ &{{D_{(i,[{j_p},\cdots,{j_q}])\,}},\;\forall p,q \in M,\;N < M} \end{aligned}} \right.$$ (14) 2.5.2 协同约束函数及协调关系:
1) UAV与目标点决策变量约束: 当
$ N \geq M $ 时, UAVs数量大于等于目标点的数量, 此时任务决策为: 每架UAV必须执行一个目标点, 每个目标点必须被一架UAV执行; 当$ N < M $ 时, UAVs数量小于目标点的数量, 此时任务决策为: 每个目标点必须分配一架UAV, 单架UAV可以巡游执行空间中的目标点.$$ \mathop {\mathop \cap \limits^N }\limits_{i = 1} D(i,j) = 1,\;\forall j = 1, \cdots ,N \ge M$$ (15) $$ \mathop {\mathop \cap \limits^M }\limits_{j = 1} D(i,j) = 1,\;\forall i = 1, \cdots ,N < M$$ (16) 式(15)和式(16)分别表示了两种不同决策对应的关系.
2) 最大航程约束
$ D(km) $ : 不同的模式下, 最大航程代价指所有分配关系的估计航程代价的总和; 该约束体现了各UAVs自身性能, 比如油耗、有效通信等.$$ \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {{d_{(i,j)}}} {D_{(i,j)}} \le \sum\limits_{i = 1}^n {{D_i}} ,\forall i = 1,\cdots,n\;} $$ (17) $$ {C_1}_{violation} = \left\{ {\begin{aligned} &{0,\;\;\;{d_{(i,j)}} \le {D_i}}\\ &{c1,\;\,{d_{(i,j)}} > {D_i}} \end{aligned}} \right.$$ (18) 式(17)中
$ d(i,j) $ 表示估计航程代价,$ D_{i} $ 表示各UAVs的限定的最大航程距离; 式(18)表示无人机i执行任务j, 若无人机i超出其自身限定的最大航程距离将对其进行惩罚.3) UAVs最小/最大速度约束
$V\;(\rm km/h)$ :$$ {V_{(i)}} = \left[ {{V_{(i){\rm{min}}}},{V_{(i){\rm{max}}}}} \right]$$ (19) $$ {C_2}_{violation} = \left\{ {\begin{aligned} &{0,\;\;\;{V_{(i)}}_{{\rm{min}}} \le {V_{(i)}} \le {V_{(i)}}_{{\rm{max}}}}\\ &{c2,\;{V_{(i)}}_{{\rm{max}}} < {V_{(i)}}\;{\text{或者}}{V_{(i)}} < {V_{(i)}}_{{\rm{min}}}} \end{aligned}} \right.$$ (20) 式(19)中
$ V_{(i)}{}_{\text{min}} $ 表示无人机i的最小速度,$ V_{(i)}{}_{\text{max}} $ 表示无人机i的最大速度; 式(20)表示若无人机i超出限定的最小速度或者最大速度将对其进行惩罚.4) 最大航行时间约束
$ T(h) $ : 表示协同分配结果中执行目标耗费时间最长的无人机, 最大航行时间也是规划完成的标志.$$ \left\{ {\begin{aligned} {{\rm{max}}\left\{ {\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {{t_{(i,j)}}{D_{(i,j)}}} } } \right\} \le \sum\limits_{i = 1}^n {{T_i}} },\\ {i = 1,\cdots,n}\\ {{T_{{\rm{max}}}} = {\rm{max}}\left\{ {\frac{{{d_{(i,j)}}{D_{(i,j)}}}}{{{v_{i({\rm{min}})}}}},\forall i,j \in N} \right\}} \end{aligned}} \right.$$ (21) $$ {C_3}_{violation} = \left\{ {\begin{aligned} &{0,\;\;\;{T_{real}}(i) \le T(i)}\\ &{c3,\;{T_{real}}(i) > T(i)} \end{aligned}} \right.$$ (22) 根据式(17)最大航程约束与式(19)最大、最小速度约束, 可以计算出最大航行时间; 式(22)表示若无人机i实际航行时间超出其限定的最大航行时间将对其进行惩罚.
5) UAVs最大载弹量约束
$ U_{missile} $ : 该约束体现了UAVs最大载弹量. 即在模式3)中, 单架无人机在巡游过程中执行任务数量不可以超过其有效地载荷量.$$ {U_{missile}}(i) \le {U_{\rm max}}(i)$$ (23) $$ {C_4}_{violation} = \left\{ {\begin{aligned} &{0,\;\;\;{U_{missile}}(i) \le {U_{{\rm{max}}}}(i)}\\ &{c4,\;{U_{missile}}(i) > {U_{{\rm{max}}}}(i)\;} \end{aligned}} \right.$$ (24) 式(23)表示无人机i的载弹量应小于其最大的载弹量; 式(24)表示若无人机i的载弹量超过其最大载弹量将对其进行惩罚.
6) 目标点之间的时序约束
$ T_{sort} $ : 该约束体现了目标点之间的执行顺序, 重要的目标点必须优先执行, 其他目标点根据其约束依次执行;$$ {T_j} < {T_{j + \tau, }}\;\;\tau \in N$$ (25) $$ {C_5}_{violation} = \left\{ {\begin{aligned} &{0,\;\;\;{T_j} < {T_{j + \tau }}}\\ &{c5,\;{T_j} \ge {T_{j + \tau }}} \end{aligned}} \right.$$ (26) 式(25)表示目标点j必须晚于目标点
$ j + \tau $ 执行,$ \tau $ 为正整数. 式(26)表示若目标点$ T_{j} $ ,$ T_{j + \tau} $ 不符合限定执行次序则进行惩罚.7) 等待时间约束
$ T_{wait} $ : 为了确保模式一与模式二中部分UAVs同时到达指定目标, 允许部分UAVs等待一段时间后再出发.$$ {T_{wait}} = \left[ {{t_{wait}}\left( 1 \right),{t_{wait}}\left( 2 \right),\cdots,{t_{wait}}\left( {{n}} \right)} \right]$$ (27) $$ {C_{6violation}} = \left\{ {\begin{aligned} &{0\;\mathop {\mathop \cap \limits^k }\limits_{i = 1} T(i) = \sigma ,}\\ &\;\;\;\;\;{k = 1,2,\cdots,m}\\ &{c6\;\mathop {\mathop \cap \limits^k }\limits_{i = 1} T(i) \ne \sigma ,}\\ &\;\;\;\;\;{k = 1,2,\cdots,m} \end{aligned}} \right.$$ (28) 式(27)限定各无人机到达目标的等待时间; 式(28)表示各目标点被攻击时间的交集不可超过时间段
$ \sigma $ , 通常$ \sigma $ 时间段认为是极小的, 可根据真实战场势态进行调整.该模型针对三种不同分配模式建立了统一的分配关系. 将航程代价、时间代价与约束违背量之和作为适应度函数. 在进化前, 建立UAVs与目标点的估计航程代价库, 进化时通过查找估计航程代价矩阵, 可以大幅提高计算效率.
3. 实验结果和分析
为验证改进后的AC-DSDE算法处理MUCTAOP有效性, 本文在Matlab R2016a进行多组仿真实验. 实验包括以下部分: 1) 选取数量较少的UAVs和目标点验证改进算法的有效性; 2) 选取数量较多的UAVs和目标点验证改进算法能够有效处理复杂环境下目标分配; 3) 将改进的AC-DSDE与同类算法进行比较.
表1中“
$ Upos $ ”、“$ Tpos $ ”、“$ Rpos $ ”分别表示无人机、目标点和雷达的坐标; “$ W $ ”表示各目标点的权重;表 1 实验初始数据Table 1 Initialization of experimental dataModel Data type 1 2 3 4 5 6 7 8 9 10 N=M Upos [10, 25, 10] [140, 15, 12] [30, 80, 13] [110, 40, 15] [80, 20, 15] [20, 55, 15] [120, 16, 17] [160, 20, 15] [80, 50, 12] [170, 62, 13] Tpos [20, 210, 13] [46, 200, 12] [64, 210, 23] [154, 210, 12] [100, 200, 12] [118, 210, 14] [82, 220, 12] [136, 190, 11] [10, 170, 10] [172, 170, 12] Rpos [130, 70, 4, 23] [120, 140, 4, 26] [42, 103, 5, 30] [42, 180, 5, 25] [50, 50, 5, 26] $V\ (\rm km/h)$ [0.2, 0.3] [0.2, 0.4] [0.4, 0.75] [0.3, 0.6] [0.2, 0.3] [0.35, 0.45] [0.3, 0.5] [0.3, 0.6] [0.3, 0.5] [0.3, 0.6] Umissile 6.0 8.0 6.0 4.0 6.0 4.0 8.0 8.0 6.0 6.0 $D\ (\rm km)$ 500 700 300 350 700 900 450 610 450 610 W 3.0 2.0 1.0 3.0 2.0 1.0 2.0 3.0 2.0 1.0 Tsort [3, 4] [5, 2] [6, 1] [7, 4] N>M Upos [10, 25, 10] [140, 15, 12] [30, 80, 13] [110, 40, 15] [80, 20, 15] [20, 55, 15] [120, 16, 17] [160, 20, 15] [80, 50, 12] [170, 40, 13] Tpos [28, 210, 13] [64, 210, 23] [154, 210, 14] [118, 210, 14] [136, 190, 11] [172, 170, 12] Rpos [130, 70, 4, 23] [120, 140, 4, 26] [42, 103, 5, 30] [42, 180, 5, 25] [50, 50, 5, 26] $V\ (\rm km/h)$ [0.4, 0.75] [0.3, 0.6] [0.2, 0.3] [0.35, 0.45] [0.3, 0.5] [0.3, 0.6] [0.2, 0.3] [0.35, 0.45] [0.3, 0.5] [0.3, 0.6] Umissile 6.0 8.0 6.0 4.0 6.0 4.0 8.0 8.0 6.0 6.0 $D\ (\rm km)$ 400 700 650 500 700 900 450 610 400 700 W 1.0 3.0 4.0 2.0 1.0 1.0 Tsort [1, 3] [2, 4] [1, 2] $Twait\ (\rm{m})$ 200 500 600 200 800 600 300 200 700 500 N<M Upos [78, 20, 15] [93, 31, 12] [31, 20, 13] [112, 32, 15] [150, 25, 10] [170, 50, 15] Tpos [28, 211, 13] [46, 220, 12] [64, 210, 23] [154, 212, 12] [100, 200, 12] [118, 213, 14] [82, 225, 12] [136, 190, 11] [10, 180, 10] [172, 170, 12] Rpos [130, 70, 4, 23] [120, 140, 4, 26] [42, 103, 5, 30] [42, 180, 5, 25] [50, 50, 5, 26] Umissile 4.0 8.0 6.0 4.0 6.0 4.0 $V\ (\rm km/h)$ [0.2, 0.3] [0.2, 0.4] [0.4, 0.75] [0.3, 0.6] [0.2, 0.3] [0.2, 0.4] $D\ (\rm km)$ 400 700 650 500 610 400 W 1.0 0.8 0.6 0.7 0.9 0.8 1.0 0.7 1.0 1.0 Tsort [4, 5] [5, 2] [6, 7] [7, 4] $Twait\ (\rm{m})$ 100 600 表2设定了两组不同实验参数. “
$ Un $ ”表示UAVs的数量, “$ Tn $ ”表示目标点的数量, “$ Pn $ ”表示种群的规模, “$ Gen $ ”代表进化迭代次数. 因为差分进化算法是随机搜索算法, 为了验证解的一致性, 本文设置“$ Num $ ”参数对同一情境下进行多次实验.表 2 两组实验进化参数的设定Table 2 Setting of experimental evolution parameters of two groups模式 实验 1 实验 2 Un Tn Pn Gen Num Un Tn Pn Gen Num N = M 10 10 50 1 000 20 30 30 50 1 000 10 N > M 10 6 50 1 000 20 30 10 50 1 000 10 N < M 6 10 50 1 000 20 10 30 50 1 000 10 3.1 验证改进算法的有效性
图4显示了实验1分配结果, 其中圆圈代表UAVs的三维坐标, 星形代表目标点三维坐标; 同时, 本文将每个坐标进行编号, 以便后续统计分配数据. 从图中看出基于AC-DSDE 算法的多机协同分配能够在多雷达区域和目标点随机分布的三维环境中, 充分结合了整体山地形, 有效地处理三种不同模式下的分配问题.
图 4 三维环境中实验1的仿真结果Fig. 4 Simulation results of Experiment 1 in a three-dimensional environment表3表示实验1中三种不同模式下无人机与目标点最优分配的结果; 其中UAV表示UAVs分配序列, Target表示对应的目标点分配序列, Cost是UAV与Target对应的总航程代价, 包含了航行距离、飞行时间等. 同时, 仿真数据均符合三种模式无人机与目标点之间的对应关系. 图4与表3表明了改进的AC-DSDE算法能够有效处理三种不同的模式, 并找到相对应的分配方案.
表 3 实验1的分配结果Table 3 Assignment results of Experiment 1模式 分配结果 N = M UAV 1 2 3 4 5 6 7 8 9 10 Target 9 6 1 7 5 2 3 10 8 4 Cost 265.9 685.4 306.1 481.3 609.2 367.6 490.1 216.4 424.6 294.0 N > M UAV 1 2 3 4 5 6 7 8 9 10 Target 1 6 2 5 1 1 4 6 5 3 Cost 429.4 311.7 338.0 437.6 866.6 354.6 530.2 216.4 424.6 294.0 N < M UAV 1 1 1 2 3 3 3 4 5 6 Target 3 5 7 6 1 2 9 8 4 10 Cost 228.7 630.7 75.3 525.9 110.5 83.1 547.1 450.6 452.8 169.6 3.2 验证算法处理复杂环境的有效性
为验证算法处理复杂环境的有效性, 本节中选取了5个评价指标对算法的性能进行评价:
1) 平均时间:
$T_{aver} = {\sum\nolimits_{i = 1}^{n}T_{i}}/Num$ ;2) 平均代价: 多组实验中总航程代价值的平均值
$C_{aver} = {\sum\nolimits_{i = 1}^{n}C_{n}}/Num$ ;3) 最优代价
$ C_{best} $ : 多组实验中最小代价值;4) 约束违背: 最优解中约束违背量总和占最优代价的百分比, 该评价指标衡量了算法的协同性能.
5)“优解”表示陷入局部最优的次数和当前优于平均代价的次数占实验总次数的百分比.
其中, 平均代价和最优代价都是综合了航程代价、时间代价和各种约束违背量的适应度值.
表4分别统计了实验1与实验2的数据, 可以得出以下结论:
表 4 两组实验分配结果的统计数据Table 4 Statistics of the results of the two groups ofexperimental assignments实验 模式 平均时间(s) 平均代价 最优代价 约束违背(%) 优解(%) 实验1 N = M 16.1 8 107.9 8 058.8 4.49 95 N > M 22.9 6 808.5 6 690.4 4.07 75 N < M 23.6 5 795.4 5 573.3 2.04 80 实验2 N = M 38.2 18 605.1 18 093.6 6.21 60 N > M 46.6 13 490.5 13 302.1 7.13 70 N < M 50.5 13 537.4 12 528.7 5.24 80 1) 实验1算法运行时间较短, 且能得到较好的分配结果, 数据表明所提出的AC-DSDE算法能够有效地处理不同模式下的多无人机协同目标分配 问题;
2) 实验2尽管增加了UAVs与目标点的数量, 算法中的执行效率有所降低, 但是AC-DSDE 在有效的时间内搜索到最优解.
3) 各模式中平均代价值与最优代价值接近, 表明改进算法搜索的结果接近全局最优解.
4) 较小的协同违背率证明改进算法协同能力较强. 较高的优解率说明了实验发现最优解的可能性较大.
图 5 三维环境中实验2的仿真结果Fig. 5 Simulation results of Experiment 2 in a three-dimensional environment3.3 AC-DSDE算法的性能
本节将从单次实验收敛曲线与多组实验平均收敛曲线进一步研究AC-DSDE算法处理多无人机协同目标分配的性能.
1) 单次实验收敛曲线与多组实验平均收敛曲线
图6中实线表示单次实验的收敛曲线, 并且显示改进算法进化迭代过程中的最优解以及代间变异随机搜索到的最优解, 分别用圆圈与星号表示. 从收敛曲线可以看出代间变异不仅增加了种群的多样性, 而且找到了更多的优解. 图7是单收敛曲线与平均收敛曲线的对比, 单收敛曲线和平均收敛曲线具有相似的收敛趋势, 搜索前期能够快速收敛到优解区域, 后期能够很快地收敛到最优解. 因此AC-DSDE具有较好的收敛性能.
图 7 实验1分配结果的单条和平均收敛曲线对比Fig. 7 Comparison of the single and average convergence curves of the results of Experiment 12) AC-DSDE与同类目标分配算法之间的比较
本节将改进后的AC-DSDE算法、DMDE算法[22]与APC-DE算法[26]进行比较. 实验所采用的进化参数、种群规模、迭代次数相同. 表5中, 变量CR表示交叉率, 变量MR表示变异率, 变量IGMR 为DE算法的代间变异率. 图8是不同算法的平均收敛曲线, 表5和图8显示, AC-DSDE算法总的航程代价值最小, 收敛速度最快, 执行时间最短. 尽管其他两种算法都能在一定的时间内找到最优解, 但总的航程代价值较高且需要更长的执行时间.
表 5 AC-DSDE与其他算法之间的比较Table 5 Comparison between AC-DSDE and other algorithms模式 方法 UAV与目标点数量 种群数量 迭代次数 实验次数 CR MR IGMR 最优代价 平均代价 平均时间 (s) N = M AC-DSDE N = M = 10 30 1 000 10 0.9 null 0.3 8 058.8 8 107.9 16.1 DMDE N = M = 10 30 1 000 10 CR null 1-CR 8 257.6 8 204.8 19.8 APC-DE N = M = 10 30 1 000 10 0.9 null 0.3 8 145.8 8 168.5 24.6 N > M AC-DSDE N = 10, M = 6 30 1 000 10 0.9 null 0.3 6 690.4 6 808.5 22.9 DMDE N = 10, M = 6 30 1 000 10 CR null 1-CR 6 737.1 6 973.7 29.19 APC-DE N = 10, M = 6 30 1 000 10 0.9 null 0.3 6 770.3 6 835.6 26.5 N < M AC-DSDE N = 6, M = 10 30 1 000 10 0.9 null 0.3 5 573.3 5 795.4 23.6 DMDE N = 6, M = 10 30 1 000 10 CR null 1-CR 5 819.9 5 970.7 26.4 APC-DE N = 6, M = 10 30 1 000 10 0.9 null 0.3 5 712.6 2 838.7 27.5 4. 总结
本文提出了基于AC-DSDE混合双策略差分进化算法以解决无人机协同目标优化分配. 首先, 为了提高算法的性能, 提出了混合双策略动态变异的方法. 该方法根据不同类型的个体选用不同的变异策略, 同时构建动态缩放因子
$ Fd $ , 解决目前进化过程中存在的探索性和开发性平衡的问题. 然后结合归档技术与代间变异方法, 在增加了种群的多样性的同时, 也保证了收敛个体不会随着迭代次数消亡. 最后扩展原有的约束条件, 增加了UAVs的载弹量约束, 限制UAVs可执行的目标个数. 仿真实验表明, 该方法能够有效快速地解决多无人机协同目标分配问题, 且协同能力强.对于下一步工作, 将着重考虑差分进化算法在多无人机协同航迹规划方法的研究, 如何有效降低三维空间复杂度, 获得关键路径点的集合, 保证最终航迹是安全且可行.
-
图 1 MUCTA在三维任务环境中的场景
Fig. 1 Simulation diagram of MUCTA in athree-dimensional environment
图 4 三维环境中实验1的仿真结果
Fig. 4 Simulation results of Experiment 1 in a three-dimensional environment
图 5 三维环境中实验2的仿真结果
Fig. 5 Simulation results of Experiment 2 in a three-dimensional environment
图 7 实验1分配结果的单条和平均收敛曲线对比
Fig. 7 Comparison of the single and average convergence curves of the results of Experiment 1
表 1 实验初始数据
Table 1 Initialization of experimental data
Model Data type 1 2 3 4 5 6 7 8 9 10 N=M Upos [10, 25, 10] [140, 15, 12] [30, 80, 13] [110, 40, 15] [80, 20, 15] [20, 55, 15] [120, 16, 17] [160, 20, 15] [80, 50, 12] [170, 62, 13] Tpos [20, 210, 13] [46, 200, 12] [64, 210, 23] [154, 210, 12] [100, 200, 12] [118, 210, 14] [82, 220, 12] [136, 190, 11] [10, 170, 10] [172, 170, 12] Rpos [130, 70, 4, 23] [120, 140, 4, 26] [42, 103, 5, 30] [42, 180, 5, 25] [50, 50, 5, 26] $V\ (\rm km/h)$ [0.2, 0.3] [0.2, 0.4] [0.4, 0.75] [0.3, 0.6] [0.2, 0.3] [0.35, 0.45] [0.3, 0.5] [0.3, 0.6] [0.3, 0.5] [0.3, 0.6] Umissile 6.0 8.0 6.0 4.0 6.0 4.0 8.0 8.0 6.0 6.0 $D\ (\rm km)$ 500 700 300 350 700 900 450 610 450 610 W 3.0 2.0 1.0 3.0 2.0 1.0 2.0 3.0 2.0 1.0 Tsort [3, 4] [5, 2] [6, 1] [7, 4] N>M Upos [10, 25, 10] [140, 15, 12] [30, 80, 13] [110, 40, 15] [80, 20, 15] [20, 55, 15] [120, 16, 17] [160, 20, 15] [80, 50, 12] [170, 40, 13] Tpos [28, 210, 13] [64, 210, 23] [154, 210, 14] [118, 210, 14] [136, 190, 11] [172, 170, 12] Rpos [130, 70, 4, 23] [120, 140, 4, 26] [42, 103, 5, 30] [42, 180, 5, 25] [50, 50, 5, 26] $V\ (\rm km/h)$ [0.4, 0.75] [0.3, 0.6] [0.2, 0.3] [0.35, 0.45] [0.3, 0.5] [0.3, 0.6] [0.2, 0.3] [0.35, 0.45] [0.3, 0.5] [0.3, 0.6] Umissile 6.0 8.0 6.0 4.0 6.0 4.0 8.0 8.0 6.0 6.0 $D\ (\rm km)$ 400 700 650 500 700 900 450 610 400 700 W 1.0 3.0 4.0 2.0 1.0 1.0 Tsort [1, 3] [2, 4] [1, 2] $Twait\ (\rm{m})$ 200 500 600 200 800 600 300 200 700 500 N<M Upos [78, 20, 15] [93, 31, 12] [31, 20, 13] [112, 32, 15] [150, 25, 10] [170, 50, 15] Tpos [28, 211, 13] [46, 220, 12] [64, 210, 23] [154, 212, 12] [100, 200, 12] [118, 213, 14] [82, 225, 12] [136, 190, 11] [10, 180, 10] [172, 170, 12] Rpos [130, 70, 4, 23] [120, 140, 4, 26] [42, 103, 5, 30] [42, 180, 5, 25] [50, 50, 5, 26] Umissile 4.0 8.0 6.0 4.0 6.0 4.0 $V\ (\rm km/h)$ [0.2, 0.3] [0.2, 0.4] [0.4, 0.75] [0.3, 0.6] [0.2, 0.3] [0.2, 0.4] $D\ (\rm km)$ 400 700 650 500 610 400 W 1.0 0.8 0.6 0.7 0.9 0.8 1.0 0.7 1.0 1.0 Tsort [4, 5] [5, 2] [6, 7] [7, 4] $Twait\ (\rm{m})$ 100 600 
下载: 导出CSV
表 2 两组实验进化参数的设定
Table 2 Setting of experimental evolution parameters of two groups
模式 实验 1 实验 2 Un Tn Pn Gen Num Un Tn Pn Gen Num N = M 10 10 50 1 000 20 30 30 50 1 000 10 N > M 10 6 50 1 000 20 30 10 50 1 000 10 N < M 6 10 50 1 000 20 10 30 50 1 000 10
下载: 导出CSV
表 3 实验1的分配结果
Table 3 Assignment results of Experiment 1
模式 分配结果 N = M UAV 1 2 3 4 5 6 7 8 9 10 Target 9 6 1 7 5 2 3 10 8 4 Cost 265.9 685.4 306.1 481.3 609.2 367.6 490.1 216.4 424.6 294.0 N > M UAV 1 2 3 4 5 6 7 8 9 10 Target 1 6 2 5 1 1 4 6 5 3 Cost 429.4 311.7 338.0 437.6 866.6 354.6 530.2 216.4 424.6 294.0 N < M UAV 1 1 1 2 3 3 3 4 5 6 Target 3 5 7 6 1 2 9 8 4 10 Cost 228.7 630.7 75.3 525.9 110.5 83.1 547.1 450.6 452.8 169.6
下载: 导出CSV
表 4 两组实验分配结果的统计数据
Table 4 Statistics of the results of the two groups ofexperimental assignments
实验 模式 平均时间(s) 平均代价 最优代价 约束违背(%) 优解(%) 实验1 N = M 16.1 8 107.9 8 058.8 4.49 95 N > M 22.9 6 808.5 6 690.4 4.07 75 N < M 23.6 5 795.4 5 573.3 2.04 80 实验2 N = M 38.2 18 605.1 18 093.6 6.21 60 N > M 46.6 13 490.5 13 302.1 7.13 70 N < M 50.5 13 537.4 12 528.7 5.24 80
下载: 导出CSV
表 5 AC-DSDE与其他算法之间的比较
Table 5 Comparison between AC-DSDE and other algorithms
模式 方法 UAV与目标点数量 种群数量 迭代次数 实验次数 CR MR IGMR 最优代价 平均代价 平均时间 (s) N = M AC-DSDE N = M = 10 30 1 000 10 0.9 null 0.3 8 058.8 8 107.9 16.1 DMDE N = M = 10 30 1 000 10 CR null 1-CR 8 257.6 8 204.8 19.8 APC-DE N = M = 10 30 1 000 10 0.9 null 0.3 8 145.8 8 168.5 24.6 N > M AC-DSDE N = 10, M = 6 30 1 000 10 0.9 null 0.3 6 690.4 6 808.5 22.9 DMDE N = 10, M = 6 30 1 000 10 CR null 1-CR 6 737.1 6 973.7 29.19 APC-DE N = 10, M = 6 30 1 000 10 0.9 null 0.3 6 770.3 6 835.6 26.5 N < M AC-DSDE N = 6, M = 10 30 1 000 10 0.9 null 0.3 5 573.3 5 795.4 23.6 DMDE N = 6, M = 10 30 1 000 10 CR null 1-CR 5 819.9 5 970.7 26.4 APC-DE N = 6, M = 10 30 1 000 10 0.9 null 0.3 5 712.6 2 838.7 27.5
下载: 导出CSV
-
[1] Zhao Yi-Jing, Zheng Zheng, Liu Yang. Survey on computational-intelligence-based UAV path planning. Knowledge-Based Systems, 2018, 158: 54−64 doi: 10.1016/j.knosys.2018.05.033 [2] Ramirez Atencia C, Del Ser J, Camacho D. Weighted strategies to guide a multi-objective evolutionary algorithm for multi-UAV mission planning. Swarm and Evolutionary Computation, 2019, 44: 480−495 doi: 10.1016/j.swevo.2018.06.005 [3] 韩博文, 姚佩阳, 孙昱. 基于多目标MSQPSO算法的UAVS协同任务分配. 电子学报, 2017, 8: 1856−1863 doi: 10.3969/j.issn.0372-2112.2017.08.008Han Bo-Wen, Tao Pei-Yang, Sun Yu. UAVs collaborative task allocation based on multi-objective MSQPSO algorithm. Acta Electronica Sinica, 2017, 8: 1856−1863 doi: 10.3969/j.issn.0372-2112.2017.08.008 [4] Vetrella A R, Causa F, Renga A. Multi-UAV carrier phase differential GPS and vision-based sensing for high accuracy attitude estimation. Journal of Intelligent & Robotic Systems, 2019, 93(1-2): 245−260 [5] Shah K, Reddy P, Vairamuthu S. Improvement in Hungarian algorithm for assignment problem. Advances in Intelligent Systems and Computing, 2015, 324: 1−8 [6] Luitpold B. Coordinated target assignment and UAV path planning with timing constraints. Journal of Intelligent & Robotic Systems, 2019, 3(4): 857−869 [7] Xin Yi, Zhu An-Min. An improved neuro-dynamics-based approach to online path planning for multi-robots in unknown dynamic environments. In: Processdings of the 2013 IEEE International Conference on Robotics and Biomimetics. Shenyang, China: IEEE, 2013. 1–6. [8] ElGibreen H, Youcef-Toumi K. Dynamic task allocation in an uncertain environment with heterogeneous multi-agents. Autonomous Robots, 2019: 1−26 [9] Hunt S, Meng Q, Hinde C. A consensus-based grouping algorithm for multi-agent cooperative task allocation with complex requirements. Cognitive Computation, 2014, 6(3): 338−350 doi: 10.1007/s12559-014-9265-0 [10] Cui Ying, Wu Xiao, Song Jiao, Ma Hui-Jiao. A dynamic task equilibrium allocation algorithm based on combinatorial auctions. In: Proceedings of the 8th International Conference on Intelligent Human-Machine Systems and Cybernetics. Hangzhou, China. IEEE, 2016. 530–533. [11] Whitbrook A, Meng Q, Chung P W H. Addressing robustness in time-critical, distributed, task allocation algorithms. Applied Intelligence, 2019, 49(1): 1−15 doi: 10.1007/s10489-018-1169-3 [12] Cao Y, Wei W, Bai Y. Multi-base multi-UAV cooperative reconnaissance path planning with genetic algorithm. Cluster Computing, 2017, 20(7): 1417−1420 [13] Roy R, Das M, Dehuri S. A combinatorial multi-objective particle swarm optimization based algorithm for task allocation in distributed computing systems. Communications in Computer and Information Science, 2011, 193: 113−125 [14] Saeedvand S, Aghdasi H S, Baltes J. Robust multi-objective multi-humanoid robots task allocation based on novel hybrid metaheuristic algorithm. Applied Intelligence, 2019, 49: 1−33 doi: 10.1007/s10489-018-1169-3 [15] Jana B, Chakraborty M, Mandal T. A task scheduling technique based on particle swarm optimization algorithm in cloud environment. Advances in Intelligent Systems and Computing, 2019, 742: 525−536 [16] Alencar R C, Santana C J, Bastos-Filho C J A. Optimizing routes for medicine distribution using team ant colony system. Advances in Intelligent Systems and Computing, 2020, 923: 40−49 [17] Kumari S, Gupta G P. Differential evolution-based sensor allocation for target tracking application in sensor-cloud. Advances in Intelligent Systems and Computing, 2018, 695: 347−356 [18] Tang Shu-Yan, Qin Zheng, Xin Jian-Kuan. Collaborative task assignment scheme for multi-UAV based on cluster structure. In: Proceedings of the 2010 International Conference on Intelligent Human-Machine Systems and Cybernetics. Nangjing, China: IEEE, 2010. 285–289. [19] Ramirez-Atencia C, Bello-Orgaz G, R-Moreno M D. Solving complex multi-UAV mission planning problems using multiobjective genetic algorithms. Soft Computing, 2017, 21(17): 4883−4900 doi: 10.1007/s00500-016-2376-7 [20] Wang Yan-Wu, Wei Yao-Wen, Liu Xiao-Kang, Zhou Nan, Cassandras Christos G. Optimal persistent monitoring using second-order agents with physical constraints. IEEE Transactions on Automatic Control, 2018, 64(8): 3239−3252 [21] 魏政磊, 赵辉, 黄汉桥. 基于SAGWO算法的UCAVs动态协同任务分配. 北京航空航天大学学报, 2018, 8: 1651−1664Wei Zheng-Lei, Zhao Hui, Huang Han-Qiao. Dynamic cooperative task assignment of UCAVs based on SAGWO algorithm. Journal of Beijing University of Aeronautics And Astronautics, 2018, 8: 1651−1664 [22] Zhao Ming, Zhao Ling-Ling, Su Xiao-Hong, Ma Pei-Jun, Zhang Yan-Hang. Improved discrete mapping differential evolution for multi-unmanned aerial vehicles cooperative multi-targets assignment under unified model. International Journal of Machine Learning and Cybernetics, 2017, 8(3): 765−780 doi: 10.1007/s13042-015-0364-3 [23] Li Xiao-Dong. Efficient differential evolution using speciation for multimodal function optimization. In: Proceedings of the Genetic and Evolutionary Computation. Washington, USA: GECCO, 2005. 873 [24] Thomsen R. Multimodal optimization using crowding-based differential evolution. In: Proceedings of the 2004 Congress on Evolutionary Computation. Portland, USA: IEEE, 2004. 1382–1389 [25] Stoean C L, Preuss M, Stoean R. Disburdening the species conservation evolutionary algorithm of arguing with radii. In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation. London, UK: 2007. 1420–1427 [26] Wang Z J, Zhan Z H, Lin Y. Dual-strategy differential evolution with affinity propagation clustering for multimodal optimization problems. IEEE Transactions on Evolutionary Computation, 2018, 22(6): 894−908 doi: 10.1109/TEVC.2017.2769108 期刊类型引用(14)
1. 马捷，李雅. 人工智能在无人机领域的应用. 无线电工程. 2024(03): 759-764 . 
百度学术2. 张昀普，付强，单甘霖，黄燕. 多传感器协同区域搜索与目标跟踪的调度方法. 北京航空航天大学学报. 2024(03): 850-860 . 百度学术3. 高卫峰，王琼，李宏，谢晋，公茂果. 无人机集群任务分配的多目标算法研究. 西安电子科技大学学报. 2024(02): 1-12 . 百度学术4. 于全友，徐止政，段纳，徐觅蜜，程义. 基于改进ACO的带续航约束无人机全覆盖作业路径规划. 航空学报. 2023(12): 303-315 . 百度学术5. 范云生，陈欣宇，赵永生，宋保健. 基于扩张状态观测器的四旋翼吊挂飞行系统非线性控制. 自动化学报. 2023(08): 1758-1770 . 本站查看6. 刘兴宇，郭荣化，任成才，闫超，常远，周晗，相晓嘉. 基于身份匈牙利算法的无人机蜂群分布式目标分配方法. 兵工学报. 2023(09): 2824-2835 . 百度学术7. 张祥银，夏爽，张天. 基于自适应遗传学习粒子群算法的多无人机协同任务分配. 控制与决策. 2023(11): 3103-3111 . 百度学术8. 蒲志强，易建强，刘振，丘腾海，孙金林，李非墨. 知识和数据协同驱动的群体智能决策方法研究综述. 自动化学报. 2022(03): 627-643 . 本站查看9. 鲁亮亮，代冀阳，应进，赵玉坤. 基于APSODE-MS算法的无人机航迹规划. 控制与决策. 2022(07): 1695-1704 . 百度学术10. 陈宇轩，王国强，罗贺，马滢滢. 基于Actor-Critic算法的多无人机协同空战目标重分配方法. 无线电工程. 2022(07): 1266-1275 . 百度学术11. 鞠锴，冒泽慧，姜斌，马亚杰. 基于势博弈的异构多智能体系统任务分配和重分配. 自动化学报. 2022(10): 2416-2428 . 本站查看12. 吴诗平，陈谋，朱荣刚，贺建良. 基于区块链的多先进战机协同作战资源自适应调度. 南京航空航天大学学报. 2022(06): 1021-1029 . 百度学术13. 张宗豪，徐斌，胡铮. 基于边缘差分进化算法多无人机目标分配. 火力与指挥控制. 2022(10): 145-151 . 百度学术14. Jian-li Su，Hua Wang. An improved adaptive differential evolution algorithm for single unmanned aerial vehicle multitasking. Defence Technology. 2021(06): 1967-1975 . 必应学术其他类型引用(11)
-
下载:
计量
- 文章访问数: 1369
- HTML全文浏览量: 266
- PDF下载量: 278
- 被引次数: 25
