改进链式多种群遗传算法的防空火力任务分配

唐俊林，张 栋，王孟阳，刘亮亮

(1.西北工业大学 航天学院，西安 710072；2.空天飞行器设计陕西省重点实验室(西北工业大学)，西安 710072)

防空火力任务分配是防空指挥的重要环节，是决定作战效果的关键因素之一[1]。其目的是最大化武器装备作战效能，寻求敌方目标逃脱概率最小的方案[2]。

目前的研究中，防空火力任务分配模型考虑的重要因素包括目标的威胁程度和火力单元对目标的杀伤概率。文献[3]从分配控制条件、弹目相对距离和飞行时间3个方面，归纳了火力单元对目标的拦截可行性判断逻辑。文献[4]细化了防空火力任务分配通用模型，从多个方面评估目标威胁程度，构建杀伤区、发射区模型和单发导弹杀伤概率模型。因此，制定详细的威胁程度评估方法和可拦截性判断对防空火力任务分配的实际应用具有重要意义。

随着计算机技术的发展，智能优化算法已经成为解决防空火力任务分配等组合优化问题的重要方法。除了遗传算法、粒子群算法等经典算法之外，布谷鸟搜索算法[5]、合同网拍卖算法[6]和博弈论[7]等方法也可以用于求解任务分配问题。文献[8]通过控制初始种群中变量的取值范围和改进变异策略来提高搜索效率。文献[9]提出非支配排序算法(NSGA-Ⅲ)，引入具有良好收敛性和分布性的参考点来指导进化。面对极大的计算复杂性，文献[10]提出一种基于改进遗传算法的元启发式算法来改善随机任务分配问题的求解。文献[11]提出针对具体问题的种群初始化方法，重新定义了配对限制和选择操作。文献[12]提出一种基于遗传算法的anytime算法，引入元级控制，来确定算法的停机时刻。文献[13]提出多种群迁移遗传算法，利用种群间的迁移机制代替选择算子的筛选机制，并改进交叉和变异算子等操作。文献[14]提出一种基于ER网络的多种群遗传算法，研究子种群网络结构对优势基因在子种群间传播速度以及算法性能的影响。防空火力任务分配的实时性要求很高，响应过慢则可能贻误战机。传统智能优化算法及其改进算法，在种群规模和迭代次数受限时并不能稳定找到全局最优解。

针对目前防空火力任务分配模型以及智能优化算法所面临的问题，本文构建了一种改进的防空火力任务分配模型。模型细化目标威胁程度的评估方法，并将可拦截性约束条件简化。此外，进一步提出链式多种群遗传算法(Chainlike multi-population genetic algorithm, CMPGA)，运用链式多种群环、多样性保持、分层选择、去顶操作等策略，加快收敛速度并提高全局搜索能力。

1 防空火力任务分配模型

1.1 作战场景与决策变量

为保护防御要地，在其周围部署m个位置不同的火力单元。假定空情显示有n个目标从各个方向袭来，我方需快速作出响应，将来袭目标分配给各火力单元，以化解敌方空袭威胁。防空火力任务分配的方案用矩阵D={dij},i∈1,2,…,m,j∈1,2,…,n描述,矩阵D的各个元素为

(1)

1.2 目标函数

最大化作战效能的目标函数建立如下:

(2)

1.3 约束条件

防空火力任务分配考虑的约束条件如下：

1)每个火力单元最多分配μi个目标，μi为火力单元i的打击通道数，即

(3)

2)每个目标最少分配1个火力单元，最多分配λj个火力单元，即

(4)

1.4 目标威胁程度模型

威胁程度的评估如下：

1)目标飞行高度威胁因子。当敌方来袭目标在低空出现时，攻击意图明显，己方的防御时间短促，威胁程度显著增强。目标飞行高度威胁因子为[15]

(5)

式中高度的临界值hc=1 500 m，衰减参数k1=10-11。

2)目标飞行速度威胁因子。飞行速度越快的目标一定程度上拥有更强的机动能力和作战能力，己方拦截更加困难，威胁程度也更大。目标飞行速度威胁因子为[15]

μv=1-e-αv

(6)

式中α=0.001 5。

3)目标射程威胁因子。在区域防空作战中，来袭目标可能是飞机或者导弹。导弹的射程直接反映导弹的杀伤威力。短程、中程导弹射程短，杀伤力有限。远程、洲际导弹搭载核弹头，破环性极强。当目标类型为导弹时，目标射程威胁因子为[4]

(7)

式中L为导弹的射程，km。

4)目标距离威胁因子。目标距离己方防御要地中心的距离r也反映目标的威胁程度。目标距离己方防御要地中心的距离r越小，威胁程度越大。目标距离威胁因子为

(8)

式中rmax为己方相对于防御要地中心的最大可探测距离。

综上所述，目标威胁系数由各威胁因子及其权重加权求和得到：

Wj=whμh+wvμv+wLμL+wrμr

(9)

式中wh、wv、wL、wr分别为目标飞行高度威胁因子、目标飞行速度威胁因子、目标射程威胁因子和目标距离威胁因子的权重，均由专家经验给出。

1.5 可拦截性判断模型

具体判断过程如下：

1)若火力单元i不满足对目标j的可拦截性条件，则令Pij=0。如此处理可将一些约束条件融入杀伤概率的计算中，有利于约束条件的简化。目标可拦截性判断如下[3]：如图1所示，点A为目标的位置，点B为火力单元的位置，以点B为圆心的圆是火力单元的杀伤区。

图1 火力单元与目标的相对位置Fig.1 Relative position of fire unit and target

①航路捷径约束。航路捷径LBC为目标速度矢量与火力单元的最短距离，即

LBC=LABsin∠EAB

(10)

火力单元无法拦截航路捷径大于其杀伤半径Ri的目标，即

LBC>Ri→Pij=0

(11)

②最大拦截速度约束。火力单元无法拦截速度超过其最大可拦截速度vmax i的目标，即

vj>vmax i→Pij=0

(12)

③目标飞离时间约束。火力单元无法拦截即将飞离其杀伤区的目标。若目标j的预估飞离时间TAE小于火力单元i的准备时间Tri和其防空导弹的预估飞行时间Tfi之和，则目标j不满足火力单元i的拦截条件，即：

Tri+Tfi>TAE→Pij=0

(13)

(14)

(15)

式中：vj为目标j的飞行速度，vi为火力单元i拦截导弹的飞行速度。

④拦截高度约束。火力单元的可拦截高度应介于其杀伤区高低界之间，即:

hj

(16)

hj>himax→Pij=0

(17)

式中：hj为目标j的飞行高度，himin、himax分别为火力单元i的杀伤区低界与高界。

2)若火力单元i满足对目标j的可拦截性条件，即航路捷径约束、最大拦截速度约束、目标飞离时间约束、拦截高度约束、杀伤概率取经验值Pij。

2 基于链式多种群遗传算法的防空火力任务分配

针对上文所建防空火力任务分配模型，提出一种链式多种群遗传算法(CMPGA)。首先提出传统遗传算法的改进措施，包括多样性保持、分层选择、去顶操作。在此基础上提出链式多种群环结构，既让多种群共享当前最优解，又一定程度上保留单个种群进化的独立性。

2.1 改进型遗传算法

2.1.1 编码方式

采用二进制编码，即表示防空火力任务分配方案的矩阵D={dij},i∈1,2,…,m,j∈1,2,…,n。

2.1.2 适应度评价

适应度表征个体的优劣程度。适应度越大，个体越优秀。适应度函数取目标函数的倒数:

(18)

2.1.3 分层选择

按轮盘赌策略从父种群中选择与父种群规模相同的N个个体，等待完成交叉变异操作后生成子种群。轮盘赌策略根据个体的适应度确定被选择的概率，个体适应度越高，被选择的概率越大。种群中适应度为f(Dk)的第k个个体被选择的概率为

(19)

式中N为种群规模。

遗传算法中，适应度相近的个体经过交叉变异后更有可能产生比父代优秀的子代个体，所以采用分层选择策略能加快种群的进化速度。所分层数根据种群大小确定，以3层为例说明。除初代种群以外，父种群中的个体已按适应度从优到劣排列，可以直接采取如下操作：从父种群的0～N/2个体中选择N/3个个体进入子种群，从父种群的N/2+1～N个体中选择N/3个个体进入子种群，从整个父种群中选择N/3个个体进入子种群。对父种群的分层如图2所示。

图2 种群分层Fig.2 Population stratification

2.1.4 单点交叉操作

对父代两个任务分配矩阵的每一行执行单点交叉操作。对第i行，随机生成区间(0,1)的数r1，若r1

图3 交叉操作Fig.3 Cross operation

2.1.5 变异操作

对任务分配矩阵的每个基因位，以Pmu的变异概率将0置为1，或将1置为0。为了增强遗传算法的局部寻优能力，每个基因位变异后都对任务分配矩阵进行冲突消解，并计算个体的适应度，若适应度大于该基因位变异前的适应度，则不对该个体后续的基因位执行变异操作。

2.1.6 多样性保持策略

借鉴NSGA-Ⅱ的思想，将子种群与父种群合并，从中选择结构不同的个体组成新的父种群[16]。将经过交叉变异的子种群和父种群合并，对合并种群的2N个个体按适应度从优到劣进行排序，依次选择结构不同的N个个体组成新一代的父种群。

为避免迭代后期种群同质化严重，在合并种群中从优到劣依次选择个体进入新父种群时，同一结构的个体最多只能有Nsi个进入新父种群。这使得新父种群中同一适应度的个体不超过Nsi，从而能持续维持种群的多样性，降低算法陷入局部极值的概率。对合并种群的2N个个体进行排序后，结构相同的个体适应度也相同，往往集中在一起。每次从合并种群中将待选个体加入新父种群前，需计算新父种群中与当前个体适应度相同的个数，若小于Nsi时，将待选个体加入，若等于Nsi时，舍弃当前个体。当Nsi=2时，从合并种群中选择个体的过程如图4所示。

图4 多样性保持的选择过程Fig.4 Selection process of diversity maintenance

2.1.7 去顶操作

在合并种群中从优到劣依次选择个体进入新父种群前，需判断合并种群的最优个体相较于前代是否改变。若最优个体连续Ga代未发生改变，说明该种群可能陷入了局部最优。为跳出局部最优，采用后退的思维方式，将已经搜寻到的一部分最优秀的个体删除，即将局部最优解删除，剩余个体继续参与后续的遗传操作，重新搜寻最优解。若最优个体连续Ga代未改变，跳过前面的Nj个个体，从第Nj+1个个体开始依次选择个体加入新父种群；否则，从第1个个体开始选择。若去顶操作后种群多样性不足，生成随机个体补全新父种群。当Nj=10时，对合并种群的去顶操作如图5所示。

图5 去顶操作Fig.5 Topping operation

2.2 基于CMPGA的防空火力任务分配

基于上述改进型遗传算法，利用多种群并行搜索的思想提出CMPGA算法。一般多种群进化算法每次迭代完成后都会将当前最优解在所有种群范围内共享[17]。这样多种群间的信息共享过于频繁，并不能充分发挥多种群的优势。本文所提算法每隔数代才会出现当前最优解的传递，并且每次只有一个种群将移民算子传递给其后一个种群。当间隔代数达到Gr时，将种群Pf的当前最差解替换为种群Pl的当前最优解。

(20)

(21)

式中：G为当前迭代数,⎣·」为向下取整,Np为种群数；mod(·)为取余数。

以首尾相连的Np个种群为例，假设当前种群为Pi,i∈0,1,…,Np-1,间隔代数达到Gr时，将种群Pi+1的最差解替换为种群Pi的当前最优解；当间隔代数再次达到Gr时，将种群Pi+2的最差解替换为种群Pi+1的当前最优解，如此循环往复。当前种群为PNp-1时，其最优解传递给种群P0。当种群Pi将

最优解传递给种群Pi+1后，需要相隔Gr×(Np-1)代，才会接受到来自种群Pi-1的最优解。这样既保留各种群自身进化的独立性，也能适时共享其他种群的最优解。4个种群构成的链式环结构如图6所示。

图6 链式多种群环结构图Fig.6 Structure of chainlike multi-population ring

在CMPGA算法中，种群数量的增加对性能的提升十分显著。算法流程图如图7所示。

图7 链式多种群遗传算法流程图Fig.7 Flow chart of chainlike multi-population genetic algorithm

基于CMPGA算法的防空火力任务分配具体步骤如下。

算法CMPGA算法求解任务分配问题

Step1分别随机初始化各个种群P0,P1,…,PNp-1，并计算个体的适应度。

Step2若达到最大进化代数，输出所有种群的全局最优解。否则，跳转至step3。

Step3采用轮盘赌策略和分层选择策略分别对各个种群执行选择操作，生成待交叉变异、与父种群规模相同的子种群。

Step4分别对各个子种群执行交叉、变异操作。

Step5分别将各个子种群和对应的父种群合并，并对合并种群的个体按适应度从优到劣排序。

Step6分别从各个合并种群中选择结构不同的N个个体组成新父种群。当种群最优解连续Ga代未变时，从合并种群的第Nj+1个个体开始依次选择个体加入新父种群；否则，从合并种群的第1个个体开始依次选择。

Step7当间隔代数达到Gr时，将种群Pf的当前最差解替换为种群Pl的当前最优解。当间隔代数未达到Gr时，不进行任何操作。跳转至step2。

2.3 冲突消解策略

本文采用冲突消解策略以使算法获得满足约束条件的解，结构如图8所示。

图8 冲突消解Fig.8 Conflict resolution

为尽量不破坏个体的结构，冲突消解策略可分为：

3 仿真结果

为了验证CMPGA算法的性能，本文选取3个标准测试函数，寻找它们的全局极小值。其后，在火力资源通道数大于来袭目标数时，对中等规模算例进行仿真，以验证防空火力任务分配模型的有效性。

3.1 算法性能测试

采用3种标准单目标优化测试函数对CMPGA算法进行对比测试。

1)Schaffer函数。

(22)

-10≤x,y≤10

(23)

该函数有无数个极小值点，在(0,0)处取得最小值0，具有强烈振荡的形态。

2)Shubert函数。

(24)

-10≤x,y≤10

(25)

此函数存在760个局部极小值，极难找到全局最优解，在(-1.425 13,0.800 32)处取得最小值-186.730 9。

3)Eggholder函数。

(26)

-512≤x,y≤512

(27)

此函数多峰值,在(x,y)=(512,404.231 9)处取得全局最小值-959.640 7。

针对以上3个标准测试函数，分别利用链式多种群遗传算法(CMPGA)、多种群遗传算法(Multi-population genetic algorithm,MPGA)[17]、遗传算法(Genetic algorithm,GA)和二进制离散粒子群算法(Binary discrete particle swarm optimization,BDPSO)求解全局极小值，均采用二进制编码和单点交叉策略，每种算法各运行100次，进行对比分析见表1～3。

由表1可知，CMPGA、MPGA、GA算法均能较为稳定地求得Schaffer函数的全局极小值，BDPSO算法容易陷入局部极值。由表2可知，CMPGA算法能较为稳定地求得Shubert函数的全局极小值，MPGA、BDPSO与GA算法均容易陷入局部极值。由表3可知，CMPGA算法仍能较为稳定地求得Eggholder函数的全局极小值，MPGA和GA算法性能次之。BDPSO算法容易陷入局部极值。由以上3个测试函数的求解可知，从收敛的快速性和结果的稳定性来看，CMPGA算法均能以较小的种群规模和进化代数，较高的概率寻得全局最优解，其性能明显领先于MPGA、BDPSO和GA算法。

表1 4种算法求解Schaffer函数100次运行结果对比Tab.1 Comparison of results of 100 runs of four algorithms for solving Schaffer function

表2 4种算法求解Shubert函数100次运行结果对比Tab.2 Comparison of results of 100 runs of four algorithms for solving Shubert function

表3 4种算法求解Eggholder 函数100次运行结果对比Tab.3 Comparison of results of 100 runs of four algorithms for solving Eggholder function

3.2 仿真算例

假设某次防空作战中，己方部署8个位置不同的火力单元。火力单元对目标的经验杀伤概率由[0.5,1.0]的随机数生成，计算目标威胁程度时，wh，wv，wL，wr均为0.25，己方防御中心位置为(0,0),其最大可探测距离rmax=90 000 m。各个火力单元及目标的参数见表4、5。

表4 火力单元参数Tab.4 Fire unit parameters

表5 目标参数Tab.5 Target parameters

3.3 仿真结果

防空火力任务分配问题的搜索空间随目标和火力单元数量的增加而急剧增大。大多数文献的仿真算例规模较小，易于求解。本文通过与二进制离散粒子群算法(BDPSO)、遗传算法(GA)和多种群遗传算法(MPGA)的对比，来体现CMPGA算法能以更大的概率快速搜寻到最优解。

CMPGA算法各参数取值为：最大进化代数200，种群数Np=5，种群规模N=80，共分为3层，交叉概率Pcro=0.9，变异概率Pmu=0.01，最大重复次数Nsi=1，传递间隔代数Gr=30，去顶代数Ga=65，去顶个数Nj=10。

BDPSO算法各参数取值为：最大进化代数500，粒子群规模SN1=500，速度惯性因子w=1.0，学习因子c1=2，学习因子c2=2。

GA算法为：最大进化代数500，遗传种群规模SN2=500，交叉概率Pcro=0.6，变异概率Pmu=0.01。采用精英策略，将当代适应度排序前SN2/10个较优解直接复制到下一代，防止已搜寻到的最优解丢失。

MPGA算法为：最大进化代数500，种群数量3，各种群规模SN3=500，交叉概率Pcro=0.6，变异概率Pmu=0.01，采用上述精英策略。

4种算法各运行100次的结果见表6和如图9所示。

表6 4种算法100次运行结果对比Tab.6 Comparison of results of 100 runs of four algorithms

图9 4种算法100次仿真结果Fig.9 Simulation results of 100 runs of four algorithms

如表6和图9可知，火力单元数大于目标数时，局部最优解较多，3种对比算法获得最优解的概率均较低。本文所提CMPGA算法，以种群总规模400，200次的迭代仍有约97%的概率获得全局最优。4种算法均求得此算例的最优解见表7。

表7 最优分配方案Tab.7 Optimal allocation scheme

为具体说明CMPGA算法快速收敛的性能，分别选取4种算法某次运行中目标函数的变化如图10所示。

图10 单次运行结果对比Fig.10 Comparison of single run results

由图10可知，CMPGA的收敛速度与MPGA相当。BDPSO和GA的收敛速度较慢。4种算法的单次运行时长见表8。

表8 单次运行时长对比Tab.8 Comparison of single run duration

从单次运算时长来看，3种对比算法所需的种群规模和进化代数较大，运行时长较长。综合考虑运算时长和寻优性能，CMPGA算法为首选。

仿真表明，本文所提的CMPGA算法，通过多种策略的结合，同时具有收敛快速和全局寻优能力强的优点，能够以极高的概率搜寻到最优解。

4 结 论

1)本文提出改进的防空火力任务分配模型，详细介绍目标威胁程度的计算，并将可拦截性判断融入杀伤概率中，以简化模型的约束条件。本文使用有效的冲突消解策略，尽可能少地破环个体结构，以保证算法易于寻优。

2)综合运用链式多种群环、多样性保持、分层选择、去顶操作等策略，提出CMPGA算法，大幅提升遗传算法的寻优性能。为验证算法性能的优越性，仿真选取3个标准测试函数和中等规模的任务分配算例。仿真结果表明，算法快速收敛的同时能有效跳出局部极值。