基于改进差分进化算法的作战目标分配

马 悦,吴 琳,郭圣明

(1. 国防大学,北京 100091;2. 中国人民解放军31002部队,北京 100091)

作战目标分配决定了兵力运用的科学性和合理性,是将作战意图落地为作战行动的关键步骤。当联合作战指挥机构将作战任务分配给作战单元后,各作战单元为完成作战任务,需明确打击/防护目标、分配兵力/火力、规划路径/航线,从而形成一系列作战行动。当多个作战单元/作战平台共同打击多个作战目标时,为解决资源冲突和达成最大作战效果,需实现在目标、火力、时间和空间等方面的协同分配。

作战目标分配是一种典型的非线性多项式完全问题,传统数学优化方法难以求解实践问题中不连续或不可微的优化目标函数。而差分进化(Differential Evolution,DE)算法无须考虑上述条件,是一种基于差分思想实现“优胜劣汰”的启发式全局寻优算法。众多学者致力于基于DE算法解决不同场景中的作战目标分配问题。例如：Li等针对多目标静态WTA问题重新定义了种群初始化、变异约束和变异选择等操作,提出一种新的离散型多目标进化算法框架;吴文海等为提高DE算法求解动态火力分配的效率,利用历史进化信息自适应调整参数;欧峤等构建了具有作战资源、弹目匹配和突防概率等约束条件的WTA模型,并利用改进的离散型DE算法进行求解。然而,标准DE算法采用固定的控制参数和变异策略,无法适应种群进化需求,也难以解决进化算法收敛精度低和易陷入局部最优的问题。为提高DE算法性能,诸多学者致力于改进控制参数、变异策略和种群结构的适应性,以降低算法停滞的风险。

上述研究能够不同程度地提高算法的全局寻优能力和收敛速度,但仍存在收敛精度不高、对不同复杂函数鲁棒性较差和无法跳出局部最优的现象。而作战目标分配问题的复杂度,随着作战单元和作战目标数目的增多，呈指数级增长,求解结果的实时性、准确性和有效性,将直接影响军事对抗中能否取得最佳作战效果。据此,本文通过分析DE算法的主要影响因素,提出一种多策略自适应协同差分进化算法(Multi-strategy Adaptive Cooperative Differential Evolution, MACDE),用于求解作战目标分配问题。以精英种群引导3个等规模种群的协同进化,各种群利用进化过程中成功变异的历史信息自适应选择变异策略和控制参数,从而满足不同进化时期对算法探索和利用的需求。通过测试和应用,证明了算法的收敛性、稳定性和可行性。

1 作战目标分配建模

假设在某次作战任务规划中,已确定了所需执行的作战任务及执行作战单元。针对打击目标清单,还需将作战目标合理分配给各作战单元。

在描述作战目标分配过程中,定义以下符号:

1)={,,…,}为作战目标清单列表,为作战目标的总数目;

2)={,,…,}为进攻方可用作战单元列表,为作战单元的总数目；

3)={,,…,}为进攻方可用弹药类型列表,为弹药类型的总数目；

4)={,,…,}为各作战目标被摧毁后的收益价值列表,为作战目标被摧毁后的收益价值,∈{1,2,…,}；

5)={,,…,}为各作战单元被摧毁后的损失价值列表,为作战单元被摧毁后的损失价值,∈{1,2,…,};

6)={,,…,}为各类型弹药消耗单位数量后的损失价值列表,为类型弹药消耗单位数量后的损失价值,∈{1,2,…,};

7)=(,,…,)为执行作战目标分配方案时被摧毁作战目标清单向量，=1表示作战目标被摧毁,否则=0;

8)=(,,…,)为执行作战目标分配方案时被摧毁作战单元清单向量，=1表示作战单元被摧毁,否则=0;

9)=(,,…,)为执行作战目标分配方案时进攻方的弹药消耗清单向量,表示类型弹药的单位消耗数量;

10)为执行作战目标分配方案时防守方的弹药消耗价值总量;

11),=(,,1,,,2,…,,,)为进攻方作战单元的挂载向量,,,为作战单元挂载的类型弹药的数目;

12)={,}×为进攻方各类型弹药对不同作战目标的命中毁伤概率，其中,,为类型弹药对作战目标的命中毁伤概率;

13)=(,,…,)为防守方一体化联合防空反导时对进攻方各作战单元的命中毁伤概率,为对作战单元的命中毁伤概率。

作战目标分配数学模型,如式(1)所示:

(1)

(2)

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

经典DE算法采用浮点矢量编码,随机初始化种群以覆盖整个解空间,种群规模、控制参数和相关策略一般固定不变,基本步骤为:

步骤1:种群初始化。根据优化问题确定种群规模、基因维度和基因取值的上下限。规模为的种群初始化方法,如式(3)所示:

(3)

步骤2:种群变异及检测。从父代种群中随机选择若干个体生成差分向量,对基向量进行扰动以生成变异体,常用的随机变异策略如式(4)所示。此外,变异会出现基因数值超出范围的情况,因此，需对变异体上基因进行边界检测,可采用“边界吸收”或“重新生成”策略进行处理。

(4)

步骤3:种群交叉。为增加变异体的多样性,将变异体与原种群个体进行基因混合,以生成新的子代个体,称为试验体。引入交叉概率,控制试验体由变异体上基因组成的概率。若采用“二项交叉”策略,试验体由式(5)计算得到:

(5)

步骤4:种群选择。采用“贪婪策略”,从父代种群和试验体集合中挑选优秀个体组成下一代种群。计算所有试验体适应值,并与父代目标体逐一对比,若试验体优于目标体,则取代目标个体,否则目标个体保留,如式(6)所示:

(6)

2.1 影响因素分析

算法的探索(Exploration)和利用(Exploitation)相互对立,不同进化阶段对全局寻优能力和收敛速度有不同的需求,如表1所示。而固定的控制参数和单一的变异策略难以保证种群在不同进化程度具备适应的进化性能。因此,常常通过适应性调整控制参数和变异策略,减缓种群多样性和收敛速度之间的矛盾。

变异缩放因子和交叉概率,对平衡算法全局和局部寻优能力至关重要,其数值大小及作用如表2所示。通常以算法进化代数、种群整体适应度和个体适应度等信息为依据进行自适应调整。在进化初期,需要较大的缩放因子以增大差分向量的扰动程度、扩大解的搜索范围和保证种群向全局最优解方向靠拢,同时需要较大的交叉概率以保证子代种群中的信息更多来自变异向量。而在进化后期,需要较小的交叉概率保证子代种群中的优质个体免于破坏,提高最终优化结果的精度,而较小的缩放因子保证了围绕优质个体周围生成变异体,使种群聚集于全局最优解附近。

表1 不同阶段需求

表2 控制参数的作用

表3 不同变异策略对比

2.2 算法改进

为避免随机搜索中种群进化被最优个体操控而陷入局部最优,多策略自适应协同进化算法(MACDE)采用分布式差分进化思想设立多个进化种群,通过定期更新精英种群和引导进化种群的交叉变异,实现种群之间的信息共享。进化种群根据自身进化程度和历史经验信息,自适应选择变异策略和控制参数。

1)协同进化机制

协同进化机制,是指多种群独立进行交叉变异并定期进行信息共享,从而实现共同进化以提高算法的寻优能力,其关键在于如何恰当地划分子种群、实现进化的互不干扰和信息共享。多种群协同进化具有很大优势:首先,不同种群的变异策略和控制参数可以多样化,能够分别实现探索未知解空间、维持精英个体进化等不同特殊任务;其次,不同种群之间存在的差异,在信息共享后能有效增加种群的多样性;第三,多种群分别进行变异交叉,有利于算法的并行化处理,有效减少求解时间。MACDE算法采用三个进化种群和一个精英种群,如图1所示。

图1 多种群协同进化

进化种群负责探索解空间和推动整个种群向全局最优解方向进化,精英种群负责保留各进化种群在历史进化中的精英个体,并适时引导进化种群搜索最优。在进化初期,进化种群保持活跃的变异活动,以尽可能探索未知解空间和保持种群内部差异性,而精英种群只更新其内部的精英个体,不对进化种群进行干扰,从而防止过早“干预”导致收敛到局部最优。经过多次迭代进化后,精英种群内个体逐步靠近全局最优,因此，可利用精英个体引导算法的进化方向。

种群内部个体间的变异交叉无法实现多种群协同进化,因此，在确保种群独立进化而不受其他种群干扰的同时,还需按照一定策略进行种群间信息的充分共享。MACDE算法中,精英种群规模为进化种群规模的30%,种群之间的信息交流与共享发生在每次迭代之后,其思路是:进化种群每次迭代进化后,取出适应度排名在前30%的个体,组成该次迭代产生的候选精英个体集合;而后分别与精英种群中的个体一一进行比较,并替换精英种群中表现较差的个体。算法迭代结束后,选择精英种群中最优个体作为最终解。

2)多变异策略选择

不同变异策略,或注重扩大随机搜索范围以增大种群多样性,或注重围绕优秀个体进行局部搜索以提高收敛速度,但难以同时兼顾探索与利用。单一变异策略,难以满足种群进化在不同时期对全局搜索能力和收敛速度的需求变化。因此,许多学者提出使用混合变异策略,但实质仍旧是不同变异策略根据执行条件的选择,刚性的组合反而难以灵活发挥各变异策略的优势。

MACDE算法采用4种变异策略,分别为DE/rand/1、DE/rand/2、DE/current-to-rand/2和DE/current-to-pbest/2。为增加种群多样性,在每次迭代时,种群个体根据以往能够产生优秀变异体的统计信息进行变异策略选择,从而充分利用前期搜索经验,选择适应于种群和个体进化程度的变异策略。变异策略选择及更新步骤为:首先,初始化各变异策略的选择概率1、2、和,并构建选择概率的斐波那契数列;然后,每个个体通过“轮盘赌”方式选择执行的变异策略;第三,分别记录每种变异策略选择的次数1、2、和以及能够产生优秀变异体的每种变异策略的次数_1、_2、_和_,变异策略的选择概率1、2、和更新方法如式(7)所示;第四,对变异策略的选择概率进行归一化处理,如式(8)所示,其中，∈{1,2,,};最后,返回第二步,继续进行种群的迭代进化和选择概率的应用与更新。

=_

(7)

(8)

算法前期以探索解空间为主,进化种群分别独立进行交叉变异以增大种群多样性;在进化后期,为引导种群加快向全局最优解处搜索,以精英种群中的优秀个体作为基变量进行种群变异。DE/rand/1、DE/current-to-rand/2和DE/rand/2计算方法不变,而DE/current-to-pbest/2的计算方法,如式(9)所示:

(9)

3)参数自适应选择

每个种群的进化程度不同,因此，难以共享控制参数和变异策略的选择经验,如种群中参数和策略的历史统计信息,无法反映种群的进化程度。因此,需要保证种群之间相对独立进化,而将精英个体的更新和交流作为种群协同进化信息共享的途径。种群内不同个体进化程度存在差异,为不同个体适应性选择不同控制参数,将更加有利于种群进化。

MACDE算法为种群每个个体都适应性地选择控制参数和。控制参数通过正态分布采样获得,而正态分布的均值根据历史进化中能够产生优秀变异体的统计信息进行调整更新,如式(10)和式(11)所示。其中,(·)为正态分布,(·)为计算数值集合算术平均值的函数;和分别为正态分布的均值;决定了历史经验对控制参数更新的影响大小;和分别为历史进化过程中能够获取优秀变异体的变异缩放因子和交叉概率的数值集合。

(10)

(11)

为保证进行充分搜索,种群前期进化具有很大随机性,此时的种群整体进化程度和个体适应度较差,短期内对控制参数选择经验的统计有较大偏差。因此，进化前期,控制参数需维持较高数值,避免受带有较大噪声的历史经验的干扰。在经过长时间进化后,可产生优秀变异体的控制参数有较大样本,此时，再引入统计信息更新修改正态分布均值,具有较大的可信度。MACDE算法中,控制参数根据种群进化进行非线性调整,参数在前期数值较低且变化缓慢,在后期数值趋于固定值。Sigmoid函数顶部和底部较为平滑,满足上述非线性变化要求,因此，采用该函数进行参数的动态计算,如式(12)所示:

(12)

2.3 算法实现

多策略自适应协同差分进化算法的基本实现流程,如图2所示。

步骤1:初始化进化种群和精英种群,确定可供选择的变异策略集合,并为变异策略的选择概率、变异参数和赋初始值。

步骤2:进化种群分别进行变异操作。首先,根据变异策略的选择概率,通过“轮盘赌”方式确定种群的变异方式;然后,根据变异缩放因子对应的采样均值进行正态分布采样,如式(10)所示;第三,进行种群变异操作,并记录每种变异策略的使用次数;最后,进行基因检测和处理。当迭代次数超过所需迭代总数一半时,开始利用精英种群中优秀个体参与各进化种群的变异,如式(9)所示。

步骤3:进化种群分别进行交叉与选择。首先,根据交叉概率对应的采样均值进行正态分布采样,如式(10)所示;然后,逐一判断变异体上的基因是否与原种群个体对应基因进行交叉,如式(5)所示;第三,计算新产生的各变异体的适应度值,如式(6)所示,采用贪婪策略选择优秀个体组成下一代种群,并记忆产生该变异体所使用的变异策略、变异缩放因子和交叉概率。

步骤4:更新变异策略的选择概率和控制参数的采样均值。根据存储的产生优秀变异体的信息,计算变异策略选择概率并归一化处理,如式(7)和式(8)所示;更新控制参数和的正态分布采样均值,如式(11)和式(12)所示。

步骤5:更新精英种群。当3个进化种群完成变异、交叉和选择操作后,选择种群中适应度排名前30%NP的优秀个体,而后逐一与精英种群中的个体进行比较,并替换表现较差的精英个体,以保持精英种群中个体的最优。

步骤6:判断迭代进化是否结束。迭代结束,则从精英种群中选择最优个体作为输出,否则继续进行迭代进化。

图2 MACDE算法流程

3 算法测试与应用

3.1 算法测试

为测试MACDE算法的可行性和有效性,选择8个测试函数,与标准DE算法、JADE算法和SaDE算法进行比较。测试函数()、()、()、()为单峰函数,测试函数()、()、()、()为多峰函数,其表达式、取值范围和理论最小值,如表4所示。

通过实验,分别从平均值、标准差、Wilcoxon rank-sum test和胜率4个方面比较各算法在测试函数上的表现。4种算法均在变量维数为=20、=30和=60的情况下独立运行40次,种群规模为变量维数的8倍,其参数设置如表5所示。

1)平均值与标准差分析

本文分别统计标准DE算法、SaDE算法、JADE算法和MACDE算法在8个函数及不同变量维数情况下求解得到的最优值(即最小值),如表6所示。在“优劣”一栏,“+”、“=”和“-”,分别表示MACDE算法优于、等于或劣于其他算法。平均值能够反映算法在求解函数最优值时收敛精度的高低,而标准差反映了算法在多次求解函数最优值时的稳定性。4种算法在变量维数为20和30时的进化代数为1 000。随着变量维数的增多,算法收敛速度将会降低,为得到理想的函数最优值,将变量维数为60时的进化代数设为1500。

表4 测试函数

表5 各算法参数

从表6中统计结果可见:

①从平均值和标准差角度,MACDE算法在8个函数上表现都不劣于其他三种算法,且只有在函数()上的表现等于SaDE算法。对于复杂单峰和多峰函数,MACDE算法虽然没有求解得到理论最优值,但寻优结果已十分接近于理论值,且明显优于其他算法。同时,MACDE算法在各函数上的标准差数值均小于其他算法,因此,具有较好的稳定性。

表6 最优解的平均值与标准差

②从不同变量维数求解结果角度。相同进化代数条件下,算法收敛精度随着变量维数的增大而降低,各算法在变量维数为30时的平均值和标准差均劣于变量维数为20时的统计结果。变量维数为60时,虽然增大了进化代数,但DE、SaDE和JADE算法在某些函数上的求解精度仍然很低,说明3种算法收敛速度很低，甚至陷入了局部最优的困境。然而,MACDE算法能够保持较高的求解精度,且在()、()、()、() 和()上的精度更高,可见该算法依然保持着较好的全局寻优能力和较快的收敛速度。

2)Wilcoxon秩和检验和胜率分析

为进一步对MACDE算法进行分析,利用威尔科克森秩和检验(Wilcoxon rank-sum test),确定MACDE算法与其他算法是否具有统计学意义上的差异,再使用胜率对算法性能进行分析。Wilcoxon rank-sum test可用于检测两组独立样本是否来自同一分布采样,当两组样本数据通过检测得到pvalue值且小于0.05时,说明样本分别来自于分布不同的总体。在判断MACDE算法与其他算法存在统计学意义上的差异后,再比较与其他算法在不同函数和维数情况下的获胜次数。如表7所示,“pvalue”一栏为MACDE分别与其他3种算法所求解函数最优值数据,在进行Wilcoxon rank-sum test所得的pvalue数值;在“差异性”一栏,“T”表示MACDE算法与其他算法存在差异,否则为“F”。“胜率”一栏为,在相同函数和变量维数情况下,各算法在40次同时独立运行过程中,能够寻得比其他算法更优结果的占比。如果存在几种算法寻优结果相同,则认为它们共同获胜,因此，4种算法的胜率相加可能大于100%。

从表6统计结果可见:

①从算法差异性来看。在相同情况下,MACDE算法所求最优解与其他算法所求解经过Wilcoxon rank-sum test后,所得pvalue数值均小于0.05。因此,MACDE算法与其他算法存在统计学意义上的差异,是一种新的差分进化算法。

②从胜率统计结果来看。SaDE算法在函数4上求解最优值的表现,能与MACDE算法媲美,但在函数5和6上却劣于JADE算法,两种算法不具有稳定性。而MACDE算法始终能够取得最接近理论最优值的解,其胜率保持在100%,对于不同函数及变量维数具有稳定的寻优表现。

3.2 算法应用

本文以联合火力打击为例进行仿真实验,对所提算法进行验证。案例中,弹药类型及数量、武器平台类型及数量、打击目标类型和弹目匹配关系等信息,如表8、表9和表10所示。

使用MACDE算法求解作战目标分配问题,在仿真环境中迭代运行1 000次,得到的适应值、敌我双方损失数(武器平台与弹药消耗)以及敌我武器平台剩余率(武器平台损失数目与初始数目之比),如图3所示。将最优解对应的染色体进行解码,得到的武器目标分配方案,如表11所示。统计数据表明:算法能够很快收敛到最优解,且结果满足作战目标分配需求,保证了较大的收益值和较小的损失值,能够在己方武器平台损失为0的情况下摧毁所有的敌方目标。

表7 Wilcoxon秩和检验及胜率统计

表8 弹药数据

表9 武器平台及目标数据

图3 仿真实验结果

表10 弹目匹配数据

表11 武器目标分配结果

4 结束语

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