一种新的精英遗传算法及在多弹拦截分配策略的应用*

王 储 南 英 许 航

南京航空航天大学航天学院，南京 211100

0 引言

武器-目标分配问题(WTA)是多对多飞行器智能协同作战中指挥决策的重要问题，其求解方法主要有枚举法、分支界定法等精确算法[1]和遗传算法，模拟退火算法，蚁群算法，粒子群算法等启发式算法[2-6]。其中，遗传算法(Genetic algorithm，GA)是一种有导向的随机搜索算法，适合解决群体搜索最优化问题[7]，但其求解效率会随着问题复杂程度逐渐降低，且容易陷入局部最优。一些学者为抑制其盲目寻优和过早收敛的局限性[8]，进行了很多研究。比如，Zhou等[9]将遗传算法的均匀变异和交叉概念引入粒子群算法中，生成算法的更新方程。Wang等[10]将自适应遗传算法与自适应变量邻域搜索算法相结合，以平衡搜索和开发能力。Zhao等[11]引入自适应交叉与变异算子和模拟退火操作，抑制了算法早熟现象。王少蕾等[12]通过进化过程中变异、交叉因子的动态自适应策略，避免算法陷入局部最优。李瑞康等[13]将遗传算法的交叉思想引入到粒子群更新的策略中，有效提升了算法的性能，拥有更好的综合搜索能力。王光源等[14]根据种群多样性测度动态调整粒子群算法的惯性权重，来抑制算法陷入局部最优。参考上述方法可知，引入自适应策略，一定程度上可以抑制算法陷入局部最优，但算法的收敛速度仍需改善，且合理地将遗传算法与其他算法或策略融合可以改善算法的性能，但单一种群进化的多样性远不如多个种群协同进化好。因此，为了进一步提升算法的性能，快速收敛得到更好的最优解，还需扩大种群的多样性，增强算法的搜索能力。

针对空战战场中多导弹对多目标的拦截-突防目标分配问题，本文采用一种基于自适应策略的改进多种群精英遗传算法，即多种群自适应遗传算法(MAGA)，来抑制算法过早收敛的情况，加快收敛速度寻找最优解。该算法在遗传算法的基础上，增加种群群落数量，引入自适应策略和迁移算子，采用精英选择与备份策略，迭代计算得出最优解。选用3种算法与本算法进行对比，并通过数值仿真算例，验证本文算法的有效性。

1 多弹拦截目标分配问题的数学描述

1.1 问题的数学描述

本文的研究背景为空中敌方多无人机来袭，我方发射多枚空空导弹进行拦截，导弹发射前将进行快速目标分配。本文导弹与目标均设为质点，且不考虑他们的空气动力、环境影响等。

假定拦截导弹表示为Mi(i=1,2,…,m)，目标无人机表示为Nj(j=1,2,…,n)。每枚导弹对目标的击毁概率已知，设导弹Mi对目标无人机Nj的击毁概率矩阵为(pij)m×n。目标第j个无人机的威胁系数为wj，目标的威胁系数越大，则被分配的导弹数量越多。导弹攻击目标的武器-目标分配决策矩阵为：

(1)

式中：vij∈Z(i=1,2,…,m;j=1,2,…,n)为第i个导弹分配给第j个目标无人机的火力单元数[12]。若vij=1，则表示导弹Mi攻击目标Nj；若vij=0，则表示导弹Mi不攻击目标Nj。

1.2 综合优势函数的构造

综合优势函数是一项用来评估目标分配结果好坏的重要指标。本文主要考虑2部分因素：1)考虑导弹攻击目标的击毁概率最大，即所有导弹毁伤目标的期望最大，可建立优势函数f1，见式(2)。2)考虑导弹与目标在作战中弹目的相对角度、相对速度与相对距离的限制与影响，参考文献[15]，本文建立优势函数f2，见式(3)。建立总的综合优势函数F=max(f1+f2)，见式(4)：

(2)

f2=c1sγsR+c2sγsv

(3)

(4)

1.3 约束条件

在多导弹拦截作战的目标分配问题中，为尽可能还原真实作战场景，增加了一些约束条件：

1) 进行目标分配时，每个目标都必须在其对应的拦截导弹的可拦截范围内。

2) 当弹目距离小于或等于50m时，就认为目标无人机将被导弹击毁。

Rm={R≤50}

(5)

3) 为尽最大能力拦截目标，每个目标必须被分配导弹。

(6)

式中：s表示某目标无人机最多允许分配的火力单元数。本文根据目标的威胁系数wj分配对应的导弹数量。

4) 模拟真实作战中的资源分配不平等，导弹的数量一般应多于或等于目标数量。

(7)

根据以上建立的多导弹对多目标拦截的目标分配数学模型及约束条件，将其运用至下一节设计的算法中。

2 多种群自适应遗传算法设计

MAGA曾被用于解决电网配电系统重构、TSP问题等。本文将其应用于空战战场中多导弹对多目标拦截对抗的目标分配问题。图1为MAGA的框架图。

图1 多种群自适应遗传算法框架图

本算法建立多个群落种群协同进化，扩大种群多样性。每个种群均采用自适应策略动态改变交叉、变异概率，保留优秀个体，抑制算法早收敛。引入迁移算子，增加多种群间的联系，设定精英选择算子进行选择与备份。该算法能有效抑制局部最优，加快收敛速度，获得更优的分配结果。下面将在2.1～2.6节中详细介绍本算法各环节算子的设计，并在2.7节中给出算法的详细步骤。

2.1 基因编码设计

初始种群PoPi(i=1,2,…,n)内的每条染色体个体编码均代表目标分配的一个可行解。本文选用十进制整数编码形式，根据目标的威胁度值，随机生成初始种群，并保证个体编码序列内无遗漏。导弹编号M从左到右依次递增，染色体内编码信息为目标无人机编号N，导弹与目标一一对应。以我方发射10枚导弹拦截敌方10架无人机为例，染色体编码形式如图2所示。

图2 十进制整数编码形式

2.2 适应度函数

适应度函数是用来评估个体是否达到最优的重要指标。本文的适应度函数主要考虑目标损毁率、角度、速度和距离等因素，选用1.2节中提出的综合优势函数F定义，见式(4)。根据式(4)计算每条染色体个体的适应度函数值，适应度值越大的个体，分配效果整体越优。

2.3 遗传算子

遗传算子主要包括选择算子、交叉算子与变异算子。选择算子能有效提升算法的收敛速度，交叉、变异算子能扩大种群多样性，防止算法过早收敛。

1)选择算子。采用轮盘赌法选择优良个体，根据式(8)计算每个个体在子代中被选中的概率，并按照此概率选择个体，构成子代种群进行下一步迭代。适应度值越大的个体被选中的概率越大。

(8)

2)交叉算子。核心思想是：在一个父代染色体P1中随机选择几个位置，并在另一个父代染色体个体P2上找到相同信息的位置。分别将两个父代染色体被选中的基因按照顺序，互相填入对方的基因序列中，一次生成两个子代染色体个体C1和C2。算法示意图如图3。

图3 交叉算子示意图

3)变异算子。采用交换变异的方式，每条染色体随机选择2个位置，互相交换编码信息。在父代染色体P1内随机选择2个位置进行交换，产生子代染色体C1。算法示意图如图4。

图4 变异算子示意图

2.4 自适应策略

交叉变异概率固定不变，存在优秀个体流失的风险。本文根据适应度函数的值自适应地改变交叉概率与变异概率，可以有效增加收敛速度，加速保留优良个体，淘汰低劣个体。本文设计的自适应交叉变异概率函数，见式(9)。

(9)

计算当前种群内个体的适应度函数值F，如果当前适应度值大于或等于平均适应度值，则通过式(9)计算交叉、变异概率；如果当前适应度值小于平均适应度值，则仍保持原来的交叉、变异概率进行遗传操作。

2.5 迁移算子

迁移算子的主要作用是增加多群落之间的联系，促进种群协同进化。本文将第1个种群PoP1适应度值排名前10的个体赋值给初始迁移种群MPoP。根据图1的流程顺序，每次迭代都将迁移种群MPoP与n个种群PoPi(i=2,3,…,n)依次互相更新进化，用适应度函数值靠前的前10个个体更新迁移种群MPoP′，同时按照种群容量择优更新当前种群PoP′。

2.6 精英选择算子

精英选择策略是选择种群中一部分优秀个体，组成一个精英种群保存备份，以防止精英个体在自适应交叉变异操作中流失。精英种群中的全部个体不参与交叉变异等遗传操作。

分别将种群PoPi(i=1,2,…,n)的前k个优秀个体保存于各自的精英种群GPoPi(i=1,2,…,n)中，并随着每次循环迭代，保证每个精英种群中始终保存各自种群发展过程中的前k个优秀个体。

2.7 MAGA算法描述

采用MAGA解决多导弹对多目标拦截对抗的目标分配问题，具体算法流程框图见图5，算法步骤如下：

图5 多种群自适应遗传算法流程框图

1)种群初始化。设定种群数目x，每个种群内含有个体数目y，随机产生共x×y条染色体。导弹数目M，目标无人机数目N。设定循环迭代次数t，最大交叉概率Pc1，最小交叉概率Pc2，最大变异概率Pm1，最小变异概率Pm2。

2)计算适应度值。解码种群内每条染色体个体，得到武器-目标分配决策矩阵V，根据式(4)计算每条染色体个体的种群适应度值。

3)遗传操作。根据式(8)进行轮盘赌选择操作。根据式(9)计算每条染色体个体的自适应交叉与变异概率，进行交叉、变异操作，得到每个种群内的新子代种群。

4)迁移操作。对每个种群内的个体按照适应度值大小进行排序，选择更新每个种群的迁移种群MPoP与当前子种群。

5)精英选择与备份。按照精英选择策略，对每个种群进行精英选择与备份操作，每次迭代都将更新精英种群。

6)判断。判断是否达到最大迭代次数t，若是，则进行7)；若否，则转2)循环迭代。

7)最优选择。将n个种群中的精英种群，根据适应度值进行逐一比较，得出最优染色体个体，即多对多拦截对抗的目标分配问题的最优解。算法结束运行。

3 数值仿真与分析

以多导弹对多目标的拦截对抗目标分配问题为背景，通过数值仿真分析，验证算法性能。假定我方共有5个火力平台，每个火力平台可发射3枚导弹，导弹总数目M=15，导弹均采用三维比例导引法来拦截目标。敌方目标无人机分3组进攻，目标总数目N=10，目标分别做不同类型的sin型机动。假设导弹的类型各不相同，每枚导弹都对特定目标有高毁伤概率，如0.7～0.9，对其他目标的毁伤概率为0.5，毁伤概率值设定见表1。本文根据目标的威胁值分配相应数量的导弹拦截，假定目标的威胁值为wj=[1,2,1,3,1,2,1,1,2,1]。

表1 导弹对目标的攻击毁伤概率表

其他参数设定为：种群数目x=3，每个种群内含有个体数目y=30，循环迭代次数t=500，随机产生最大交叉概率Pc1=0.8+rand(0,0.1)，最小交叉概率Pc2=0.7，随机产生最大变异概率Pm1=0.1+rand(0,0.1)，最小变异概率Pm2=0.05，适应度函数常数c1=0.5,c2=0.5。rand(0,0.1)表示在(0,0.1)区间均匀分布的随机数。

应用MAGA进行武器-目标分配，为验证本文设计算法的有效性，选用遗传算法(GA)，自适应遗传算法(AGA)，多种群遗传算法(MGA)进行对比分析。通过20组数值仿真验证，可得到MAGA算法的最优目标分配方案为：[1,6,5,9,4,7,2,10,3,4,6,2,9,4,8]，最优适应度为15.713。四种算法的最优适应度平均值与最大值，见表2。

表2 四种算法的最优适应度值

基于MAGA算法导弹拦截目标的轨迹，见图6～7。可见本算法可以对机动目标很好地进行分配，且当目标威胁度大于1时，可分配多个导弹进行拦截。四种算法的最佳适应度变化曲线和最优适应度函数箱型图，见图8～9。

图6 基于MAGA算法的多对多拦截轨迹俯视图

图7 基于MAGA算法的多对多拦截三维轨迹图

图8 四种算法的适应度对比

分析图8的仿真结果，对比曲线GA与MGA可知，MGA寻找的最优解远优于GA寻找的最优解，单种群遗传算法容易陷入局部最优，多种群遗传算法能有效地扩大种群多样性，抑制算法早熟；对比曲线MGA与MAGA可知，MAGA的收敛速度优于MGA，MAGA约在迭代20步左右收敛到较优解，MGA则约在80步左右收敛到较优解。可见引入自适应策略，可以有效增加算法的收敛速度，还可以抑制算法局部最优。

由图9的箱形图和表2可知，MGA与MAGA的平均适应度值很高且变化幅度很小，但MGA存在一些离散点，稳定性略差于MAGA；GA与AGA相比可知，AGA整体优于GA，可见加入自适应策略还可以获得更好的最优解。

图9 四种算法的最优适应度箱形图

4 结束语

本文在多导弹对多目标的拦截对抗目标分配问题的实战背景下，提出将多种群自适应遗传算法(MAGA)应用于武器-目标分配问题中，总结如下：

1)适应度函数与约束条件。本文选用武器击毁目标概率最大为评估标准，增加导弹与目标的相对距离、速度和角度等变量，使得问题描述地更精确真实，求解精度得到提高。

2)多个种群与迁移算子。本文采用多个种群做并行迭代计算，通过迁移算子加强种群间的联系，有效扩大种群多样性，抑制算法过早收敛。

3)自适应策略与精英选择策略。本文引入自适应策略动态改变交叉、变异概率，有效保留优秀个体，加速淘汰低劣个体。引入精英选择策略来选择备份优秀个体。

通过与GA、MGA、AGA算法进行对比分析，验证了本文设计的MAGA算法能有效提高求解精度与收敛速度，抑制局部最优。在多导弹拦截多机动目标的算例中，证明了该算法可用于解决一定规模空战中的武器-分配问题，对多导弹拦截多目标作战的智能决策有一定的参考价值。