基于改进多目标简化群优化算法求解动态武器目标分配问题

邱少明 王雪珂 杜秀丽 冯江惠 王建伟

(大连大学通信与网络重点实验室 辽宁 大连 116622)

0 引 言

武器-目标分配问题(Weapon Target Assignment,WTA)提供武器资源的分配方案,是一种非确定性多项式(Non-deterministic Polynomial,NP)完全问题。目前重点研究多个判别标准下求解最优分配方案的问题,因此常看作多目标优化问题(Multi-objective Optimization Problem,MOP),WTA通常分为静态武器目标分配问题(Static Weapon Target Assignment,SWTA)和动态武器目标分配问题(Dynamic Weapon Target Assignment,DWTA),SWTA的分配是对武器的一次完全分配,而DWTA的出现是由于作战时目标在空间和时间上的不确定性,使部分武器不能高效地投入战斗,或新出现的目标使分配过程更加复杂造成的。DWTA的研究大部分都与实际作战环境结合,模型中触及诸多要素,过程也更为复杂,所以目前研究结果较少。在算法模型上,由于目标群的出现属于随机过程,且整个武器系统的空间分布形态多样,不同类型目标出现的时空分布不同,所以,对DWTA的模型研究十分复杂,目前主要研究在特定的作战态势下,通过假设一些条件来简化和分析问题。DWTA分配阶段是通过在有限时间内,合理地分配各阶段的WTA方案,最终得到WTA最优方案。Kline等[1]系统地总结了从1958年到2018年为止,SWTA和DWTA模型从基础模型到适应各种复杂变体的改进模型,并分析了这些模型的利弊,本文的模型有一部分也参考了该文中的模型设计。

对DWTA问题的研究主要在于寻求一种有效算法,解决时间因素对武器目标对分配过程的影响,目前很多研究仍然局限于没有从分配的动态过程解决问题,或局限于静态分配的思想,例如,Chen等[2]提出的基于禁忌搜索的拍卖算法和基于贪婪局部搜索的Memetic算法解决带约束的WTA问题就局限于静态分配的思想。刘传波[3]通过在DWTA问题中提出Memetic算法,设置每个目标的截止时间来动态调整武器的作战状态,并用遗传算法结合模拟退火算法平衡算法的开发和探索。该算法具有任意时间输出特性,在性能和动态随机过程表现出色,符合实际武器目标分配的需求。邱少明等[4]在蝙蝠算法初始部分,放宽部分约束条件,并结合差分进化算法,求解效率更高效。

DWTA问题可以体现作战过程的随机性,近年来考虑了时间因素的DWTA逐渐成为研究的重要方向。Kalyanam等[5]提出通过随机动态规划得到最大预期累积奖励的最优闭环控制策略,通过对目标设置阈值控制武器对目标的分配。Wang等[6]针对离散粒子群优化算法(DPSO)解决大规模及复杂离散问题时收敛慢甚至无收敛的问题,提出一种基于直觉模糊熵的离散粒子群算法,通过制定粒子群直觉模糊参数的选择策略及速度突变机制和位置突变策略,改善了可能的次优位置及邻域,用该算法解决DWTA问题,可以得到较好的全局最优解。Chang等[7]提出了一种改进的人工蜂群(ABC)算法,利用基于规则的启发式因子对种群进行初始化,解决了传统ABC算法收敛慢的问题,并将该算法根据DWTA的特点用整数编码来解决DWTA问题,加快了求解过程,并提高了解的准确性,由此表明ABC算法是一种有效的SI优化算法。

DWTA是在SWTA的基础上发展而来,是下一步研究的重点。该领域的研究仍处于起步阶段,其中在DWTA模型中大多问题都是基于特定的假设简化环境,进行对应的计算,对不确定因素的影响不能准确量化,再加上时间、地点、气候、地形和武器性能等约束条件偏少,因此目前的各种模型还不能普适化。在算法方面,目前的算法也普遍具有收敛速度慢、面对大规模问题时收敛精度低、不能满足DWTA对时间的要求等问题,因此必须对现有算法进行组合与改进,研究如何加快算法运行时间,以及如何平衡求解精度与求解效率的问题。

有很多优秀的智能计算算法可以改造为多目标优化算法,为求解多目标问题服务,例如Yeh[8]提出的单目标简化群优化算法(Simplified Swarm Optimization,SSO)就在收敛性方面得到了比粒子群优化算法(PSO)更好的效果,所以将这些算法及其变体算法的多目标实现应用到WTA问题中,有望得到更高的收敛效率和更优的解。

本文首先在单目标谐波简化群优化算法的基础上,将单变量搜索机制转变为全变量搜索机制,并引入非支配排序算法,支持多目标优化的进化算法应用。由于此前没有对该算法进行过多目标情况下的研究,所以将该算法与多目标简化群优化算法、多目标单变量谐波简化群优化算法用ZDT系列多目标测试函数进行性能方面的对比分析,然后将算法运用到DWTA中研究其求解效率。仿真验证多目标简化群优化算法的收敛性和多样性,结果表明将该算法应用到DWTA问题中时,在求解精度较高的情况下,求解效率相对其他算法有较大提升。

1 相关理论

1.1 动态多目标优化问题(DMOP)

DMOP的数学描述如式(1)所示。

(1)

s.t.gi(X,t)≤0i=1,2,…,p

X∈Ω(t)⊂Rnt∈[t0,ts]

式中:t∈[t0,tx]⊂R,X=(x1,x2,…,xn)T是Rn空间的n维向量;gi(x,t)叫作基于时间变量t的约束条件,Ω(t)={x|gi(x,t)≤0,i=1,2,…,p}是决策变量空间,且仅当所有目标上的决策向量X1不比另一个决策向量X2差时,叫作X1支配X2;fi(X,t),i=1,2,…,m为阶段t问题的子目标函数,各子目标间相互冲突,这样的折中解的集合叫做Pareto最优解集、非劣解集或非支配解集,所有Pareto最优解组成的曲面为Pareto前沿。

1.2 谐波步长策略(CLARANS)

谐波步长策略(Harmonic Step-length Strategy,HSS)旨在改善传统连续SSO中步长固定对求解带来的影响[9],为了提高开发性能,根据谐波序列,HSS如下:

(2)

式中:Δi,k是i代第k个变量的步长;Uk和Lk是第k个变量的上限和下限;i是当前代数;k是当前变量的索引;Nvar是变量数;符号“· ”是下限函数。式(2)中的1.25是文献[9]中已被证明的可得到更优值的初始步长。经过实验,Δ=1.25的效果胜过其他取值。1、1/2、1/3和1/4等的顺序被称为谐波序列,基于谐波序列提出的HSS可以表示为:

(3)

让每一代步长持续50代。步长Δi,k的值从一个生成周期减少到另一个生成周期。gBest和某些解决方案经过长期运行或几代后接近最佳值。这些解决方案的更新仅需稍作更改即可更接近最佳状态,而不会脱离最佳状态。使用谐波序列,因此将步长从HSS的早期固定生成调整为后期动态生成,以克服连续SSO固定步长的障碍。

2 基于改进多目标SSO(MOSSOa)

2.1 简化群优化算法

SSO是Yeh[8]提出的一种新的基于总体的优化算法,以弥补粒子群优化算法(PSO)在解决离散问题方面的不足。由于该算法的简单性、效率和灵活性,它特别适合解决多变量优化问题。SSO与PSO一样,还使用搜索空间内的大量随机解进行初始化,然后由更新机制指导搜索以寻找最佳解,更新机制表示为:

(4)

令Nsol和Nitr分别表示总体大小和迭代总数。SSO的总体步骤概述如下:

步骤2令i=1。

步骤5如果F(Pi)比全局最优解F(G)好,则G=Pi。

步骤6如果i

步骤7若t=Nitr,程序结束;否则t=t+1,返回步骤2。

2.2 MOSSOa总体步骤

改进多目标SSO的整体步骤简述如下:

步骤1随机创建种群,通过非支配排序算法求得全局最优解。

步骤2当前代数为1,根据式(2)设置步长的初始值。

步骤3重新计算粒子中的每个变量。

步骤4更新全局最优解,如果当前阶段时间已到,则转步骤5,否则转步骤6。

步骤5程序终止,输出最优解。

步骤6更新当前迭代次数下的步长值,并执行步骤3。

2.3 MOSSOa具体实现

在SSO中,全局最优方案gBest在产生新种群方面起着关键作用,SSO在扩展到多目标进化算法时,全局最优方案应被一种非支配方案代替,这里选用非支配排序算法求Pareto解,非支配排序算法有两步,首先对粒子划分等级,其次在同一级中,根据每个粒子的拥挤距离进行统一排序,拥挤距离越近,说明多样性越差,粒子在同等级时拥挤距离近的应排在较后的位置。

文献[10]中已证明SSO中用个体最优解pBest更新个体的一种方案可以被丢弃,从而获得更有效的解决方案,这样做不会影响求解质量,因此使用文献[9]中式(2)关于连续SSO的更新机制,去掉利用pBest更新的一项,如式(5)所示。

(5)

在更新机制中增加步长元素,步长间隔为[-1,1]。但是即使这样也不能得到很好的解,因此文献[9]中通过将步长中的间隔从[-1,1]修改为[-0.5,0.5],并将SSO中的三个参数cr、cg和cw从固定的一个值变成每个解都有对应的值。另外在更新过程中,对每个解中的每个变量都进行更新,这里称为全变量更新机制(Update Mechanism all-variable,UMa),对应的有单变量更新机制(Update Mechanism one-variable,UM1)。如果步长太长,则更新机制无法收敛到最佳状态;相反,如果步长太短,则没有足够的动力来寻找解,即寻找解的周期会变长。当步长固定时,不能通过动态调整使粒子接近最终点,因此将HSS机制运用到步长的更新中,使步长随着迭代动态更新。

综上,结合2.1节的原始SSO更新机制和1.2节的HSS策略,改进后的粒子更新公式如式(6)和式(7)所示。

(6)

(7)

式中:Xi+1,j是更新后的个体;j表示阶段数;k表示第k个变量;σ1,k和σ2,k是在[-0.5,0.5]之间产生的统一随机变量;ρk是[0,1]间的统一随机变量;Δk的步长用式(3)进行改进;gk表示全局最优解的第k个变量。

在式(7)中,只能将解决方案更新为更好的值;否则,UMa将保留原始解决方案,然后再进行更新。式(6)是UMa中最重要的部分,其背后的概念是每个变量都更新为其自身的邻域,即gBest的邻域。通过上述方案改进解的质量。

3 用DCI-HQPSOGA求解SWTA问题

3.1 DWTA问题模型

DWTA问题模型在文献[1]中SWTA问题模型的基础上进行构建。

DWTA模型中对目标的约束条件可以分为对目标的空间约束和时间约束两种,这里将模型简化,只考虑对目标的时间约束,DWTA模型在SWTA模型的基础上,将分配过程分为两个阶段,每个阶段随机选择若干个目标,作为该时间环境下可打击的目标,对所选择的目标随机分配武器,分配的合理度用资源耗费均衡性指标(Resource-consumption Balance Index,RBI)来衡量[11],假设一共有t个阶段,第k个阶段所耗费武器的资源溢价系数的计算式为:

RBIik=ci/(ci-j+1)

(8)

假设现阶段所使用武器的比例占总武器数量的比例为Bi,可用式(9)表示。

(9)

该指标中的资源溢价系数可以判断当前阶段的武器供给负荷,通过将武器供给负荷量化,得到资源溢价系数,与作战成本相关联,来保证资源消耗的均衡性。

υi=RBIik·REIi

(10)

则武器i第k次调度资源耗费指数表示为式(11),其中Ni为当前阶段的剩余武器总数量。

(11)

资源耗费指数要近似或小于目标现阶段的价值比例r,以保证在下一阶段有足够的武器资源,实际上该资源耗费均衡性指标相当于一个约束条件。

式中:xij表示分配给目标j的第i种武器的数量。

构建两个目标函数:目标生存概率最小函数f1和武器弹药消耗最少函数f2。第i种武器对目标j的毁伤概率为pij,第i种武器打击目标j时目标j的生存概率为qij=1-pij、价值为Vj。f1计算式表示为:

(12)

目标价值是对战术、目标威胁度等指标的综合考量[12]。

设武器消耗量取决于武器使用个数与其对于目标的价值,则f2计算式表示为:

(13)

(14)

综上所述,DWTA模型如式(15)所示。

(15)

i=1,2,…,m,j=1,2,…,n,k=1,2,…,t

3.2 用DCI-HQPSOGA实现WTA

DWTA问题种群的初始化使用各类武器对目标的毁伤概率表和目标价值表,种群规模为PSize=50,武器种类数m=10,每种武器数对应为C=[3,1,1,5,1,1,1,8,1,10],目标数n=8。在此基础上,加入“阶段”这个时间环境,假设当前有两个阶段,第一阶段出现目标的比例用一个随机值r表示,然后从目标集合中随机挑选出占总数量比例为r的目标,作为当前要打击的对象。武器的分配满足约束条件,其中武器在现阶段分配的资源耗费指数不能大于r,以保证后续阶段武器处于可防御状态,否则武器数量过少,将不能胜任防御任务。对于每个阶段的时间要求,根据武器的总数量以及以往学习经验中对作战规模的了解,为每个阶段设定1 s的分配时间。

4 实验与结果分析

4.1 改进多目标SSO性能测试

因本文算法在迭代过程中会更新所有变量,记为MOSSOa,MOSSO1算法与MOSSOa其他地方相同,唯一不同的地方是在对粒子迭代更新时MOSSO1只随机更新粒子中的一个变量。首先,采用两目标测试函数ZDT2-ZDT4对比分析MOSSO、MOSSO1和MOSSOa三种算法的性能,三个测试函数是两目标最小化问题,其中ZDT4具有219个局部最优值,干扰全局Pareto前沿的搜索,可检测算法克服陷入局部最优的能力[15];再用GD(世代距离)、IGD(反世代距离)、HV(超体积指标)和Spacing(均匀性度量指标)检测算法收敛性和多样性,GD度量解的收敛性,Spacing度量解分布的均匀性,IGD和HV综合度量解的收敛性和多样性,多样性包括体现粒子分布均匀程度的均匀性和整个解集在目标空间中分布广泛程度的广泛性,GD、Spacing和IGD值越小越好,HV值越大越好。MOSSO1算法在文献[9]中作为一种单目标算法被提出,这里将其改造成多目标算法进行分析,除了只更新粒子中的一个变量,其他地方都与MOSSOa保持一致。实验种群数和迭代次数均为100,取20次运行的最好结果,所求Pareto前沿如图1所示,四种性能指标结果如表1-表4所示。

表1 三种算法在GD指标上的比较

表2 三种算法在IGD指标上的比较

表3 三种算法在HV指标上的比较

图1 三种算法在ZDT1-ZDT4上的Pareto前沿

可以看出,MOSSOa算法与真实Pareto曲线重合得最多,MOSSO算法次之,最差的是MOSSO1算法。在ZDT2和ZDT3中,MOSSOa算法的值较其他两种算法有明显的优势,说明MOSSOa算法无论从收敛性还是多样性来看都优于其他两种算法,但是算法在ZDT4函数上效果低于其他两种算法,说明算法在跳出局部最优方面没有MOSSO算法好,MOSSO算法保留了个体最优解,可以找到多个峰值,从而避免了陷入局部最优,所以在ZDT4函数上效果最好,但是这样也影响了收敛效率。综上,MOSSOa算法较优于其他两种算法。

4.2 MOSSOa在WTA中的应用

各类型武器对目标的毁伤概率表和目标价值表如表5和表6所示[16],其中Wi表示第i种武器。迭代次数为3 000,武器种类数m=10,每种武器数对应为C=[3,1,1,5,1,1,1,8,1,10],目标数n=8。

表5 武器对目标毁伤概率值表

表6 目标价值表

假设当前有两个阶段,第一阶段出现目标的比例用一个随机值r表示,然后从目标集合中随机挑选出占总数量比例为r的目标,作为当前要打击的对象。武器的分配满足约束条件,其中武器在现阶段分配的资源耗费指数不能大于r,以保证后续阶段武器处于可防御状态,否则武器数量过少,将不能胜任防御任务。对于每个阶段的时间要求,根据武器的总数量以及以往学习经验中对作战规模的了解,为每个阶段设定1 s的分配时间。

改进多目标SSO在DWTA问题中的求解效果主要通过各阶段的求解质量和求解效率两方面来验证,为进行对比分析,MOSSO算法和MOSSOa算法也实现了在DWTA各阶段的求解,为了直观地表示求解质量的高低,将两个目标函数作归一化求和处理并作求解质量曲线,三种算法在两个阶段的收敛情况如表7所示,三种算法的求解质量和求解效率如图2所示。

表7 三种算法在两个阶段的收敛情况表

图2 三种算法在DWTA问题中的收敛效果

可以看出,在两个阶段中,MOSSOa比其他两个算法求解质量更高。MOSSO和MOSSO1两者各在一个阶段中比另一个好,则不能看出哪个更优秀。算法在每个阶段执行的时间相同,迭代的次数不同,线条周长越长,代表迭代次数越多,从第一阶段明显看出,MOSSO1的线条最长,因此其迭代次数最多,说明算法执行一次的时间最快,但也因此牺牲了求解质量。从表7可以看出,MOSSOa比MOSSO迭代次数多,算法执行时间更快,但还是没有MOSSO1快,因为MOSSO1在每个粒子中只随机选择一个变量进行更新。而MOSSO中,每个粒子需要使用两个以上的方程式,生成两个随机数、四个乘法和三个求和,才能移至下一个迭代。由于MOSSOa不需要使用速度,它仅使用几个随机数,粒子的每个变量只循环一次。所以与MOSSO算法相比,MOSSOa算法消耗更少的计算时间,效率更高。

在MOPSO中,所有粒子将根据粒子的局部和全局最佳值连续移动,这意味着该算法不会吸收外部新鲜值中的任何其他成分,而MOSSOa可以显示出其效率,尤其是在覆盖后重新定位目标对象时。MOSSOa具有灵活的粒子自适应搜索窗口以及自适应参数。

MOSSOa的更新机制比其他主要算法的更新机制简单得多,使用以上方法可以有效地维持粒子的多样性,同时保持较高的求解效率。

5 结 语

本文主要围绕DWTA问题,对适于求解该问题的算法进行研究。将MOSSOa算法应用于DWTA模型,并进行收敛速度和精度分析。本文算法首先将非支配排序算法引入SSOa算法中,使其变为多目标优化算法;其次在SSOa算法中引入HSS策略,在更新过程中动态改变步长,获得更为多样化的解,在ZDT测试函数中的测试效果表明算法收敛性较好。将算法应用于具有RBI指标衡量的DWTA算法中,证明了在保证每个阶段分配合理的情况下,算法可以求得较优的解。算法的解决对满足实际应用条件的武器目标分配问题进行继续深入研究具有深刻的现实意义,继续提高算法处理的时效性及灵活性是下一步研究的重点。