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

指挥控制与仿真 >

2022 , Vol. 44 >Issue 3: 20 - 24

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

理论研究

基于不完全信息博弈的动态武器目标分配

  • 姜广胜 1, 2 ,
  • 史宪铭 1 ,
  • 陈静 2 ,
  • 赵美 1 ,
  • 刘昊邦 1
展开
  • 1.陆军工程大学石家庄校区,河北 石家庄 050000
  • 2.陆军步兵学院石家庄校区,河北 石家庄 050083

作者简介:姜广胜(1987—),男,硕士,讲师,研究方向为装备技术。

史宪铭(1975—),男,博士,副教授。

Copy editor: 许韦韦

收稿日期: 2021-12-29

  修回日期: 2022-02-24

  网络出版日期: 2022-06-17

收起

Dynamic Weapon Target Assignment Based on Incomplete Information Game

  • JIANG Guang-sheng 1, 2 ,
  • SHI Xian-ming 1 ,
  • CHEN Jing 2 ,
  • ZHAO Mei 1 ,
  • LIU Hao-bang 1
Expand
  • 1. Shijiazhuang Campus,AEU, Shijiazhuang 050000
  • 2. Shijiazhuang Campus,Army Infantry College of PLA, Shijiazhuang 050083, China

Received date: 2021-12-29

  Revised date: 2022-02-24

  Online published: 2022-06-17

Fold

摘要

考虑合成分队作战存在不确定性和动态性的特征,基于博弈论构建不完全信息下的动态武器目标分配模型,建立攻防支付矩阵,利用遗传算法求解不完全信息条件下的纳什均衡,最后通过案例分析和软件仿真证明了模型和算法的可行性,通过博弈论与遗传算法相结合的方式能够快速获得最优的武器目标分配方案,有效提高实际作战能力。

关键词： 动态武器目标分配; 博弈; 不完全信息; 纳什均衡; 遗传算法

本文引用格式

姜广胜 , 史宪铭 , 陈静 , 赵美 , 刘昊邦 . 基于不完全信息博弈的动态武器目标分配[J]. 指挥控制与仿真, 2022 , 44(3) : 20 -24 . DOI: 10.3969/j.issn.1673-3819.2022.03.004

Abstract

Considering the uncertain and dynamic characteristics of synthetic detachment operations, based on the game theory, a dynamic weapon target assignment model under incomplete information is built, and an offensive and defensive payment matrix is established. The Nash equilibrium under incomplete information is solved by genetic algorithm. Finally, the feasibility of the model and algorithm is proved by case analysis and software simulation. The optimal weapon target assignment scheme can be quickly obtained by combining game theory with genetic algorithm, which effectively improves the actual combat capability.

Key words： dynamic weapon target assignment; contest; incomplete information; Nash equilibrium; genetic algorithm

武器目标分配[1](Weapon Target Assignment,WTA)是作战指挥决策的基础,获得合理、科学的分配策略是打赢现代化战争的关键。为了获得最优的分配策略,国内外学者做了大量研究,其中包括蚁群算法、拍卖算法、粒子群算法[2⇓-4]等,但大部分把敌方看作无对抗能力的防御对象,仅考虑我方的分配对策,没有考虑敌方的分配对策对我方分配对策产生的影响,忽略了实际作战的动态博弈性。敌我双方的战场态势一直处于变化之中,作战过程实际上就是一场博弈。博弈论[5]是一门完整的科学理论,在古代田忌赛马中就已经灵活运用,在现代也广泛应用于经济、政治、军事等具有竞争性、冲突性和对抗性的领域,其在军事领域,不仅被应用于武器目标分配,还可以应用于无人机编队、舰艇对抗等。
因此,本文充分考虑敌我双方的战场态势变化、毁伤效能评估等因素,以博弈论为基础,建立一种不完全信息的动态武器目标分配模型,并利用遗传算法模拟动态作战过程,缩小决策点范围,有效提高我方武器作战中对未知信息的推理能力。

1 问题描述

合成分队中的武器[6]包括步兵战车、自动炮、坦克等,这些作战力量的价值和打击能力各不相同,由于战场情况瞬息万变,常常包含不确定、动态的复杂因素,敌我双方武器装备的价值和打击能力也随机变化,即各武器装备的价值和打击能力具有随机性和不确定性。因此,作战一方很难获取另外一方武器装备的价值和打击能力等信息,也就是说,敌我双方在作战过程中掌握的信息是不对称的。如何在敌我双方掌握信息不对称的情况下,科学合理地确定我方用哪些武器打击敌方哪些目标的打击方案,以期用最小的打击成本获得最大的毁伤效果是动态武器目标分配要解决的关键问题。因此,利用不完全信息动态博弈模型可以更加合理地对多武器多目标分配问题进行建模,将合成分队的动态武器目标分配问题转化为在不完全信息动态博弈中求解打击策略纳什均衡解的过程。纳什均衡为一个策略组合,是博弈双方的一种均衡状态,通过求解纳什均衡解有助于科学选择打击方案,提高作战效能。

2 模型构建

2.1 矩阵博弈的定义

合成分队的武器目标分配中,将敌我双方分别看作博弈的两个局中人,利用k阶段动态博弈展开作战,如图1所示。
图1 敌我双方k阶段作战动态博弈树
博弈的第1阶段,我方可以选择策略 S 11 1或 S 12 1,如果选择 S 11 1,博弈结束,敌我双方的支付函数分别为(z1(S11),z2(S11));选择 S 12 1,继续博弈。当博弈进行到第k阶段,此时,敌方可以选择策略 S 21 k或 S 22 k;当进入第k+1阶段,我方在不知道敌方策略的情况下,可以选择策略 S 11 k + 1或 S 12 k + 1,此时敌我双方对应的支付函数分别为(z1(Sk+1,2),z2(Sk+1,2)),表示局中人i针对当前决策的支付函数。
一般情况下,动态博弈[7]包括以下要素:一是局中人,指的是参与博弈的主体,即我方武器和敌方目标;二是策略集,指的是博弈双方有顺序选择的策略集合;三是赢得函数,指的是博弈双方根据选择的策略获得的收益值;四是均衡解,指的是博弈双方最优策略的组合。多武器多目标分配问题可以建模为一个双矩阵博弈模型G=(N,S,Z)[8],具体为:
1)N={1,2}为博弈中的两个局中人,N=1代表我方, N=2代表敌方;
2)S={ s 1 i k, s 2 j k}为博弈中两个局中人的行动策略, s 1 i k为我方第k阶段选择第i种策略, s 2 j k为敌方第k阶段选择第j种策略;
3)Z=(z1(sk,i),z2(sk,j))为博弈中两个局中人选择某种行动的支付函数。

2.2 不完全信息

不完全信息[9]指的是博弈的两个局中人没有完全掌握对方的事前信息,另一局中人的策略和选择是不确定的。动态博弈中,我方的目的是在保护自身不被敌方攻击的同时对敌方实施打击,敌方的目的是在保护自身不被我方打击的同时对我方实施攻击,这存在于整个博弈的过程。由于动态博弈存在多变性、随机性等特点,使两个局中人无法掌握博弈中的全部信息,其中,最突出的就是武器目标的杀伤威力不同导致敌我双方的毁伤评估结果具有不完全性,求解最优策略时必须考虑这一因素。

2.3 支付矩阵

由于模型中只存在两个局中人,一个局中人的支付等于另一个局中人的收益,博弈双方的支付和收益的和永远为零,因此可以将模型看作基于不完全信息的两人零和非合作博弈[10]。
假设我方有M个武器参与作战,敌方有N个目标参与作战,敌我双方武器目标的价值集合分别为W和D。
W={W1,W2,···,Wi,···,Wm}
其中,Wi表示第i个武器的价值。
D={D1,D2,···,Dj,···,Dn}
其中,Dj表示第j个武器的价值。
假设我方的第i个武器命中敌方的第j个目标的概率为pwij,我方的第i个武器被敌方的第j个目标命中的概率为pdji,我方的第i个武器打击敌方的第j个目标的支付值为
Rwij=(Dj/max D)*pwij
我方的第i个武器打击敌方的第j个目标、第m个武器打击敌方的第n个目标的融合支付值为
Rw= R w i j + R w m n 2
敌方的第j个目标打击我方的第i个武器的支付函数为
Rdji=(Wi/max W)*pwij
敌方的第j个目标打击我方的第i个武器、敌方的第n个目标打击我方的第m个武器的融合支付值为
Rd= R d j i + R d n m 2
多武器多目标分配动态博弈的支付函数为
zij= ∑ i = 1 mhijRwij- ∑ j = 1 nljiRdji
其中,hij和lij都有0、1两个取值。hij=1代表我方的第i个武器打击敌方的第j个目标,hij=0代表我方的第i个武器没有打击敌方第j个目标;lij=1代表敌方的第j个目标打击我方的第i个武器, lij=0代表敌方的第j个目标没有打击我方的第i个武器。
根据式(3)和式(5),可得敌我双方的支付矩阵为P。
PW= R w 11 R w 12 ··· R w 1 N R w 21 R w 22 ··· R w 2 N ︙ ︙ ︙ ︙ R w M 1 R w M 2 ··· R w M N
PD= R d 11 R d 12 ··· R d 1 M R d 21 R d 22 ··· R d 2 N ︙ ︙ ︙ ︙ R d N 1 R d N 2 ··· R d N M

3 求解方法

3.1 纳什均衡的基本概念及求解方法

根据博弈的基本特性,任意矩阵博弈至少存在一个纳什均衡解[11]。纳什均衡可定义为,对于一个n人博弈G={τ,S,U},策略组合s*=( s 1 *,···, s 2 *,···, s n *)为纳什均衡,当且仅当∀i∈τ,∀si∈Si时,有:
ui( s i *, s - i *)≥ui(si, s - i *)
在这个策略组合中,一方的策略都是针对另一方策略的最优反应。
求解纳什均衡解的过程是一项复杂的工程问题,为了提高求解速度,常常借助一些智能算法,比如神经网络算法、粒子群算法和遗传算法等。遗传算法是由Holland提出的一种快速搜索算法,利用生物进化中的编码现象和遗传机制能自动获取和调整搜索空间,具有较好的全局寻优能力,被广泛应用于机器学习、信号处理、打击博弈等问题中。因此,本文在构建多武器多目标分配的博弈模型基础上,利用遗传算法求解纳什均衡[12-13]。

3.2 遗传算法求解纳什均衡解的步骤

3.2.1 编码

编码主要模仿生物的染色体, 针对最优策略问题, 需要将其变量按照某种编码方式构建一种编码规则,实现由工程问题向遗传问题的转化。根据动态博弈的相关特性,分别对敌我双方的武器目标分配策略进行编码。
我方武器分配策略的编码采用十进制整数编码方式,编码长度为M*N,染色体编码为(Vij)M*N,其中Vij的约束条件为公式(10)。
Vij≤M
敌方目标分配策略的编码采用二进制编码方式,dj=1表示第j个目标是我方武器的打击对象,dj=0表示第j个目标不是我方武器的打击对象。

3.2.2 适应度函数

针对每个染色体i,分别计算到达所有基因位时的支付函数 z i k,找到 z i k最大值所在的基因位,根据基因位的参与者来选择最优策略,若i=1,zik>0,表示选择该染色体对我方有利;若i=2,zik<0,表示选择该染色体对敌方有利。因此,染色体适应度函数可以用支付函数zik来表示。

3.2.2 交叉

交叉是遗传算法中非常重要的一环,利用交叉可以获得两个群体的新一代个体,新一代个体的特性与父辈的特性息息相关。在武器目标分配问题中,常常采用的是单点交叉方法。
第k代的染色体为Ak(1)和Ak(2),随机产生的交叉位为 B i j k,对应的交叉位区间为[ B i ( j + 1 ) k, B i N k],染色体的编码区间为[ A i ( j + 1 ) k, A i N k]。假设γ为第k代的交叉位区间的一个随机点,即γ∈[ B i ( j + 1 ) k, B i N k],交叉后的两个染色体为:
A i γ k + 1(1)=|α A i γ k(2)+(1-α) A i γ k(1)|
A i γ k + 1(2)=|α A i γ k(1)+(1-α) A i γ k(2)|
其中,α为一个随机常数,取值区间为0≤α≤1。

3.2.3 变异

变异是产生新个体的辅助操作,通过设定变异概率可以改变某个或某些个体的基因值,决定算法的局部搜索能力。为了防止算法陷入局部最优的困境,变异概率一般较低,采用单点随机定位的运算来确定。
第k代的染色体Ak(l)为随机确定的一个变异染色体,对应的变异位为 B i j k(l),编码值为 C i j k(l)。第k+1代的染色体编码值为
C i j k + 1(l)=|β*qi|
其中,β为一个随机常数,取值区间为0≤β≤1。

3.2.4 终止策略

如果每个种群迭代的代数均已达到规定的迭代次数,并且某染色体的适应度值在若干代内不再改变,则算法终止,此时适应度值在若干代不再改变的染色体为最优分配方案,即纳什均衡解;否则,继续迭代,直到出现最优解。

3.2.5 求解算法步骤

求解算法步骤详见图2所示。
图2 遗传算法求解纳什均衡解的流程图

4 算例分析

为了证明本文提出的基于不完全信息博弈的动态武器目标分配模型及求解算法的有效性,采用案例分析和软件仿真相结合的方式进行验证。

4.1 案例分析

假设我方的武器数量为2,即M={武器1,武器2},敌方的目标数量也为2,即N={目标1,目标2},双方都在对方的视野范围内进行博弈。假设我方武器的价值为W=[ 65 72],武器的命中概率为Pij= 0.78 0.77 0.62 0.82,敌方目标的预估价值为D=[ 68 70],目标的击中概率为Pji= 0.79 0.81 0.84 0.60。敌我双方武器目标分配问题的构建过程为:
1) N={W,D},为双矩阵博弈的两个局中人;
2)我方的打击策略集为{ S 1 1, S 2 1, S 3 1, S 4 1},敌方的打击策略集{ S 1 2, S 2 2, S 3 2, S 4 2},其中,策略 S 1 1表示我方武器1打击敌方目标1,我方武器2打击敌方目标2; 策略 S 2 1表示我方武器1打击敌方目标1,我方武器2打击敌方目标1;策略 S 3 1表示我方武器1打击敌方目标2,我方武器2打击敌方目标1;策略 S 4 1表示我方武器1打击敌方目标2,我方武器2打击敌方目标2;策略 S 1 2表示敌方目标1打击我方武器1,敌方目标2打击我方武器2;策略 S 2 2表示敌方目标1打击我方武器1,敌方目标2打击我方武器1;策略 S 3 2表示敌方目标1打击我方武器2,敌方目标2打击我方武器1;策略 S 4 2表示敌方目标1打击我方武器2,敌方目标2打击我方武器2。敌我双方的纯策略集合如表1和表2所示。
表1 W方和D方武器目标分配的策略集合
我方武器打击策略 敌方目标打击策略
策略1 我方武器1打击敌方目标1
我方武器2打击敌方目标2		 敌方目标1打击我方武器1
敌方目标2打击我方武器2
策略2 我方武器1打击敌方目标1
我方武器2打击敌方目标1		 敌方目标1打击我方武器1
敌方目标2打击我方武器1
策略3 我方武器1打击敌方目标2
我方武器2打击敌方目标1		 敌方目标1打击我方武器2
敌方目标2打击我方武器1
策略4 我方武器1打击敌方目标2
我方武器2打击敌方目标2		 敌方目标1打击我方武器2
敌方目标2打击我方武器2
表2 敌我双方的策略集合
W方 S w 1 S w 2 S w 3 S w 4
1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1
D方 S D 1 S D 2 S D 3 S D 4
1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1
3)计算敌我双方策略集的支付值,如表3所示。
表3 敌我双方策略集的支付值
W方 策略 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1
支付值 0.79 0.68 0.67 0.80
D方 策略 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1
支付值 0.66 0.74 0.78 0.71

4.2 软件仿真

为了验证本文提出的多武器多目标博弈模型的合理性和求解算法的高效性,将遗传算法求解不完全信息博弈纳什均衡的时间与神经网络算法(BP)和粒子群算法(PSO)求解同一模型纳什均衡的时间进行对比,利用软件进行仿真试验。假设敌我双方武器目标数量分别是2、3、4、5、6、7、8、9、10、11个,武器目标的价值J= ( D , W ) , D ∈ ( 0,100 ) , W ∈ ( 0,100 ),打击概率p∈(0,1)。借助软件计算不同作战规模下三种算法求解纳什均衡解的时间,如表4所示。
表4 求解纳什均衡的时间表
算法时间
作战规模		 神经网络算法 粒子群算法 遗传算法
2*2 0.5 0.05 0.1
3*3 0.7 0.1 0.15
4*4 0.8 0.15 0.3
5*5 1.0 0.2 0.4
6*6 1.6 1.0 0.8
7*7 2.6 1.8 1.5
8*8 4 3 2.5
9*9 4.5 3.5 1.9
10*10 4.2 3.3 1.8
11*11 3.7 3.4 1.7
通过表4能够清楚看到不同规模下,使用神经网络算法、粒子群算法和遗传算法求解纳什均衡的时间。不同算法的求解时间结果对比图,如图3所示。
通过图3可以看出,神经网络算法求解纳什均衡解的时间明显长于遗传算法的求解时间,而粒子群算法在作战规模较小的时候运算时间短于遗传算法,而一旦网络规模增大,它的运算时间会长于遗传算法的求解时间,考虑实际作战规模的影响,应该优先选择遗传算法求解纳什均衡。因此,通过对比,进一步验证了所构建模型的合理性和算法的可行性,为解决合成分队动态武器目标分配问题提供一定支撑。

5 结束语

合成分队敌我双方的攻防过程实际上就是一场动态博弈过程,考虑实际作战存在许多不完全信息,提出了一种基于不完全信息的多武器多目标博弈模型,将动态武器目标分配问题转化为求解纳什均衡的过程,借助遗传算法给出了求解思路,利用仿真证明了本文构建的模型和求解算法的有效性,可以提高指挥决策的科学性。在后续研究中,将进一步考虑武器资源是否正常供应、战场态势等因素,对合成分队的多武器多目标分配问题进行研究,提高均衡解的精确性和适用范围。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Shalumov V, Shima T. Weapon-Target-Allocation Strategies in Multiagent Target-Missile-Defender Engagement[J]. Journal of Guidance Control and Dynamics, 2017, 40(10):1-13.

DOI

[2]
Lee Z J, Lee W L. A Hybrid Search Algorithm of Ant Colony Optimization and Genetic Algorithm Applied to Weapon-Target Assignment Problems[C]// Intelligent Data Engineering and Automated Learning, Hong Kong, China, 2003(2690):278-285.

[3]
陈华东, 王航宇, 王树宗, 等. 基于合同机制的协同作战分布式目标分配研究[J]. 系统仿真学报, 2009, 21 (16):200-203.

[4]
Lu X, Di H, Jia Z, et al. Optimal Weapon Target Assignment Based on Improved QPSO Algorithm[C]// 2019 International Conference on Information Technology and Computer Application (ITCA), Guangzhou, China, IEEE, 2019:217-220.

[5]
张先剑. 空陆攻防博弈的动态武器目标分配[J]. 国防科技大学学报, 2019, 41(2): 185-190.

[6]
徐克虎, 孔德鹏, 陈金玉. 合成分队动态武器目标分配协同决策模型[J]. 火力与指挥控制, 2016, 41(6):62-66,72.

[7]
Ma F, Cao Z Y, Liu H. Construction and Search of Strategy Space of Target Assignment Based on Game Theory[J]. Systems Engineering and Electronics, 2010, 32(9):1941-1945.

[8]
韩玉龙, 严建钢, 杨士锋, 等. 基于灰双矩阵博弈的舰载无人机编队协同对海突击目标分配[J]. 电光与控制, 2016, 23(4):16-20,56.

[9]
隋永华, 郭雷, 俞利新, 等. 基于不完全信息空战的火力分配建模与应用[J]. 火力与指挥控制, 2012, 37(7):158-160.

[10]
熊义杰. 现代博弈论基础[M]. 北京: 国防工业出版社, 2010.

[11]
Ye M, Hu G. Distributed Seeking of Time-Varying Nash Equilibrium for Non-Cooperative Games[J]. IEEE Transactions on Automatic Control, 2015, 60(11):3000-3005.

DOI

[12]
Wang W, Cheng S C, Zhang Y Z. Research on Approach for a Type of Weapon Target Assignment Problem Solving by Genetic Algorithm[J]. Systems Engineering and Electronics, 2008(9):1708-1711.

[13]
马昌威. 多目标优化问题的遗传算法改进研究[J]. 电子设计工程, 2014, 22(11):145-147.

Options
文章导航

/

〈 〉