基于改进差分进化算法的跨平台武器目标分配方法

隆雨佟, 陈爱国, 史红权, 曾 黎

(1. 电子科技大学计算机科学与工程学院, 四川 成都 611731; 2. 大连舰艇学院, 辽宁 大连 116018)

0 引 言

随着信息技术和装备水平的发展,在现代作战中,武器单元的划分粒度更加精细,一次武器通道的组织通常包括预警探测、指挥决策、跟踪瞄准、火控解算、武器发射、制导控制等环节,传统的平台级协同作战方式指各个平台独立组织各自的武器通道,而在能力要素级协同作战方式下武器通道中的各环节可由不同平台交叉完成[1]。因此,跨平台的能力要素级武器单元协同利用,已成为提高合成编队等作战体系效能的重要手段。为了更好地完成能力要素级单元协同作战,武器目标分配(weapon target assignment, WTA)问题中各平台的分配方案必须分别计算,其建模与求解也面临着更大的挑战。因此,亟需一种针对跨平台WTA问题的建模求解方法以更好地完成合成编队内各平台的战术协同。

在建模方面,现有研究通常将整个编队作为资源划分的最小单位[2-3],不关注武器单元具体来自哪个平台,若后续涉及到跨平台协同制导则无法分辨武器的发射平台,不利于计算平台间的协作。文献[4]提到了多平台问题,但并没有相应的约束体现平台间的差异。另外,现有方法对WTA问题模型决策变量的编码大致分为两种,一种定义为某个武器单元是否参与拦截某个来袭目标[5],取值为0或1;一种定义为某类型武器单元参与拦截某个来袭目标的数量[2],取值为非负整数。在后者的定义中,单个决策变量包含的信息大于前者,而两者的搜索空间是一样的,因此采用后者的方式定义决策变量能大幅减少计算时间。其次,传统WTA问题的维度只考虑了武器单元与来袭目标的数量,问题通常被描述为m个武器n个目标的形式,这种做法同样忽略了武器与来袭目标的种类以及平台等信息,当同种武器数量过多时编码长度也会增加,影响求解效率[6-8]。最后,在优化目标的选取上,不少研究把最大化毁伤概率作为优化目标,同时规定每次拦截必须把全部资源消耗殆尽[3,5,9],这种做法难以应对多轮次打击,在真实作战场景中运用困难,所以应该把资源消耗作为优化目标考虑进去。对此,文献[10]将最小化来袭目标生存概率、最小化弹药消耗量价值、最小化资产损害作为优化目标建立了一个多目标优化模型并利用多目标优化算法求解,但耗时较长。文献[11]则将最大化防空作战效果与武器消耗成本的比值作为优化目标建立为单目标优化问题,但仅靠比值并不能独立地反映两个指标各自的好坏,同样比值下的两种分配方案的真实作战效果可能相去甚远。因此,优化目标的选取上既要综合考虑毁伤概率与成本消耗,也要独立反映出两者的好坏,才能使作战综合效益最大化。文献[12]在建模过程中将武器平台纳入了考虑范围,但忽略了导弹类型对毁伤概率的影响。

在算法方面,传统WTA问题已被证明为非确定性多项式完全(non-deterministic polynomial complete, NP-C)问题[13],本文研究的跨平台WTA问题规模由来袭目标数量、武器单元种类、平台数量与武器单元库存共同决定,四者中的其一增长便会导致问题求解难度呈指数级上涨。对此,学者们提出了精确算法与近似算法以解决该问题。其中,精确算法能够准确计算出WTA问题的全局最优解,如文献[14]提出了最大边际收益(maximal marginal return, MMR)算法实现对WTA问题的精确求解。文献[15]采用动态规划(dynamic programming, DP)也能准确计算出WTA问题的最优解。但是精确算法对WTA问题要求较为严苛,只能求解比较简单的小规模问题;对于高纬度大规模复杂约束的WTA问题,采用近似算法求解能取得更好的效果[16-19],其中元启发式算法应用较为普遍。如文献[4]提出了采用混沌策略的自适应差分进化算法,该算法通过计算种群适应度的方差判断是否陷入局部最优解,并施加混沌扰动助其跳出局部最优。文献[9]提出了一种基于随机邻域的自适应差分进化算法以提高传统差分进化算法的性能,但求解高维问题仍有困难。文献[20]提出了一种改进粒子群算法以提高传统粒子群算法的后期收敛能力。文献[21]提出了一种基于匈牙利-模拟退火的双层搜索算法用于解决多阶段WTA问题,能够有效缩短求解时间,但适用场景较窄。文献[22]提出了一种人工鱼群算法与改进和声搜索算法的混合算法求解WTA问题。文献[23]提出了一种改进粒子群优化算法分阶段求解多目标WTA问题。

针对建模方面的问题,本文将决策变量定义为平台的能力要素级武器单元数量以解决跨平台协作问题;加入平台资源约束使模型更贴合现实场景;采用整数编码的形式让模型能更高效地解决大规模问题;再将毁伤概率与成本消耗的分段联立函数作为优化目标,综合考虑两者的同时也能独立反映两者的优劣。

针对算法方面的问题,应该选取快速,高效,稳定,通用的优化算法用于求解。结合带存档的自适应差分进化算法(adaptive differential evolution with optional external archive, JADE)[24]是近年来差分进化算法中比较典型的一种改进算法,寻优能力突出,具有优秀的可靠性与鲁棒性。但经过本文实验表明,传统的优化算法在搜索后期陷入局部最优解时缺乏相应的跳出机制,致使收敛结果停留在局部最优解上,这一现象在解决高维度大规模带约束优化问题时尤为突出。因此,本文利用混沌映射的遍历性与随机性提出了一种混沌种群重构(chaotic population reconstruction, CPR)机制,能够帮助算法跳出局部最优解。同时,结合JADE算法提出了CPR-JADE算法,最后通过对比实验验证本文方法的有效性。

1 本文方法

1.1 问题形式化定义

本文定义参数如下:

ci——i类武器单元的单位成本;

aij——第k平台分配i类武器单元拦截第j个目标的数量;

qij——无其他因素影响下,单发i类武器单元对j类目标的基本毁伤概率;

pij——所有参与拦截第j个目标的i类武器单元的毁伤概率;

Pi——对第i个目标的毁伤概率。

首先,假定合成编队中有n个平台,m种武器单元,预测对方会使用r种单元进攻,某一时刻出现了t个来袭目标。先验条件是各平台的武器单元库存量D,每种类型武器单元的单位成本以及单枚弹药拦截目标的基本毁伤概率。武器单元库存量如下:

而不同种类的武器单元具有在造价、发射时间与装填时间上的差异,所以发射不同的武器单元有不同的成本。为了体现这些差异,本文自定义了各武器单元的成本C,如下:

C=(ci)1×m

此外,由于拦截范围或任务执行限制等因素,不是每个平台都有能力拦截所有目标,所以存在平台约束,反映为能力矩阵E,表示平台是否能够拦截某来袭目标,表示如下:

同时,又因为不同种类的来袭目标具有不同的射程、装药量、锁定范围与飞行速度,防空武器还具有不同的追踪能力,所以m种武器单元在单独拦截r种来袭目标时都有各自的毁伤概率,组成单枚武器单元毁伤概率矩阵Q=(qij)m×r。总体的单枚武器单元毁伤概率矩阵表示如下:

A=[A(1),A(2),…,A(n)]

因此,A(k)的列和表示针对各个来袭目标第k平台分配武器单元参与拦截的总数量,A(k)的行和表示第k平台每一种类型的武器单元消耗量。

1.2 跨平台资源调度模型

该模型中将武器单元细化到各个平台,面对多个目标来袭时能针对某一来袭目标从各平台中随意调配资源实施打击,其拦截轨道如图1所示。

图1 跨平台多目标拦截轨道示意图Fig.1 Cross platform multi-target interception trajectory diagram

跨平台资源调度模型的数学表达式为

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

模型的优化目标为总体毁伤概率Pdam与成本消耗con的联立函数f。在实际作战中,毁伤概率应该尽量大,但不可能达到1,并且随着Pdam越接近1边界效益递减越严重,因此需要成本消耗加以制约,同时又不能为了节约成本过分降低毁伤概率,所以本文考虑加入概率阈值Pthr,当Pdam

对于总体毁伤概率Pdam的计算,基于不同类型的武器单元对不同类型的来袭目标的毁伤概率不同这一先验条件,所以需要分开计算针对各来袭目标的毁伤概率,而针对某一来袭目标,又要分开计算不同类型的武器单元参与拦截的毁伤概率。因为成功拦截某一来袭目标的对立事件为参与拦截该目标的所有类型的武器单元都拦截失败,而单类型武器单元拦截失败的概率为所有平台发射的该类武器单元都拦截失败的事件的概率,所以对来袭目标j的毁伤概率Pj为式(3)和式(4)。其中,pij表示来自所有平台的参与拦截第j个来袭目标的第i类武器单元的毁伤概率。最后,用所有对来袭目标的毁伤概率求几何平均即可作为衡量总体打击效果的总体毁伤概率Pdam。

式(6)～式(8)为资源约束条件,式(6)表示每次分配武器单元时不得超过剩余库存量;式(7)表示各平台内某类武器单元的总消耗量不得超过总库存量;式(8)表示每个来袭目标至少分配一枚武器单元参与拦截。

本文将平台约束与资源约束式(8)定义为硬约束,当不满足时通过式(4)与式(2)得到的值为0。将资源约束式(6)与式(7)定义为软约束,使用罚函数法进行处理,构建辅助函数:

g(A)=f(A)+ε·h(A)

(9)

式中:A为问题的解;g(A)为增广目标函数;ε为罚因子;h(A)为惩罚项,定义为

(10)

表示保留资源消耗量大于库存量的解的信息,给予其一个惩罚使其往可行域靠近,当ε取值够大就能保证增广目标函数的最优解与原目标函数的最优解一致。

1.3 基于CPR-JADE算法的模型求解

在跨平台资源调度模型中,问题规模由平台数量、来袭目标数量以及弹药种类的乘积决定,搜索空间由问题规模与武器单元库存决定。由于成本消耗与库存的约束导致可行域急剧缩小。本模型实则是一个高维度大规模带约束优化问题,传统的优化方法已不足以高效求解。而混沌映射的遍历性与随机性和差分进化优秀的可靠性与鲁棒性能够很好地满足问题需求,因此本文基于以上两种方法提出CPR-JADE算法实现模型的高效求解。

1.3.1 JADE算法

差分进化算法是1997年由Storn等人提出的一种进化算法[25],拥有出色的寻优能力,被广泛运用于多个领域当中,如电力工业[26]、能源规划[27]、生物医药[28]、化学安全[29]等。经典差分进化算法的迭代过程包括变异、交叉及选择3种算子,首先父代种群里的父代个体通过差分变异产生突变向量,再通过交叉产生子代个体,然后对比父代个体与子代个体的适应度选择进入下一代种群的个体,最终形成子代种群。

JADE算法作为近年来被提出的改进差分进化算法,受到了广泛的关注,已有上千次引用。该算法保留了差分进化算法的交叉与选择框架,主要在变异算子与参数的自适应调整上作了改进并引入了外部存档机制。

在变异算子上,不同于传统的DE/rand/1算子,JADE算法选择了DE/current-to-pbest/1算子:

(11)

交叉算子为

(12)

式中:vij表示变异产生的第i个个体的第j维数据;xij表示原种群中第i个个体的第j维数据;jcrossover为随机指定的某一维,保证至少一维数据会发生变异,CR∈(0,1)为交叉因子。

选择算子为

(13)

除此之外,JADE算法的缩放因子F与交叉因子CR采用自适应调整,并且每一个个体的变异与每一维数据的交叉有独立的F与CR。缩放因子F与交叉因子CR的调整策略如下:

Fi～N(μF,0.1),Fi∈(0,1)

(14)

CRij～N(μCR,0.1),CRij∈(0,1)

(15)

式中:Fi表示第i个个体的缩放因子;CRij表示个体中第i行第j列数据的交叉因子;N(μ,σ2)表示期望为μ,方差为σ2的正态分布。

在选择算子中每当有子代个体淘汰掉父代个体,便将本淘汰个体的Fi与CRi分别存入集合SF与SCR中,再进一步改变期望μF与μCR的值:

μF=(1-c)μF+c·L(SF)

(16)

μCR=(1-c)μCR+c·ave(SCR)

(17)

式中:c为常数;ave(·)表示算数平均值;L(·)表示Lehmer平均值,具体为

(18)

1.3.2 CPR机制

在差分进化算法解决高维大规模带约束的WTA问题的过程中,由于解空间复杂,算法可能会陷入局部最优解,无法进一步更新最优解,从而大幅降低算法的搜索效率并可能影响最终的结果,这种现象被称为更新停滞。

混沌映射生成的混沌序列具有无序性,遍历性,不可预测等特点[30],为了解决更新停滞现象,本文提出了基于混沌映射的CPR机制。其思想为当算法出现更新停滞现象时,代表种群中的个体基本集中在局部最优解附近,单纯依靠算法本身难以在短时间内跳出局部最优解,因此需要一种外部机制打乱当前的搜索方向,使算法重新在全局范围内进行搜索,从而增加搜索到全局最优解的概率。

具体做法为当算法出现更新停滞现象时,首先通过将当前最优解中每维的数值变换到(0, 1)的区间内,公式如下:

(19)

其次,利用混沌映射产生种群数量减一个混沌序列,最后将混沌序列映射回整数空间,替换掉原种群中除最优个体以外的其余个体,完成种群重构。

另外,由文献[30]提出的LTS(logistic-tent system)映射具有更优秀的遍历性[31],因此本文用其生成混沌序列,表达式如下:

μ∈(0,4);x∈(0,1)

(20)

式中:μ为超参数,当μ=0时模型退化为Tent映射,当μ=4退化为Logistic映射,本文取μ=2。CPR伪代码如算法1所示。

算法 1 CPR机制输入 当前种群Pop,种群数量num输出 重构种群PopnewPopnew←Indbest;/* 将当前最优个体加入新种群 */if Indbest≠ Indlast/* Indlast为上次重构之后的最优解,初始为None */ then cur←Indbest; else cur←Indlast;end ifwhilei

1.3.3 CPR-JADE算法

本文将CPR机制与JADE算法结合提出CPR-JADE算法,流程如图2所示。

图2 CPR-JADE流程框图Fig.2 Flow diagram of CPR-JADE

本文还采用混沌映射初始化种群,可使得初始种群分布更加均匀,提高优化效率,具体操作与CPR机制类似。另外,JADE算法中的外部存档原用于存放在选择算子中被淘汰掉的个体,在CPR-JADE算法中也用于存放重构种群时被淘汰掉的个体。CPR-JADE伪代码如算法2所示。

算法 2 CPR-JADE输入 种群数量num,平台数量Np,武器单元种类Na,来袭目标数量Ne,迭代轮数T输出 最优解IndbestμCR=μF=0.5; counter=0; Dim=[Np,Na×Ne]混沌序列初始化种群for t=1 to T for i=1 to num; 自适应生成F与CR/*式(14)和式(15)*/ vi, t=mutation(xi, t)/*式(11)*/ r=rand(Dim) for j=1 to Np for k=1 to Na×Ne if rand(0, 1)

2 实验与分析

为体现CPR-JADE算法的有效性,本文选择了差分进化算法以JADE算法作为对比,并针对不同的数据规模设置了3个不同的对照组,能更直观地体现各算法在不同情况的表现。

2.1 实验环境与参数设置

实验运行环境:操作系统为Windows 10家庭版,CPU为AMD Ryzen7 4800H with Radeon Graphics 2.90 GHz,内存16 GB,编程语言为Python 3.7。

各算法的参数设置情况:基于差分进化的方法中,缩放因子F=0.8,交叉因子CR=0.8;基于JADE的方法中,μF=0.5,μCR=0.5;基于CPR-JADE的方法中,μF=0.5,μCR=0.5,K=10,其中nite为迭代次数。所有方法种群数量为10,迭代次数为150,调用评价函数次数不超过1 600。概率阈值为0.95。

实验中,平台最大数量为10,定义为

S=[s1,s2,…,s10]

武器单元的种类最大数量为10,定义为

F=[f1,f2,…,f10]

来袭目标的种类为3,定义为

B=[b1,b2,b3]

来袭目标最大数量为10,定义为

Bs=[b1,b2,b3,b2,b3,b1,b2,b1,b3,b1]

基本毁伤概率矩阵Q为

武器单元成本消耗C为

C=[100,105,110,115,120,125,130,135,140,145]

能力矩阵E为

各平台武器单元库存D为

2.2 实验结果与对比

2.2.1 216维数据规模

在本组实验下编队中平台数量、各编队拥有武器单元种类数量与来袭目标数量均为6,分别取S、F、Bs中的前6个,因此决策变量维度为216。每种方法运行150次,平均结果如表1所示,150次中各方法最优结果迭代曲线图如图3所示。

从图3(c)可以看到,在该规模下尽管最后的结果差异比较明显,但3种算法均能各自得出结果。其中,本文提出的CPR-JADE算法最早完成收敛且适应度最高。从反映平均结果的表1可以看到,CPR-JADE的平均适应度也为最高,而且标准差最低代表算法稳定性较高,耗时虽然最长但仍在可接受的范围内。

图3 216维规模下的概率-消耗迭代图Fig.3 Probability-consumption iterative graph under dimensional scale 216

表1 216维规模下平均结果对比Table 1 Comparison of average results under dimensional data scale 216

2.2.2 512维数据规模

在本组实验下编队中平台数量、各编队拥有武器单元种类数量与来袭目标数量均为8,因此决策变量维度为512。

每种方法运行100次,平均结果如表2所示,100次中各方法最优结果迭代曲线图如图4所示。

表2 512维规模下平均结果对比Table 2 Comparison of average results under dimensional data scale 512

图4 512维规模下的概率-消耗迭代图Fig.4 Probability-consumption iterative graph under dimensional scale 512

观察图4(c)可以发现,由于问题规模的上升,搜索难度急剧增大,差分进化算法已不能完成求解,而JADE算法也陷入了局部最优解出现了早熟收敛的现象。反之,CPR-JADE算法由于CPR机制可以帮助其在复杂问题中跳出局部最优解才能不断更新最优解。平均结果方面,由于差分进化算法已不能在规定迭代轮次内完成收敛,所以适应度标准差最低,而能够收敛的JADE算法以及CPR-JADE算法中CPR-JADE算法依然更加稳定。

2.2.3 1 000维数据规模

在本组实验下编队中平台数量、各编队拥有武器单元种类数量与来袭目标数量均为10,因此决策变量维度为1 000。另外,由于该规模较大,为了更好地反映各算法的表现,本文把迭代轮次更改为500,调用评价函数次数不超过5 100。

同样地,每种方法运行100次,平均结果如表3所示,100次中各方法最优结果迭代曲线如图5所示。

表3 1 000维规模下平均结果对比Table 3 Comparison of average results under dimensional data scale 1 000

观察图5(c)可以发现,3种算法的差距进一步拉开,差分进化算法仍然不能收敛,而JADE算法虽然一直在更新最优解但是每次提升幅度较小,推断是陷入了局部最优解。CPR-JADE算法有两次更新大幅提升了最优解的适应度,代表算法跳出了局部最优解,显著证明了CPR机制的作用。

图5 1 000维规模下的概率-消耗迭代图Fig.5 Probability-consumption iterative graph under dimensional scale 1 000

平均结果方面,CPR-JADE算法依然能够取得最高的适应度和较低的标准差,证明了算法的稳定性和高效性,但由于此规模较大所以各算法耗时较高。

3 结束语

相较于传统合成编队防空中的WTA模型,本文将资源分配的最小单位细化到各平台的能力要素级武器单元,并综合考虑毁伤概率与武器单元成本消耗提出了跨平台防空武器单元优化分配模型。提出了CPR机制并结合JADE算法提出了CPR-JADE算法,以求解高维度大规模带约束的WTA问题。再通过与差分进化、JADE在各种数据规模下的仿真实验对比,展现了CPR-JADE算法在各种情况下的优秀表现,满足了本文在短时间内求得毁伤概率高于概率阈值且成本消耗尽可能小的需求,验证了本文提出模型与算法的正确性和有效性。

后续研究计划从两方面开展,一是模型的建立方面,进一步引入区分多任务的跨平台协同,如跨平台火力打击与制导的协同作战模型;另一方面是求解方法,进化算法面对此类问题时基本可以做到快速高效求解,但随着数据规模的上升求解效率会逐渐下降,后续考虑加入其他领域的方法,在有限的时间内实现准确求解。