基于改进烟花算法的多导弹目标分配方法

安炳合; 寇佳禹; 王永骥; 刘磊

doi:10.15892/j.cnki.djzdxb.2020.03.026

PDF(1612 KB)

弹箭与制导学报 ›› 2020, Vol. 40 ›› Issue (3) : 113-118. DOI: 10.15892/j.cnki.djzdxb.2020.03.026

基于改进烟花算法的多导弹目标分配方法

作者信息 +

A Multi-targrts Allocation Method Based on Improved Fireworks Algorithm

Author information +

文章历史 +

摘要

为有效解决在多导弹拦截情况下的目标分配方法,文中基于改进的烟花算法提出一种新型目标分配方法。首先根据作战场景,对目标分配问题进行建模,定义了综合优势函数。为求解目标分配问题,设计了一种改进的烟花算法,改进的烟花算法在传统烟花算法的基础上引入差分进化算法中的交叉变异操作,提高算法的搜索能力。在数值仿真中,针对标准函数,使用改进的烟花算法与其他智能优化算法进行对比试验,试验结果证明了改进烟花算法的优越性。最后使用提出的算法求解分配问题,仿真结果证明新方法可以快速搜索出最佳分配方法,证明了算法的有效性。

Abstract

In order to solve the target allocation problem effectively in the case of multi-missile interception, this paper proposes a new target allocation method based on the improved fireworks algorithm. Firstly, according to the battle scenario, the target allocation problem is modeled and the comprehensive advantage function is defined. To solve the problem of target assignment, an improved fireworks algorithm is designed. Based on the traditional fireworks algorithm, the cross and variation operations of differential evolution algorithm are introduced to improve the search ability of the algorithm. In the numerical simulation, the improved fireworks algorithm is compared with other intelligent optimization algorithms for the standard function. The experimental results prove the superiority of the improved fireworks algorithm. Finally, the proposed algorithm is used to solve the allocation problem. The simulation results show that the proposed method can be used to quickly search for the best allocation method, which prove the effectiveness of the algorithm.

导出引用

安炳合, 寇佳禹, 王永骥, 等. 基于改进烟花算法的多导弹目标分配方法[J]. 弹箭与制导学报, 2020, 40(3): 113-118 https://doi.org/10.15892/j.cnki.djzdxb.2020.03.026

AN Binghe, KOU Jiayu, WANG Yongji, et al. A Multi-targrts Allocation Method Based on Improved Fireworks Algorithm[J]. Journal of Projectiles, Rockets, Missiles and Guidance, 2020, 40(3): 113-118 https://doi.org/10.15892/j.cnki.djzdxb.2020.03.026

中图分类号： E927;TP18;V271.4

0 引言

随着现代战争需求的提升,单一导弹对目标进行拦截已经难以满足作战要求。在多个目标需要被拦截的情况下,需要多个导弹协同作战。因此,在多导弹情况下的目标分配问题是作战过程中需要被解决的重要问题。在分配过程中需要考虑不同导弹对目标拦截的优势度,同时保证所有目标都被拦截,且不出现浪费火力的现象。已有不少学者对该问题进行了研究。

YANG F根据饱和攻击战术的思想,建立了武器-目标分配优化模型^[1],将火力分配决策与路径规划过程相结合,提出了一种在多火力和多约束条件下实现饱和攻击的方法。DOU J基于单舰空导弹射击区定义方法^[2],提出了编队舰空导弹系统的目标分配方法。王晓红基于目标的威胁度建立了一种目标分配模型^[3],采用匈牙利算法求解了分配问题。群体智能算法作为一种求解函数最优值的有效方法,也被广泛应用在目标分配问题中。针对火力分配问题,李平建立了一种层次分配结构^[4],把武器的作战效费比作为总的性能指标,利用遗传算法对性能指标进行了优化。周凌超在导弹与目标战术关系的基础上^[5],建立了多目标分配的数学模型,并提出一种改进的模拟退火算法对目标分配问题进行求解。黄峰首先改进了蚁群算法的搜索机制^[6],提出一种半约束随机蚁群算法,之后根据动态威胁因素,建立了防御过程的目标函数,利用改进的蚁群算法对多波次目标下的最优分配问题进行了求解。

在已有成果的基础上,针对多导弹拦截多目标情形下的目标分配问题,文中提出一种基于改进烟花算法的分配方法。首先综合考虑导弹的速度倾角,弹-目相对距离,弹-目速度关系对拦截效果的影响,建立了综合优势函数。之后将差分进化算法的交叉变异操作引入到烟花算法中,提出一种改进的烟花算法。对同一个标准函数,使用改进的烟花算法以及其他智能优化算法进行优化,仿真结果证明了改进后的算法具有更快的收敛速度。最后将提出的改进烟花算法用于求解目标分配问题,试验结果证明使用改进的烟花算法可以在较短的时间内完成目标分配任务。

1 多导弹目标分配建模

导弹与目标在平面内的相对运动模型如图1所示:其中M代表导弹,T代表目标,R代表导弹与目标的相对距离,V_M为导弹的速度,V_T为目标的速度,λ为视线角(LOS),即导弹与目标的连线与基准线之间的夹角。导弹的导弹偏角为θ_M,目标的弹道偏角为θ_T,γ为导弹的速度前置角,即导弹速度方向与视线之间的夹角。

图1 导弹-目标相对运动示意图

Full size|PPT slide

根据几何关系可以得到:

γ=θ_M-λ

(1)

在多导弹进行目标拦截的过程中,需要进行合理的目标分配,获得最大的作战效能。同时在分配的过程中应保证所有目标都被拦截,且不存在过多导弹拦截同一目标的火力浪费现象。因此需要根据导弹的物理状态设计综合优势函数,保证分配的结果能使综合优势函数达到最大值,达到最优的拦截效能。在综合优势函数中主要需要考虑导弹的角度优势,导弹的距离优势以及导弹的速度优势对拦截过程的影响^[7-8]。首先假设目标全部在导弹导引头的检测范围内,且多弹之间可以通过通讯网络相互通讯。

下面对各优势函数做具体分析:

1)导弹的角度优势

导弹速度方向沿视线方向的分量为V_Mcosγ,导弹速度沿视线方向的分量越大,越有利于导弹对目标的拦截,速度前置角γ的取值范围为[-π,π],因此γ的绝对值越小,V_Mcosγ的值越大,当γ=0时,导弹可以获得最大的角度优势。根据以上分析定义如下的角度优势函数:

S_γ=1-

\frac{|γ|}{π}

(2)

随着

|γ|

的增大,角度优势S_γ 逐渐减小,符合实际物理意义。

2)导弹的距离优势

当目标进入导弹的导引头检测范围时,相对距离越小,越有利于拦截。因此定义距离优势函数:

s_R=

e^{- \frac{|R|}{a}}

(3)

其中:a为当前状态下所有导弹与不同目标间距离的最大值。设计的距离优势函数随着距离的增大而减小。

3)导弹的速度优势

在一般情况下,提高导弹的速度更有利于对目标的拦截,因此定义速度优势函数:

s_V=

e^{- \frac{V_{T}}{V_{M}}}

(4)

在实际交战过程中,当导弹的距离优势与速度优势较大,但角度优势较小,即导弹的速度沿视线分量较小时,综合优势函数也不会很大^[7]。考虑以上特性,采用综合优势函数:

$s=M(c₁s_γs_R+c₂s_γs_V)$

(5)

综合优势函数由两部分组成,角度优势与距离优势的乘积项以及角度优势与速度优势的乘积项。其中:M>0为正常数,c₁、c₂为两部分的权重因子,满足条件c₁>0,c₂>0, 且c₁+c₂=1 。

设在交战过程中,有i个导弹执行拦截任务,有j个目标需要被拦截,根据定义的综合优势函数可以计算出综合优势函数矩阵S为:

[\begin{array}{l} s_{1,1} & s_{1,2} & \dots & s_{1, j} \\ s_{2,1} & s_{2,2} & \dots & s_{2, j} \\ ︙ & ︙ & ︙ \\ s_{i, 1} & s_{i, 2} & \dots & s_{i, j} \end{array}]

式中:s_i_,_j表示第i个导弹对第j个目标的综合优势函数值。

定义拦截矩阵D为:

[\begin{array}{l} d_{1,1} & d_{1,2} & \dots & d_{1, j} \\ d_{2,1} & d_{2,2} & \dots & d_{2, j} \\ ︙ & ︙ & ︙ \\ d_{i, 1} & d_{i, 2} & \dots & d_{i, j} \end{array}]

式中:d_i_,_j的取值范围为{0,1},当d_i_,_j=1 时代表第i个导弹对第j 个目标进行拦截,当d_i_,_j=0时代表第i个导弹不对第j个目标进行拦截。为保证每一个导弹对应一个目标,且每一个目标都被拦截到,应满足条件:

\sum_{m = 1}^{j} d_{n, m} = 1 (n = 1,2, \dots, i)

(6)

\sum_{n = 1}^{i} d_{n, m} \geq 1 (m = 1,2, \dots, j)

(7)

为了避免出现过多导弹拦截同一目标造成火力浪费的现象,加入限制条件:

\sum_{n = 1}^{i} d_{n, m} \leq G (m = 1,2, \dots, j)

(8)

式中:G为针对同一目标的最大拦截弹数。

根据以上分析,可以将目标分配问题转化成含有约束的非线性整数规划问题:

m a x F = \sum_{n = 1}^{i} \sum_{m = 1}^{j} d_{n, m} \cdot s_{n, m}

(9)

约束条件为:

\sum_{m = 1}^{j} d_{n, m} = 1 (n = 1,2, \dots, i)

(10)

1 \sum_{n = 1}^{i} d_{n, m} G (m = 1,2, \dots, j)

(11)

群体智能算法是求解非线性规划问题的有效手段,相较于传统的求解方法,在求解空间较大时具有较大的优势,同时不需要函数的梯度信息,更有利于实际应用。因此提出一种改进的烟花算法并应用改进的烟花算法求解目标分配问题。

2 改进的烟花算法设计

烟花算法是学者TAN Y提出的一种新型群体智能优化算法,它启发于烟花的爆炸过程^[9],在搜索最优解的过程中,以烟花的火花作为问题的可行解,模拟烟花爆炸产生新的火花的方式在旧的可行解的基础上产生新的可行解,并根据可行解的适应度函数(即待优化函数)进行选择,直到找到问题的最优解。但是,传统的烟花算法中种群内部的烟花粒子之间无法进行有效的信息交流:为了充分利用烟花粒子中所包含的可行解信息,文中在传统烟花算法的基础上引入差分进化算法中的交叉、变异操作,加强了粒子间的信息交流,提高算法的全局搜索能力。改进后的算法的流程如下:

步骤1:初始化。首先,根据待求解优化问题复杂程度,确定种群内部烟花粒子的数目以及维数,初始化烟花粒子X的取值并计算所有烟花粒子的适应度函数值。然后,设置烟花算法中爆炸半径系数

\tilde{R}

、爆炸火花系数

\tilde{N}

、变异火花数目以及选择差分进化算法中交叉策略、变异策略、缩放因子F、交叉率C_R。

步骤2:爆炸。以第i个烟花粒子x_i为例进行说明:根据其适应度函数值f(x_i)分别按照式(12)、式(13)计算该烟花爆炸产生的火花数量N_i以及爆炸半径R_i。

N_{i} = r o u n d (\tilde{N} \cdot \frac{f_{m a x} - f (x_{i}) + ε}{\sum_{i = 1}^{N} (f_{m a x} - f (x_{i})) + ε})

(12)

R_{i} = \tilde{R} \cdot \frac{f (x_{i}) - f_{m i n} + ε}{\sum_{i = 1}^{N} (f (x_{i}) - f_{m i n}) + ε}

(13)

式中:f_max和f_min分别代表所有烟花粒子中适应度函数值的最大值和最小值,ε是一个很小的常数,用来避免分子被零除。由式(12)、式(13)可知,当烟花粒子的适应度越好,即f(x_i)越小时,该烟花粒子的爆炸半径越小,爆炸数目越多。采用这样的爆炸策略有利于在适应度较优的粒子附近寻找到最优解。

为了防止爆炸产生的火花数目过多或者过少,采用式(14)所示的策略对N_i进行限制。

N_i=

\{\begin{array}{l} N_{m i n}, N_{i} N_{m i n} \\ N_{i}, N_{m i n} \leq N_{i} \leq N_{m a x} \\ N_{m a x}, N_{i} N_{m a x} \end{array}

(14)

假设烟花的维数为E,然后在每个即将爆炸的烟花x_i中随机抽取一些维度k(1≤k≤rand(0,1)·E),并采用式(15)所示的策略对爆炸产生火花的每一维位置进行计算。

x_{i, j}^{k}

x_{i}^{k}

+R_i·rand(-1,1)

(15)

式中:x_i,j为烟花x_i爆炸产生的第j(1≤j≤N_i)个火花。根据式(15)即可计算所有烟花爆炸产生火花的每一维位置。

假若爆炸产生火花的第k维度的值超出了可行域[x_low,x_up],则采用式(16)所示取模的方法将其映射到可行域内。

x_{j}^{k}

x_{l o w}^{k}

|x_{j}^{k}|

mod(

x_{u p}^{k}

x_{l o w}^{k}

)

(16)

最后对所有爆炸产生的火花计算其各自的适应度函数值。

步骤3:差分变异。借鉴差分进化算法中交叉、变异的操作^[10],产生一定数量的变异火花。首先在当前种群内部任意选取4个不同的个体Q₁、Q₂、Q₃、Q₄以及适应度最优个体 Q_best,按照式(17)的计算方式交叉产生第i个变异火花U_i,F为缩放因子。

U_i=Q_best+F·(Q₁-Q₂)+F·(Q₃-Q₄)

(17)

然后在种群内部随机选取一个未选择过的烟花或火花粒子Q_i,并按照所设定的交叉率C_R对粒子U_i中的第j维信息进行变异操作,产生式(18)所示的最终变异火花U_i,并计算其适应度函数值。

U_i,j=

\{\begin{array}{l} U_{i, j}, r a n d (0,1) C_{R} \\ Q_{i, j}, 其 他 \end{array}

(18)

步骤4:选择。首先选取当前种群(包括烟花、子代火花、变异火花)中适应度最优的个体参与下一次迭代,然后采用轮盘赌的方式在其余的所有个体中选取参与下一次迭代的其余个体。每个体被选中的概率采用式(19)所示的策略进行计算。

P (x_{i}) = \frac{\sum_{j = 1}^{N} |x_{i} - x_{j}|}{\sum_{k = 1}^{N} \sum_{j = 1}^{N} |x_{k} - x_{j}|}

(19)

式中:分子

\sum_{j = 1}^{N} |x_{i} - x_{j}|

表示第i个烟花粒子与种群内部其余粒子间的距离,分母

\sum_{k = 1}^{N} \sum_{j = 1}^{N} |x_{k} - x_{j}|

表示种群内部所有烟花粒子两两之间的距离总和,N为当前种群中所有烟花以及火花的数目。由式(19)可知,距离其他烟花位置越远的烟花,被选择的概率越大;距离其他烟花位置越近的烟花,被选择的概率越小。这样的选择策略既能剔除冗余的烟花粒子,又保证了参与下一次迭代寻优的烟花粒子具有多样性,不容易陷入局部最优解中。

步骤5:判断。若算法已达到最大迭代次数或者最优解满足所需要求则结束迭代寻优过程。反之,跳至步骤2继续循环迭代寻优。

整个改进烟花算法的流程如图2所示。

图2 改进烟花算法流程图

Full size|PPT slide

3 数值仿真

3.1 改进烟花算法性能测试

为了验证改进的优化算法的有效性,使用差分进化算法(DE),传统的烟花算法(FWA),以及改进的烟花算法(improved FWA)对两个标准函数进行优化。差分进化算法参数设置为: 交叉率C_R=0.3,缩放因子F=1.2,传统的烟花算法中参数设置为:爆炸半径系数

\tilde{R}

=300,爆炸火花系数

\tilde{N}

=100,最大爆炸火花数目N_max=20,最少爆炸火花数目N_min=5。改进烟花算法参数的设置与传统烟花算法和差分进化算法中的参数相同。仿真在Windows10\Matlab2015a 环境下进行,CPU主频为1.7G,3种算法的种群数全部选取为30。

1)标准测试函数Beale 函数如式(20)所示。

J₁(x,y)=(1.5-x+xy)²+(2.25-x+xy²)²+ (2.625-x+xy³)²

(20)

J₁(x,y)在其定义域x∈[-4.5, 4.5], y∈[-4.5, 4.5] 内是一个多模态函数,存在多个极小值点,全局最小值点为J₁(3,0.5)=0。其函数图像如图3所示,使用上述3种优化算法搜索函数的最小值,仿真结果如图4所示。

**图3 Beale函数图像**

Full size|PPT slide

图4 适应度函数变化曲线

Full size|PPT slide

根据适应度变化曲线可以看出,使用改进后的烟花算法收敛速度更快,认为当适应度函数的值小于1×10^-4时,优化算法已经找到最优解。使用传统烟花算法找到最优解需要的迭代次数为20次,使用改进的烟花算法需要6次,使用差分进化算法需要28次,改进的烟花算法需要的次数最少,证明了改进烟花算法具有较好的收敛性。

2)标准测试函数Eggholder 函数如式(21)所示。

J₂(x,y)=-(y+47)sin

\sqrt{|y + \frac{x}{2} + 47|}

-xsin

\sqrt{x - (y + 47)}

(21)

J₂(x,y)在其定义域x∈[-512, 512], y∈[-512, 512] 内存在众多极小值点,其函数图像如图5所示,函数的全局最小值点为J₁(512,404.2319)=-959.6407。使用上述3种优化算法搜索函数的最小值,仿真结果如图6所示。

**图5 Eggholder 函数图像**

Full size|PPT slide

图6 适应度函数变化曲线

Full size|PPT slide

根据适应度变化曲线可以看出,使用改进后的烟花算法,达到最大迭代次数后,使用改进的烟花算法已经找到了全局最优解,且收敛速度较快,最终使用传统烟花算法搜索的结果为 J₂(507.8374,398.3313)=-937.489,使用差分进化算法搜索的结果为J₂(-465.7,385.7107)=-894.579,使用改进烟花算法搜索到的最优解为:J₂(512,404.2131)=-959.640,由仿真结果可以看出使用改进烟花算法优化得到的解更接近真实最小值点,证明改进后的烟花算法具有更好的全局搜索能力。

3.2 使用改进的烟花算法求解目标分配问题

设执行拦截任务的导弹共有6个,需要被拦截的目标为4个,每一代火花数目选取为10个,导弹的位置与目标位置如表1所示,导弹的速度均为300 m/s,目标的速度为150 m/s,导弹的弹道偏角均为0° 。综合优势函数的参数取值为c₁=0.5, c₂=0.5, M=5, G=2。根据当前交战状态以及式(5)可以计算出当前综合优势函数矩阵S,之后采用改进的烟花算法对分配方案进行优化。改进烟花算法参数的设置与3.1节相同。

表1 导弹与目标位置分布 m

编号	(x,y)
导弹1	(13 500,-2 000)
导弹2	(15 000,0)
导弹3	(17 000,3 000)
导弹4	(18 000,5 000)
导弹5	(16 000,6 000)
导弹6	(18 000,10 000)
目标1	(35 000,-1 000)
目标2	(35 000,2 000)
目标3	(37 000,5 000)
目标4	(35 000,9 000)

烟花粒子采用如图7所示的方式编码:每一个烟花粒子共6维,第k (k=1~6)维的取值代表第k枚导弹拦截的目标序号,按此方式编码可满足一枚导弹只拦截1个目标的约束。在烟花算法的迭代过程中,检测粒子是否满足约束式(11),如不满足则该烟花粒子的综合优势函数直接取0值。优化过程适应度函数变化曲线如图8所示,最终目标分配结果如图9所示。

图7 烟花粒子的编码方式

Full size|PPT slide

图8 综合优势函数变化曲线

Full size|PPT slide

图9 目标分配结果

Full size|PPT slide

由仿真结果可以看出:经过5次迭代后,改进的烟花算法找到了最优的目标分配方案,找到的最优分配方案与使用穷举法计算出的最优方案相同,即导弹1、导弹2拦截目标1,导弹3拦截目标2,导弹4、导弹5拦截目标3,导弹6拦截目标4,实现了最大的优势函数,且分配结果在几何关系上适合各个导弹的拦截,并满足目标分配过程中的约束条件。找到最优方案需要的时间小于0.4 s,满足了快速目标分配的要求。仿真结果证明了文中提出方法的有效性与优越性。

4 总结

对导弹拦截情况下的目标分配问题进行了一定探索性研究,提出了一种基于改进烟花算法的目标分配方法。首先分析了交战情况下的弹-目优势关系,并建立了基于综合优势函数的目标分配数学模型。为了求解目标分配模型,将差分进化算法中的交叉变异操作引入到烟花算法中,提出了一种改进的烟花算法。在数值仿真中,首先通过标准函数的测试证明了改进烟花算法具有较好的收敛性与全局搜索能力,之后将改进的烟花算法用于求解目标分配问题,仿真结果证明使用提出的方法可以快速地找到最优分配方法,验证了算法的有效性。

参考文献

列表( 原文顺序 | 文献年度倒序 | 文中引用次数倒序 ) 可视化分析

[1]	YANG F, DONG C Y, WANG Q. Multi-target decision-making of saturation attack for anti-ship missile weapon-target assignment[C]// IEEE. Proceedings of 2009 International Workshop on Intelligent Systems and Applications.[S.l.]:IEEE,2009: 1-4. 本文引用 [1]

[2]	DOU J H, DONG S Q, YU J X. Target allocation study for formation ship-to-air missile system based on the missile fire zone[J]. Journal of Computational Intelligence and Electronic Systems, 2013, 2(2): 156-160. 本文引用 [1]

[3]	王晓红, 沈永福. 防空导弹目标分配优化方法研究[J]. 弹箭与制导学报, 2012, 32(4):49-52. 本文引用 [1]

[4]	李平, 李长文. 武器目标协同火力分配建模及算法[J]. 指挥控制与仿真, 2015, 37(2):36-40. 本文引用 [1]

[5]	周凌超. 基于改进模拟退火算法的导弹目标分配方法[J]. 工业控制计算机, 2018, 31(1):95-97. 本文引用 [1]

[6]	黄峰, 陈中起, 冯金富, 等. 基于半约束随机搜索的空舰导弹目标分配方法[J]. 系统工程与电子技术, 2013, 35(8):1676-1680. 本文引用 [1]

[7]	吴森堂. 导弹自主编队协同制导控制技术[M]. 北京: 国防工业出版社, 2015: 67-86. 本文引用 [2]

[8]	黄家成, 谢奇峰. 基于遗传算法的协同多目标攻击空战决策方法[J]. 火力与指挥控制, 2004, 29(1):49-52. 本文引用 [1]

[9]	TAN Y, YU C, ZHENG S Q, et al. Introduction to fireworks algorithm[J]. International Journal of Swarm Intelligence Research, 2013, 4(4): 39-70. 本文引用 [1]

[10]	王杰文. 差分进化算法研究进展[J]. 湖南第一师范学报, 2009, 9(6):144-147. 本文引用 [1]

基金

国家自然科学基金(61873319)

国家自然科学基金(61473124)

PDF(1612 KB)

Accesses

Citation

Detail

段落导航

收稿日期	出版日期
2019-06-27	2020-06-20
发布日期
2025-02-12

选择文件类型/文献管理软件名称

选择包含的内容