基于竞争蛙跳算法的联合火力打击任务规划方法

王海峰,高小军,刘 昊

(1.中国人民解放军31696部队,辽宁 锦州 121000;2.郑州联勤保障中心,河南 郑州 450000)

联合火力打击是未来联合作战的重要环节,对联合火力打击任务规划的综合效果评估和优化是联合作战筹划中的工作重点和难点[1]。考虑到联合火力打击任务规划中涉及的火力打击兵器种类、弹药类型和目标数量繁多,问题复杂度远高于过往战争形态中以单一兵种的动态火力分配问题,手工作业手段难以应对,必须考虑引入智能优化算法求解联合火力打击任务规划问题。联合火力打击任务规划中的兵力、火力、目标分配问题在军事运筹领域属于动态火力分配问题,以被证明属于NP完全问题[2]。针对此类问题,国内外的学者已经进行了充分的研究和论证,随着计算机运算能力的大幅提升和人工智能研究的逐步深入,运用智能优化算法通过多代迭代找到NP问题最优解成为解决此类问题的有效解法。

智能优化算法是20世纪70年代随人工智能而兴起的一类仿生算法,代表算法包括以模拟生物群落行为规律的蜂群算法[3]、蚁群算法[4]、蛙跳算法[5]、鱼群算法[6]、萤火虫算法[7]、布谷鸟算法[8]、粒子群算法[9]、细菌觅食算法[10]等;以模拟自然界规律的细胞膜优化算法[11]、模拟退火算法[12]、量子进化算法[13]等;以及模拟生物种群内部演化规律的遗传算法[14]、贪心算法[15]等。上述智能优化算法各自的理论出发点均不相同,但算法设计存在共同点:一是设计可动态调整的智能体框架,结合具体问题的可行解建立一一对应的映射关系,将问题求解转化为向量空间中找最佳位置向量;二是通过引入伪随机数使智能体在向量空间中随机游走或多代变异演化,使可行解无限逼近周边最优;三是通过设定退出条件限制迭代次数,并输出优化后的最优解作为时限内的可行解。相比于基于数学函数的线性规划算法,智能优化算法具有非线性不连续、约束条件调整方便、最优解输出可控等优点,然而算法也存在易陷入局部最优陷阱,以及收敛代数和优化效果不可控的风险。基于此,本文以蛙跳算法为标准,借鉴并引入遗传算法中的寿终正寝和优胜劣汰机制,设计了竞争蛙跳算法,并将该算法引入联合火力打击任务规划问题求解中,实现了动态火力分配的自动生成和智能优化,取得了良好的工程应用效果。

1 问题描述

联合火力打击任务规划问题是在限定的兵力、火力和目标条件下,确保以完成火力打击任务份额为前提,使我方兵力和火力损耗最小的动态兵力、火力、目标分配问题。设我方参与联合火力打击的兵力为B={b1,b2…bn},其中bk表示第k个火力打击部队的编号、兵力种类、打击参数、执行任务次数、执行任务时长、任务间隔时长等变量集合;敌方目标为D={d1,d2…dm},其中dl表示第l个目标的编号、种类、应毁伤程度、对应弹药需求量等变量集合;H(dl,bk)、D(dl,bk)、S(dl,bk)、T(dl,bk)分别表示使用第k个火力打击部队打击第l个目标时,对目标造成的毁伤程度,弹药消耗量,我方兵力预计损耗量,火力打击总体时长等变量。联合火力打击任务规划问题的硬约束条件如下:

1)保证完成上级赋予的火力打击任务份额。设任务规划共包含p个子任务,规定的火力打击任务份额为G;则约束条件的数学模型表述如下

(1)

2)保证我方各参战部队有足够弹药应对突发任务。设任务规划中第k个部队执行p次任务,每次弹药消耗量为l,弹药总量为Lk;则约束条件的数学模型表述如下

(2)

3)保证在规定时限内完成火力打击任务。设任务规划共包含p个子任务,发起火力打击时刻为Ts,规定火力打击截止时刻为Tz,第k个部队的火力打击总时长为Tk;则约束条件的数学模型表述如下:

(3)

max{T1,T2,…,Tk}≤Tz-Ts

(4)

在达成硬约束条件的前提下,设定软约束条件如下:

1)尽可能在最短时间内对目标实施火力打击(防止目标逃离)；

2)尽可能节约我方弹药量,以备不时之需；

3)尽可能减少我各参战部队的兵力损耗；

4)尽可能平均分配各部队的火力打击任务量；

5)尽可能压缩总体火力打击时长；

6)尽可能对同一目标实现多兵器、多弹种联合火力打击。

问题的难点:1)各约束条件相互为制约,须通过智能算法建立数学模型找到最佳平衡点;2)目标清单处于动态更新中,随时会出现新的目标打击任务,因此联合火力打击任务规划要保证预留部队和弹药量应对临机任务。

2 算法构建

智能优化算法应用于联合火力打击任务规划问题求解,主要由数据录入、向量空间建立、综合评估、竞争蛙跳4个部分构成。数据录入部分将当前态势下获取的实时目标情报信息、我方火力打击部队的实时信息录入,结合前期已知的各兵器、弹种对各目标的毁伤能力信息,为后续的智能优化提供数据支撑;向量空间建立部分以打击部队，消耗弹药，打击目标建立多维空间,将动态兵力、火力、目标分配问题转化为多维向量空间中寻找最优解向量问题;综合评估部分以数据录入为基础,将固定输入条件下的联合火力打击任务规划通过数学模型的量化评估指标计算综合评分;竞争蛙跳部分以向量空间和综合评估为基础,通过竞争蛙跳,经过多代迭代,获取联合火力打击任务规划在向量空间中对应的最佳位置,并将解向量转化为唯一对应的任务规划结果输出。智能优化算法的流程如图1所示。

图1 智能优化算法流程图

2.1 竞争蛙跳模型

标准蛙跳算法以自然界中蛙群为参考对象,设蛙群分散在多个独立的子群落中,各子群中的最差评分个体可通过有限次数蛙跳向周边的高分位置转移,若转移失败则引入新个体替代最差评分个体;定期将子群落中的个体打乱重组,防止子群落中的个体陷入局部最优。标准蛙跳算法流程如图2所示。

图2 标准蛙跳算法流程图

通过对标准蛙跳算法分析可知,其算法核心包含两部分:一是通过最差评分个体向周边移动的蛙跳操作探索高分位置;二是定期打乱重组防止算法陷入局部最优。然而算法也存在如下缺陷:一是对偶然产生的局部最高评分个体无法规避,该个体会繁殖众多类似的后代个体替代低分个体,使种群多样性受到破坏,导致算法陷入局部最优;二是蛙跳冗余问题,最差评分个体若处于低分区域,但未达到删除的程度时,算法会频繁对其实施无意义的重复蛙跳动作,导致系统资源消耗。基于此,本文借鉴遗传算法中的寿终正寝和优胜劣汰机制,引入寿命和淘汰系数对蛙跳算法进行改造。算法思想是，为了防止局部高分个体的大量繁殖,为所有个体添加寿命系数,设每次打乱重组后为所有个体寿命+1,若有个体寿命达到上限,不论其综合评分结果如何,均删除该个体,以模拟自然界的寿终正寝生命历程;为了防止无意义蛙跳问题,为所有个体添加淘汰系数,设个体的每次蛙跳动作后且评分未提升,则淘汰系数+1,若有个体蛙跳次数达到上限,不论其综合评分结果如何,均删除该个体,以模拟自然界的优胜劣汰自然选择规律。竞争蛙跳算法流程如图3所示。

图3 竞争蛙跳算法流程图

个体数据结构如表1所示。

表1 个体数据结构

具体算法步骤如下:

Step1:创建初始种群,每个个体对应向量空间中的唯一点位。

Step2:计算种群内所有个体的综合评分,记录最高评分个体Xq。

Step3:将种群内所有个体按评分排序,并按序号平均分配到m个子群中,保证各子群内个体总评分相差不大。

Step4:所有个体寿命+1。

Step5:对各子群的最低评分个体Xw实施蛙跳操作,蛙跳后的新位置个体为X′w。

Step6:若X′w的综合评分高于Xw,则用X′w替代Xw。

Step7:否则重复5-6,若k次蛙跳后的X′w综合评分低于Xw,则用该子群最高分个体繁殖新个体代替Xw。

Step8:更新所有个体淘汰系数。

Step9:将所有子群打乱重组,记录最高评分个体Xq。

Step10:重复Step3-8,直至达成退出条件,输出最高评分个体。

2.2 评估指标模型

本文中针对联合火力打击任务规划的各约束条件,共设计了3类、11项评估指标。具体评估指标如图4所示。

图4 联合火力打击任务规划评估指标

设共有m支部队,第i支部队打击半径为oi,可执行打击任务次数为ci,任务执行时长di,任务间隔时长ei,部队所在地坐标为(xmi,ymi);目标打击表中共有n个目标,第j个目标的标准毁伤程度为hj,目标所在地坐标为(xnj,ynj);毁伤能力表中第i支部队对第j个目标火力打击,毁伤40%对应出动次数为g40ij,毁伤60%对应出动次数为g60ij;火力打击任务规划中共有子任务r个,第k个子任务的执行任务次数为lk,打击开始时刻为pk,打击结束时刻为qk;u为部队每次执行任务后的兵力损耗百分比。首先要对任务规划进行可行性判断。

1)剔除超过部队射程的子任务,计算公式为

(5)

2)剔除超出最大出动能力的子任务,计算公式为

(6)

然后计算各评估指标。

1)单目标打击时长(Aj)。用以表示对第j个目标实施联合火力打击的总用时,计算公式为:

Aj=max{qj}-min{pj}

(7)

2)单部队打击次数(Bi)。用以表示第i个部队已实施火力打击的次数,计算公式

(8)

3)整体打击时长(C)。用以表示该任务规划的联合火力打击总用时,计算公式为

C=max{qk}-min{pk}

(9)

4)单目标冗余弹药比例(Ej)。用以表示对第j个目标实施联合火力打击的弹药用量,超过规定毁伤弹药用量的比例。设投入弹药比例为Dj,s表示目标等级,d表示出动次数;计算公式为

(10)

Ej=max{0,Dj-100}

(11)

5)单目标完成任务比例(Fj)。用以表示任务规划中对第j个目标实施联合火力打击的任务完成度,计算公式

Fj=min{100,Dj}

(12)

6)体系破击能力(Gr)。用以表示完成第r个子任务时,对敌体系作战能力的破坏程度,计算公式为

(13)

7)防空削弱能力(Hr)。用以表示完成第r个子任务时,对敌防空能力的破坏程度,计算公式为

(14)

8)地面打击削弱能力(Ir)。用以表示完成第r个子任务时,对敌地面打击能力的破坏程度,计算公式为

(15)

9)弹药剩余比例(Ji)。用以表示第i个部队执行完火力打击任务后的弹药剩余比例,计算公式为

(16)

10)兵力剩余比例(Ki)。用以表示第i个部队执行完火力打击任务后,按照敌方的体系破击能力、防空削弱能力、地面打击削弱能力情况,预测剩余的兵力占原有兵力的比例,计算公式为

(17)

11)联合打击次数(L)。用以表示对各目标实施联合火力打击过程中,实现了多种兵器、多种弹药在同一时刻对同一目标实施复合火力打击的次数,计算公式为

(18)

(19)

2.3 综合评分模型

本文使用熵权法[16]将单目标指标和单部队指标进行融合处理,生成唯一对应的评估指标,而后使用理想点法[17]将11项评估指标综合计算评分。以单目标指标的融合计算过程为例,设共有m个火力打击目标,有n个任务规划参与评估,建立初始矩阵X;熵权法的计算流程如下:

Step1:归一化处理。生成归一化矩阵P,计算公式为

(20)

Step2:熵值计算。生成m个目标的对应熵值ej,计算公式为

(21)

Step3:熵权重计算。生成第m个目标的对应熵权重tj,计算公式为

(22)

Step4:融合评估指标计算。生成n个任务规划的融合评估指标值zi,计算公式为

(23)

当获取n个任务规划的11项评估指标后,使用理想点法的计算流程如下。

Step1:计算正负理想点A+和A-,计算公式为

(24)

(25)

Step2:计算第i个任务规划与正负理想点之间的距离di+和di-,计算公式为

(26)

(27)

Step3:计算第i个任务规划的综合评分Mi,计算公式为

(28)

3 仿真分析

为了验证竞争蛙跳算法在联合火力打击任务规划中的优化效果,本文采用文献[5]提供的标准蛙跳算法作为对比算法。仿真实验计算机配置为Intel酷睿双核处理器T7300 2.0 GHz，3G内存，Window 7 32位操作系统，vc6.0编程平台。

3.1 参数有效性分析

为了验证最优搭配组合的参数设置,设计实验如下:选取变异概率、种群规模、蛙跳步长、蛙跳尝试次数、寿命上限、淘汰系数上限、退出条件代数为待调节参数,每次调整其中一个参数的取值范围,并通过竞争蛙跳算法的多代迭代最优评分为参考条件,将参数调整为最佳位置,如此反复,直至所有参数均达成最优值,输出最优评分个体。所有参数的最优值如表2所示。

3.2 效果对比分析

为了检验算法的优化效果,以标准蛙跳算法和标准遗传算法作为对比实验,计算经过500代迭代进化的最优个体综合评分结果。算法最高评分对比变化情况和各代最高评分对比变化情况如图5和图6所示。

表2 参数优化统计

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

图6 各代最高评分对比

实验结果表明,竞争蛙跳算法相比于标准蛙跳算法和标准遗传算法,收敛速度更快,能够在较少代数内达成全局最优。图6中,标准蛙跳算法的各代最优个体评分抖动不大,表明高分的超级个体影响了算法的寻优能力,限制了种群的多样化发展方向;相比而言,竞争蛙跳算法的各代最优个体评分抖动明显,表明种群正在向多样化发展,试图突破当前位置局限,寻找全局最优解。

3.3 规划结果分析

为了检查算法在联合火力打击任务规划具体问题中的应用效果,将三种算法得到的最优个体进行对比分析。三种算法的时间消耗对比情况如图7所示,收敛代数对比情况如图8所示。

图7 算法时间消耗对比

图8 算法收敛代数对比

实验结果表明,竞争蛙跳算法由于引入了淘汰系数,蛙跳更具方向性,同时避免了无意义的重复蛙跳动作,因此收敛代数更短,时间消耗更少。对标准蛙跳算法和竞争蛙跳算法得到的任务规划11项评估指标进行对比分析,两种算法的评估指标对比情况如图9所示。

图9 算法评估指标分值对比

实验结果表明,除了单部队打击次数(No.4)和体系破击能力(No.8)评估指标外,竞争蛙跳算法的各项评估指标均优于标准蛙跳算法,由此可知,标准蛙跳算法获取的最优个体并不是全局最优个体,竞争蛙跳算法相比较而言具备更优异的全局寻优能力。

竞争蛙跳算法对应的联合火力打击任务规划示例如表3所示。

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

4 结束语

本文在前人对智能优化算法研究的基础上,创造性地将遗传算法中的寿终正寝和优胜劣汰机制引入到蛙跳算法中,设计了综合效果更优异的竞争蛙跳算法,并以此为基础实施联合火力打击任务规划,通过竞争蛙跳算法的多代迭代获取最优的规划计划,使任务规划综合评分达成全局最优。创新点有，一是梳理了联合火力打击任务规划的硬性和软性约束条件,并提出了量化评分算法,实现了对联合火力打击任务规划的量化评估;二是设计了新的智能优化算法——竞争蛙跳算法,经仿真实验验证,优化分值和收敛效率均高于标准算法;三是将智能优化算法引入联合火力打击任务规划问题中,实现了基于计算机的自动优化评估。仿真实验结果表明,该方法可引入到联合火力打击任务规划问题优化中,能够动态生成最优的任务规划,并以此为基础拟制火力打击方案和计划,并提出量化的辅助决策建议,为联合作战指挥员定下火力打击决心提供参考标准。