不确定条件下基于烟花算法的无人机任务分配_余稼洋.pdf

第 44 卷第 4 期兵 器 装 备 工 程 学 报2023 年 4月收稿日期:2022 05 24;修回日期:2022 06 23作者简介:余稼洋(1999)，男，硕士研究生，E-mail:y1312887589163 com。通信作者:郭建胜(1965)，男，博士，教授，E-mail:Yjy_0412 sina com。doi:1011809/bqzbgcxb202304015不确定条件下基于烟花算法的无人机任务分配余稼洋，郭建胜，张晓丰，解涛，姚赛(空军工程大学 装备管理与无人机工程学院，西安710051)摘要:无人机任务分配问题是近几年的研究热点，但同时考虑不确定性和多目标的研究尚处于起步阶段。基于不确定性理论，建立了一种目标函数和约束条件均包含不确定变量的不确定多目标任务分配模型，并分别引入期望值准则和机会约束将其转化为确定型优化模型。针对传统烟花算法只能解决单目标问题和在收敛速度方面的不足，引入幂律分布函数和 Levy 变异算子，结合多目标优化理论和两阶段搜索策略设计了一种两阶段搜索的多目标烟花算法。通过实例仿真验证所提模型及算法的可行性和有效性。关键词:不确定理论;无人机多目标任务分配;烟花算法;幂律分布;Levy 变异;两阶段搜索本文引用格式:余稼洋，郭建胜，张晓丰，等 不确定条件下基于烟花算法的无人机任务分配 J 兵器装备工程学报，2023，44(4):104 111Citation format:YU Jiayang，GUO Jiansheng，ZHANG Xiaofeng，et al UAV task allocation based on firework algorithmunder uncertain conditions J Journal of Ordnance Equipment Engineering，2023，44(4):104 111中图分类号:V19文献标识码:A文章编号:2096 2304(2023)04 0104 08UAV task allocation based on firework algorithmunder uncertain conditionsYU Jiayang，GUO Jiansheng，ZHANG Xiaofeng，XIE Tao，YAO Sai(College of Equipment Management and Unmanned Aerial Vehicle Engineering，Air Force Engineering University，Xi an 710051，China)Abstract:UAV task allocation is a hot topic in recent years，while the research considering bothuncertainty and multi-objective development is still in its infancy Firstly，based on the uncertainty theory，this paper establishes a mathematical model of uncertain multi-objective task allocation with uncertainvariables included in objective functions and constraint conditions，and introduces the expected valuecriterion and opportunity constraint to transform the model into an optimized deterministic oneFurthermore，in order to solve the problem of dealing with single objective problems only and overcome theshortcoming of the convergence speed of the traditional firework algorithm，a multi-objective fireworkalgorithm with two-stage search is designed by introducing power-law distribution function and Levyvariation operator，combined with multi-objective optimization theory and two-stage search strategyFinally，the feasibility and effectiveness of the proposed model and algorithm are verified by examplesimulationKey words:uncertainty theory;UAV multi-objective task allocation;firework algorithm;power-lawdistribution;Levy variation;two-stage search0引言现代战争逐步呈现出“无人化”趋势，无人机因其速度快、零伤亡、全天候等优点广泛应用于军事领域，对空战模式产生革命性的影响1。如何在复杂战场环境下，对无人机作战任务进行分配，使之在满足限定条件下，得到决策者满意的任务分配方案，成为当前无人机应用领域研究的一个热点。目前，绝大多数无人机任务分配问题的研究都基于参数确定这一假设。但是，受虚假情报、恶劣天气等不确定因素影响，无人机任务分配过程中的油耗量、飞行时间、飞行威胁等不可测，造成确定条件下的任务分配方案失去最优性。模糊集理论、鲁棒优化理论和概率论是解决不确定问题的常用方法，但是模糊集在数学上不具有自洽性2，鲁棒优化求解的结果相对保守3，应用概率论的前提是不确定变量的概率分布可以获取，但在实际作战环境中缺乏采样数据，需要根据相关领域专家对不确定变量进行评估以获取相关参数信息。为此，Liu4 5 提出了不确定理论，并有相关学者开展了大量理论和应用研究6 8，无人机任务分配问题涉及较少。因此，本文中主要研究带时间窗的不确定无人机多目标任务分配问题。由于目标函数和约束中均包含不确定变量，传统的优化方法无法解决此问题。本文中基于不确定理论，建立一种新的不确定无人机任务分配模型，分别引入期望值准则和机会约束将带有不确定变量的模型转为确定型优化模型。当前求解任务分配问题的方法主要有穷举法、约束规划法、图论法、列表法及聚类法等，但这些方法在计算实时性、准确性等方面仍有较大提升空间。烟花算法(fireworks algo-rithm，FWA)是谭营于 2010 年提出的一种智能算法，主要用于求解连续空间的单目标优化问题，其被证明具有良好的优化性能9。文献 10中引入量子的思想，提出了一种自适应旋转角的量子烟花算法;文献 11 中将遗传算法和烟花算法结合，并增加模拟退火流程;文献 12 中引入维度方差、禁忌搜索策略和轮盘赌策略改进变异算子和选择算子。文献 10 12 中对算法的搜索速度和求解精度做出大量贡献，但只能解决单目标优化问题。为将烟花算法应用到多目标优化问题上，文献 13 中以各目标适应度值乘积大小判断解的优劣以确定火花爆炸半径及数量，并引入 Pareto 优越理论改进选择策略;文献 14 中以规范后的各目标适应度值之和判断解的优劣以确定火花爆炸半径及数量;文献 15中引入Pareto 优越理论和精英反向学习策略改进算法的选择策略，以上文献虽成功的将烟花算法拓展到多目标优化问题求解中，但简单地以各目标适应度值乘积或求和来确定爆炸算子中火花半径和数量，可能造成烟花盲目搜索，降低搜索效率;此外，算法在求解精度上仍有较大提升空间。因此，本文中采用幂律分布函数改进爆炸算子，以适应度等级确定火花爆炸半径和数量;此外，引入 Levy 变异算子并结合多目标优化理论和两阶段搜索策略提出了一种两阶段搜索的多目标烟花算法(MLFWA)，避免了算法的盲目搜索和早熟收敛，有效提高了算法搜索速度和全局搜索能力。最后通过实例仿真验证了算法和模型的有效性和可行性。1不确定条件下无人机任务分配问题无人机打击任务分配问题是指无人机从基地出发，在相关约束条件下以最小的代价实现对所有任务目标的火力打击，并回到基地的过程。该问题可表示为无向完全图 G=V+，E+上的不确定整数规划问题。1 1模型构建模型相关参数表示如下:V=1，2，3，n 表示任务目标集，O=0 表示无人机基地，记 V+=VO;m 和 n 表示无人机数量和任务目标数量;Yk=yk1，yk2，ykl，yk0 为任务序列，表示无人机 k 依次对目标 y1，y2，yl实施打击，并返回基地;Tk=Tky1，Tky2，Tkyl 表示序列 Yk中无人机到达各目标的时间(l m);xij 0，1 是决策变量，xij=1 表示无人机打击目标 i 后直接打击目标 j，否则 xij=0;距离矩阵 D=dij(n+1)(n+1)表示无人机基地到各目标的距离和目标之间的距离;当 i=1 时，dij表示基地到目标 j 1 的距离;当 i1时，表示目标 i 1 到目标 j 1 的距离，且有 dij=dji和 dii=0;dij与战场实际环境、敌雷达威胁等因素有关，为简化计算，以两点欧式距离代替实际距离。1 1 1目标函数实际战场环境中，无人机在路径(i，j)上受电磁干扰、地形等带来的威胁 ij和飞行时间 tij无法准确得知，两者均为不确定变量。在任务分配问题中，决策者希望无人机以最小代价完成任务。一方面，需要降低无人机受到的威胁代价 F1。假设 ij是满足正态分布的一系列独立不确定变量，即 ijN(eij，ij)。故威胁代价 F1可表示为F1=mk=1(i，j)Ekijxkij(1)另一方面，需要降低因无人机未按时打击目标而产生的延迟惩罚 F2。设完成任务可接受的时间窗为 0，Timei，未在时间窗内完成打击任务的无人机，有延迟惩罚 Cki，延迟时间越长，惩罚越大。延迟惩罚 F2可表示为F2=mk=1jYkCkj(2)Ckj=00 Tkj Timej(Tkj Timej)xkijTimej Tkj(3)Tkj=t0y1xk0y1+ji=2tyi1yixyi1yi(4)其中:为延迟惩罚系数;i 为无人机的前序任务。1 1 2约束条件无人机打击任务分配约束主要包含以下 3 类。501余稼洋，等:不确定条件下基于烟花算法的无人机任务分配1)燃油约束受限于无人机性能，单架无人机携带燃油数是一定的。受飞行高度、速度等因素影响，无人机在路径(i，j)上的单位飞行距离油耗 ij无法确定，为不确定变量。为确保无人机能够安全返航，必须满足(i，j)E+kijdijxkij Ak(5)式中，Ak为单架无人机携带的燃油总量。2)任务协同约束对于每个目标，其打击任务只能被一架无人机执行，即mk=1iV+，ijxkij=mk=1jV+，ijxkij 1，j V+(6)3)路径起止约束每架无人机都是从基地出发执行任务，最终返回基地，故路径起止约束为iVx0i=jVxj0=1(7)1 2模型等价转换显然，模型中求解空间的不等式约束及目标函数中均包含不确定变量，无法确定可行解集和实现寻优，属于不确定规划问题。期望值是不确定变量的重要统计特征，期望值模型是不确定规划的常用处理方法。Liu4 引入不确定机会约束，以最小化目标函数的期望值为准则，构建了期望值模型以解决不确定规划问题。式(8)是期望值模型的数学表达式。minxE F(x，)s t M Gi(x，)0 i，i=1，2，(8)其中，M Gi(x，)0 i是置信度水平为 的不确定机会约束，确保了模型有确定的可行解集。由此，无人机打击