苏 山，马泽远，张 立，周梦平，刘昊东
(上海机电工程研究所，上海 201109)
随着进攻导弹技术的不断发展,单一拦截弹防空模式已经无法满足现代作战需求[1-3],因此多拦截器技术(multiple kill vehicle,MKV)应运而生。通常多拦截器技术是指通过一次导弹发射,释放出多个拦截器,同时摧毁多个来袭威胁目标的技术,以增加对来袭导弹的拦截概率并提高拦截效率。在多拦截器技术众多分支中,目标分配技术极为重要,受到研究者的普遍重视。
针对武器目标分配问题(weapon target allocation,WTA),Shi等[4]引入一种大规模稀疏问题的进化算法(SparseEA),解决了特定问题初始化方法,带有奖励策略的遗传算子能够考虑变量的稀疏性高效生成解的问题,并提出了一种改进的非支配解选择方法来处理约束。Fu等[5]提出了一种变概率赋值技术,用概率分配方式代替随机均匀分配方式对遗传算法变量进行初始化,生成接近最优个体的初始种群个体,表现出了比传统初始化方法更优的计算结果。Wang等[6]设计了一种基于遗传算法的变值控制方法,以克服智能算法在解决WTA时由于问题规模过大或无法获得可行解而导致求解速度过慢的缺点。Zhang等[7]开发一种基于差分进化的粒子群优化算法求解器以求解多任务优化问题,展示出了比传统算法更优的计算效果。吴诗辉等[8]以分配方案末速度差之和最大为优化目标,以给定均匀分配度为约束条件,将其转化为带约束的非平衡任务分配问题,并用线性规划方法进行求解。目前,针对WTA问题的研究方向依然主要集中在传统智能启发式优化算法的改进上,通常通过融合不同的启发式算法,或加入更优的初始化策略以提高算法的计算效率以及其他性能。在相似领域中,Zammit等[9]针对3维无人机路径规划问题,比较了A*算法与快速探索(RRT)随机树算法,开发了一组变体来减轻标准算法中固有的缺点,通过相同场景下的计算发现改进后的A*算法性能更优。Chen等[10]通过引入人工势场法与A*算法进行结合,极大的改进了A*算法的计算速度,并有效缩短了所规划的路径长度。Li等[11]提出了一种基于高斯分布信息素挥发的蚁群算法来解决复杂环境下的机器人避障及路径规划问题,实现了更高效的避障效果。Alnowibet等[12]针对多约束优化问题提出了一种混合梯度模拟退火算法,在效率、质量、鲁棒性上都得到了一定程度的提升。
文中以防空拦截器为研究对象,开展基于改进粒子群优化的多拦截器目标分配方法研究。首先建立多拦截器目标分配数学模型,将目标分配问题转化为离散优化问题;然后针对传统离散粒子群算法(DPSO)计算效率不足的问题,引入改进粒子群优化算法,进行编解码策略和分配算法的设计,并以一种包含三种邻域结构的变邻域搜索算法,分别解决了传统粒子群算法求解离散优化和局部收敛的问题;接着设计了局部跳出策略的启动准则,以平衡算法的算力开销,提高算法适应性;最后在数值仿真中设计了三种不同的工况,验证了所设计的改进粒子群优化算法有效性。
文中目标分配问题建立在如下的条件或假设上:
1)进攻飞行器以及拦截器实时位置速度矢量均已知;
2)每枚拦截器最多分配给1枚进攻飞行器。
文中主要对收益适应度函数进行建模,用以表征分配效能。收益包含进攻飞行器对拦截方设施威胁程度、拦截成功概率等指标。威胁程度可以用威胁距离、进攻飞行器飞行速度以及打击目标的重要程度等来衡量。文中将进攻飞行器Ej威胁程度适应度函数Fr,j定义为:
Fr,j=τ1exp(Rt+(1-sgn(Rt))r+
τ2(1-exp(-v))+τ3Fr3)
(1)
根据文献[13],拦截器Pi对进攻飞行器Ej的拦截概率估计模型函数表示为:
(2)
当采用M枚拦截器(Pi,i=1,2,…,M)对N个进攻飞行器(Ej,j=1,2,…,N)进行拦截时,为保证最佳的整体拦截效果,指定所有拦截器都需要分配到进攻飞行器,而每枚拦截器至多分配给一个进攻飞行器。设计所有分配到的拦截器对进攻飞行器Ej的拦截成功率定义为:
(3)
式中,Λij表示分配矩阵Λ中的元素,并且
(4)
设计目标分配总收益适应度为总的进攻飞行器威胁程度与拦截概率的组合,记为:
(5)
下面首先介绍粒子编码解码策略,解决传统粒子群算法无法解决离散优化的问题;然后引入改进粒子群优化算法,利用变邻域搜索算法(VNS)邻域结构变换的特点,解决粒子群优化算法容易陷入局部最优问题,并在算法中引入了跳出准则以平衡变邻域搜索算力消耗问题。
2.1 粒子编码解码策略
对于最优目标分配问题,其求解类似于整数规划问题,而粒子群优化算法的更新是一个连续变化的过程,难以避免出现非整数的解。因此对于连续变化的粒子需要通过合适策略进行编解码才能匹配问题的解。
由前面分析可知,每一Λ矩阵都代表一个分配结果,其具体含义为:矩阵行代表同一个拦截器编号,列代表同一个目标飞行器编号。矩阵中元素Λij=0代表拦截器i不分配给目标j,Λij=1则反之。由于同一枚拦截器最多只能分配给一个目标,因此可以很容易得知,应满足约束矩阵无穷范数应当小于或等于1,即
(6)
因此该优化问题可表示为:
(7)
式中F*表示最优适应度函数。
文中以粒子分配矩阵Λ作为粒子的位置,欲得到满足要求的分配矩阵,则需要对连续变化的粒子位置进行解码。
首先,可以明确得知每一种分配结果的适应度值以及分配约束;其次,最优分配对应的分配矩阵元素值为1,而其他值为0。基于上述条件,给出以下引理。
根据上述引理,文中设计粒子Λ位置初值满足Λij∈[0,1],那么根据适应度函数式(5)进行迭代的粒子群优化算法能够收敛到极值点,且满足式(7)。以下给出证明过程。
证明:考虑适应度函数式(5)与式(3),则
(8)
(9)
对式(9)取极大值可得:
(10)
由定义可知粒子矩阵Λ仅在列上有约束,而各行取值完全独立,则有
(11)
当设计此任务分配问题的适应度函数为式(8)的形式时,运行粒子群优化算法,粒子的位置会自发向整数解上收敛。因此,粒子充分收敛后的位置可以满足式(7)约束,即为该离散优化问题的解。
2.2 引入VNS算法改进策略
PSO算法执行过程中,容易陷入局部收敛,从而导致最终收敛到的非全局最优解。下面设计基于变邻域搜索(VNS)算法的局部跳出策略,从而保证算法能够有效跳出局部极值进而找到全局最优解。
VNS算法的核心思想是利用不同的邻域结构进行交替搜索,从而跳出原来的解,扩展算法搜索范围。而对于文中给出的粒子形式,其邻域结构意义十分明确。首先对于一个矩阵有行变换和列变化两种基本的变换方式,而由粒子矩阵Λ定义可知,不同的行和列分别表示不同的拦截器和不同的目标飞行器。于是行变换和列变化均能够在不破坏原粒子离散特性的基础上,改变当前分配策略并形成新的分配,进而找到全局最优解。
由上述定义可以得知,Λ矩阵行变换和列变换均能改变当前的分配策略,跳出局部解并扩大搜索范围。于是在文中定义如下三种邻域结构。
1)第一邻域结构(交换邻域,swaped nerghborhood):选取Λ矩阵中第i行与第j行进行交换,且i=random{1,2,…,M},j=random{1,2,…,M},i≠j;同时选取第k列与第l列进列交换,且k=random{1,2,…,N},l=random{1,2,…,N},k≠l。
2)第二邻域结构(转置邻域,inverted neighborhood):在Λ矩阵中任选第i行,并将该行元素进行对称转置,且i=random {1,2,…,M},Λij=Λi(N-j+1),j∈{1,2,…,N},其余部分保持不变。
3)第三邻域结构(置换邻域,exchanged neighborhood)向量,随机生成一个满足粒子约束的行向量,并将该行向量替换Λ矩阵中任意第i行,i=random{1,2,…,M},组成新的Λ矩阵。
根据以上三种邻域结构,设计对应邻域抖动算法。算法设计思路为:针对每一种邻域结构,设定搜索次数K,在每次搜索中,执行相应变邻域操作,并将操作前后适应度值进行比较,记录更优解。
得到上述三种邻域抖动算法之后,设计变邻域搜索算法,将这三种邻域操作包括进来,形成完整的变邻域搜索策略。由于任何一种邻域结构的成功改变均能够改变原先分配策略,因此设计当邻域结构改变能够使得适应度函数值增加时,应当针对改变后的分配矩阵从第一邻域结构重新开始新一轮搜索。包含三种邻域结构的变邻域算法流程如图1所示。
图1 VNS算法框架示意图Fig.1 VNS algorithm Framework
由上面的分析可以看出,对于一个陷入局部收敛的PSO算法,将一个分配矩阵当作PSO算法中的一个粒子,通过进行上述的操作邻域就能够实现收敛局部的广度搜索,进而增加求得全局最优解的可能性。
当进行粒子群算法求解时,粒子位置会自发收敛到一个非0即1的整数序列,此时适应度值将保持不变,粒子群算法可以看作进入了局部收敛,且此时进入变邻域搜索不会破坏粒子收敛性。因此文中以粒子的适应度函数值变化情况作为粒子是否进入局部收敛状态的判断,并以此作为变邻域搜索的启动准则,增加了变邻域算法的自适应性。同时由于局部跳出策略计算量大,为了平衡计算开销,设计一定的跳出间隔,当第一次跳出后,经过指定的迭代次数,并且满足粒子适应度不发生变化时(局部收敛)进行跳出算法的执行。
于是,一种结合变邻域搜索的粒子群优化算法的流程图如图2所示。算法划分为粒子群优化以及变邻域搜索两大部分,二者通过变邻域算法启动准则连接。当达到启动准则后,则对粒子加入变邻域的操作,使得粒子跳出局部收敛。
图2 改进粒子群算法流程图Fig.2 Flow chart of improved particle swarm optimization
针对提出的改进粒子群优化算法分别设置三组仿真工况:
1)对比贪婪算法(greedy algorithm,GA)、传统粒子群算法(particle swarm optimization,PSO,采用文中的编解码策略)、离散粒子群(discrete particle swarm optimization,DPSO)算法及遍历算法(traversal algorithm,TA),验证改进粒子群优化算法(improved particle swarm optimization,IPSO)优越性。
2)通过调整系数验证启动准则的有效性。
3)场景变化时的目标分配算法。
设置仿真场景:
1)10枚拦截器参数见表1,包括位置坐标、速度、攻击距离及最大探测距离。
表1 拦截器参数Table 1 Interceptor parameters
2)8枚进攻飞行器参数见表2,包括位置坐标、速度及重要程度。
表2 目标飞行器参数Table 2 Target vehicle parameters
3.1 仿真试验1
使用文中设计的改进粒子群优化算法与传统粒子群优化算法、DPSO算法及贪心算法进行比较,分配结果的适应度函数变化如图3所示。
图3 算法收敛曲线比较Fig.3 Algorithm convergence curve comparison
图3展示了分别采用文中给出的改进粒子群优化算法、传统粒子群算法、DPSO算法和贪婪算法针对给出的仿真场景进行分配仿真的计算结果。横坐标表示迭代的代数,纵坐标表示全局最优适应度函数。红线表示改进粒子群优化算法的最优适应度变化曲线,蓝色虚线表示传统粒子群算法的最优适应度变化曲线,“x”型点为进行变邻域搜索的代数,黑色虚线表示贪婪算法适应度变化曲线,蓝色实线表示DPSO算法收敛曲线。比较传统粒子群算法曲线可以得知,在粒子群优化算法还未收敛时,两算法的收敛曲线大致保持一致;粒子开始收敛时,二者出现明显不同,可以看出,在传统粒子群优化算法迭代到第30代左右时,粒子已经陷入了收敛状态,此后变一直保持局部收敛的状态。而对比改进粒子群优化算法,在第30代之后,当满足进入变邻域局部搜索的条件时(图中“x”型点),算法便会进行一次变邻域搜索,找到一个新的更优的解,从而让粒子群算法跳出局部最优的状态,并向全局最优进行收敛。对比离散粒子群优化算法(DPSO),由于此离散算法在粒子空间中无收敛的概念,精细搜索(局部搜索)能力较差,表现为适应度收敛速度慢且很难找到全局最优解。由贪心算法的适应度变化曲线可以看出,在迭代10次时,其实算法已经计算完成,并且收敛到了一个较差的结果。
由表3目标分配结果可以看出,采用几种算法最终收敛结果都能使得目标分配矩阵元素收敛到0或1,并且满足一枚拦截器最多分配给一个目标的约束;由于仿真场景中拦截器数量多于进攻目标的数量,因此可以看出有些目标被分配给多于一枚的拦截器,符合实际情况。同时,对比三种分配算法的分配结果也可以看出,使用改进粒子群优化算法的最优适应度值更大,更接近遍历算法得到的全局最优值。
表3 目标分配结果Table 3 Target assignment result
3.2 仿真试验2
验证改进粒子群优化算法中局部跳出算法启动准则的合理性。试验次数为5,试验结果记录如表4所示。
表4 跳出准则合理性试验结果Table 4 Out of the criterion rationality test results
表5 新增进攻飞行器参数Table 5 Adding parameters of attacking aircraft
由上面试验结果可以看出,随着间隔代数的增加,算法执行所花费的时间就越多,当间隔代数设置为7时,算法平均收敛时间为0.168 9 s;同时,间隔代数增加也意味着算法计算结果更好,综合时间开销与计算结果准确性的平衡,可以取间隔代数为15。
3.3 仿真试验3
设置一个额外的进攻飞行器,模拟一个在目标分配算法运行途中突然发现新的目标需要进行计算的场景。原场景与上面仿真场景相同,在算法迭代次数为75时,发现了一个新的目标,则此时的目标分配场景变为10枚拦截器分配给9枚进攻飞行器的场景。
仿真结果如图6所示。图中对比了算法执行途中加入新进攻飞行器与不加新进攻飞行器的最优适应度。其中红色实线代表原改进粒子群优化算法的适应度变化曲线,蓝色虚线代表新增进攻飞行器的改进粒子群优化算法的最优适应度变化曲线。由图中曲线可以看出,在迭代次数为75之前,两次仿真变化趋势基本一致并且收敛到同一个最优适应度;迭代次数为75时,由于新增了一架进攻飞行器,目标分配算法将基于之前的计算结果进行粒子元素扩充,在改进粒子群优化算法的作用下,适应度值快速增加,对应的目标分配结果也产生了变化,结果如图4所示。由图4曲线可以看出,中途出现任务变化时,算法可以在利用原计算结果的基础上继续进行计算,不用重新设定场景重新计算,节省了大量的算力。
图4 试验3最优适应度变化曲线Fig.4 Experiment 3 optimal fitness curve
文中主要针对多飞行器拦截过程中的目标分配问题进行了算法设计和仿真分析,通过设计一种改进粒子群优化算法解决了一般离散粒子群优化算法容易陷入局部收敛的问题,同时通过设计适应度函数模型确保连续收敛的算法最终能够收敛到离散的点,并满足目标分配的约束条件。经过仿真分析证明文中设计的改进粒子群优化算法能够收敛到满足分配约束的粒子位置,且相对传统算法分配效能提高了9.4%,收敛结果与全局最优偏差不超过0.1%。
考虑到文中算法中,变邻域搜索接入方式为在PSO算法收敛后间隔指定代数串行参与计算,导致算法计算效率相较PSO算法有所降低。未来研究可考虑变邻域算法的并行同步计算,进一步提高算法效率。
猜你喜欢 拦截器邻域适应度 改进的自适应复制、交叉和突变遗传算法计算机仿真(2022年8期)2022-09-28多动能拦截器协同制导规律的研究及仿真制导与引信(2022年2期)2022-07-22英国MARSS公司推出新型反无人机拦截器无人机(2022年2期)2022-05-20以色列“天锁”公司展出新式反无人机拦截器轻兵器(2022年5期)2022-05-19稀疏图平方图的染色数上界吉林大学学报（理学版）(2020年3期)2020-05-29基于邻域竞赛的多目标优化算法自动化学报(2018年7期)2018-08-20关于-型邻域空间周口师范学院学报(2016年5期)2016-10-17基于空调导风板成型工艺的Kriging模型适应度研究中国塑料(2016年11期)2016-04-16基于时序扩展的邻域保持嵌入算法及其在故障检测中的应用华东理工大学学报(自然科学版)(2014年2期)2014-02-27少数民族大学生文化适应度调查教育与职业(2014年16期)2014-01-19