一种基于混合组遗传算法的火力引导任务分配方法

王天喜，祁 涛，张 程，苏凝钢

（1.北方自动控制技术研究所，太原 030006；2.中国华阴兵器试验中心，陕西 华阴 714200）

0 引言

随着精确制导武器精度和威力的不断提升，现代战场上应用精确制导武器实施地面精确打击成为常见的作战形式。引导打击作为特种作战的一种作战样式，是实现特殊条件下精确打击的一种作战手段，其目的是为了在敌战区精确引导制导武器对发现的目标实施有效打击。

引导打击的典型作战流程为渗透占位→侦察→定位→上报情报→引导任务分配→引导打击→评估→校正→再打击→摧毁→撤退［1］。本文主要考虑引导任务分配部分，当前的火力引导任务分配主要依赖人工分配，当短时间内需要决策大量目标的引导任务时，指挥员往往需要耗费大量时间，而且分配结果也容易陷入局部最优，本文设计了一种快速、最优的火力引导任务分配算法，来辅助指挥员完成火力引导任务分配。

1 火力引导任务元素

1.1 基本假设

1）已部署的照射器与火力单元的通信质量良好，能够保证情报信息和任务口令的正常传输；

2）照射器能够与指定火力单元进行协同指挥，完成火力引导打击任务。

1.2 目照通视

1.3 目照距离

1.4 照炮夹角

2 火力引导分配模型

2.1 问题描述

已知有n个目标，m个照射器，k个火力单元，其中每个目标的打击次数为Si，打击时刻为ti（i=1，2，3，…，n）；每个照射器同一时刻只能照射一个目标，照射时间间隔为10 min，如何将这些目标合理地分配给照射器。其中，每个目标要尽量分配备用照射器，并考虑地图通视、目照距离、照炮夹角等限制条件［2-4］。

2.2 线性规划模型

线性规划方程为：

式（4）和式（5）中的5 和20，分别代表距离限制和角度限制。

3 FFD+GGA算法

采用FFD（降序首次适应）+GGA（组遗传）［2］算法来求解该问题［5-6］。

首先初始化照射器序列，排序为L1，L2，...，Lm，将目标根据打击时刻递增进行排序，排序后序列为a1，a2，...，an逐个对照射器与目标进行匹配，筛分出目标对应的照射器集合C1，C2，...，Cn。从对应的集合中选择两个照射器，作为该目标的照射引导单元。算法流程图如下页图1所示。

图1 FFD算法流程图Fig.1 FFD algorithm flow chart

图2 分组遗传算法流程图Fig.2 Flow chart of grouping genetic algorithm

3.1 编码

目标火力引导分配问题只和所用的照射器数有关，而与每个目标具体分给哪个照射器是没有关系的，在分组遗传算法采用以下的编码方式［7-8］：

假设编号为1 到6 的目标编码为：｛L1，L4｝，｛L3，L5｝，｛L1，L2｝，｛L2，L3｝，｛L6，L7｝，｛L4｝，它所代表的是目标1 分配给1、4 号照射器，目标2 分配给3、5 号照射器，目标3 分配给1、2 号照射器，目标4 分配给2、3号照射器，目标5 分配给6、7 号照射器，目标6 分配给4号照射器。

按照随机的顺序生成初始种群，L1，L2，...，Lm，然后按照FFD算法的步骤进行分配。

3.2 适应度函数设计

遗传算法是利用种群中每个个体的适应度值进行搜索，对于算法迭代过程中每代个体的优劣程度通过个体适应度的大小进行评价。所以，适应度函数的设计至关重要，它将直接影响遗传算法收敛速度的快慢以及是否能找到最优解，适应度值越大，遗传到下一代的概率就越大，质量就越好。

确定适应度函数的原则：最终解中使用的照射器个数尽量少，每个照射器与所照目标在要求范围内距离越大越好，每个照射器的任务尽量平均，每个目标尽量分配两个照射器，每个目标与所对应照射器的目照夹角在5°～15°之内越好。适应度函数为：

其中，N为分配结果中照射器使用的个数；Fi为第i个照射器所负责的目标个数；C为分配结果中照射器所负责目标的最大个数；K为大于1 的常数，这里取k=2；L为分配结果中负责两个目标的照射器个数；M为分配结果中所分配的目标的个数；Dj为第j个目标与所对应照射器的距离；j=1，2，3，...，m，第j个目标与所对应照射器的目照夹角。

3.3 遗传算子设计

3.3.1 选择算子

在生成初始种群后，用新设计的适应度函数计算每一个个体的适应度值。使用精英选择法去选择适应度较大的部分个体遗传到下一代种群中。

3.3.2 交叉算子

针对以上编码方式，采用以下交叉操作：

1）随机选择一个集合中2 个交叉点，并在父代中选出交叉片段。

2）将第2个父代的交叉片段插入到第1个父代的交叉点前面。这意味着第2个父代中的一些分组插入到第1个父代中。

3）删除第1个父代中出现两次的目标。第1个父代中的分组也会跟着改变。

4）重新插入被删除的目标，在本文采用FFD 方法进行插入。

5）改变2 个父代的角色并重新应用步骤2）～步骤4）操作来产生下一代。

交叉操作的具体步骤如下所示：

使用FFD算法随机产生两个父代染色体。

对照射器随机排列得到一个随机序列并按照FFD算法进行分配，得到一个分配方案为：

｛L1，L4｝，｛L3，L5｝，｛L1，L2｝，｛L2，L3｝，｛L6，L7｝，｛L4｝

它所代表的是目标1 分配给1、4 号照射器，目标2 分配给3、5 号照射器，目标3 分配给1、2 号照射器，目标4 分配给2、3 号照射器，目标5 分配给6、7号照射器，目标6分配给4号照射器。

再对一个随机序列进行分配，得到另一个分配方案为：

｛L4，L6｝，｛L5，L7｝，｛L1，L5｝，｛L2，L3｝，｛L6，L7｝，｛L1，L4｝

它所代表的是目标1 分配给4、6 号照射器，目标2 分配给5、7 号照射器，目标3 分配给1、5 号照射器，目标4 分配给2、3 号照射器，目标5 分配给6、7号照射器，目标6分配给1、4号照射器。

得到两个染色体及其交叉点如下所示：

在选定的染色体上选定如上交叉位置，把第1个染色体的交叉片段替换掉第2 个染色体交叉点处，得到如下所示的新的染色体：

就得到一条新的染色体来说，需注意的是，新插入的染色体片段，要进行合格性验证。

3.3.3 变异算子

交叉操作产生的后代不能进行迭代进化时，算法不一定已经收敛。进行变异操作可产生更广泛的个体，避免陷入局部最优。变异操作是先给定一个变异概率p，再从群体中任意选择一个个体，产生随机数rand，若rand＜p，那么就对这个个体实施变异。具体方法是随机选取个体染色体的两个位置，对这两个位置一定长度的染色体片段进行交换，完成变异操作。

例如得到一个染色体：

选取上图所指的染色体片段，把5 变成7（根据条件进行筛选）从而产生一条新的染色体，如下所示：

以上，应用混合分组遗传算法来求解火力引导

4 仿真实验

利用C++实现该算法，进行仿真实验，首先任意生成一些目标和与之匹配的照射器，取交叉概率为Pc=0.8，变异概率Pm=0.15，种群规模m=10，种群最大迭代次数为4 000，目标个数为20～40 个。本次实验了10个实例。表1分别列出了求解结果。

表1 仿真计算结果Table 1 Simulation calculation results

5 结论

当前火力引导任务分配还处于人工手动决策阶段，当短时间内有大量目标需要决策时，就需要一种快速、最优的火力引导任务分配算法，来实现火力引导任务自动分配，从而大大提高指挥员战场作战效率。本文基于火力引导任务分配问题的需求，建立了火力引导任务分配模型，提出采用FFD+GGA 算法来求解该问题，通过进行仿真实验，比对人工决策和BF+GGA 算法的求解结果，发现FFD+GGA算法能够取得很好的分配结果。