基于进化粒子群算法的联合火力打击任务规划方法∗

刘 昊 宋敬峰 陈 超

（1.国防大学联合作战学院 石家庄 050000）（2.31696部队参谋部 锦州 121000）（3.93123部队参谋部 辽阳 111000）

1 引言

联合火力打击任务规划是联合作战火力打击过程中对诸军兵种火力打击部队执行火力打击任务的动态规划任务集合，是确定火力打击中目标、部队、弹种、用量的格式化命令表述形式，是指挥员用以指挥联合火力打击的最终输出指令样式[1]。在军事运筹领域，联合火力打击任务规划属于动态火力分配问题，是典型的NP完全问题，在诸军兵种联合作战的背景下，火力分配又融入多兵种、多弹种的多维变量，使优化计算复杂度和算法工作量进一步提升，传统机械化战争中依靠人工分配火力打击任务的规划方式难以应对，必须考虑采用计算机辅助规划的手段予以解决[2]。随着计算机性能的提升和人工智能技术的发展成熟，智能优化算法逐步替代原有以线性规划为代表的数学规划方法，成为任务规划领域的主流算法。相较于数学规划方法，智能优化算法具备指标离散性、约束条件可调、输出结果可控等优点，广泛应用于工程实践领域。

智能优化算法按照优化原理可分为模拟生物种群特征的遗传算法[3]、量子进化算法[4]；模拟自然界物理规律的细胞膜渗透算法[5]、模拟退火算法[6]；以及模拟生物群体行为特征的蜂群算法[7]、蚁群算法[8]、粒子群算法[9]、蛙跳算法[10]等。上述智能优化算法中，遗传算法提出相对较早，算法设计较为简单，对后代各类智能优化算法影响较大；粒子群算法是1995年由Kennedy和Eberhart提出，其模拟自然界中鸟群觅食的行为特征，通过设计智能体向空间中的“食物丰沛区”移动寻找最优解，具备较高的迭代效率。然而粒子群算法也存在易陷入局部最优和迭代次数不可控的问题，无法保证在有限时间内找到符合要求的全局最优解。本文通过借鉴遗传算法和粒子群算法的内在原理，在粒子群算法中引入遗传算法中遗传变异和优胜劣汰的生物竞争机制，构造进化粒子群算法，以此提升迭代效率和全局寻优能力，并将算法引入联合火力打击任务规划中，解决任务规划的优化问题。

2 问题描述

联合火力打击任务规划问题的核心是在有效时限内对我方兵器、弹种和敌方目标之间的最优化匹配，以实现体系破击毁伤效果，并以完成上级赋予的目标火力毁伤任务份额为前提，减少我方兵力和弹药损耗。根据问题需求，可对联合火力打击任务规划设定硬约束条件如下。

一是必须保证完成上级赋予的火力毁伤任务份额；二是必须保证我方火力打击部队能够随时执行临机火力打击任务；三是必须保证所有火力打击任务在规定时限内完成。设联合火力打击的部队模型用B=｛b1，b2，……，bn｝表示，其中 bk代表火力打击部队的属性集合；联合火力打击目标模型用D=｛d1，d2，……，dm｝表示，其中dl代表火力打击目标的属性集合；H（dl，bk）表示第k支部队对第l个目标实施火力打击产生的毁伤程度；G（dl，bk）表示第 k支部队担负对第l个目标的火力打击任务份额；p表示任务规划的子任务数量，l表示弹药消耗量，Lk表示第k支部队的弹药总量，Ts表示火力打击起始时刻，Tz表示火力打击结束时刻，Tk表示第k支部队的火力打击总时长。则根据联合火力打击任务规划的硬约束条件，建立数学模型如下：

此外，为了使联合火力打击任务规划可量化比较优劣，在满足硬约束条件的前提下，设置软约束条件如下。

一是我方参加火力打击的部队兵力损耗越小越好；二是我方执行火力打击的弹药消耗越少越好；三是各军兵种部队的执行任务压力尽量平均；四是完成联合火力打击的总体时长越少越好；五是保持随时有空余部队执行临机火力打击任务；六是对同一目标同一时刻的复合打击次数越多越好。

通过对联合火力打击任务规划的软硬约束条件分析和建模可知，问题的难点在于各约束条件纵横交叉、相互制约，难以在评分算法中取得统一的综合评估结果；此外，参与联合火力打击的诸军兵种部队的兵器、弹种、作战使用条件各不相同，使联合火力打击任务规划的可行性评估难度大幅提升，手工规划难以解决，必须依靠智能算法通过多代迭代求解。

3 算法构建

智能优化算法应用于联合火力打击任务规划，可采取问题视角切换、随机变量迭代、批量评估选优的方法设计算法构架，选择合适的智能优化算法种类，完成任务规划的优选和输出。基于此，智能优化算法由数据录入、向量空间建立、综合评估、粒子群优化四个部分构成。数据录入模块采集联合火力打击任务规划所需的基础数据，以格式化形式存储分发；向量空间建立模块将联合火力打击任务规划的兵力、火力、目标转换为多维空间中的维度，从而将优化问题视角切换为多维向量空间寻优问题；综合评估模块按照粒子群个体的空间位置向量结构计算综合评分并输出，作为评估个体优劣的依据；粒子群优化模块构造能够随机觅食的种群个体，通过多代迭代寻优并输出最优解向量。智能优化算法的流程如图1所示。

图1 智能优化算法流程图

3.1 进化粒子群算法

粒子群算法是借鉴鸟群觅食行为设计的智能优化算法，算法在多维向量空间中随机产生众多个体，将空间位置的综合评分看做食物，则个体可根据所在位置周边的食物丰沛情况自主游走，经过多代迭代使最优个体综合评分收敛于全局最优解。粒子群算法流程如图2所示。

图2 粒子群化算法流程图

进化粒子群算法在标准粒子群算法基础上，借鉴遗传算法中的优胜劣汰进化机制，在个体结构中引入寿命和淘汰系数，当个体处于食物贫瘠区，随着多次游走导致淘汰系数上升，当超过淘汰阈值即判断当前空间位置附近没有最优解，删除该个体；由高分个体繁殖后代个体代替删除个体，繁殖个体寿命+1；当有个体寿命达到上限，判定个体死亡，删除超龄个体以防算法陷入局部最优。进化粒子群算法的流程如图3所示。

图3 进化粒子群化算法流程图

具体算法如下：

Step1：建立向量空间。

Step2：设置初始种群。个体结构如表1所示。

表1 进化粒子群算法个体结构

Step3：计算个体下一游走位置。设个体当前的位置为Xi，Pi为个体当前为止游走到的最优位置，Qi为种群当前游走到的最优位置，Vi为个体当前游走步长；r1和r2为随机实数。则个体下一游走步长Vi+1计算公式为

设种群个数为n，Pij为第j个个体当前为止游走到的最优位置，迁移系数Mi计算公式为

设u为0～1之间的随机实数，个体下一游走位置Xi+1计算公式为

Step4：计算所有个体综合评分。

Step5：种群淘汰。删除淘汰系数超过阈值的个体，删除超过寿命上限的个体，而后对所有个体比较历史最优评分，删除低评分个体。

Step6：种群繁殖。使用轮盘法选中父代个体，按照变异概率对个体中的火力分配任务进行调整，产生新个体，使种群规模达到上限。

Step7：重复Step3～6，直至算法满足退出条件：在达到收敛代数阈值时，最优个体综合评分未更新。算法退出并输出全局最优个体历史综合评分。

3.2 评估指标模型

对于联合火力打击任务规划的软硬约束条件，本文采取层次分析法，对任务规划的评估指标进行量化分析，将其分为单目标指标类、单部队指标类、体系指标类，并将其细化为11项具体评估指标。评估指标明细如图4所示。

图4 评估指标明细

设参加联合火力打击的部队数为m，其中第i支部队打击半径为oi，火力打击次数上限为ci，执行任务耗时为di，火力打击任务间隔转换耗时为ei，部队坐标位置为xmi和ymi；火力打击目标的数量为n，其中第j个目标的规定毁伤程度为hj，目标坐标位置为xnj和ynj；若第i支部队对第j个目标实施火力打击，设压制火力毁伤对应的火力打击次数为g40ij，歼灭火力毁伤对应的火力打击次数为g60ij；联合火力打击任务规划中，设共包含子任务数为r个，其中第k个子任务的执行火力打击次数为lk，起始时刻为pk，结束时刻为qk；部队执行任务对应的兵力损耗系数为u。对任务规划的可行性判断主要包括：

1）保证目标距离不能超过部队射程。计算公式为

2）保证部队执行任务数不能超过任务上限数。计算公式为

对各类评估指标的量化分析如下：

1）单目标打击时长（Aj）。表示第j个目标在任务规划火力打击过程中，遭火力打击的起止时长。计算公式为

2）单部队打击次数（Bi）。表示第i支部队在任务规划火力打击过程中，实际完成火力打击的次数。计算公式为

3）整体打击时长（C）。表示任务规划中各火力打击子任务的总体起止时长。计算公式为

4）单目标冗余弹药比例（Ej）。表示第j个目标在任务规划火力打击过程中，被分配到的弹药用量超过其规定毁伤程度对应弹药量的比例。设投入弹药比例为Dj，目标等级为s，火力打击次数为d。计算公式为

5）单目标完成任务比例（Fj）。表示第j个目标在任务规划火力打击过程中，被分配到的弹药用量与规定毁伤程度对应弹药量的比例。计算公式为

6）体系破击能力（Gr1）。表示当执行完第r1个子任务时，对敌目标体系的破坏程度。计算公式为

7）防空削弱能力（Hr1）。表示当执行完第r1个子任务时，对敌防空预警能力的破坏程度。计算公式为

8）地面打击削弱能力（Ir1）。表示当执行完第r1个子任务时，对敌地面打击能力的破坏程度。计算公式为

9）弹药剩余比例（Ji）。表示第i支部队在任务规划火力打击后，剩余弹药量占携带弹药总量的比例。计算公式为

10）兵力剩余比例（K）i。表示第i支部队在任务规划火力打击后，通过综合衡量敌方的体系破击情况、防空削弱情况、地面打击削弱情况，综合预测兵力剩余数量占原有兵力数量的比例。计算公式为

11）复合打击次数（L）。表示任务规划中对目标实现多弹种、多兵种立体交叉火力打击的总次数。计算公式为

3.3 综合评分模型

在评估指标模型中，单目标指标类和单部队指标类是针对每个目标和每支部队计算的评估分值，因此需将各子评分融合为对应的评估指标分值，本文采用熵权法[11]进行子评分的融合计算。以单部队指标类的单部队打击次数评估指标为例，设目标数为m，联合火力打击任务规划的参评数为n，建立矩阵X。熵权法计算指标类的计算流程如下：

Step1：归一化处理。通过归一化变换将矩阵X转换为矩阵P，计算公式为

Step2：熵值计算。通过熵值公式将矩阵P中的m列转换为ej，计算公式为

Step3：熵权重计算。通过熵权重公式将熵值ej转换为熵权重tj，计算公式为

Step4：融合评估指标类计算。通过矩阵X和熵权重tj生成评估指标值zi，计算公式为

通过熵权法获取n个联合火力打击任务规划的11类评估指标后，使用理想点法[12]获取各任务规划的综合评分，实现联合火力打击任务规划的量化对比评估。计算流程如下：

Step1：理想点计算。获取正负理想点的空间位置A+和A-，计算公式为

Step2：理想距离计算。获取第i个任务规划和正负理想点位置的空间距离di+和di-，计算公式为

Step3：综合评分计算。获取第i个任务规划的综合评分Mi，计算公式为

4 仿真分析

为了验证粒子群算法在联合火力打击任务规划问题求解中的具体优化性能，设计仿真实验如下：采用文献[3]提供的标准遗传算法和文献[9]提供的标准粒子群算法作为参照对象，通过同类同源对比效果的方法分析算法的优缺点和有效性。仿真实验建模环境为Intel酷睿双核处理器T7300 2.0GHz；3G运行内存；Windows 7 32位操作系统；vc6.0仿真编程环境。

4.1 参数有效性分析

鉴于进化粒子群算法优化过程中的调试参数众多，难以有效衡量算法的综合优化效果，采取蒙特卡罗仿真的方法对各参数在取值范围内的优化迭代，找到最佳参数取值组合。根据算法的内部结构，选取的参数包括：个体寿命上限、个体变异概率、个体淘汰系数上限、觅食步长、允许觅食次数、判定收敛代数，r1，r2。各参数的优化结果如表2所示。

表2 参数优化结果

4.2 优化效果分析

为了检验进化粒子群算法应用于联合火力打击任务规划的有效性，并分析算法性能，以标准粒子群算法和遗传算法作为对比算法，统一设定迭代次数为500代，并标记各代最优个体的综合评分，以及全局最优个体的综合评分。三种算法各代最优个体综合评分情况如图5所示。

图5 各代最优个体综合评分对比

三种算法全局最优个体综合评分情况如图6所示。

图6 全局最优个体综合评分对比

实验结果表明，进化粒子群算法相比于标准粒子群算法和遗传算法的收敛效率和收敛综合评分均较高，侧面证明了标准粒子群算法和遗传算法通过有限代数的迭代获取的最优个体并非全局最优个体，相比之下进化粒子群算法能够在有限代数内获取更高性能的可行解，算法的应用性和寻优能力更强。通过对图5的分析可知，由于进化粒子群算法引入了遗传算法中的个体优胜劣汰机制，并且加入了寿命限制系数，使得算法的全局寻优能力更强，图5中进化粒子群算法各代最优个体综合评分抖动的更频繁剧烈，算法通过多代尝试寻找全局范围内的最优解，标准粒子群算法和遗传算法在此方面的表现相对较弱。

4.3 最优结果对比分析

将三种算法获取的全局最优个体对比分析，图7为最优个体内各评估指标的对比分析情况。

图7 全局最优个体各评估指标对比

实验结果表明，进化例子群算法最优个体的弹药剩余比例（No.6）评估指标明显优于标准粒子群算法和遗传算法，侧面证明了进化粒子群算法在应对临机火力打击任务时具备更好的优化效果。综合评分的比较上，进化粒子群算法最优个体综合评分明显高于另外两种算法。图8为三种算法完成收敛的迭代次数对比分析情况。

图8 算法迭代次数对比

图9为三种算法获取最优个体的时间消耗对比分析情况。

图9 算法时间消耗对比

实验结果表明，进化粒子群算法的迭代次数和时间消耗都要低于标准粒子群算法，基本和遗传算法持平，遗传算法的效率最高，但综合考虑最优个体的性能表现，进化粒子群仍然具备较强的竞争能力。进化粒子群算法获取的最优联合火力打击任务规划示例如表3所示。

表3 联合火力打击任务规划示例

5 结语

本文在借鉴标准粒子群算法的基础上，将遗传算法中的优胜劣汰和寿终正寝机制引入到粒子群算法，使算法的收敛效率和全局寻优能力进一步增强，并将其引入到联合火力打击任务规划具体问题求解中。创新点有：一是设计了基于标准粒子群算法的进化粒子群算法，经仿真实验检验，算法的各方面性能指标均优于原算法。二是通过对联合火力打击任务规划的约束条件分析，构建了能够实现任务规划综合评分的数学模型及相应评估算法。三是将智能优化算法引入联合火力打击任务规划中，实现了自动优化，为指挥员指挥决策提供了量化的辅助决策参考。