0 引言
现代战争逐步呈现出“无人化”趋势,无人机因其速度快、零伤亡、全天候等优点广泛应用于军事领域,对空战模式产生革命性的影响[1]。如何在复杂战场环境下,对无人机作战任务进行分配,使之在满足限定条件下,得到决策者满意的任务分配方案,成为当前无人机应用领域研究的一个热点。
目前,绝大多数无人机任务分配问题的研究都基于参数确定这一假设。但是,受虚假情报、恶劣天气等不确定因素影响,无人机任务分配过程中的油耗量、飞行时间、飞行威胁等不可测,造成确定条件下的任务分配方案失去最优性。模糊集理论、鲁棒优化理论和概率论是解决不确定问题的常用方法,但是模糊集在数学上不具有自洽性[2],鲁棒优化求解的结果相对保守[3],应用概率论的前提是不确定变量的概率分布可以获取,但在实际作战环境中缺乏采样数据,需要根据相关领域专家对不确定变量进行评估以获取相关参数信息。为此,Liu[4-5]提出了不确定理论,并有相关学者开展了大量理论和应用研究[6-8],无人机任务分配问题涉及较少。因此,本文中主要研究带时间窗的不确定无人机多目标任务分配问题。由于目标函数和约束中均包含不确定变量,传统的优化方法无法解决此问题。本文中基于不确定理论,建立一种新的不确定无人机任务分配模型,分别引入期望值准则和机会约束将带有不确定变量的模型转为确定型优化模型。
当前求解任务分配问题的方法主要有穷举法、约束规划法、图论法、列表法及聚类法等,但这些方法在计算实时性、准确性等方面仍有较大提升空间。烟花算法(fireworks algorithm,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+=V∪O;m和n表示无人机数量和任务目标数量;
为任务序列,表示无人机k依次对目标y1,y2,…,yl实施打击,并返回基地;
表示序列Yk中无人机到达各目标的时间(l<m);xij∈{0,1}是决策变量,xij=1表示无人机打击目标i后直接打击目标j,否则xij=0;距离矩阵D=[dij](n+1)×(n+1)表示无人机基地到各目标的距离和目标之间的距离;当i=1时,dij表示基地到目标j-1的距离;当i≠1时,表示目标i-1到目标j-1的距离,且有dij=dji和dii=0;dij与战场实际环境、敌雷达威胁等因素有关,为简化计算,以两点欧式距离代替实际距离。
1.1.1 目标函数
实际战场环境中,无人机在路径(i, j)上受电磁干扰、地形等带来的威胁ηij和飞行时间tij无法准确得知,两者均为不确定变量。在任务分配问题中,决策者希望无人机以最小代价完成任务。一方面,需要降低无人机受到的威胁代价F1。假设ηij是满足正态分布的一系列独立不确定变量,即ηij～N(eij,σij)。故威胁代价F1可表示为
(1)
另一方面,需要降低因无人机未按时打击目标而产生的延迟惩罚F2。设完成任务可接受的时间窗为[0,Timei],未在时间窗内完成打击任务的无人机,有延迟惩罚
延迟时间越长,惩罚越大。延迟惩罚F2可表示为
(2)
(3)
(4)
其中:λ为延迟惩罚系数;i为无人机的前序任务。
1.1.2 约束条件
无人机打击任务分配约束主要包含以下3类。
1) 燃油约束
受限于无人机性能,单架无人机携带燃油数是一定的。受飞行高度、速度等因素影响,无人机在路径(i, j)上的单位飞行距离油耗εij无法确定,为不确定变量。为确保无人机能够安全返航,必须满足
(5)
式中,Ak为单架无人机携带的燃油总量。
2) 任务协同约束
对于每个目标,其打击任务只能被一架无人机执行,即
(6)
3) 路径起止约束
每架无人机都是从基地出发执行任务,最终返回基地,故路径起止约束为
(7)
1.2 模型等价转换
显然,模型中求解空间的不等式约束及目标函数中均包含不确定变量,无法确定可行解集和实现寻优,属于不确定规划问题。
期望值是不确定变量的重要统计特征,期望值模型是不确定规划的常用处理方法。Liu[4]引入不确定机会约束,以最小化目标函数的期望值为准则,构建了期望值模型以解决不确定规划问题。式(8)是期望值模型的数学表达式。
(8)
其中,M{Gi(x,ξ)≤0}≥αi是置信度水平为α的不确定机会约束,确保了模型有确定的可行解集。由此,无人机打击任务分配期望值模型为
(9)
2 两阶段搜索的多目标烟花算法
2.1 多目标烟花算法
2.1.1 编码方式及初始化
在无人机打击任务分配问题中,每个烟花均代表一种可行的任务分配方案。烟花xi的长度为n,即需打击目标数,以确保每个任务均能分配到无人机且不会重复分配。本文中采取半连续编码,整数部分表示执行任务的无人机编号,根据小数部分值大小确定无人机执行任务的顺序。以2架无人机打击5个目标为例,烟花(1.7,2.5,1.3,2.1,2.7)表示无人机1依次打击目标3、1,无人机2依次打击目标5、2、4。
然后,根据烟花数量N初始化解空间,并计算初始解的适应度值。烟花的初始解产生方式为
xi=xmin+(xmax-xmin)rand(0,1)
(10)
其中:xi=(xi1,xi2,…,xin)为第i个烟花的位置;xij为第i个烟花在第j维度上的值;xmax和xmin表示火花的上下界。
2.1.2 爆炸算子
传统FWA中,烟花产生的火花数和振幅依赖于烟花种群的适应度值,且烟花间差异不可控。虽然其限制了极端烟花产生的火花数,但未考虑其对种群中其他烟花的火花数的影响。此外,在多目标问题中,帕累托解不分优劣,无法得到最大和最小适应度值,故无法简单地根据适应度值大小计算烟花产生的火花数及振幅。故考虑使用幂律分布函数,按照烟花适应度值高低将搜索种群划分为若干等级,以此计算烟花产生的火花数
(11)
式中:k为烟花的适应度等级;a为分布形状系数,其值越大,高适应度值的烟花产生的火花数越多。
2.1.3 变异算子
烟花算法采用高斯变异以增加种群多样性。但高斯变异扰动范围较小,且其变异范围为整个实数区间,对于搜索范围为正实数区间的任务分配问题会造成重复搜索,大大降低了变异效率。
图1和图2给出了Levy分布、柯西分布和高斯分布的概率密度函数和分布函数,可以看出Levy分布的波峰更高,尾翼更宽,且其变异范围为正实数区间,增大了算法的搜索范围及搜索效率。Levy分布的概率密度函数及分布函数分别为
图1 3种分布的概率密度函数曲线
Fig.1 Probability density function curves for each distribution
图2 3种分布的分布函数曲线
Fig.2 Distribution function curves for each distribution
(12)
F(X;u;c)=P{X≤x}=
(13)
其中:u为位置参数,影响分布曲线的左右平移,函数定义域为[u,+∞];c为标度参数,其数值越小,Levy分布的波峰越高,尾翼越宽。
引入Levy变异算子的火花变异公式为
x′ik=round(β×xik)
(14)
其中, β为服从Levy分布的随机数。
2.1.4 映射
考虑到部分烟花爆炸和变异产生的火花值可能会超出可行域,考虑使用模运算将超出可行域的火花映射到可行域内
(15)
式中:| |表示绝对值运算;mod表示模运算。
2.1.5 选择
对于多目标优化问题,解集质量和解集的覆盖范围是判断帕累托解优劣的标准[16]。算法迭代过程中选取适应度值好、分布分散的烟花更有利于寻优。首先建立容量为W的外部档案室,用以存储迭代过程中产生的烟花;其次,根据Pareto优越理论用非支配排序法将烟花划分为不同的非支配等级[17],针对同一等级烟花,根据式(16)计算烟花的拥挤度距离,非支配等级越小,距离越大,烟花越好,即任务分配方案越好,选取最优的N个烟花作为下次迭代的初始烟花种群。若档案室中烟花的数量超出上限W时,按照非支配排序和拥挤度距离选择最优的W个烟花留在档案室,删除多余烟花
(16)
式中:u为当前烟花邻域内烟花数;dmin和dmax为烟花种群最近和最远距离。相较于传统拥挤度计算方法,式(16)能够反映出当前烟花在种群中的整体分布,能够更好地度量烟花的领域分布,有利于在整体和局部上保证烟花的多样性。
2.2 两阶段搜索策略
为更好更快得到帕累托解,提出一种两阶段搜索方式,如图3所示。第一阶段为快速搜索阶段,其目的为加速搜索;第二阶段是寻优搜索阶段,其目的为提高解的多样性。
图3 两阶段搜索示意图
Fig.3 Two-stage search diagram
2.2.1 快速搜索阶段
第一阶段主要目的是加快算法搜索速度,使种群迅速接近帕累托前沿,故用当前种群到实际帕累托前沿的距离指导算法搜索。但在实际中,绝大多数多目标优化问题的帕累托解不易获取,无法准确计算种群到帕累托前沿的距离。故考虑引入一个参考点,用当前种群到参考点的距离代替其到真实帕累托解的实际距离,以指导算法搜索。
参考点一般选取搜索域的边界或搜索域外的点,否则会造成搜索种群无法接近帕累托前沿。如图4所示,x1,x2,x3,x4,x5为搜索种群,A、B、C、D表示不同的参考点。其中A和B位于搜索域内,C位于搜索域边界,D位于搜索域外。当选取B、C、D作为参考点时,种群会朝着帕累托前沿搜索;当选取A作为参考点时,粒子x1,x2朝着帕累托前沿搜索,但粒子x3,x4,x5逐渐远离帕累托前沿,造成搜索效率降低。
图4 不同位置参考点搜索过程示意图
Fig.4 Schematic diagram of reference point search process at different locations
2.2.2 寻优搜索阶段
第一阶段虽然加速了种群对帕累托解的逼近,但也导致种群过度集中(见图3)。为使算法能够快速找到具有多样性的解,需要增强算法在单次搜索过程中的搜索范围,故将传统FWA中的高斯变异算子换为变异范围更广的Levy变异算子。
2.2.3 搜索转换策略
当快速搜索的种群收敛时,需要自动进入寻优搜索阶段,如何设计合适的搜索阶段转换指标是该算法的关键问题之一。考虑以子代个体支配父代个体数的均值作为阶段转换指标。当子代个体能够支配较多父代个体,认为当前种群在快速接近帕累托解;否则,认为当前种群的搜索正在收敛。当满足式(17)时,可以认定种群搜索已经收敛。
ui<α
(17)
式中:ui为子代个体能够支配父代个体数的均值;α为指标转换阈值。不同阈值对算法的影响将在第4节详细说明。
3 实例仿真
3.1 评价指标
多目标算法的性能比较往往比较困难,需要考虑解集质量、算法求解效率、鲁棒性等诸多方面。本文中选取超体积指标(Hypervolume,HV)评价算法优劣。HV度量了解集的空间覆盖情况,能同时衡量算法的多样性和收敛性。HV值越大,表明帕累托前沿分布越均匀,收敛性越好[16]。HV的计算公式为
HV(A)=[1-f1(xi)][1-f2(xi)]+
(18)
其中, fm(xi)表示解xi的第m个目标函数值。将目标函数值范围进行归一化,则有HV(A)∈[0,1]且越接近1表示解集质量越高。
3.2 算法测试
为验证MLFWA的有效性,在ZDT和DTLZ系列[18]多目标测试函数上验证算法性能,选取多目标遗传算法(NSGA-Ⅱ)、基于分解的多目标进化算法(MOEA/D)和多目标粒子群算法(MOPSO)作为对比。其中,DLZT系列测试函数的优化目标数和搜索变量数均可拓展,考虑到本文中研究的是双目标优化问题,故优化目标数取2。各测试函数特性和问题维度如表1所示。各算法初始种群规模设为100,最大迭代次数为1 000次,外部档案室的大小为50。
表1 各测试函数的相关参数及特性
Table 1 Parameters and characteristics for each test function
测试问题特性维度ZDT1凹形30维ZDT2凸形30维ZDT3不连续30维ZDT6凸形10维DLTZ1线性、多模态10维DLTZ2凹形10维
为减少随机因素对算法性能影响,各算法独立运行50次,得到各算法HV的均值及方差,见表2。算法在测试函数上的帕累托前沿如图5所示。结果表明,MLFWA算法求解的解集质量及算法稳定性要优于对比算法。
图5 各算法在测试函数中的帕累托前沿
Fig.5 The Pareto front for each algorithm in the test function
表2 各算法HV的均值和方差
Table 2 The mean value and variance of HV for each algorithm
测试函数MLFWA均值方差MOPSO均值方差MOEA/D均值方差NSGA-Ⅱ均值方差ZDT10.652 95.02E-040.641 20.002 70.649 00.001 70.598 60.068 6ZDT20.323 50.00110.316 30.380 80.307 80.003 70.236 50.077 5ZDT30.605 83.83E-040.596 30.012 80.590 10.003 20.513 40.057 9ZDT60.313 25.88E-040.313 40.003 30.300 30.00 20.294 50.035 4DLTZ10.872 23.46E-040.868 84.50E-050.862 20.002 40.852 40.002 7DLTZ20.206 42.50E-040.201 40.001 50.197 00.001 60.193 40.002 1
表3给出了不同α值下ZDT系列测试函数在阶段转换时的HV指标。结果表明,α值越小,进入寻优搜索阶段的搜索种群质量更高。图6给出不同α值下的MLFWA算法在ZDT1测试函数中第二阶段初始解分布。
表3 不同α值ZDT系列测试函数的HV值
Table 3 HV value of ZDT test functions with different α
测试函数α=1α=0.5α=0.1α=0.05ZDT10.350.390.410.41ZDT20.060.070.080.10ZDT30.150.190.320.33ZDT60.040.050.060.07
图6 ZDT1测试函数中不同α值第二阶段初始解分布
Fig.6 The initial solution distribution of different E values in the second stage in ZDT1 test function
3.3 实例仿真
为验证本文中提出的任务分配模型及MLFWA算法,设计场景为4架无人机执行14个任务目标。采用NSGA-Ⅱ算法、MOEA/D算法、MOPSO算法和前文提到的MLFWA算法分别进行求解,各算法参数设置与4.2相同。为便于分析,将无人机和任务目标看作质点,在任务分配过程中不考虑无人机之间的通信约束。仿真区域设置为90 km×150 km的平面,各目标坐标及任务时间窗见表4所示。
表4 任务目标点参数
Table 4 The parameters of targets
任务编号时间窗/min坐标点/km1[0,60][8,47]2[0,50][22,40]3[0,100][45,75]4[0,40][90,60]5[0,50][17,82]6[0,70][120,55]7[0,50][107,42]8[0,70][100,75]9[0,30][60,30]
续表(表4)
任务编号时间窗/min坐标点/km10[0,30][75,20]11[0,80][110,23]12[0,60][50,5]13[0,100][105,13]14[0,100][50,22]
为确保实验结果的准确性,各算法重复运行50次,最大迭代次数为200。MLFWA和其他对比算法在任务分配实例上求解的解集分布如图7所示。从图7可以看出,本文中所提MLFWA在求解无人机多目标任务分配问题中解的质量要明显优于NSGA-Ⅱ、MOEA/D、MOPSO算法。
图7 各算法求解结果示意图
Fig.7 Schematic diagram of solution results for each algorithm
对各算法求解得到的目标函数值进行归一化,计算得到各算法运行30次的HV均值和方差,如表5所示。从表5可以看出,MLFWA在实例中求解得到的解集HV均值要大于3种对比算法,说明了MLFWA求解得到的解集具有较好的多样性和收敛性。但MLFWA的求解得到解集的HV值的方差要略大于MOEA/D、NSGA-Ⅱ算法,说明算法的稳定性略差于MOEA/D、NSGA-Ⅱ算法。由于多目标优化问题主要关注解集质量,故在提升算法求解质量的前提下,适当降低算法稳定是可取的。
表5 各算法的HV均值和方差
Table 5 The mean and variance of HV for each algorithm
算法均值方差MLFWA0.770.084MOPSO0.670.091MOEA/D0.490.055NSGA-Ⅱ0.470.042
4 结论
针对不确定条件下无人机多目标任务分配问题,运用不确定理论将任务执行过程中的威胁、油耗、飞行时间等不确定变量进行量化处理,将其建模为确定型多目标优化问题。引入幂律分布函数和Levy变异算子,结合多目标优化理论和两阶段搜索策略提出了一种两阶段搜索的多目标烟花算法,克服了传统烟花算法不能解决多目标问题的缺陷,并有效提高了算法的求解精度和效率。实验结果表明,MLFWA能够在满足油耗等约束的前提下,有效找出最佳任务分配方案。
下一步工作主要包括以下几个方面。从理论层面,考虑利用不确定性理论中的乐观值、悲观值准则直接求解多目标问题;从模型层面,考虑任务目标价值时变、战场威胁改变、无人机战损等因素细化模型,使之更贴近战场实际;从算法层面,考虑多目标优化理论和智能算法如何更好的结合,以降低算法复杂度及增强算法寻优效率。
[1] DOD U.Unmanned systems integrated roadmap:FY2013—2038[R].Washington,DC,USA,2013.
[2] LIU B.Uncertainty Theory (5th)[M].Beijing:Uncertainty Theory Laboratory,2016.
[3] EVERS L,DOLLEVOET T,BARROS A I,et al.Robust UAV mission planning[J].Annals of Operations Research,2014,222(1):293-315.
[4] LIU B D.Uncertainty theory[M].2nd.Berlin:Springer,2007:9-103.
[5] LIU B D.Some research problems in uncertainty theory[J].Journal of Uncertain Systems,2009,6(1):3-10.
[6] WANG Z,ZHENG M,GUO J,et al.Uncertain UAVISR mission planning problem with multiple correlated objectives[J].Journal of Intelligent &Fuzzy Systems,2017,32(1):321-335.
[7] ZHENG M,YUAN Y,WANG Z,et al.Efficient solution concepts and their application in uncertain multi-objective programming[J].Applied Soft Computing,2016,56:557-569.
[8] WANG J,GUO J,ZHENG M,et al.Uncertain multi-objective orienteering problem and its application to UAV reconnaissance mission planning[J].Journal of Intelligent &Fuzzy Systems,2017,34(4):2287-2299.
[9] PHOLDEE N,BUREERAT S.Comparative performance of meta-heuristic algorithms for mass minimisation of trusses with dynamic constraints[J].Advances in Engineering Software,2014,75:1-13.
[10]林剑萍,廖一鹏.结合分数阶显著性检测及量子烟花算法的NSST域图像融合[J].光学精密工程,2021,29(6):14.
LIN Jianping,LIAO Yipeng.A novel image fusion method with fractional saliency detection and QFWA in NSST[J].Optics and Precision Engineering,2021,29(6):14.
[11]邹适宇,李复名,谢爱平,等.基于改进烟花算法的资源分配[J].航空学报,2021,42(12):324716.
ZOU Shiyu,LI Fuming,XIE Aiping,et al.Resource allocation based on improved fireworks algorithm[J].Acta Aeronautica et Astronautica Sinica,2021,42(12):324716.
[12]余敏建,游航航,韩其松,等.基于改进烟花算法的空战指挥引导对策生成[J].系统工程与电子技术,2019,41(12):2780-2788.
YU Minjian,YOU Hanghang,HAN Qisong,et al.Generation of air combat command and guidance countermeasures based on improved fireworks algorithm[J].System Engineering and Electronics,2019,41(12):2780-2788.
[13]张涛,刘天威,李富章,等.基于改进烟花算法的多目标多机器人任务分配[J].信号处理,2020,36(8):1243-1252.
ZHANG Tao,LIU Tianwei,LI Fuzhang,et al.Multi-objective multi-robot task allocation based on improved fireworks algorithm[J].Signal Processing,2020,36(8):1243-1252.
[14]黄伟建,郭芳.基于烟花算法的云计算多目标任务调度[J].计算机应用研究,2017,34(6):1718-1731.
HUANG Weijian,GUO Fang.Cloud computing multi-objective task scheduling based on fireworks algorithm[J].Computer Application Research,2017,34(6):1718-1731.
[15]毛宗杨,陈韬伟,余益民,等.膜计算框架下的多目标烟花爆炸算法[J].重庆理工大学学报,2018,32(11):147-155.
MAO Zongyang,CHEN Taowei,YU Yimin,et al.Multi-objective fireworks explosion algorithm based on membrane computing framework[J].Journal of Chongqing University of Technology,2018,32(11):147-155.
[16]王丽萍,任宇,邱启仓,等.多目标进化算法性能评价指标研究综述[J].计算机学报,2021,44(8):30.
WANG Liping,REN Yu,QIU Qicang,et al.Survey on performance indicators for multi-objective evolutionary algorithm[J].Chinese Journal of Computers,2021,44(8):30.
[17]闫璐,张琦,丁舒忻,等.基于双目标优化的高速铁路列车运行调整[J].中国铁道科学,2022,43(2):161-171.
YAN Lu,ZHANG Qi,DING Shuxin,et al.High-speed railway train operation adjustment based on objective optimization[J].China Railway Science,2022,43(2):161-171.
[18]HUBAND S,HINGSTON P,BARONE L,et al.A review of multi-objective test problems and a scalable test problem toolkit[J].IEEE Transactions on Evolutionary Computation,2006,10(5):477-506.