中国科技核心期刊      中国指挥与控制学会会刊     军事装备类重点期刊
Command Control and Simulation

Command Control and Simulation >

2022 , Vol. 44 >Issue 4: 31 - 41

DOI: https://doi.org/10.3969/j.issn.1673-3819.2022.04.006

Theory & Research

Operational Targets Assignment Based on Improved DE Algorithm

  • MA Yue 1, 2 ,
  • WU Lin 1 ,
  • GUO Sheng-ming 1
Expand
  • 1. National Defense University, Beijing 100091
  • 2. Unit 31002 of PLA, Beijing 100091, China

Received date: 2021-12-09

  Revised date: 2021-12-24

  Online published: 2022-08-16

Fold

Abstract

Aiming at the shortcomings of traditional differential evolution algorithm in solving operational targets assignment, such as high parameter sensitivity, low accuracy of high-dimensional variables and easy to fall into local optimization, an improved multi strategy cooperative differential evolution algorithm is proposed. The elite population is used to guide the three coevolution populations which have the same size. Each population takes the historical information of excellent variants as self-learning experience, and adaptively selects mutation strategy, mutation scaling factor and crossover probability according to the degree of evolution, so as to balance the global search ability and convergence speed. Compared with three common algorithms on eight test functions, the average value, standard deviation, Wilcoxon rank-sum test and winning rate of the optimal solution are analyzed to test the convergence and stability of the algorithm. Taking a joint fire strike as an example, the simulation results show that the algorithm can effectively solve the problem of operational targets assignment.

Key words： operational targets assignment; differential evolution; multi strategy; coevolution; adaptive parameter

Cite this article

MA Yue , WU Lin , GUO Sheng-ming . Operational Targets Assignment Based on Improved DE Algorithm[J]. Command Control and Simulation, 2022 , 44(4) : 31 -41 . DOI: 10.3969/j.issn.1673-3819.2022.04.006

作战目标分配决定了兵力运用的科学性和合理性,是将作战意图落地为作战行动的关键步骤。当联合作战指挥机构将作战任务分配给作战单元后,各作战单元为完成作战任务,需明确打击/防护目标、分配兵力/火力、规划路径/航线,从而形成一系列作战行动。当多个作战单元/作战平台共同打击多个作战目标时,为解决资源冲突和达成最大作战效果,需实现在目标、火力、时间和空间等方面的协同分配。
作战目标分配是一种典型的非线性多项式完全问题,传统数学优化方法难以求解实践问题中不连续或不可微的优化目标函数。而差分进化(Differential Evolution,DE)算法无须考虑上述条件,是一种基于差分思想实现“优胜劣汰”的启发式全局寻优算法。众多学者致力于基于DE算法解决不同场景中的作战目标分配问题。例如:Li等[1]针对多目标静态WTA问题重新定义了种群初始化、变异约束和变异选择等操作,提出一种新的离散型多目标进化算法框架;吴文海等[2]为提高DE算法求解动态火力分配的效率,利用历史进化信息自适应调整参数;欧峤等[3]构建了具有作战资源、弹目匹配和突防概率等约束条件的WTA模型,并利用改进的离散型DE算法进行求解。然而,标准DE算法采用固定的控制参数和变异策略,无法适应种群进化需求,也难以解决进化算法收敛精度低和易陷入局部最优的问题。为提高DE算法性能,诸多学者[4⇓⇓⇓⇓-9]致力于改进控制参数、变异策略和种群结构的适应性,以降低算法停滞的风险。
上述研究能够不同程度地提高算法的全局寻优能力和收敛速度,但仍存在收敛精度不高、对不同复杂函数鲁棒性较差和无法跳出局部最优的现象。而作战目标分配问题的复杂度,随着作战单元和作战目标数目的增多,呈指数级增长,求解结果的实时性、准确性和有效性,将直接影响军事对抗中能否取得最佳作战效果。据此,本文通过分析DE算法的主要影响因素,提出一种多策略自适应协同差分进化算法(Multi-strategy Adaptive Cooperative Differential Evolution, MACDE),用于求解作战目标分配问题。以精英种群引导3个等规模种群的协同进化,各种群利用进化过程中成功变异的历史信息自适应选择变异策略和控制参数,从而满足不同进化时期对算法探索和利用的需求。通过测试和应用,证明了算法的收敛性、稳定性和可行性。

1 作战目标分配建模

假设在某次作战任务规划中,已确定了所需执行的作战任务及执行作战单元。针对打击目标清单,还需将作战目标合理分配给各作战单元。
在描述作战目标分配过程中,定义以下符号:
1)Tg={tg1,tg2,…,tgN}为作战目标清单列表,N为作战目标的总数目;
2)U={u1,u2,…,uM}为进攻方可用作战单元列表,M为作战单元的总数目;
3)W={w1,w2,…,wL}为进攻方可用弹药类型列表,L为弹药类型的总数目;
4)Vtg={vtg1,vtg2,…,vtgN}为各作战目标被摧毁后的收益价值列表,vtgi为作战目标tgi被摧毁后的收益价值,i∈{1,2,…,N};
5)Vu={vu1,vu2,…,vuM}为各作战单元被摧毁后的损失价值列表,vuj为作战单元uj被摧毁后的损失价值,j∈{1,2,…,M};
6)Vw={vw1,vw2,…,vwL}为各类型弹药消耗单位数量后的损失价值列表,vwl为wl类型弹药消耗单位数量后的损失价值,l∈{1,2,…,L};
7)Tgl=(tgl1,tgl2,…,tglN)为执行作战目标分配方案时被摧毁作战目标清单向量,tgli=1表示作战目标tgi被摧毁,否则tgli=0;
8)Ul=(ul1,ul2,…,ulM)为执行作战目标分配方案时被摧毁作战单元清单向量,ulj=1表示作战单元uj被摧毁,否则ulj=0;
9)Wl=(wl1,wl2,…,wlL)为执行作战目标分配方案时进攻方的弹药消耗清单向量,wll表示wl类型弹药的单位消耗数量;
10)Vlsum为执行作战目标分配方案时防守方的弹药消耗价值总量;
11)Wut,j=(wt,j,1,wt,j,2,…,wt,j,L)为进攻方作战单元uj的挂载向量,wt,j,l为作战单元uj挂载的wl类型弹药的数目;
12)RPro={rprol,i}L×N为进攻方各类型弹药对不同作战目标的命中毁伤概率,其中,rprol,i为wl类型弹药对作战目标tgi的命中毁伤概率;
13)BPro=(bpro1,bpro2,…,bproM)为防守方一体化联合防空反导时对进攻方各作战单元的命中毁伤概率,bproj为对作战单元uj的命中毁伤概率。
作战目标分配数学模型,如式(1)所示:
m a x α × F 1 ( X ) + β × ( F 2 ( X ) F 3 ( X ) )
s . t . x i , j ∈ X ∑ i = 1 N x i , j ≤ 1 1 - ∏ l = 1 L ( 1 - r p r o l , i ) w j , l > 0 , ∀ x i , j ≠ 0 1 - ∏ j = 1 M ∏ l = 1 L ( 1 - r p r o l , i ) w j , l x i , j > P ∏ j = 1 M ( 1 - b p r o j ) x i , j > Q i ∈ { 1 , … , N } , j ∈ { 1 , … , M } , l ∈ { 1 , … , L }
式中,变量xi,j表示是否指派作战单元uj打击作战目标tgi。当指派uj打击tgi时xi,j=1,否则xi,j=0。 ∑ i = 1 Nxi,j≤1表示作战单元uj最多只能攻击一个作战目标;1- ∏ l = 1 L(1-rprol,i ) w j , l>0对于∀xi,j≠0恒成立,表示当指派单元uj打击tgi时,需保证uj所携带弹药对tgi能够造成损伤; ∏ j = 1 M(1-bproj ) x i , j>Q,表示指派打击tgi的所有作战单元能够突防敌一体化联合防空反导体系的概率应大于阈值Q; 1- ∏ j = 1 M ∏ l = 1 L ( 1 - r p r o l , i ) w j , l x i , j>P,表示指派打击tgi的所有作战单元对该目标的总体命中毁伤概率应大于阈值P。F1(X)、F2(X)和F3(X)分别表示使命完成度、摧毁目标总收益和总损失,计算方法为:
F1(X)= ∑ j = 1 M u l j - ∑ i = 1 N t g l i ∑ j = 1 M u l j - ∑ i = 1 N t g l i
F2(X)= ∑ i = 1 N(tgli×vtgi)+Vlsumt
F3(X)= ∑ j = 1 Mulj×vuj+ ∑ l = 1 Lwll×vwl

2 多策略协同差分进化算法

经典DE算法采用浮点矢量编码,随机初始化种群以覆盖整个解空间,种群规模、控制参数和相关策略一般固定不变,基本步骤为:
步骤1:种群初始化。根据优化问题确定种群规模、基因维度和基因取值的上下限。规模为NP的种群初始化方法,如式(3)所示:
x i , j 0=xj_min+rand×(xj_max-xj_min)
其中, x i , j 0表示初始种群的第i个个体的第j维基因的取值;i∈{1,2,…,NP},表示种群中的第i个个体;j∈{1,2,…,D},表示个体的第j维基因;xj_min、xj_max是第j维基因可取的最大和最小值;rand为(0,1)之间的随机数。
步骤2:种群变异及检测。从父代种群中随机选择若干个体生成差分向量,对基向量进行扰动以生成变异体,常用的随机变异策略如式(4)所示。此外,变异会出现基因数值超出范围的情况,因此,需对变异体上基因进行边界检测,可采用“边界吸收”或“重新生成”策略进行处理。
v i G + 1= x r 1 G+F×( x r 2 G- x r 3 G)
式中, v i G + 1表示第G+1代种群中第i个变异体; x r 1 G、 x r 2 G和 x r 3 G分别为第G代种群中的第r1、r2和r3个个体,且r1、r2、r3∈{1,2,…,NP};F为变异缩放因子,控制差分向量对基向量的扰动程度。
步骤3:种群交叉。为增加变异体的多样性,将变异体与原种群个体进行基因混合,以生成新的子代个体,称为试验体。引入交叉概率CR,控制试验体由变异体上基因组成的概率。若采用“二项交叉”策略,试验体由式(5)计算得到:
u i , j G + 1= v i , j G + 1 , 　 r a n d ( 0,1 ) ≤ C R o r 　 j = j r x i , j G , o t h e r w i s e
式中, u i G + 1为第G+1代试验体; x i G为第G代种群中相应的个体,也称为目标体。jr是[1,D]内的随机整数,条件j=jr确保了试验中一定有基因来自变异体。
步骤4:种群选择。采用“贪婪策略”,从父代种群和试验体集合中挑选优秀个体组成下一代种群。计算所有试验体适应值,并与父代目标体逐一对比,若试验体优于目标体,则取代目标个体,否则目标个体保留,如式(6)所示:
x i G + 1= u i G + 1 f ( u i G + 1 ) ≫ f ( x i G ) x i G f ( x i G ) ≫ f ( u i G + 1 )
式中,f(·)为适应度函数。当目标函数为求解最大值时,f( u i G + 1)≫f( x i G)表明前者优于后者,反之亦然。

2.1 影响因素分析

算法的探索(Exploration)和利用(Exploitation)相互对立,不同进化阶段对全局寻优能力和收敛速度有不同的需求,如表1所示。而固定的控制参数和单一的变异策略难以保证种群在不同进化程度具备适应的进化性能。因此,常常通过适应性调整控制参数和变异策略,减缓种群多样性和收敛速度之间的矛盾。
表1 不同阶段需求
阶段 需求
进化
初期		 种群个体适应度差,为避免算法陷入局部最优,需要较大的种群多样性以充分在解空间中进行搜索,因此,要减缓进化速度和扩大寻优范围
进化
后期		 为寻找最优解,需提高算法的局部勘探能力和提高进化速度,因此,需要缩小寻优范围和有效保留进化过程中的优良个体,提高收敛速度
变异缩放因子和交叉概率,对平衡算法全局和局部寻优能力至关重要,其数值大小及作用如表2所示。通常以算法进化代数、种群整体适应度和个体适应度等信息为依据进行自适应调整。在进化初期,需要较大的缩放因子以增大差分向量的扰动程度、扩大解的搜索范围和保证种群向全局最优解方向靠拢,同时需要较大的交叉概率以保证子代种群中的信息更多来自变异向量。而在进化后期,需要较小的交叉概率保证子代种群中的优质个体免于破坏,提高最终优化结果的精度,而较小的缩放因子保证了围绕优质个体周围生成变异体,使种群聚集于全局最优解附近。
表2 控制参数的作用
参数 作用 数值较大 数值较小 等于0
缩放
因子		 控制差分向量对基向量的扰动程度,影响算法的全局寻优能力和寻优速度,取值为[0,1]之间的随机浮点数 增大对基向量的扰动程度,有利于提高种群多样性和算法的全局寻优能力,但收敛速度较慢 有利于提高算法的局部寻优能力和算法的收敛速度 变异操作中的差分向量为0,相当于没有进行变异操作
交叉
概率		 控制变异个体信息进入子代种群的概率,反映了父代、中间变异体和子代之间的信息交换程度,取值为[0,1]之间的随机浮点数 子代信息主要来源于变异个体,从而提高了种群多样性和全局搜索能力,但也极易破坏优质个体,降低了收敛速度 子代的产生集中在父代个体周围,提高了种群的局部寻优能力和算法收敛速度 子代信息几乎全部来自父代,种群失去搜索能力
在不同进化时期自适应选择变异策略,称为多策略自适应选择(Multi-strategy Adaptive Select),其主要思路是:以迭代次数或种群适应度相关统计信息判断进化程度,并据此选择适应的变异策略或混合策略。变异策略可用“DE/A/B”形式表示,A指定了基向量,B指定了差分向量的数目。各种变异策略的公式及特点,如表3所示。其中, v i G + 1表示第G+1代种群中第i个变异体;r1、r2、r3、r4和r5是在[1,NP]之间随机选取的整数,且满足r1≠r2≠r3≠r4≠r5≠i; x r 1 G、 x r 2 G、 x r 3 G、 x r 4 G和 x r 5 G为第G代种群中的随机个体, x b e s t G为第G代种群中最优个体; x p b e s t G为最优种群中的随机个体,而最优种群是当代种群中适应度排名在前p的个体;变异缩放因子F决定了变异程度,影响算法的全局寻优能力;随机数K∈(0,1),在种群规模足够大时,尽量使用两个差分向量以增加种群多样性。
表3 不同变异策略对比
策略 公式 特点
DE/rand/1 v i G + 1= x r 1 G+F×( x r 2 G- x r 3 G) rand表示基向量为随机个体,有利于保持较大的搜索范围和种群多样性,具有较好的全局搜索能力,对解决多峰问题表现较好,但寻优速度较慢
DE/rand/2 v i G + 1= x r 1 G+F×( x r 2 G- x r 3 G)+
F×( x r 4 G- x r 5 G)
DE/current-to-rand/2 v i G + 1= x i G+F×( x r 1 G- x i G)+
F×( x r 2 G- x r 3 G)		 在DE/rand/2基础上,围绕当前个体展开随机搜索,增强了局部搜索能力和收敛速度
DE/best/1 v i G + 1= x b e s t G+F×( x r 1 G- x r 2 G) best表示基向量为种群最优个体,引导种群个体向最优处靠近,寻优速度较快,对解决单峰问题表现较好,但易陷入局部最优
DE/best/2 v i G + 1= x b e s t G+F×( x r 1 G- x r 2 G)+
F×( x r 3 G- x r 4 G)
DE/rand-to-best/1 v i G + 1= x r 1 G+K×( x b e s t G- x r 1 G)+
F×( x r 2 G- x r 3 G)		 在DE/rand/B基础上,通过种群最优个体 x b e s t G的引导,以牺牲部分全局搜索能力为代价,增强了局部搜索能力和收敛速度
DE/rand-to-best/2 v i G + 1= x r 1 G+K×( x b e s t G- x r 1 G)+
F×( x r 2 G- x r 3 G)+F×( x r 4 G- x r 5 G)
DE/current-to-best/1 v i G + 1= x i G+K×( x b e s t G- x i G)+
F×( x r 1 G- x r 2 G)		 引导围绕最优个体和当前个体展开搜索,能够加速算法趋优收敛进程,但难以保证种群多样性,易收敛至局部最优
DE/current-to-best/2 v i G + 1= x i G+K×( x b e s t G- x i G)+
F×( x r 1 G- x r 2 G)+F×( x r 3 G- x r 4 G)
DE/pbest/1 v i G + 1= x p b e s t G+F×( x r 1 G- x r 2 G) pbest表示基向量为种群中适应度排名在前p的一个随机个体。相比best策略,能够避免种群个体只聚集于最优个体而导致早熟。xr2是历史最优个体集合与当前最优种群的随机个体
DE/current-to-pbest/1 v i G + 1= x i G+K×( x p b e s t G- x i G)+
F×( x r 1 G- x ˙ r 2 G)

2.2 算法改进

为避免随机搜索中种群进化被最优个体操控而陷入局部最优,多策略自适应协同进化算法(MACDE)采用分布式差分进化思想设立多个进化种群,通过定期更新精英种群和引导进化种群的交叉变异,实现种群之间的信息共享。进化种群根据自身进化程度和历史经验信息,自适应选择变异策略和控制参数。
1)协同进化机制
协同进化机制,是指多种群独立进行交叉变异并定期进行信息共享,从而实现共同进化以提高算法的寻优能力,其关键在于如何恰当地划分子种群、实现进化的互不干扰和信息共享。多种群协同进化具有很大优势:首先,不同种群的变异策略和控制参数可以多样化,能够分别实现探索未知解空间、维持精英个体进化等不同特殊任务;其次,不同种群之间存在的差异,在信息共享后能有效增加种群的多样性;第三,多种群分别进行变异交叉,有利于算法的并行化处理,有效减少求解时间。MACDE算法采用三个进化种群和一个精英种群,如图1所示。
图1 多种群协同进化
进化种群负责探索解空间和推动整个种群向全局最优解方向进化,精英种群负责保留各进化种群在历史进化中的精英个体,并适时引导进化种群搜索最优。在进化初期,进化种群保持活跃的变异活动,以尽可能探索未知解空间和保持种群内部差异性,而精英种群只更新其内部的精英个体,不对进化种群进行干扰,从而防止过早“干预”导致收敛到局部最优。经过多次迭代进化后,精英种群内个体逐步靠近全局最优,因此,可利用精英个体引导算法的进化方向。
种群内部个体间的变异交叉无法实现多种群协同进化,因此,在确保种群独立进化而不受其他种群干扰的同时,还需按照一定策略进行种群间信息的充分共享。MACDE算法中,精英种群规模为进化种群规模的30%,种群之间的信息交流与共享发生在每次迭代之后,其思路是:进化种群每次迭代进化后,取出适应度排名在前30%的个体,组成该次迭代产生的候选精英个体集合;而后分别与精英种群中的个体一一进行比较,并替换精英种群中表现较差的个体。算法迭代结束后,选择精英种群中最优个体作为最终解。
2)多变异策略选择
不同变异策略,或注重扩大随机搜索范围以增大种群多样性,或注重围绕优秀个体进行局部搜索以提高收敛速度,但难以同时兼顾探索与利用。单一变异策略,难以满足种群进化在不同时期对全局搜索能力和收敛速度的需求变化。因此,许多学者[10-11]提出使用混合变异策略,但实质仍旧是不同变异策略根据执行条件的选择,刚性的组合反而难以灵活发挥各变异策略的优势。
MACDE算法采用4种变异策略,分别为DE/rand/1、DE/rand/2、DE/current-to-rand/2和DE/current-to-pbest/2。为增加种群多样性,在每次迭代时,种群个体根据以往能够产生优秀变异体的统计信息进行变异策略选择,从而充分利用前期搜索经验,选择适应于种群和个体进化程度的变异策略。变异策略选择及更新步骤为:首先,初始化各变异策略的选择概率PR1、PR2、PCR和PCPB,并构建选择概率的斐波那契数列;然后,每个个体通过“轮盘赌”方式选择执行的变异策略;第三,分别记录每种变异策略选择的次数numR1、numR2、numCR和numCPB以及能够产生优秀变异体的每种变异策略的次数num_bestR1、num_bestR2、num_bestCR和num_bestCPB,变异策略的选择概率PR1、PR2、PCR和PCPB更新方法如式(7)所示;第四,对变异策略的选择概率进行归一化处理,如式(8)所示,其中,k∈{R1,R2,CR,CPB};最后,返回第二步,继续进行种群的迭代进化和选择概率的应用与更新。
P=num_best/num
P'k=Pk/ ∑ i ∈ { R 1 , R 2 , C R , C P B } Pi
算法前期以探索解空间为主,进化种群分别独立进行交叉变异以增大种群多样性;在进化后期,为引导种群加快向全局最优解处搜索,以精英种群中的优秀个体作为基变量进行种群变异。DE/rand/1、DE/current-to-rand/2和DE/rand/2计算方法不变,而DE/current-to-pbest/2的计算方法,如式(9)所示:
v i G + 1= x i G + K × ( x p b e s t G - x i G ) + F × ( x r 1 G - x r 2 G ) , τ < 0.5 x i G + K × ( x ˙ p b e s t G - x i G ) + F × ( x r 1 G - x r 2 G ) , τ ≥ 0.5
式中, x p b e s t G为种群排名前p的随机优秀个体,而 x ˙ p b e s t G为精英种群中排名前p的随机优秀个体;τ=G/Gmax反映了种群进化程度,Gmax为最大迭代次数。为了确保有足够的较优个体和较快的迭代速度,设置以下限制条件:当种群前p的个体数目小于Δ时,至少选择Δ个随机最优个体,且最多选择3Δ个较优个体。
3)参数自适应选择
每个种群的进化程度不同,因此,难以共享控制参数和变异策略的选择经验,如种群A中参数和策略的历史统计信息,无法反映种群B的进化程度。因此,需要保证种群之间相对独立进化,而将精英个体的更新和交流作为种群协同进化信息共享的途径。种群内不同个体进化程度存在差异,为不同个体适应性选择不同控制参数,将更加有利于种群进化。
MACDE算法为种群每个个体都适应性地选择控制参数F和CR。控制参数通过正态分布采样获得,而正态分布的均值根据历史进化中能够产生优秀变异体的统计信息进行调整更新,如式(10)和式(11)所示。其中,randn(·)为正态分布,mean(·)为计算数值集合算术平均值的函数;uF和uCR分别为正态分布的均值;c决定了历史经验对控制参数更新的影响大小;SF和SCR分别为历史进化过程中能够获取优秀变异体的变异缩放因子和交叉概率的数值集合。
FG+1=randn( u F G + 1,0.1)
CRG+1=randn( u C R G + 1,0.3)
u F G + 1=(1-c)× u F G+c×mean(SF)
u C R G + 1=(1-c)× u C R G+c×mean(SCR)
为保证进行充分搜索,种群前期进化具有很大随机性,此时的种群整体进化程度和个体适应度较差,短期内对控制参数选择经验的统计有较大偏差。因此,进化前期,控制参数需维持较高数值,避免受带有较大噪声的历史经验的干扰。在经过长时间进化后,可产生优秀变异体的控制参数有较大样本,此时,再引入统计信息更新修改正态分布均值,具有较大的可信度。MACDE算法中,控制参数根据种群进化进行非线性调整,参数c在前期数值较低且变化缓慢,在后期数值趋于固定值。Sigmoid函数顶部和底部较为平滑,满足上述非线性变化要求,因此,采用该函数进行参数c的动态计算,如式(12)所示:
c=cmax×sigmoid G m a x × ( τ - 0.3 ) 60

2.3 算法实现

多策略自适应协同差分进化算法的基本实现流程,如图2所示。
图2 MACDE算法流程
步骤1:初始化进化种群和精英种群,确定可供选择的变异策略集合,并为变异策略的选择概率、变异参数F和CR赋初始值。
步骤2:进化种群分别进行变异操作。首先,根据变异策略的选择概率,通过“轮盘赌”方式确定种群的变异方式;然后,根据变异缩放因子对应的采样均值进行正态分布采样,如式(10)所示;第三,进行种群变异操作,并记录每种变异策略的使用次数;最后,进行基因检测和处理。当迭代次数超过所需迭代总数一半时,开始利用精英种群中优秀个体参与各进化种群的变异,如式(9)所示。
步骤3:进化种群分别进行交叉与选择。首先,根据交叉概率CR对应的采样均值进行正态分布采样,如式(10)所示;然后,逐一判断变异体上的基因是否与原种群个体对应基因进行交叉,如式(5)所示;第三,计算新产生的各变异体的适应度值,如式(6)所示,采用贪婪策略选择优秀个体组成下一代种群,并记忆产生该变异体所使用的变异策略、变异缩放因子和交叉概率。
步骤4:更新变异策略的选择概率和控制参数的采样均值。根据存储的产生优秀变异体的信息,计算变异策略选择概率并归一化处理,如式(7)和式(8)所示;更新控制参数F和CR的正态分布采样均值,如式(11)和式(12)所示。
步骤5:更新精英种群。当3个进化种群完成变异、交叉和选择操作后,选择种群中适应度排名前30%NP的优秀个体,而后逐一与精英种群中的个体进行比较,并替换表现较差的精英个体,以保持精英种群中个体的最优。
步骤6:判断迭代进化是否结束。迭代结束,则从精英种群中选择最优个体作为输出,否则继续进行迭代进化。

3 算法测试与应用

3.1 算法测试

为测试MACDE算法的可行性和有效性,选择8个测试函数,与标准DE算法、JADE算法和SaDE算法进行比较。测试函数f1(x)、f2(x)、f7(x)、f8(x)为单峰函数,测试函数f3(x)、f4(x)、f5(x)、f6(x)为多峰函数,其表达式、取值范围和理论最小值,如表4所示。
表4 测试函数
序号 函数 取值范围 最优值
f1(x) ∑ i = 1 x i 2 D [-100,100] 0
f2(x) ∑ i = 1 ∑ q = 1 x q i 2 D [-100,100] 0
f3(x) ∑ i = 1 [ x i 2 D - 10 c o s ( 2 π x i ) + 10 ] [-5.12,5.12] 0
f4(x) 1 4000 × ∑ i = 1 x i 2 D - ∏ i = 1 c o s D x i i + 1 [-600,600] 0
f5(x) ∑ i = 1 | x i s i n x i + 0.1 x i | D [-10,10] 0
f6(x) ∑ i = 1 D - 1 [ 100 ( x i + 1 - x 1 2 ) 2 + ( 1 - x i 2 ) 2 ] [-2,2] 0
f7(x) ∑ i = 1 D x i 2 + ∑ i = 1 D 0.5 i x i 2 + ∑ i = 1 D 0.5 i x i 4 [-5,10] 0
f8(x) ∑ i = 1 D x i 2 ( 10 6 ) ( i - 1 ) / ( D - 1 ) [-100,100] 0
通过实验,分别从平均值、标准差、Wilcoxon rank-sum test和胜率4个方面比较各算法在测试函数上的表现。4种算法均在变量维数为D=20、D=30和D=60的情况下独立运行40次,种群规模为变量维数的8倍,其参数设置如表5所示。
表5 各算法参数
算法 缩放因子 交叉概率
F μ δ CR μ δ
DE 0.6 — — 0.5 — —
SaDE — 0.5 0.3 — — 0.1
JADE — — 0.1 — — 0.1
MACDE — — 0.3 — — 0.1
1)平均值与标准差分析
本文分别统计标准DE算法、SaDE算法、JADE算法和MACDE算法在8个函数及不同变量维数情况下求解得到的最优值(即最小值),如表6所示。在“优劣”一栏,“+”、“=”和“-”,分别表示MACDE算法优于、等于或劣于其他算法。平均值能够反映算法在求解函数最优值时收敛精度的高低,而标准差反映了算法在多次求解函数最优值时的稳定性。4种算法在变量维数为20和30时的进化代数为1 000。随着变量维数的增多,算法收敛速度将会降低,为得到理想的函数最优值,将变量维数为60时的进化代数设为1 500。
表6 最优解的平均值与标准差
函数 算
法		 D=20 D=30 D=60
平均值 标准差 优劣 平均值 标准差 优劣 平均值 标准差 优劣
f1 DE 4.07E-08 1.09E-08 + 4.43E-01 7.25E-02 + 1 887.05 251.987 1 +
SaDE 4.72E-40 1.72E-39 + 3.04E-31 1.20E-30 + 1.07E-45 2.01E-45 +
JADE 6.22E-17 3.93E-16 + 1.54E-06 4.40E-06 + 24.704 97 9.932 828 +
MACDE 3.85E-61 4.39E-61 6.39E-46 8.44E-46 4.58E-58 2.59E-58
f2 DE 4.81E-03 1.94 E-03 + 3.79E+01 13.456 94 + 2873.385 770.835 +
SaDE 4.97E-29 1.47E-28 + 1.19E-17 2.77E-17 + 1.51E-11 1.67E-11 +
JADE 7.50E-08 3.12E-07 + 1.21E-01 0.124 257 + 271.613 2 81.926 88 +
MACDE 4.16E-41 7.62E-41 1.54E-25 2.61E-25 6.82E-18 7.57E-18
f3 DE 76.988 4 4.040 223 + 176.199 2 4.575 15 + 543.649 9 6.955 631 +
SaDE 9.33E-02 2.95E-1 + 1.24E-01 3.34E-01 + 57.936 26 14.347 01 +
JADE 78.974 87 5.428 79 + 162.152 7 6.232 168 + 425.857 4 12.787 88 +
MACDE 0 0 0 0 0 0
f4 DE 2.03E-01 6.64E-02 + 7.68E-01 5.78E-02 + 18.426 58 2.541 92 +
SaDE 0 0 = 0 0 = 0 0 =
JADE 1.11E-03 4.28E-03 + 2.16E-03 5.87E-03 + 1.2317 1.11E-01 +
MACDE 0 0 0 0 0 0
f5 DE 1.73E-02 1.15E-03 + 9.40E+00 0.994 304 + 55.687 7 2.071 67 +
SaDE 1.28E-03 7.74E-04 + 5.50E-03 1.64E-03 + 1.86E-03 3.18E-03 +
JADE 3.36E-03 4.97E-03 + 5.53E-04 3.17E-03 + 1.18E-01 6.94E-02 +
MACDE 4.32E-17 1.80E-16 1.61E-13 4.79E-13 2.33E-29 9.37E-29
f6 DE 5.53E-04 2.26E-04 + 2.41E+00 0.680 219 + 176.4462 15.089 +
SaDE 9.10E-22 2.47E-21 + 6.40E-15 1.92E-14 + 2.81E-18 5.05E-18 +
JADE 1.48E+00 1.933 247 + 6.39E+00 5.622 39 + 48.943 34 5.8786 78 +
MACDE 0 0 1.25E-26 1.81E-26 1.78E-29 2.82E-29
f7 DE 1.24E-07 4.55E-08 + 5.13E-02 1.22E-02 + 20.093 79 5.623 746 +
SaDE 1.51E-39 3.54E-39 + 7.83E-30 9.98E-30 + 2.25E-36 5.19E-36 +
JADE 1.73E-13 7.55E-13 + 3.39E-06 7.68E-06 + 0.071 981 0.034 993 +
MACDE 2.54E-55 7.29E-55 4.26E-40 8.37E-40 6.26E-47 1.08E-46
f8 DE 7.89E-06 2.25E-06 + 5.64E+01 11.458 14 + 124 613.6 18 000.28 +
SaDE 9.09E-37 1.56E-36 + 1.49E-28 3.33E-28 + 1.19E-41 2.34E-41 +
JADE 1.70E-33 1.07E-32 + 4.89E-11 1.60E-10 + 65.445 78 52.466 82 +
MACDE 2.01E-57 3.55E-57 1.32E-42 1.65E-42 6.07E-54 8.16E-54
从表6中统计结果可见:
①从平均值和标准差角度,MACDE算法在8个函数上表现都不劣于其他三种算法,且只有在函数f4(x)上的表现等于SaDE算法。对于复杂单峰和多峰函数,MACDE算法虽然没有求解得到理论最优值,但寻优结果已十分接近于理论值,且明显优于其他算法。同时,MACDE算法在各函数上的标准差数值均小于其他算法,因此,具有较好的稳定性。
②从不同变量维数求解结果角度。相同进化代数条件下,算法收敛精度随着变量维数的增大而降低,各算法在变量维数为30时的平均值和标准差均劣于变量维数为20时的统计结果。变量维数为60时,虽然增大了进化代数,但DE、SaDE和JADE算法在某些函数上的求解精度仍然很低,说明3种算法收敛速度很低,甚至陷入了局部最优的困境。然而,MACDE算法能够保持较高的求解精度,且在f1(x)、f5(x)、f6(x)、f7(x)和f8(x)上的精度更高,可见该算法依然保持着较好的全局寻优能力和较快的收敛速度。
2)Wilcoxon秩和检验和胜率分析
为进一步对MACDE算法进行分析,利用威尔科克森秩和检验(Wilcoxon rank-sum test)[12],确定MACDE算法与其他算法是否具有统计学意义上的差异,再使用胜率对算法性能进行分析。Wilcoxon rank-sum test可用于检测两组独立样本是否来自同一分布采样,当两组样本数据通过检测得到pvalue值且小于0.05时,说明样本分别来自于分布不同的总体。在判断MACDE算法与其他算法存在统计学意义上的差异后,再比较与其他算法在不同函数和维数情况下的获胜次数。如表7所示,“pvalue”一栏为MACDE分别与其他3种算法所求解函数最优值数据,在进行Wilcoxon rank-sum test所得的pvalue数值;在“差异性”一栏,“T”表示MACDE算法与其他算法存在差异,否则为“F”。“胜率”一栏为,在相同函数和变量维数情况下,各算法在40次同时独立运行过程中,能够寻得比其他算法更优结果的占比。如果存在几种算法寻优结果相同,则认为它们共同获胜,因此,4种算法的胜率相加可能大于100%。
表7 Wilcoxon秩和检验及胜率统计
函数 算法 D=20 D=30 D=60
pvalue 差异性 胜率 pvalue 差异性 胜率 pvalue 差异性 胜率
f1 DE 7.17E-15 T 0.0% 7.18E-15 T 0.0% 3.40E-08 T 0.0%
SaDE 7.17E-15 T 0.0% 7.18E-15 T 0.0% 3.40E-08 T 0.0%
JADE 7.17E-15 T 0.0% 7.17E-15 T 0.0% 3.40E-08 T 0.0%
MACDE — — 100.0% — — 100.0% — — 100.0%
f2 DE 7.18E-15 T 0.0% 7.17E-15 T 0.0% 3.40E-08 T 0.0%
SaDE 7.17E-15 T 0.0% 7.18E-15 T 0.0% 3.40E-08 T 0.0%
JADE 7.18E-15 T 0.0% 7.17E-15 T 0.0% 3.40E-08 T 0.0%
MACDE — — 100.0% — — 100.0% — — 100.0%
f3 DE 2.76E-13 T 0.0% 1.87E-12 T 0.0% 3.40E-08 T 0.0%
SaDE 0.044 703 T 90.6% 3.87E-11 T 56.3% 3.40E-08 T 0.0%
JADE 1.05E-13 T 0.0% 1.05E-13 T 0.0% 4.00E-09 T 0.0%
MACDE — — 100.0% — — 100.0% — — 100.0%
f4 DE 9.83E-17 T 0.0% 9.83E-17 T 0.0% 4.00E-09 T 0.0%
SaDE 3.52E-15 T 100.0% 7.17E-15 T 100.0% 3.40E-08 T 100.0%
JADE 9.83E-17 T 62.5% 9.83E-17 T 7.5% 4.00E-09 T 0.0%
MACDE — — 100.0% — — 100.0% — — 100.0%
f5 DE 7.18E-15 T 0.0% 7.18E-15 T 0.0% 3.40E-08 T 0.0%
SaDE 1.13E-14 T 0.0% 7.18E-15 T 0.0% 3.40E-08 T 0.0%
JADE 7.18E-15 T 2.5% 7.18E-15 T 2.5% 3.40E-08 T 0.0%
MACDE — — 97.5% — — 97.5% — — 100.0%
f6 DE 7.18E-15 T 0.0% 7.18E-15 T 0.0% 3.40E-08 T 0.0%
SaDE 2.56E-2 T 0.0% 6.23E-4 T 0.0% 3.40E-08 T 0.0%
JADE 9.83E-17 T 57.5% 7.18E-15 T 0.0% 2.66E-08 T 0.0%
MACDE — — 100.0% — — 100.0% — — 100.0%
f7 DE 7.17E-15 T 0.0% 7.18E-15 T 0.0% 3.40E-08 T 0.0%
SaDE 7.17E-15 T 0.0% 7.17E-15 T 0.0% 3.40E-08 T 0.0%
JADE 7.17E-15 T 0.0% 7.18E-15 T 0.0% 3.40E-08 T 0.0%
MACDE — — 100.0% — — 100.0% — — 100.0%
f8 DE 7.17E-15 T 0.0% 7.17E-15 T 0.0% 3.40E-08 T 0.0%
SaDE 7.17E-15 T 0.0% 7.17E-15 T 0.0% 3.40E-08 T 0.0%
JADE 7.17E-15 T 0.0% 7.18E-15 T 0.0% 3.40E-08 T 0.0%
MACDE — — 100.0% — — 100.0% — — 100.0%
从表6统计结果可见:
①从算法差异性来看。在相同情况下,MACDE算法所求最优解与其他算法所求解经过Wilcoxon rank-sum test后,所得pvalue数值均小于0.05。因此,MACDE算法与其他算法存在统计学意义上的差异,是一种新的差分进化算法。
②从胜率统计结果来看。SaDE算法在函数4上求解最优值的表现,能与MACDE算法媲美,但在函数5和6上却劣于JADE算法,两种算法不具有稳定性。而MACDE算法始终能够取得最接近理论最优值的解,其胜率保持在100%,对于不同函数及变量维数具有稳定的寻优表现。

3.2 算法应用

本文以联合火力打击为例进行仿真实验,对所提算法进行验证。案例中,弹药类型及数量、武器平台类型及数量、打击目标类型和弹目匹配关系等信息,如表8、表9和表10所示。
表8 弹药数据
序号 类型 数量 价值
1 W_1 2 0.6
2 W_2 24 0.05
3 W_3 16 0.04
4 W_4 80 0.05
表9 武器平台及目标数据
ID 类型 所属方 数量 价值 挂载/数量
1 P1 Red 2 0.05 W1/1
2 P2 Red 2 0.4 W2/4
3 P3 Red 2 0.4 W2/4
4 P4 Red 2 0.5 W2/4
5 P5 Red 2 0.6 W3/8
6 T1 Blue 2 0.6 W4/20
7 T2 Blue 2 0.8 W4/20
8 T3 Blue 2 0.5 -
9 T4 Blue 2 0.9 -
表10 弹目匹配数据
平台 弹药
W1 W2 W3 W4
P1 - - - 0.4
P2 - - - 0.5
P3 - - - 0.4
P4 - - - 0.4
P5 - - - 0.5
T1 0.6 0.8 0.7 -
T2 0.7 0 0.6 -
T3 - 0.6 0 -
T4 0.8 0.5 0.7 -
使用MACDE算法求解作战目标分配问题,在仿真环境中迭代运行1 000次,得到的适应值、敌我双方损失数(武器平台与弹药消耗)以及敌我武器平台剩余率(武器平台损失数目与初始数目之比),如图3所示。将最优解对应的染色体进行解码,得到的武器目标分配方案,如表11所示。统计数据表明:算法能够很快收敛到最优解,且结果满足作战目标分配需求,保证了较大的收益值和较小的损失值,能够在己方武器平台损失为0的情况下摧毁所有的敌方目标。
图3 仿真实验结果
表11 武器目标分配结果
平台 目标
T1 T2 T3 T4 T5 T6 T7 T8
P1 × × × ✓ × × × ×
P2 × × × × × ✓ × ×
P3 × ✓ × × × × × ×
P4 × × × × × × ✓ ×
P5 ✓ × × × × × × ×
P6 × × × × × × × ✓
P7 × × × × ✓ × × ×
P8 × × ✓ × × × × ×
P9 × ✓ × × × × × ×
P10 × × × ✓ × × × ×

4 结束语

为提高基于差分进化算法求解作战目标分配的精确度和合理性,本文提出一种改进的多策略协同差分进化算法,采用多种群协同和多变异策略适应性选择机制,以多种群协同进化优势保证种群的多样性和全局搜索能力,以不同变异策略优势的有效结合满足不同进化阶段对算法全局搜索能力和收敛速度的需求,以变异缩放因子和交叉概率的自适应性选择满足种群进化程度对参数的敏感性要求,从而弥补传统进化算法收敛精度低和易陷入局部最优的缺陷。实验结果表明:MACDE算法具备较强的全局寻优能力,能够在高维变量情况下保持较好的收敛精度和收敛速度,对不同函数及变量维数具有稳定的寻优能力。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Li X Y, Zhou D Y, Pan Q, et al. Weapon-Target Assignment Problem by Multi-objective Evolutionary Algorithm Based on Decomposition[EB/OL]. (2018-10-13) [2021-12-01]. https://doi.org/10.1155/2018/8623051

[2]
吴文海, 郭晓峰, 周思羽, 等. 改进差分进化算法求解武器目标分配问题[J]. 系统工程与电子技术, 2021, 43(4):1012-1021.

[3]
欧峤, 贺筱嫒, 郭圣明. 基于改进DDE算法的协同目标分配问题研究[J]. 指挥与控制学报, 2019, 5(4):282-287.

[4]
Storn R, Price K. Differential Evolution-a Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces[EB/OL].(1995-03-01) [2021-12-01]. http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1995/tr-95-012.pdf/

[5]
Swagatam D, Amit K, Chakraborty U K. Two Improved Differential Evolution Schemes for Faster Global Search[C]// Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation Conference, Washington DC: ACM, 2005:991-998.

[6]
Zhang J Q, Sanderson A C. JADE: Adaptive Differential Evolution with Optional External Archive[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5):945-958.

DOI

[7]
朱琳. 差分进化算法的改进研究[D]. 兰州: 西北师范大学, 2018.

[8]
方力, 陈春花, 周文, 等. 一种自适应差分进化算法及其在空间堆智能设计中的初步应用[J]. 核技术, 2021, 44(5): 50604.

[9]
Tian M N, Gao X B, Dai C. Differential Evolution with Improved Individual-based Parameter Setting and Selection Strategy[J]. Applied Soft Computing, 2017(56):286-297.

[10]
胡福年, 董倩男. 多策略自适应变异的差分进化算法及其应用[J]. 计算机工程与科学, 2020, 42(6):1076-1088.

[11]
陈学志, 李垣江, 张天亮, 等. 基于种群竞争的自适应差分进化算法[J]. 江苏科技大学学报(自然科学版), 2020, 34(6):80-85.

[12]
Zou D X, Li S, Kong X Y, et al. Solving the Dynamic Economic Dispatch by a Memory-based Global Differential Evolution and a Repair Technique of Constraint Handling[J]. Energy, 2018(147):59-80.

Options
Outlines

/

〈 〉