基于遗传算法的虚兵火力协同任务规划

黄义松　赵德勇　李明雨

摘要：从虚拟兵力智能化角度出发，针对虚拟兵力火力协同任务规划问题，提出了一种对重要目标优先打击，同时弹药消耗最低的任务规划模型，并采用遗传算法对不同火力单元打击多个任务目标的规划问题进行求解优化。最后通过仿真试验对构建的算法进行验证，结果表明构建的模型算法能够很好地对火力协同任务规划问题进行求解，提高火力打击效益，实现虚拟兵力的智能决策。

关键词：虚拟兵力；遗传算法；任务规划；火力协同

一、前言

火力协同任务规划作为虚拟兵力智能行为的重要组成部分，是一种NP完全问题[1]，也是实现虚拟兵力智能决策行为的关键环节。在对多个目标进行火力协同任务规划的活动过程中，火力任务分配的结果直接影响着火力打击的效果，同时也是虚拟兵力智能决策的重难点。刘钰等[2]提出了融合禁忌搜索概念的遗传算法，对舰载机的保障调度优化展开了研究。王海峰等[3]将蛙跳算法和遗传算法相结合，对联合火力打击目标动态分配问题进行了研究。王书勤等[4]采用遗传算法对武警捕歼任务的兵力派遣问题进行了研究。李天龙等[5]在空地多目标火力分配优化问题上，引入遗传算法构建数学模型并进行了验证。对于任务规划这种NP完全问题的优化，遗传算法作为较早提出的智能化算法，其结果优化显著，并且具有较好的鲁棒性，能够较好地实现对任务规划问题进行求解和优化[6]。

二、问题描述

在指挥训练活动中，虚拟兵力按照指挥信息对多个目标实施火力打击的过程中，火力协同任务规划问题是虚拟兵力智能决策需要重点考虑的问题。不同虚拟兵力对多个目标进行火力打击所涉及的兵力选择、火力运用、目标选定等问题以及动态调整分配是一种NP完全问题。火力协同必须在完成火力打击任务的情况下，考虑打击目标的重要程度、威胁程度、毁伤程度、目标类型和选定兵力位置、射程、命中概率、毁伤能力、弹药消耗等因素，对火力运用、弹药损耗等问题进行优化。

三、算法构建

遗传算法在本质上是对NP完全问题进行智能优化的一种算法。在组织火力协同任务规划采用遗传算法进行智能决策时，其算法步骤可大致划分为数据录入阶段、数据向量转换阶段、评估阶段以及优化处理阶段。其中，数据录入阶段主要是将火力协同任务中的参与协同的单位、打击目标等具体战场态势信息数据输入计算系统中；数据转换阶段主要是将输入的战场态势信息数据转化为多维度的数据向量，实质上是将火力协同任务规划问题转变为在多维度几何空间中求得整体性最优解的问题；评估阶段主要通过火力协同任务规划的评估模型，对转化后的数据进行计算，评估当前的火力规划下所得的评分；优化处理阶段以评估阶段所得的评分为依据，在多维空间中随机选取个体，利用智能优化算法对选取的个体进行交叉变异得到新的个体，并对其进行评估，同时对评分最优的个体进行标记。在经过多次迭代循环后输出最优个体。

传统的遗传算法能够以灵活的方式对大部分优化问题求解，能够有效地避免局部极小值的发生。但其在个体选择方面上的随机性，有时会导致需要进行较长次数的迭代，无法快速地对问题求解。同时对于较为复杂的问题，往往还需要占用极大地内存用来计算。为解决上述问题，可以这里引入蚂蚁算法中的信息素的概念，利用信息素浓度来影响个体的交叉变异，提高进化效率，减少迭代的次数。具体的算法如图1所示。

1.种族初始化。针对火力协同任务分配问题，可以这里采用二进制的方法进行编码，用基因位来表示打击目标所对应的火力单位，既每个基因组表示目标由第几个火力单位负责打击，基因组可视为种族中的一个个体。例如基因组100010中的基因位数表示有6个火力单元，1表示相应基因位的火力单元对该目标进行打击，0表示不打击，则该基因组代表的打击方案为该目标由第1和第5火力单元负责打击。若有n个目标，基因长度就为6n，代表每个目标的基因之间用“：”进行分隔，“：”不参与实际运算。种族初始化就是尽可能多的随机生成个体，构成第一代种族群体，既表示着不同火力分配方案的集合。同时生成个体的信息素初始浓度以及火力单元禁忌表。

2.适应度函数。经过对火力协同任务规划进行问题描述，根据梳理出的约束条件，我们主要将打击目标的威胁程度、目标类型和火力单元的位置、射程、命中概率、弹药留存比作为评估的影响因素来构建适应度函数（见表1）。

3.种族灭绝。“种族灭绝”并不是将所有的个体信息进行删除，而是按照一定的比例减少个体的数量，并令存活下的个体寿命加1。“种族灭绝”是为了能够更快的从种群中选择优秀的个体，作为父体以产生后代，选择的方法对生成的后代个体具有较大的影响。这里采用轮盘法的方式来确定要保留的个体，使得评分高的个体能有较大的概率得以保留，同时也确保评分低的个体有概率得以生存，其选择公式如下所示：

4.交叉变异（更新信息素浓度）。交叉变异是对生物染色体交换基因和基因突变的仿真。其中交叉是从种族灭绝后留存的个体中选择两个作为双亲，并在它们的基因组中选择截断点，将被截断的基因相互交换，产生新的个体，根据截断点的不同，交叉类型可划分有：一点交叉、二点交叉以及均匀交叉，其基因交换过程如图2所示。变异环节根据火力单元禁忌表选择基因变异的方向，并且更新个体的信息素浓度，提高发生变异个体的信息素浓度，相应地降低未发生变异个体的信息素浓度。设μij为火力单元i对目标j进行火力打击的信息素浓度，α为μij的重要度参数；fij为火力单元i对目标j进行火力打击的适应度，β为个体适应度的影响系数；H表示火力单元禁忌表，既不可选择的火力单元的集合。发生变异概率δij的公式如下：

5.判断退出。判断遗传算法是否达到设置的退出条件，若未达到则重复上述环节，若已经达到退出条件，则输出最优的个体并退出。

四、案例分析

五、结语

本文针对虚拟兵力火力协同任务规划的智能决策问题，提出了一种信息素遗传算法对NP完全问题进行智能优化的方法。通过对决策问题进行梳理分析，得到软硬2类约束条件，建立了基本问题模型，并采用遗传算法对问题求解，并通过仿真实例对算法进行验证。结果表明该算法能够在综合考虑打击目标的重要程度、威胁程度、毁伤程度、目标类型和选定兵力的位置、射程、命中概率、毁伤能力、弹药消耗等因素的情况下，对火力协同任务规划进行求解和优化，有效地提高了火力打击效益。

参考文献

[1]邢岩，刘昊，吴世杰.基于信息素遗传算法的联合火力打击任务规划[J].兵器装备工程学报，2020，41（8）：169-175，192.

[2]刘钰，王能建，罗旭，等.采用改进遗传算法的舰载机保障调度方法[J].国防科技大学学报，2020，42（2）：194-205.

[3]王海峰，高小军，刘昊.基于竞争蛙跳算法的联合火力打击任务规划方法[J].指挥控制与仿真，2019，41（4）：65-71.

[4]王书勤，黄茜.基于遗传算法的武警捕歼战斗兵力优化指派建模与仿真[J].数学的实践与认识，2020，50（15）：164-169.

[5]李天龙，张军超.基于融合算法的空—地多目标攻击火力分配[J].电光与控制，2019，26（11）：56-59.

[6]李敏强，寇纪淞，林丹，等.遗传算法的基本理论与应用[M].北京：科学出版社，2002.

作者单位：黄义松、赵德勇，陆军工程大学石家庄校区；李明雨，陆军步兵学院石家庄校区