中国科技核心期刊      中国指挥与控制学会会刊     军事装备类重点期刊
指挥控制与仿真

指挥控制与仿真 >

2023 , Vol. 45 >Issue 1: 89 - 94

DOI: https://doi.org/10.3969/j.issn.1673-3819.2023.01.015

武器与信息系统

改进蛙跳算法求解武器目标分配问题

  • 喻世轶 1 ,
  • 张亮 2 ,
  • 周学广 1
展开
  • 1.海军工程大学, 湖北 武汉 430033
  • 2.中国人民解放军91642部队, 海南 三亚 572000

喻世轶(1991—),男,硕士研究生,讲师,研究方向为数据分析、仿真模型。

张 亮(1981—),男,工程师。

Copy editor: 张培培

收稿日期: 2022-08-19

  修回日期: 2022-09-25

  网络出版日期: 2023-02-20

收起

Improved leapfrog algorithm for weapon target assignment

  • YU Shi-yi 1 ,
  • ZHANG Liang 2 ,
  • ZHOU Xue-guang 1
Expand
  • 1. Naval University of Engineering, Wuhan 430033
  • 2. Unit 91642 of PLA, Sanya 572000, China

Received date: 2022-08-19

  Revised date: 2022-09-25

  Online published: 2023-02-20

Fold

摘要

针对武器目标分配问题,提出一种改进蛙跳算法来求解空间受限的武器目标分配。首先,基于武器目标分配原则建立多约束条件下武器目标分配模型,并将多目标优化问题转化为单目标优化问题;其次,采用基于非支配等级和拥挤度因子的精英选择策略改进初始种群的多样性和均匀度,提升算法最优解的质量;最后,通过合理的想定背景进行仿真计算,结果表明:该方法可有效平衡搜索时间和全局最优解质量,可作为编队防空作战时武器目标分配的一个不错选择,通过与SFLA算法和遗传算法进行比对分析,表明该算法相对SFLA算法求解的最优解质量高,相对遗传算法搜索效率高。

关键词： 武器目标分配; 蛙跳算法; 拥挤度; 非支配排序

本文引用格式

喻世轶 , 张亮 , 周学广 . 改进蛙跳算法求解武器目标分配问题[J]. 指挥控制与仿真, 2023 , 45(1) : 89 -94 . DOI: 10.3969/j.issn.1673-3819.2023.01.015

Abstract

Aiming at the problem of weapon target distribution, an improved leapfrog algorithm is proposed to solve space constrained weapon target assignment. Firstly, based on the principle of weapon target assignment, a weapon target assignment model under multiple constraints is established, and it transforms the multi-objective optimization problem into a single objective optimization problem. Secondly, elite selection strategy based on non-dominated level and crowding factor is adopted to improve the diversity and evenness of initial population and the quality of the optimal solution of the algorithm. Finally, the simulation calculation is carried out through a reasonable scenario background, the results show that this method can effectively balance the search time and the quality of global optimal solution. It can be used as a good choice for weapon target allocation in formation air defense operations, and compared with SFLA and GA, the results show that this algorithm has higher quality of optimal solution than SFLA and higher search efficiency than GA.

Key words： weapon-target assignment; leapfrog algorithm; crowding degree; Nondominant sort

武器目标分配(Weapon-target Assignment,WTA)是指依据作战目的、可使用武器的技战术性能、目标威胁等级等约束条件,结合战场态势信息,合理快速地分配武器资源,确定最佳武器目标分配方案,以实现最佳的协同作战效果或最佳的作战目的。武器-目标分配问题作为作战指挥决策过程中的一个关键环节,一直以来都受到研究人员的高度关注。如何快速高效地给出武器目标分配方案,对于缩短指挥员的决策时间,提升指挥决策效能具有重要意义。
武器-目标分配问题属于NP完全问题,求解WTA问题的计算量较大,随着决策变量的维度增加,计算量呈指数增长,因此,目前,国内外的学者通常采用智能优化算法进行求解,常用的有遗传算法[1]、粒子群算法[2]、匈牙利算法[3]、人工鱼群算法[4]、差分进化算法[5]等。其中,遗传算法因具有较强的全局搜索能力被广泛应用,并且针对其易早熟,搜索效率低,受参数影响较大的弱点,提出的改进算法也很多[6⇓⇓⇓-10]。本文针对遗传算法在求解武器目标分配时计算时间较长的问题,利用蛙跳算法的快速计算性能[11],借鉴基于非支配等级和拥挤度因子的精英选择策略[12],改善初始种群的多样性和均匀度,提高了算法搜索最优解的质量,同时,计算时间相对遗传算法较短。

1 受空间约束的武器目标分配模型

1.1 问题描述及分配原则

假设我水面舰艇编队通过预警侦察体系发现有n批来袭空中目标,水面舰艇有m种不同型号的防空武器可供使用,在作战过程中的某一时刻,每类武器系统可使用的武器资源为ci(i=1,2,…,m),第i种防空武器对第j类目标的命中概率为pij(i=1,2,…,m,j=1,2,…,n)。
水面舰艇编队防空作战的武器目标分配原则如下:
1)每类武器可以对多个目标进行分配,同时每个目标可以被分配多个武器系统;
2)每种型号的防空武器在作战时间内分配的武器资源不能超过该防空武器系统的武器资源总数;
3)为确保不遗漏任何目标,每个目标至少被分配一个型号的武器;
4)根据防空武器使用的一般原则——避免资源浪费,每一类型的防空武器对同一个目标分配的最大武器资源数为3,且每个目标被分配的武器资源总数也不超过3;
5)由于每类防空武器都有射击条件,最简单的就是空间约束,因此,不能保证每类防空武器都能对每个来袭目标进行拦截;
6)分配的目标是为了获取最大作战效能,即毁伤目标的数学期望最大,同时消耗武器的成本最小。

1.2 武器目标分配模型

假设编队内有m种不同型号的防空武器,每种防空武器的资源总数为ci(i=1,2,…,m),每种防空武器的成本为ei(i=1,2,…,m),来袭空中目标为n批,目标的威胁度系数为dj(j=1,2,…,n),第i种防空武器对第j类目标的毁伤概率为pij(i=1,2,…,m,j=1,2,…,n),则武器目标分配的决策方案为
X = x 11 x 12 … x 1 n x 21 x 22 … x 2 n ︙ ︙ ⋱ ︙ x m l x m 2 … x m n
其中,xij(i=1,2,…,m,j=1,2,…,n)表示第i类武器对第j类目标分配的武器资源数,当xij>0时,表示第i类武器对第j类目标分配xij个武器资源,反之表示不分配武器资源。
另外,根据分配原则5),不是每类武器都能对所有目标进行拦截,假设分配禁忌决策为
Y = y 11 y 12 … y 1 n y 21 y 22 … y 2 n ︙ ︙ ⋱ ︙ y m 1 y m 2 … y m n
其中,yij(i=1,2,…,m,j=1,2,…,n)表示为第i类武器对第j类目标是否能分配武器的判断变量,当yij=1时表示第i类武器对第j类目标可分配武器,反之则表示不能分配,用来作为生成初始决策种群的约束条件。
根据分配原则6)可建立防空武器目标分配模型如式(3)所示:
max f1(x)= ∑ j = 1 ndj 1 - ∏ i = 1 m ( 1 - p i j ) x i jmin f2(x)= ∑ i = 1 mei ∑ j = 1 nxijs.t. ∑ i = 1 m x i j ≥ 1 ∑ i = 1 m x i j ≤ 3 ∑ j = 1 n x i j ≤ c i x i j ≤ 3 ∑ j = 1 n d j = 1 ( d j > 0 )
式(3)是一个多目标优化问题,为利于算法求解,通常将多目标转化为单目标进行求解,因此,本文将实现最大的防空作战效果和最小的武器消耗成本两个目标变为一个目标,即求解单位成本内取得的最大防空作战效果,则该模型变为
max f(x)= f 1 ( x ) f 2 ( x )= ∑ j = 1 n d j 1 - ∏ i = 1 l ( 1 - p i j ) x i j ∑ i = 1 l e i ∑ j = 1 n x i j
s.t. ∑ i = 1 l x i j ≥ 1 ∑ i = 1 l x i j ≤ 3 ∑ j = 1 n x i j ≤ c i x i j ≤ 3 ∑ j = 1 n d j = 1 ( d j > 0 )

2 蛙跳算法原理

蛙跳算法是2003年提出的一种仿生学智能优化算法[13],适用于组合优化问题,参数少,计算速度快,具有全局寻优的特点。其主要思想:假设湿地有一群青蛙,可通过在湿地中不同的石头上跳跃来寻找食物。每只青蛙代表组合优化问题的一个解,且有自己的文化,个体之间通过文化来交换信息。初始时,将青蛙分成若干个子群,在子群中每个个体之间通过文化相互影响,随着子群的不断进化,实现局部搜索。当子群进化到一定阶段后,各子群之间再进行文化信息交换,实现全局搜索。重复上述过程,直到满足停止条件。
其算法模型可描述为:首先随机产生规模为N(维数为l)的初始种群P={X1,X2,…,XN},其中Xi=[xi1,xi2,…xil]表示问题的一个解。再根据目标函数计算每个解对应的适应度值,并进行降序排序。然后将初始种群分为m个子群,每个子群中有n个青蛙,即N=m×n,具体的分配方法:总群中第1只青蛙分配给第1个子群,第2只分配给第2个子群,直到第m只分配给第m个子群,第m+1只青蛙分配给第1个子群,依次类推,直到全部分配完毕。将每个子群中青蛙的最优适应度值和最差适应度值个体记为Xb、Xw,其相应的适应度值记为vb、vw,然后,在每个子群中按照式(4)进行局部搜索:
d = r a n d ( ) · ( X b - X w )   ( | d m i n | ≤ d ≤ | d m a x | ) X w n e w = X w + d
式中,rand()表示0~1之间的随机数,d为子群中最差解更新的步长,dmax、dmin为步长的最大值和最小值, X w n e w为更新后的青蛙,如果更新后的青蛙 X w n e w的适应度值优于Xw,则替换原来的Xw。反之,则用总群的最优适应度值青蛙Xg替换子群中最优的青蛙Xb代入式(5)进行局部搜索,如果得到的新解仍然不能满足要求,则随机产生一个新的青蛙替代原来的青蛙Xw。重复上述过程iN次,即完成局部搜索,所有子群完成局部搜索以后,将所有子群中的青蛙重新混合,再按适应度值重新排序、分组、局部搜索,直到满足停止条件,得到的解即为相对最优解。

3 基于非支配等级和拥挤度因子优选的改进蛙跳算法求解武器目标分配问题

本文针对传统蛙跳算法(SFLA)全局寻优质量不高的问题进行改进,在兼顾计算时间的前提下,通过基于非支配等级和拥挤度因子的精英选择策略改进初始种群的生成,提高初始种群的多样性和均匀性,以期在有限的迭代次数中获得相对较优的最优解。

3.1 解的编码

在基于改进的蛙跳算法求解武器目标分配问题中,需要对决策变量进行变换,将多维矩阵决策变量变为一维矩阵,即X=[x11,x12,…,x1n,x21,x22,…,x2n,…,xm1,xm2,…,xmn],有利于蛙跳算法的更新计算。

3.2 初始解的生成

蛙跳算法(SFLA)的初始解通常是随机生成的,其多样性和均匀性不可控,借鉴文献[13]的思想,对初始解进行预处理,假设算法中参与迭代计算的种群规模为N,则先随机生成数倍于N的种群规模,设为mul*N。
首先,根据帕累托支配关系给初始种群进行非支配关系排序,并给每个解赋予一个非支配关系等级,假设某个个体不被其他任何个体支配,则该个体的非支配等级为1,将种群中所有非支配等级为1的个体挑选出来,剩下的个体再进行一次非支配关系排序,挑选出来的非支配个体等级为2,依次类推,直到所有的个体都被赋予非支配等级,其流程图如图1所示。
图1 非支配等级排序

Fig.1 Non dominated ranking

其次,同一非支配等级集合中进行拥挤度因子计算,给每个决策向量Xi添加一个拥挤度因子变量flog_crowi,将所有个体分别根据每个目标函数fj(x)的函数值fi(x)_value进行升序排列,找到对应的最大值fj(x)_value_max和最小值fj(x)_value_min,并将最大值和最小值对应的个体的拥挤度因子设为无穷大inf,其余个体的拥挤度因子按照公式flog_crowij=(fj(xk+1)_value-fj(xk-1)_value)/(fj(x)_value_max-fj(x)_value_min)进行计算,然后进行累加,得到每个个体的拥挤度因子flog_crowi= ∑ j = 1 nflog_crowij,其算法流程如图2所示。
图2 拥挤度因子算法流程

Fig.2 The algorithm flow of congestion factor

最后,按照精英选择策略从mul*N个个体中挑选N个作为参与迭代计算的初始种群,具体算法思想是:根据个体的两个属性值——非支配等级pareto_rank和拥挤度因子flog_crowi,所有个体按照非支配等级由低到高的顺序进行排序,从支配等级低的个体开始,依次将非支配等级对应的全体变量放入初始种群Pt,直到当某一非支配等级pareto_ranki对应的个体大小超出了种群N为止,然后对非支配等级为pareto_ranki的个体集合Ci按照拥挤度因子由大到小的顺序排序,拥挤度因子大的优先选入Pt,直到Pt的个体数量达到N为止。通过此种方法生成的初始种群相对随机生成种群具有较好的多样性和均匀度。

3.3 更新策略

搜索策略采用传统蛙跳算法(SFLA)的更新策略,基于非支配等级和拥挤度因子的精英选择策略改进蛙跳算法求解武器目标分配问题的算法流程如图3所示。
图3 基于改进蛙跳算法的武器目标分配流程图

Fig.3 The flow chart of weapon targe allocation based on leapfrog algorithm

4 仿真计算及结果分析

假设有5批从不同方位来袭的目标,水面舰艇编队有4型防空武器系统,每种武器拥有的资源总数和毁伤概率如表1所示(其中,有相同型号的武器系统和相同型号的来袭目标)。
表1 武器系统基本参数

Tab.1 Basic parameters of weapon system

武器平
台编号		 武器资
源数量		 目标编号(毁伤概率)
1 2 3 4 5
1 15 0.80 0.75 0.82 0.69 0.75
2 10 0.75 0.70 0.77 0.64 0.70
3 12 0.80 0.75 0.82 0.69 0.75
4 8 0.82 0.77 0.84 0.71 0.77
每个目标的威胁等级系数分别为{0.204 9,0.225 6,0.181 1,0.196 9,0.190 7},4型武器系统的价值分别为{1.2,1.0,1.2,0.6}。每型武器受射界的限制,其分配禁忌决策如表2所示,该决策可作为生成初始决策种群的约束条件。
表2 武器分配禁忌表

Tab.2 Taboo list of weapon distribution

武器 目标
1 2 3 4 5
1 1 1 1 1 1
2 1 1 1 0 1
3 1 1 1 1 1
4 0 0 1 0 1
在内存8 G,处理器为Intel(R) Core(TM)i5-5700 CPU @3.40GHz,64位操作系统的计算机上通过Matlab对算法进行实现,取参数为初始种群个数50,子群数5,子群个体10,子群迭代次数5,总群迭代次数50,计算的最优目标值为0.144 8,对应的最优决策变量为
X= 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1
其最优适应度值变化曲线如图4所示。
图4 最佳适应度值的变化曲线

Fig.4 Change curve of optimal fitness value

本文将该算法与传统蛙跳算法、遗传算法进行多次运算比对分析,每种算法都运行10次,运行结果如表3所示。
表3 各种算法的性能对比

Tab.3 Performance comparision of various algorithms

序号 传统蛙跳算法 改进蛙跳算法 遗传算法
运行时间 最优适应度 运行时间 最优适应度 运行时间 最优适应度
1 6.146 4 0.136 3 19.999 3 0.121 3 25.303 4 0.152 7
2 3.12 0.099 3 14.258 5 0.111 7 50.575 5 0.169 6
3 3.198 0.109 2 14.398 9 0.110 1 48.906 3 0.148 7
4 3.446 7 0.098 3 16.317 7 0.140 8 59.810 8 0.196 9
5 4.446 0.094 6 15.818 5 0.112 8 49.779 9 0.164 5
6 4.570 8 0.104 4 16.052 5 0.124 1 52.556 7 0.169 6
7 11.871 7 0.108 9 17.284 9 0.116 3 52.395 1 0.16
8 2.854 8 0.104 6 16.130 5 0.11 45.006 3 0.169 6
9 3.744 0.104 6 17.456 5 0.116 30.872 6 0.146 8
10 3.931 2 0.107 7 14.742 1 0.126 8 28.657 4 0.137 1
均值 4.732 96 0.106 79 16.245 94 0.118 99 44.386 4 0.161 55
由表3可以看出,改进蛙跳算法相对传统蛙跳算法其寻优时间变长,但最优适应度值明显变优,且时间的增加幅度不大;改进蛙跳算法相对传统遗传算法的最优适应度值较小,但其寻优时间相对遗传算法要减少很多。而水面舰艇编队防空作战时,对时效性要求较高,改进后的蛙跳算法在时间增加相对较少的前提下,使最优度值有了较大的改善,是解决编队防空作战时武器目标分配问题的一个不错的选择。

5 结束语

本文针对空间受限的水面舰艇编队防空武器目标分配问题,提出一种基于拥挤度因子和非支配排序的改进蛙跳算法,大大改善了初始种群的多样性和均匀度,相对传统蛙跳算法提高了最优解的质量,相对传统遗传算法大大减少了寻优时间,对于防空作战这种实时性要求很高的武器目标分配来说是一个不错的选择。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
BAYRAK A E, POLAT F. Employment of an evolutionary heuristic to solve the target allocation problem efficiently[J]. Information Sciences, 2013(222): 675-695.

[2]
梅海涛, 华继学, 王毅, 等. 基于IF-HPSO算法的防空作战WTA问题研究[J]. 计算机科学, 2017, 44(5): 263-267.

DOI

MEI H T, HUA J X, WANG Y, et al. Optimization study on weapon-target assignment problem in air-defense operation based on intuitionistic fuzzy hybrid particle swarm optimization[J]. Computer Science, 2017, 44(5): 263-267.

[3]
马原野. 武器-目标分配关键技术及仿真[D]. 西安: 西安电子科技大学, 2019.

MA Y Y. Key technology and simulation of weapon-target assignment[D]. Xi’an: Xidian University, 2019.

[4]
邵诗佳. 基于智能算法的武器目标分配问题研究[D]. 哈尔滨: 哈尔滨工程大学, 2019.

SHAO S J. Research on weapon target assignment based on intelligent algorithm[D]. Harbin: Harbin Engineering University, 2019.

[5]
WU X C, CHEN C, DING S X. A modified MOEA/D algorithm for solving Bi-objective multi-stage weapon-target assignment problem[J]. IEEE Access, 2021(9): 71832-71848.

[6]
LEE Z J, LEE W L. A hybrid search algorithm of ant colony optimization and genetic algorithm applied to weapon-target assignment problems[M]. Intelligent Data Engineering and Automated Learning. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003: 278-285.

[7]
杨进帅, 李进, 王毅, 等. 改进遗传算法求解防空作战WTA问题[J]. 空军工程大学学报(自然科学版), 2017, 18(4): 93-98.

YANG J S, LI J, WANG Y, et al. Extraction of weapon-target assignment in air defense with improved genetic algorithm[J]. Journal of Air Force Engineering University(Natural Science Edition), 2017, 18(4): 93-98.

[8]
李强. 多导弹协同作战目标分配和制导律研究[D]. 哈尔滨: 哈尔滨工业大学, 2017.

LI Q. Research on target assignment and guidance law for cooperative engagement of multi-missile[D]. Harbin: Harbin Institute of Technology, 2017.

[9]
向勇. 联合火力打击中目标分配问题优化模型及算法研究[D]. 西安: 西安电子科技大学, 2018.

XIANG Y. Modeling and algorithm for joint target assignment problem in fire strike[D]. Xi’an: Xidian University, 2018.

[10]
谢永杰. 多平台防空导弹任务分配及协同制导方法研究[D]. 哈尔滨: 哈尔滨工业大学, 2019.

XIE Y J. Research on task assignment and cooperative guidance method of multi-platform air defense missile[D]. Harbin: Harbin Institute of Technology, 2019.

[11]
张凯, 周德云, 潘潜. 基于混合蛙跳算法的协同空战火力分配[J]. 计算机工程与应用, 2014, 50(17): 263-266.

ZHANG K, ZHOU D Y, PAN Q. Weapon-target assignment based on shuffled frog leaping algorithm in cooperative air combat[J]. Computer Engineering and Applications, 2014, 50(17): 263-266.

[12]
聂俊峰, 陈行军, 苏琦. 基于NSGA-Ⅲ算法的集群目标来袭火力分配建模与优化[J]. 兵工学报, 2021, 42(8): 1771-1779.

DOI

NIE J F, CHEN X J, SU Q. Modeling and optimization of weapon-target assignment for group targets defense based on NSGA-Ⅲ algorithm[J]. Acta Armamentarii, 2021, 42(8): 1771-1779.

DOI

[13]
EUSUFF M M, LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Journal of Water Resources Planning and Management, 2003, 129(3): 210-225.

DOI

Options
文章导航

/

〈 〉