改进型布谷鸟搜索算法的防空火力优化分配模型求解

2019-02-15孙海文谢晓方孙涛庞威

兵工学报 2019年1期

孙海文，谢晓方，孙涛，庞威

(1.海军航空大学岸防兵学院，山东烟台 264001； 2.31102部队，江苏南京 210000)

0 引言

火力分配是防空作战中的重要组成部分[1]，它根据敌我双方的作战力量，明确哪些火力单元对哪些目标在何时采取何种射击方案进行拦截。

目前，传统的防空火力优化分配模型主要采用毁伤概率越大越好原则[2-3]。当处于火力资源相对充足的情况下，也存在很多的火力资源约束条件：文献[4]限制了拦截同一目标的火力单元数量，并以此对火力优化分配进行了约束；文献[5]定义一个毁伤概率均值的概念，即单位火力单元的毁伤概率，将其作为火力优化分配模型的原则，利用尽可能少的火力资源达到最大化的毁伤概率。这些火力优化分配模型由于火力资源的约束，往往在有限资源的条件下，利用毁伤概率大的火力单元进行目标分配[6]，但这忽视了目标进入火力单元发射区的时间，即飞临时间，当这些火力单元分配给更远目标时将会贻误战机。

此外，防空火力优化分配问题是一种整数型非线性多维组合优化决策问题，属于非确定性(NP)问题[7]，常用求解算法有匈牙利算法[8]、粒子群算法[9-11]、蚁群算法[12]以及遗传算法[13]等。综合分析这些方法，主要存在以下两方面问题：一方面部分方法控制参数较多，较难调整出适合的控制参数来有效地进行问题优化；另一方面不能有效地平衡全局探索和局部开发，往往顾此失彼，无法满足对实时性及准确度要求较高的优化问题。Yang等[14]提出了一种新的生物启发算法，即布谷鸟搜索算法(CSA)，该算法因具有结构简单、控制参数少和搜索能力强等优点，被广泛应用。文献[15]提出了基于初始交叉和变异的混合CSA，避免过早收敛，并应用于可靠性冗余分配问题。文献[16]分析了种群规模对算法性能的影响，提出了采用正交化学习的CSA，并对23个基准问题进行了算法测试，结果表明基于正交化学习增强了CSA的探测能力以及收敛性。文献[17]提出了离散CSA，有效地解决了旅行商问题。文献[18]提出了一种基于混沌的CSA，有效地提高了CSA的全局探索能力。文献[19]提出了一种动态自适应CSA，引入Rechenberg的1/5法则和学习因子来调整控制参数，仿真结果表明该方法动态适应性强，是一种高效简便的参数调整方法。从这些文献中可以得到3个主要结论：1)采用Lévy 飞行[14,20]搜索和偏好随机搜索后，都是对每个新解同时修改所有维的值来进行比较分析，没有考虑各维间变化的相互干扰；2)大部分文献并没有考虑将多种搜索模型相结合，提高全局探索能力；3)很少有文献充分利用种群的规模和数量来提高CSA的性能。

综上所述，本文提出了一种新的火力分配模型，即在传统模型上设置联合毁伤概率门限，同时加入目标飞临时间参数，在满足毁伤概率门限的前提下，选择目标威胁度大、飞临时间短、火力单元数量少的分配组合。在此基础上，提出了一种多种群并行CSA(MPCSA)，该算法引入了多个种群同时对解空间进行协同搜索，通过移民算子进行信息相互，各种群采用不同的控制参数取值和搜索模型；在此基础上，引入柯西变异算子构建新的全局搜索模型，能有效提高算法的全局探索能力；采用贪婪方式对全局探索到的解逐维进行更新，保留改善的解并进行种群更新，从而提高局部开发能力。最后，通过仿真分析，验证了所建模型的优势以及MPCSA求解火力优化分配问题的有效性和优越性。

1 防空火力优化分配模型

防空火力优化分配应遵循的主要原则：1)优先对威胁度大的目标进行拦截[7]；2)充分利用火力单元对不同目标的毁伤程度，在满足毁伤门限要求的条件下，用尽可能少的火力单元进行拦截；3)兼顾拦截时机，优先拦截飞临时间短的目标。针对这些原则，本文在传统防空火力分配模型的基础上进行了改进。

假设某一次编队防空作战中，m个空袭目标编号为Tj(j=1,2,…,m)，n个火力单元的编号为Fi(i=1,2,…,n)。令xij为决策变量，若第i个火力单元被分配拦截第j个目标，则xij=1，否则xij=0；令pij为第i个火力单元对第j个目标的毁伤概率。设Pj为所分配火力对第j个目标的联合毁伤概率，则

(1)

目标j到拦截该目标火力单元的飞临时间之和为

(2)

式中：tij为第j个目标到第i个火力单元的飞临时间。

引入预先毁伤概率阀值和飞临时间的火力- 目标分配模型：

(3)

(4)

(5)

从(3)式中发现目标函数Vmax与第j个目标的威胁度Wj呈正相关，而与j(xij)呈负相关。这个模型表明火力分配在控制火力数量的情况下，选择飞临时间之和小的火力单元，分配给威胁度大的目标。(4)式保证各来袭目标分配的火力单元联合毁伤概率都达到预期毁伤概率门限如果火力- 目标分配方案中则该目标的分配无效。毁伤概率门限是根据战场态势由指挥员或指挥系统确定。(5)式表示一个火力单元至多只能分配给一个目标。

2 求解防空火力优化分配的MPCSA

CSA是一种新的启发式算法[21]，其灵感来自于布谷鸟类动物在巢鸟产卵时的占巢寄生行为，即寄生性布谷鸟会将卵放置到宿主巢穴中。CSA利用发现概率融合了全局随机探索和局部随机开发。布谷鸟全局探索采用Lévy飞行模型将有效地对解空间进行最优解的探索。经全局探索得到更新解，根据发现概率pa(即各宿主发现陌生鸟卵的概率)，选取其中一部分进行局部开发。全局探索和局部开发相结合将有效地提高算法的收敛速度，具体2种搜索方式如下：

1)基于Lévy飞行的全局探索：

(6)

2) 基于发现概率pa和偏好随机游走的局部开发：

(7)

在过去的几十年里，优化问题的复杂性越来越高，进化算法也日益增多，Wolpert等[22]证明了没有哪种算法能适用于所有的优化问题。因此，针对不同的问题，需要设计不同的方法进行解决。本文改进了全局和局部搜索模式，并引入了多种群并行搜索的思想，以此来提高CSA的寻优能力。根据新思路提出新的全局探索模型，根据火力优化分配的特点，采用贪婪方式逐维进行寻优；在确定搜索模型的基础上，另一个新的思路是多种群并行搜索，即建立多个种群，各种群分别采用不同的控制参数取值和搜索模型进行同步搜索，通过移民算子进行种群间的相互交流，这种搜索模式兼顾了多种搜索模型的特点，降低了对控制参数的依赖性，增强了全局探索的能力，提高了收敛速度。

2.1 新全局探索模型

尽管Lévy 飞行模型中步长变化的大小能很好地探索全局空间，但为了进一步提高全局探索能力，需要一个更好地探索方式进行空间探索。柯西变异算子具有更广泛的分布范围，能更快地跳出局部区域[23]。利用柯西变异算子产生一个柯西分布随机数δ，将这个随机数代入全局探索公式中，产生一个新解。

柯西密度函数为

(8)

式中：g为尺度参数，通常取值为1.

柯西分布函数为

(9)

式中：y∈[0,1]。

根据(9)式，可得

δ=tan (π(y-0.5)).

(10)

根据(10)式，可产生一个0～1分布的柯西分布随机数。根据(6)式可得新的全局探索公式为

(11)

2.2 逐维局部开发模型

在CSA中，尽管偏好随机游走能有效地提高算法寻优能力，但火力分配模型属于多维目标函数，各维变量之间存在相互干扰，该搜索模型对解向量采用整体更新策略，从而影响了算法的收敛速度和解的质量。

针对上述问题，引入贪婪式逐维更新的思路。在每一代更新中，从第1维变量开始，更新该维的值，保持其他维的值不变，将其与其他维的值组合成一个新解，并与旧解进行比较。若改善当前的解，则保留新解，否则放弃当前维的更新值，进入下一维的操作。基于贪婪式逐维更新模式，将有效避免整体更新中各维之间的相互干扰，使得各维共同沿着优质解的方向变化，从而有效地提高局部开发能力。

2.3 多种群并行搜索

影响CSA寻优能力的因素主要有下列3个方面：

1)由于搜索模型自身结构的限制，单一的搜索模型将很难进一步提高搜索能力。

2)算法中存在控制参数，例如步长控制因子α和缩放因子r，控制参数不同的取值，将影响步长大小及变化尺度，进而可能导致不同的计算结果。至此，许多学者对控制参数的改进进行了探索，提出了自适应参数控制。但是，控制参数的设定往往是结合实际问题进行多次探索总结出来的，算法的性能在很大程度上受到控制参数设定的影响。

3)种群规模对算法寻优能力也存在较大影响。当种群规模较小时，群体多样性程度低，个体间竞争性较弱，随着迭代搜索的进行，群体会很快趋于单一化，并终止寻优；当种群规模较大时，将造成计算量的增加，影响计算效率。

针对上述问题，本文提出了多种群并行寻优的思想，如图1所示。

该思想具体内容如下：

1)突破了传统CSA仅靠单一种群和单一搜索模型进行寻优的框架，引入多种群同时进行优化搜索；为了增强算法的搜索能力，不同的种群赋予不同的搜索模型以及不同的控制参数。

2)各种群之间是相互独立的，为了实现多种群并行寻优，通过移民算子将各种群联系起来；最优解的获取是多个种群并行寻优的综合结果。移民算子将种群进化过程中的最优个体定期地引入到其他种群中，替换掉目标种群中的最差个体，从而实现多种群之间的信息交换。

3)设置精华种群，在进化的每代中，筛选出其他种群中的最优个体放入精华种群中进行保存，为了防止破坏和丢失各种群产生的最优个体，精华种群不进行搜索更新。

总之，引入多个种群同时对解空间进行并行搜索，有效地降低了算法控制参数设定不当对方案优化的影响，抑制了未成熟收敛的发生，兼顾了算法的全局探索和局部开发能力的均衡。

2.4 基于MPCSA求解火力优化分配

综合以上分析，基于MPCSA求解防空火力优化分配的具体步骤如下：

步骤1初始化种群。同时生成M个种群，每个种群的个体数量为N. 针对整数型火力优化分配问题，采用的编码可表示为x=[x1x2…xn]，其中xi为0～m之间的整数，xi=j表示将第i个火力单元分配给第j个目标，xi=0表示第i个火力单元没有分配给任何一个目标。

步骤2适应度评估。选择(3)式作为适应度函数，获取各初始种群中的最优个体，并设置一个精华种群，分别记录各种群中最优个体的适应度值和编码。

步骤3多种群同时进行全局探索。一半种群采用(6)式，另一半种群采用(11)式同时进行更新，生成多个新种群。其中，各种群的全局探索公式选取不同的控制参数取值，在更新过程中计算个体适应度值，保留改善的解。

步骤4将步骤3中生成的多种群，同时进行局部开发。根据发现概率pa以及(7)式，采用贪婪式逐维搜索模型生成多个新种群，同样在更新过程中计算个体适应度值，保留改善的解。至此，该种群完成一次进化。

步骤5更新精华种群。将进化后的各种群中的最优个体保存到精华种群中。

步骤6设置移民算子。移民算子每隔一定的进化代数，将各种群进化过程中的最优个体引入其他种群中，替换掉目标种群中的最差个体，从而实现多种群之间的信息交换。

步骤7提取精华种群中的最优个体，判断是否满足终止条件(通常终止条件有两种：一种是达到规定的进化代数；另一种是在规定进化代数内最优个体适应度值不发生变化)，若满足，则算法终止；若不满足，则返回执行步骤2～步骤6.

3 仿真实验

为了验证本文所提防空火力分配模型的优势以及MPCSA求解该防空火力优化分配的有效性和优越性，进行仿真实验比较分析。

3.1 防空火力分配模型比较分析

假设在防空作战中，某一来袭目标进入我防区，在敌目标来袭方向上的5个火力单元处于空闲状态。各火力单元对来袭目标的毁伤概率[p11p21p31p41p51]T=[0.824 0.782 0.683 0.810 0.843]T；来袭目标威胁度W1=0.17；来袭目标到各火力单元发射区时间[t11t21t31t41t51]T=[10 s 16 s 11 s 9 s 13 s]T。

分别采用本文所提防空火力分配模型M1、毁伤概率越大越好模型M2以及文献[11]所提的带有火力资源约束的分配模型M3进行火力优化分配。其中模型M1和M3中的毁伤概率门限为0.9. 3种模型的最优分配方案、目标毁伤概率以及平均飞临时间如表1所示。

表1 3种模型的最优分配方案、目标毁伤概率以及平均飞临时间

由表1中可知：模型M2采用5个火力单元拦截同一目标，虽然目标的毁伤概率最高，但火力资源浪费最严重，且毁伤概率提高幅度较小(数量级为10-2)；模型M3采用毁伤概率最高的两个火力单元拦截同一目标，在保持较高毁伤概率的同时节省了火力资源，但来袭目标到两个火力发射区的平均飞临时间较长，因此会贻误战机。本文所提模型M1在满足目标期望毁伤概率的条件下，采用飞临时间最短的两个火力单元对目标进行拦截，极大地节省了火力资源，并且不会贻误战机。

表2 模型M1的最优分配方案

表3 模型M3的最优分配方案

由表2和表3可知：模型M3采用毁伤概率最高的火力单元对各来袭目标进行拦截，虽然节省了火力资源，但其不考虑飞临时间，容易贻误战机；模型M1在满足目标期望毁伤概率的条件下，采用飞临时间最短的火力单元对目标进行拦截，极大地节省了火力资源，同时又不会贻误战机，进一步证明了M1的优势性，此外，还证明了MPCSA的有效性。

3.2 MPCSA仿真分析

为了验证本文所提算法的实用性和优越性，分别利用粒子群搜索(PSO)算法、自适应遗传算法(DGA)[3]、CSA、改进CSA(ICSA)[25]以及MPCSA对8个来袭目标和10个空闲火力单元进行火力优化分配仿真实验。PSO和DGA的种群规模均为50；CSA和ICSA的种群规模均为20；MPCSA的种群规模为5，种群数量为10；迭代次数均为300次。

图2所示分别为基于PSO算法、DGA、CSA、ICSA以及MPCSA的防空火力分配优化过程。从图2可见：PSO算法很不稳定，而且在接近200代时仍然未稳定下来，表明适应度值还有上升的可能性，其收敛速度较慢；DGA、CSA、ICSA以及MPCSA的收敛速度均有较好表现(100代以内)，具体收敛性能排序为CSA>MPCSA>ICSA>DGA，其中CSA的收敛性能最好。记录仿真中各算法的最优适应度值，如表4所示。

由表4可知，各算法的最优适应度值从大到小排序为MPCSA>ICSA>DGA>PSO算法>CSA，适应度值越大，代表分配方案越优。尽管MPCSA的收敛性能不是最优的，但其收敛速度与DGA、ICSA差距较小，且其最优适应度值最大，表明MPCSA在保证较高收敛速度的同时，具有较优的全局探索能力。

为了进一步检验本文所提MPCSA的寻优性能，对PSO算法、DGA、CSA、ICSA以及MPCSA分别进行了50次仿真。为保证目标分配实时性，需要算法在较短时间内寻找到尽量接近最优适应度次优值。设置各算法参数，使其进行一次仿真的运行时间的大约为1.5 s左右。各算法的蒙特卡洛仿真结果如图3～图7所示。

由图3～图7对比可见，5种算法均无法保证每次都找到最优适应度值，这是因为为保证算法具有较快的运行速度，各算法参数设置限制了算法找到最优适应度值的能力。进一步分析可知，5种算法每次仿真均能找到可行适应度值，其中，MPCSA的最优适应度值波动幅度较小，数值较稳定。为准确地比较各算法性能，取5种算法关键性能指标的统计结果，如表5所示。

由表5可知，在相同运行时间的50次仿真中，MPCSA适应度值的均值最大，标准差最小，且适应度值大于0.240 0的次数明显高于其他算法，表明MPCSA的全局探索性能较优越。

表5 5种算法性能指标的统计结果

为了进一步说明MPCSA的性能，各算法分别进行50次仿真，在保证适应度值大于0.240 0的概率不小于70%的条件下，统计各算法的平均运算时间，如表6所示。

由表6可见，在保证较高概率搜索到较优解的条件下，MPCSA的平均运行时间最短，具有较高的寻优效率。

表6 5种算法的平均运行时间

综合上述分析可知：PSO算法虽然表现出较好的全局探索能力，但其收敛速度较慢(迭代次数达上千次)；DGA、CSA、ICSA以及MPCSA在收敛速度上均有较好的表现，但DGA、CSA以及ICSA在全局探索中容易陷入局部极值，MPCSA能在迭代25次左右搜索到最优解，其收敛性较好，且由表5和表6分析可知，MPCSA方法能有效地平衡全局探索和局部开发，具有较高的寻优效率。