基于突防效能的导弹-目标分配求解算法
2019-07-04齐长兴毕义明
齐长兴,毕义明,李 勇
(火箭军工程大学, 西安 710025)
导弹作战时面临着弹道导弹防御系统的拦截,充分运用各种突防技术可以提高导弹突防效能,同时,合理分配导弹,对敌方导弹防御系统进行压制,也是提高导弹作战效能的重要手段。以提高导弹突防效能为目的,合理进行导弹-目标分配是一种典型的武器-目标分配(Weapon,Target,Assignment,WTA)问题,就是在作战资源一定的情况下,通过对进攻导弹(主突导弹、辅攻导弹)合理配置,对敌方导弹防御系统进行压制,通过对辅攻导弹的合理配置和战术运用,提高导弹突防效能。
WTA问题是一个典型的NP完全问题[1],随着规模的增加,问题的求解时间呈指数级增长。传统的算法在解决这类问题时较为困难,当前主要采用启发式算法求解。文献[2]提出了离散粒子群优化求解WTA问题的方法;文献[3]提出了求解WTA问题的局部协同控制方法;文献[4]将MOPSO (Multi-object Particle Swarm Optimization, MOPSO) 和TOPSIS(Technique for Order Preference by Similarity to an Ideal Solution,TOPSIS)结合,进行多目标武器目标分配问题求解;文献[5]提出了一种自适应并行群选择算法解决武器目标分配问题,取得了较好的应用效果;文献[6]建立了基于改进型多目标粒子群优化算法,应用于较大规模的WTA问题实时求解等。但是这些算法不同程度上存在早熟收敛、进化速度慢及计算复杂等问题,在实际问题应用中还需要进行调整优化。
基于突防效能的导弹-目标分配问题是在给定作战条件下,以导弹防御系统为作战目标,合理分配火力使得主突导弹突防效能最高。本文构建了基于突防效能的导弹-目标分配模型,并以粒子群算法为主体,采用混沌优化策略和禁忌搜索策略对粒子群算法进行优化,构建改进的混合粒子群算法对模型进行求解,案例分析验证了方法的可行性。
1 导弹-目标分配问题描述与建模
设m为导弹武器的种类,Mi(i=1,2,3,…,m)为第i种导弹武器的数量;n为导弹防御体系中作战主体(例如,预警卫星、预警机、雷达、反导导弹、电子战装备、电磁武器等)数量。l为防御系统体系中作战主体类型数,nj(j=1,2,3,…,l)为第j种作战主体的数量。第i类导弹对防御体系中第j个作战主体毁伤概率为eij。引入WTA矩阵,分配矩阵X和毁伤概率矩阵E分别为:
(1)
(2)
xij=1表示分配了第i个导弹武器打击敌j个目标,否则xij=0。eij表示第i个导弹武器打击敌j个目标使得毁伤概率。
针对导弹防御系统中不同的作战主体对导弹防御系统整体功能发挥的作用重要度不同,对不同的作战主体进行打击后,提高导弹突防效能的程度不同,本文引入突防贡献度的概念,对导弹突防作战效果进行评价。突防贡献度即:对导弹防御系统中某个作战主体(节点)进行打击后,对导弹突防效能提高的贡献,用[0,1]区间的实数表示突防贡献度的大小。考虑突防贡献度后,导弹-目标火力分配模型可以表示为:
(3)
式中,F为导弹突防的效益函数;Cj为第j个作战主体被打击后的突防贡献度,采用专门的评价方法进行确定。
2 改进的混合粒子群优化算法
粒子群优化(Particle Swarm Optimization,PSO)算法具有良好的全局和局部搜索能力[7],在求解问题优化时得到了很好的应用。但是粒子群优化算法后期容易陷入早熟收敛,局部寻优能力不高。本文提出了一种基于混沌优化与禁忌搜索策略的混合粒子群优化算法[8]。采用混沌优化方法生成初始种群,以保持种群多样性;采用禁忌搜索策略,以提高搜索效率,避免了基本粒子群优化算法中存在的易于陷入局部最优的问题。
2.1 Tent混沌映射模型
Logistic映射和Tent映射在混沌系统中具有较为广泛的应用,Tent映射比Logistic映射的遍历性和迭代速度更快[9]。因此,采用Tent映射产生混沌序列,其表达式为:
z(t+1)=T(z(t))=
(4)
式中,z(t)∈[0,1]。
Tent映射在迭代过程中存在小周期(0.2,0.4,0.8,0.6),以及在不稳定周期点0.25,0.5,0.75将迭代到不动点0。为避免该现象的出现,对tent映射进行改进,改进后的tent映射为:
当z(t)=0,0.25,0.5,0.75,或z(t)=z(t-k),k=0,1,2,3,4时,z(t+1)=z(t)+0.01·rand(0,1)
Tent映射混沌序列生成的步骤如下:
步骤1初始化,随进生成n个[0,1]区间的随机数。
步骤2进行混沌变换。
根据混沌模型,进行混沌变换,生成n个混沌变量。
步骤3将混沌变量映射到变量区间。
将混沌序列映射到变量空间[xjmin,xjmax],得到初始种群中第i个体的第j个分量xij,xij=xjmin+(xjmax-xjmin)·zij。
2.2 粒子群优化算法
1) 算法描述
基本PSO算法的数学描述为:N维搜索空间中,种群位置为X={x1,x2,…,xn}T,第i个粒子位置为xi=(xi1,xi2,…,xin),速度为vi=(vi1,vi2,…,vin)。在迭代过程中,通过跟踪个体的最优位置和全局最优位置来更新个体的速度和位置,设pi为第i个粒子所经历的个体最优位置,pi=(pi1,pi2,…,piN),pg为全局最优位置,pg=(pg1,pg2,…,pgn)。
PSO算法的进化方程为:第t代粒子的第n维速度和位置由以下公式计算:
vin(t+1)=ωvin(t)+c1r1(pin(t)-xin(t))+
c2r2(pgn(t)-xin(t))
(5)
xin(t+1)=xin(t)+vin(t+1)
1≤i≤M,1≤n≤N
(6)
式中,vin(t)表示第i个粒子的第n维在第t次迭代中的位置和速度;ω为惯性权重,c1、c2为学习因子,r1、r2为[0,1]区间内的随机数;-vmax≤vin(t)≤vmax,vmax为预先设定的最大迭代步长。
对于目标分配问题,需要对粒子的位置和速度取整,使搜索在整数域中进行,对速度分量进行修订,如公式所示。
vin(t+1)=int[ωvin(t)+c1r1(pin(t)-xin(t))+
c2r2(pgn(t)-xin(t))]
(7)
xin(t+1)=xin(t)+vin(t+1)
1≤i≤M,1≤n≤N
(8)
2) 编码和解码
为保持种群多样性和个体均匀分布,采用Tent混沌映射初始化种群。首先利用Tent混沌映射生成混沌序列,然后将混沌序列映射到解空间,最后对所有解排序,将适应度较优的作为初始化种群的解。
根据要解决的问题的需要,对PSO算法中的粒子进行编码,并满足约束条件,采用实数编码方式进行编码。PSO粒子编码方案如图1所示。
图1 PSO算法编码方案
图1表示n类导弹打击m个目标的编码,Xij表示第i类导弹打击第j个目标的数量。每个目标对应一个基因段,每个基因段长度为n,则编码的长度为m×n。
3) 参数设计
取目标函数为适应度函数。
(9)
1) 惯性权重,
惯性权重取值大小影响算法的搜索能力,为了平衡全局搜索和局部搜索能力,设计自适应惯性权重。在算法早期采用较大的惯性权重,以保证较强的全局搜索能力;在算法后期采用较小的惯性权重,可以提高局部搜索精度。
根据全局最优值的变化情况自适应调整惯性权重,调整策略如下:
ω(t)=(1+e-k)-1
(10)
式中,ω(t)为第t次迭代时惯性权重,k为进化速度因子。
(11)
式中,fg(t)为第t代全局最优值的适应度。
2) 学习因子优化
对学习因子进行混沌处理,以提高算法的收敛速度。
Ci(t+1)=Cmin+(Cmax-Cmin)·zi(t+1)
(12)
式中,Ci(t)∈[1.4,2]。
4) 早熟处理
粒子群算法迭代后期,收敛速度降低,易于陷入局部最优,出现早熟现象,当出现早熟现象时,对粒子进行混沌优化,使其跳出局部最优,提高全局搜索能力。
设定一个计数器P,用于统计当前全局最优解连续出现的次数。给定一个阈值c,如果p=c则认为出现局部最优,陷入早熟。
当粒子群出现早熟现象时,采用Tent混沌映射对当前生成的粒子进行混沌优化,使其跳出局部最优值。
步骤1采用Tent混沌映射对当前全局最优值进行混沌变换;
步骤2计算混沌变换后适应度值,与当前全局最优解比较,取较优解作为当前全局最优解;
步骤3判断是否终止条件,如果满足则输出最优解,否则转到步骤1。
2.3 禁忌搜索策略
TS(Tabu Search) 算法是一种全局逐步寻优的亚启发式搜索算法,并得到了较好的发展[10]。TS算法通过设置禁忌表,避免对局部最优解的重复搜索,同时通过设置“特赦准则”,保持搜索过程的多样性。
禁忌搜索算法的基本过程如下:
步骤1设置禁忌表(tabu list)H=∅,并选定一个初始解X′;设置禁忌长度Tmax、终止条件、候选集Can_N(X′)等。
TS算法对初值依赖性较强,可以用PSO算法产生的性能优良的解作为TS算法的初值,有利于进行禁忌搜索,提高搜索速度;同时禁忌搜索到的解为PSO算法提供较好的粒子,提高全局搜索能力。
2.4 改进的混合粒子群优化(HPSO)算法流程
改进的混合PSO算法的基本思想是,以PSO算法为主体,通过混沌序列对粒子速度和位置进行初始化生成初始种群;设定自适应惯性权重,平衡全局搜索能力和局部搜索能力;采用混沌序列生成学习因子;通过对粒子的速度和位置优化获得寻优目的。在粒子进化过程中引入禁忌搜索策略,避免对粒子的重复访问,提高了搜索效率;通过早熟判断机制进行早熟判断,通过混沌优化使其跳出局部最优,提高算法的全局搜索能力。算法流程如图2所示。
算法基本步骤如下:
步骤1初始参数设置。规模、最大迭代次数、控制变量、禁忌长度、特赦条件。
步骤2种群初始化,采用混沌优化方法生成初始种群。
步骤3进行种群编码,设置禁忌表为空。
步骤4计算适应度值。
步骤5粒子寻优,根据粒子群的状态,确定粒子群的个体最优位置和全局最优位置,更新粒子的个体最优值和全局最优值。
步骤6判断是否满足终止条件,如果满足则进行解码、输出结果,否则继续进行迭代。
步骤7确定候选解,确定当前最优解为候选解,并将其加入禁忌表中,更新禁忌表,用当前的候选解替换最早进入禁忌表的解。
步骤8判断候选解是否满足特赦准则,如果满足,则将解禁解作为当前最优解,更新禁忌表和当前状态,转入步骤4;否则,执行下步操作。
步骤9判断候选解的禁忌属性,选择最佳解为当前解,更新禁忌表,转入步骤4。
步骤10判断是否满足终止条件,如果满足停止迭代,输出最优解;否则转到步骤4。
图2 算法流程
3 算例分析
3.1 算例设置
A国在XX岛部署了弹道导弹防御系统,包括早期预警卫星1部(D1),预警雷达1部(D2),指控中心1部(D3),拦截弹系统1套(D4),电子对抗装置一部(D5),共5个目标。
C国导弹作战集团主作战导弹型号为X型弹道导弹,辅助攻击导弹为A型和B型常规弹道导弹,A型导弹数为15,B型导弹数为10,作战策略为采用辅攻导弹进行第1波次攻击,对导弹防御系统进行打击,降低其对X型导弹的拦截能力。
通过专家打分法对导弹防御系统中作战主体的突防贡献度打分,经过归一化处理得到突防贡献度如表1所示。
表1 突防贡献度
导弹对目标的毁伤概率是指导弹突破敌方防御后成功毁伤目标概率,如表2所示。
表2 毁伤目标概率
仿真环境为:Windows7 64位操作系统,3.50 GHz处理器,8G内存,Matlab R2014a仿真平台。分别用粒子群优化算法(PSO)、混沌优化粒子群算法(CPSO)、禁忌搜索粒子群算法(TSPSO)及改进的混合粒子群优化算法(HPSO)进行仿真运算,均采用实数编码方式进行编码。主要参数设置为:各算法的种群规模为30,最大迭代次数为100;PSO算法中惯性权重为0.7,学习因子为1.49;TSPSO算法中禁忌表长度为5,特赦准则采用“best so far”准则解禁最优解,惯性权重为0.7,学习因子为1.49;HPSO算法初始惯性权重为0.7,初始学习因子为1.49,早熟判断阈值为3。
3.2 仿真结果分析
分别采用粒子群优化算法(PSO)、混沌优化粒子群算法(CPSO)、禁忌搜索粒子群算法(TSPSO)及改进的混合粒子群优化算法(HPSO)进行仿真运行100次,
分别采用4种算法进行仿真运行100次,得到适应度平均值,适应度变化曲线如图3所示。
图3 平均适应度值变化曲线
图3描述了分别采用四种算法进行问题求解是时适应度变化情况,通过仿真分析可知,与PSO算法、CPSO算法和TSPSO算法相比,HPSO算法收敛速度最快,可以较快的获得全局最优解,而且采用HPSO算法获得的全局最优解优于PSO算法、CPSO算法和TSPSO算法。
分别采用4种算法获得的最优导弹火力目标分配结果如表3~表6所示。
表3 混合粒子群算法得到的导弹-目标分配结果
表4 混沌优化粒子群算法得到的导弹-目标分配结果
表5 禁忌搜索粒子群算法得到的导弹-目标分配结果
表6 粒子群算法得到的导弹-目标分配结果
采用HPSO算法获得的导弹-目标分配方案对应的最优适应度值为0.903,即经过先期打击,后续突防导弹的突防效能可以达到0.903;采用CPSO算法获得的导弹-目标分配方案对应的最优适应度值为0.902,即经过先期打击,后续突防导弹的突防效能可以达到0.902;采用TSPSO获得的导弹-目标分配方案对应的最优适应度值为0.896,即经过先期打击,后续突防导弹的突防效能可以达到0.895。可知,采用HPSO算法获得的导弹目标分配方案适应度值最大,效果最好。
4 结论
1) 通过案例分析和仿真试验表明,改进的混合粒子群优化算法具有较好的收敛性,适用于求解导弹目标分配问题。
2) 本文未考虑火力打击动态过程中目标毁伤后对目标分配的影响,突防贡献度的赋值具有一定的主观性,下一步将对这方面的问题加强研究。