编队防空多通道-多目标匹配策略研究*

许迟，赵晓哲，史红权，王永春

(海军大连舰艇学院，辽宁 大连 116018)

编队防空多通道-多目标匹配策略研究*

许迟，赵晓哲，史红权，王永春

(海军大连舰艇学院，辽宁 大连 116018)

针对舰艇编队防空武器组织中的多通道与多目标的匹配问题，提出一种基于策略的方法。根据双边匹配决策理论，给出防空多通道-多目标匹配问题的相关描述，进一步提出基于稳定性和效益最大的2种匹配策略，并阐述了策略意图和相应的实现算法，以此得到通过定制双边匹配策略来获得编队防空多通道与多目标匹配方案的方法。最后通过一个实例来说明使用该方法解决此类问题的可行性和有效性。

舰艇编队防空；双边匹配；匹配策略；稳定匹配；效益最大；算法

0 引言

随着信息技术的快速发展和在军事领域的普遍应用，军事斗争已经体现出了整体与整体、系统与系统之间成体系的对抗。海上舰艇编队面临着日益严峻的空中威胁，需要全面调度编队内部各种资源，以此提高编队拦截威胁目标的能力。这就要求指挥员能够根据当时的作战环境，不仅能够组织起指控、传感器、武器各节点相互密切合作的武器通道，而且在编队统一安排和调度全部通道资源的基础上，迅速形成各个武器通道对指定目标的交战关系[1]。如何科学合理地组织好通道与目标的匹配是编队防空武器组织中面临的最为关键的环节之一。

传统的通道与目标的匹配方法只考虑了单边主体的需求。主要分为2种：一种是基于目标威胁的，即依据空中目标对编队各平台威胁程度的大小，按照序列来选择武器通道抗击，对于编队平台，也就是“谁(空中威胁)打我(平台)，我打谁”、“谁对我威胁大，我打谁”，这种组织方式只考虑了受主要威胁平台对来袭目标的抗击愿望和需求，没有考虑平台抗击效果如何，是不可取的。第2种是基于抗击效果的，依据编队内各武器通道对目标抗击效果的排序，来选择抗击效果好的通道抗击，也就是“谁(平台)打的好(对象是空中威胁)，由谁来打”，这种组织方式考虑了编队抗击目标武器通道的能力，优先保障抗击效果，在某种意义上是可行的，但从舰艇防空决策者的角度来讲，忽视了主要受威胁者的抗击诉求，并且对于受威胁舰艇在区域防御阶段结束后需展开末端防御时在技战术上将产生一定的影响，因此是有缺陷的。

双边匹配决策理论是指在决策过程中充分考虑各方匹配主体的满意度要求，尽量使双方主体间形成稳定的匹配对，其目的在于通过合理的匹配方法使双方主体都达到满意的结果[2]。双边匹配决策研究起源于古典婚姻匹配问题[2-3]。目前较好地解决了医院与实习生、学生入学、人与组织、电子中介交易、风险投资和企业并购等匹配问题，以及产业链供需匹配、体育比赛场上队员安排、高考志愿填报等问题[4]。

根据系统科学相似性原理，将双边匹配理论扩展到军事领域，能够解决相似问题。双边匹配应用领域的显著特征主要体现在：资源有限，需求特定，且有实现双边匹配的必要和可能[5]。Roux[6]将威胁评估(threat evaluation，TE)与武器分配(weapon assignment，WA)过程进行组合，分析了TE，WA与指挥控制、数据融合、态势感知、决策支持、网络中心战和交战过程的关系。Huma[7]提出了基于稳定婚姻算法的空中威胁评估与武器分配方法，将TE和WA过程看作是两阶段有约束匹配问题。考虑了通过匹配在多个武器与多个目标之间建立关联，但没有对作战资源组织进行有效的建模与分析。目前国内还没有查到在舰艇编队防御作战研究中关于双边匹配理论应用的相关文献。

1 双边匹配相关理论

1.1 双边匹配的定义[8]

在双边匹配问题中，存在着双方主体集合，设甲方主体集合为A={A1，A2，…，An}，其中Ai表示第i个甲方主体，i=1，2，…，n；乙方主体集合为B={B1，B2，…，Bn}，其中Bj表示第j个乙方主体，j=1，2，…，n。其中n表示各方包含的主体数目，I=(1，2，…，n)。双边匹配就是依据双方主体所提供的偏好信息，按照一定的准则找到2个主体个数相等的集合A′⊆A与B′⊆B，并同时建立A′与B′中主体间的一一对应关系。

双边匹配可界定为甲乙双方主体集合的映射μ：A∪B→B∪A，且∀Ai∈A，∀Bj∈B满足下列条件：

(1)μ(Ai)∈B；

(2)μ(Bj)∈A；

(3)μ(Ai)=Bj当且仅当μ(Bj)=A；

(4) 若μ(Ai)=Bj，则μ(Ai)≠Bk，∀k∈I，k≠j。

其中：μ(Ai)=Bj表示Ai与Bj在μ中匹配；μ(Ai)≠Bj则表示Ai与Bj在μ中不匹配。

1.2 稳定和满意双边匹配[9]

设Ri=(ri1，ri2，…，rin)为甲方主体Ai给出的关于乙方主体集合B的序值向量，其中rij表示甲方主体Ai把乙方主体Bj排在第rij位，rij∈I。同理，设Ti=(t1j，t2j，…，tnj)T为乙方主体Bj给出的关于甲方主体集合A的序值向量，其中tij表示乙方主体Bj把甲方主体Ai排在第tij位，tij∈I。若甲方主体Ai把乙方主体Bj排在第1位，即rij=1，则Ai对Bj满意程度最高。若甲方主体Ai把乙方主体Bj排在最后一位，即rij=n。

稳定匹配：对于双边匹配μ，若存在Ai0，Ai1，Bj0，Bj1， i0，i1，j0，j1∈I，其中i0≠i1，j0≠j1，满足ri0j1≤ri0j0，ti0j1≤ti0j0，则称μ是不稳定的，否则称为稳定双边匹配。

满意匹配：对于双边匹配μ，若∃Ai0，Ai1，Bj0，Bj1， i0，i1，j0，j1∈I，其中i0≠i1，j0≠j1，满足ri0j1+ri1j0≤ri0j0+ri1j1，ti0j1+ti1j0≤ti0j0+ti1j1，且等式不同时成立，则称μ是不满意的，否则称为满意双边匹配。

双边匹配解决的问题是：依据甲方主体Ai给出的序值向量Ri(i=1，2，…，n)与乙方主体Bj给出的序值向量Tj(j=1，2，…，n)，通过某种决策分析方法，大致在n!个双边匹配中选择一个“最优”的匹配方案，使双方主体之间形成理想的匹配。

2 舰艇编队防空多通道-多目标双边匹配问题描述

2.1 匹配基本目的

运用双边匹配决策理论，同时照顾双边主体的需求，尽可能可以使双方得到兼顾。在多通道-多目标匹配中，既考虑平台武器通道对各空中目标抗击能力，保障武器通道能力的发挥，取得较优抗击效果；又考虑空中目标对各平台威胁程度，尽可能满足受目标威胁较大平台的抗击诉求。

2.2 匹配的主体

舰艇编队在防空过程中存在着两方的匹配主体，一方是由空中威胁目标形成的防空作战“需求”，另一方是由防空武器构成的作战能力“供给”，且每方主体均由多个个体“威胁”或“通道”组成。设空中威胁目标集合为T={T1，T2，…，Tn}，其中n为空中威胁数量，Ti表示第i个空中威胁；设舰空导弹武器通道集合为C={C1，C2，…，Cm}，其中m为备选武器通道数量，Cj表示第j个备选武器通道。

2.3 匹配的评估值信息

多目标-多通道双边主体的评估值是指对武器通道抗击能力或空中目标威胁程度的度量。防空作战中空中目标威胁估计和通道能力评估是制定防空作战计划的重要环节，评估值可通过威胁估计和通道能力评估获得。

某通道的威胁评估值是某目标对其所属平台的威胁大小；某目标对应的能力评估值是指某武器通道抗击该目标的能力大小。设各平台受空中目标威胁评估值矩阵为T=(tij)m×n；tij表示第j个通道所属平台受到第i个目标威胁程度的评估值。设各威胁目标的武器通道能力评估值矩阵为C=(cij)m×n，cij表示第i个通道对第j个目标的抗击能力评估值。

2.4 匹配的序值信息

根据匹配原理[8-15]，双方主体要求存在一方主体对另一方主体满意度的评价序值，即双方匹配的“意愿”。在防空作战中，空中威胁个体对各平台构成不同程度的威胁，可生成威胁程度序列；武器通道对各空中目标体现不同的抗击能力，可生成抗击能力序列。

将各平台的空中目标威胁排序表示为序值向量Pi(i=1，2，…，m)，Pi为第i个平台对应的威胁序值向量，Pi=(pi1，pi2，…，pin)；各威胁对应的武器通道抗击能力排序表示为序值向量Qj(j=1，2，…，n)，Qj为第j个威胁目标对各通道所属平台威胁程度的排序，Qi=(qi1，qi2，…，qim)，m为备选通道数量。且双边主体数量可以相等或不等。m>n，说明空中威胁数量大于备选通道数量；m=n，说明空中威胁数量等于备选通道数量；m

3 武器通道的匹配策略及算法

前面内容阐述了双边匹配的基本概念以及编队防空武器通道与目标的匹配问题，因此分别基于匹配结果的稳定性和匹配效益，提出稳定匹配和效益最大2种匹配策略，下面分别阐述匹配策略的相应算法。

3.1 基于稳定性的匹配策略及算法

3.1.1 策略意图

为实现编队兼顾“抗击能力”和“威胁程度”的双边需求，得到一个稳定的匹配结果，可采用稳定匹配策略，使编队各武器通道抗击能力的发挥和受威胁舰艇的抗击诉求达到一种均衡的状态[16]。当匹配完结时这种状态不存在这样一组武器通道和威胁目标(通道C1与目标T1匹配，通道C2与目标T2匹配)，C1打击T2比T1能力更强，而T2对C1所属平台比C2威胁更大。

3.1.2 延迟接受算法(GS算法)

(1) 算法描述

延迟接受算法由Gale和Shapley提出，用于研究学校申请和婚姻稳定问题，后在经济领域用于研究稳定匹配[2-3]。算法思想为：存在2个集合A={a1，…，an}和B={b1，…，bn}，集合A中的个体ai对于集合B中的个体bj存在一个偏好次序P(x)|x=ai，bj。例如若P(ai)=b1，b2，b3…，bm，则表示ai的首位偏好为b1，并依次类推。首先集合A中的个体将按照偏好顺序向集合B的个体发出征求匹配信息，如bj未匹配，则bj将暂时接受ai，如已匹配，则个体bj根据自己的偏好函数P(bj)决定是否暂时接受ai，同时未匹配的ai将划去P(ai)偏好序集的当前首位。然后按照次偏好向集合B的个体发出匹配信息，开始下一轮匹配，直到集合A中不存在个体向集合B中发送信息。最后，由集合B向当前匹配的集合A中的个体发出正式接受的匹配信息，完成整个匹配过程，即所谓延迟接受。

(2) 逻辑流程

稳定匹配能够兼顾双边需求，但匹配算法是从一边主体最优的角度出发的，所以主动的一方将更有优势。由此稳定匹配策略可进一步分为“抗击优先”和“威胁优先”的2类匹配策略。

“抗击优先”匹配策略由抗击能力较强的武器通道占据主动地位，优先与相应目标得到匹配，并得到一个稳定的结果。目的是充分发挥编队武器组织的抗击能力，确保在兼顾双边需求的稳定匹配结果中由抗击能力最强的武器通道对相应目标实施抗击。基于GS算法求解匹配结果的逻辑流程如图1所示。

图1 “抗击优先”武器通道稳定匹配策略逻辑流程图Fig.1 “Operation first” weapon channel stable matching tactic logic diagram

“威胁优先”匹配策略由威胁程度较大的空中目标占据主动地位，优先与相应平台得到匹配，并得到一个稳定的结果。目的是充分考虑空中目标对平台的威胁程度，确保在兼顾双边需求的稳定匹配结果中由受威胁程度最大的平台组织武器对相应目标实施抗击。基于GS算法求解匹配结果的逻辑流程如图2所示。

图2 “威胁优先”武器通道稳定匹配策略逻辑流程图Fig.2 “Threat first” weapon channel stable matching tactic logic diagram

3.2 基于效益最大的匹配策略及算法

3.2.1 策略意图

决策者在匹配通道进行匹配时，希望匹配结果的所有匹配对的能力和威胁评估的效益总和尽可能大。并且在匹配算法中允许决策者添加指定的约束条件。

3.2.2 多目标优化模型

(1) 模型描述

下面通过建立多目标决策模型求解来获得最大评估总和的匹配结果。引入0-1变量xij，其中

(1)

(2)

(3)

(4)

其中：Ft与Fc分别为空中目标对匹配平台威胁总和与平台武器通道对匹配目标抗击能力总和的量化表示；式(1)和(2)作为目标函数表达双方主体的匹配需求，式(1)表示空中目标对匹配武器通道平台的威胁总和尽可能大，式(2)表示武器通道对匹配目标抗击能力总和尽可能强；式(3)是指每个通道只能与一个威胁目标相匹配，式(4)是指每个威胁目标只能与一个通道相匹配，即双方主体之间的匹配是一对一的匹配。

实际作战中，决策者可能认为目标Ft和Fc重要程度不同。不妨设ωt和ωc分别为目标Ft和Fc权重，满足0≤ωt，ωc≤1，ωt+ωc=1，利用线性加权将以上模型转化为单目标优化模型。式(1)和(2)可合并为

(5)

式中：ωk(k=1，2)能够反映目标Ft和Fc在双边匹配中的重要程度，即ωk的大小能够体现“抗击”或“威胁”的优先程度，其作为决策参量由决策者给出。

在目标模型基础上，决策者可以根据需要对匹配施加约束，若决策者要求与各威胁目标匹配的通道抗击能力不小于最低可接受的评估值，不妨设阈值为T0，小于阈值T0决策者则认为通道能力过低无法满足抗击要求；同理可设威胁评估值阈值为C0。有如下约束：

(6)

或者

(7)

根据战场态势，决策者有时会在作战中指定某平台发射舰空导弹抗击特定目标，即指定由抗击能力序值为第a位的武器通道所属平台抗击某目标，且该目标对其威胁程度排在第b位。可限制：xab=1。且根据模型可知：

(8)

并且

(9)

(2) 模型求解

求解最大效益匹配的算法步骤如下：

步骤4 通过构建式(6)～(9)等约束条件，以体现决策者在匹配策略中的战术意图，并形成匹配策略的规划模型。

步骤5 求解上述匹配的规划模型，方法包括采用多项式算法编程求解，或利用Lingo 11.0或Cplex 9.0等优化软件求解，如遇复杂约束条件也可采用遗传算法等智能优化算法加以求解。根据模型求解结果，可得目标与通道的匹配方案。

4 实例分析

假设我方舰艇编队(编号为1001～1005)面临严重空中威胁，现已展开防空队形，准备组织编队舰艇使用中远程舰空导弹协同抗击来袭目标。通过对威胁目标分析可得目标对我方舰艇威胁评估数据如表1所示。(9001～9008)为空中威胁目标批号。

通过编队武器组织我方可使用8个通道协同抗击来袭目标，并对各通道能力进行了评估，得评估数据如表2所示。其中编号1001A，1001B，1002A等表示备选武器通道。1001A表示基于平台1001的武器通道，1001B表示基于平台1001的第2条武器通道，以次类推。

4.1 匹配策略与模型求解

现需要从备选武器通道中挑选出通道来抗击指定目标。下面分别采用2种匹配策略完成空中威胁目标和防空武器通道的双边匹配。

稳定匹配策略：

决策者希望得到稳定匹配结果，并尽可能使空中威胁目标与抗击能力最强的武器通道相匹配。即采用“抗击优先”的稳定匹配策略，基于GS算法利用计算机C++编程实现求解，可得匹配结果为

{(9001，1001A)，(9002，1003A)，(9003，1002A)，(9004，1004B)，(9005，1003B)，(9006，1001B)，(9007，1004A)，(9008，1005A)}.

根据稳定双边匹配定义可验证上述匹配结果为稳定双边匹配。

效益最大策略：

决策者采用能够获取最大效益的匹配策略，并假设决策要求匹配的通道抗击能力评估值在整体的平均评估值以上，同时所属平台受抗击的目标威胁程度不低于平均威胁评估值的60%。

通过建立多目标优化决策模型，利用黄金分割线取权重系数ωc=0.618，ωt=0.382，利用线性加权法将多目标转化为单目标优化决策模型如下：

(10)

(11)

(12)

(13)

(14)

表1 各空中目标对舰艇编队威胁程度评估值数据表

表2 各武器通道对威胁目标抗击能力评估值数据表

由于模型属指派问题模型，可采用匈牙利法求解，使用Lingo 11.0等软件均可求得匹配结果：{(9001，1003A)，(9002，1003B)，(9003，1002A)，(9004，1004B)，(9005，1005A)，(9006，1001A)，(9007，1004A)，(9008，1001B)}.

并求得效益值为Z2=5.75。依据式(10)可求解第1种策略的匹配效益值Z1=5.53。

4.2 结果分析

从匹配结果可以看出，除目标9003，9004，9007匹配的通道在策略不同时没有变动外，其余通道均有调整，并且Z1

稳定匹配策略的匹配结果满足稳定性要求，但匹配效益小于第2种策略。第2种策略能够获得在约束条件下匹配的最大效益评估，但出现了(9005，1005A)，(9006，1001A)的不稳定匹配。

如匹配对(9005，1005A)和(9002，1003B)：相比通道1005A抗击目标9005的能力评估，通道1003B要更强；并且同时相比目标9002，目标9005对1003平台的威胁更大。由此表明，匹配结果出现了平台1003没有能够与“对我威胁相对大，由我抗击相对好”的威胁目标匹配的“尴尬”局面。匹配对(9006，1001A)与(9008，1001B)同理如此。

综上可知，第1种策略为保证匹配结果的稳定性而损失了总体效益，而第2种策略为追求匹配结果的效益而牺牲了匹配的稳定性。

5 结束语

本文将舰艇编队协同防空时空中威胁目标这一“任务需求”和区域防空武器抗击通道“能力供给”视作双边匹配原理中的匹配组合，通过阐述基本原理，说明两者内含机制的相似性，提出编队协同防空武器组织的双边匹配策略，并通过实例验证能够求得有效的匹配结果，证明了运用双边匹配方法来研究舰艇编队区域协同防空的武器组织问题是切实可行的。但本文在研究过程中，对编队的协同抗击通道能力的评估与空中目标的威胁程度进行了假设，而实际中这些信息可能是不确定的。因此，如何处理不确定的抗击能力与威胁程度信息条件下的匹配问题，是下一步研究的方向。

[1] 缪旭东，王永春.舰艇编队协同防空任务规划理论与应用[M].北京：国防工业出版社，2013. MIAO Xu- dong，WANG Yong- chun.Mission Planning Theory and Application for Air Defense of Navy Vessel Formation[M].Beijing：National Defense Industry Press,2013.

[2] ROTH A E.Common and Conflicting Interests in Two- Sided Matching Markets[J].European Economic Review，1985，27(1)：75-96.

[3] GALE D，SHAPLEY L.College Admissions and the Stability of Marriage[J].American Mathematical Monthly，1962，69(1)：9-15.

[4] 陈希，樊治平.双边匹配决策的研究现状与展望[J].管理评论，2012，24(1)：169-176. CHEN Xi，FAN Zhi- ping.Research Status and Prospect of Two- Sided Matching Decision Making[J].Management Review，2012，24(1)：169-176.

[5] 赵晓哲，王永春，许迟.舰艇编队协同防空武器组织的研究现状与展望[J]，火力与指挥控制，2016，41(1)：1-6. ZHAO Xiao- zhe，WANG Yong- chun，XU Chi.Review and Prospect of Research on Weapon Organizing in Coordinated Air Defense of Naval Vessel Formation[J].Fire Control and Command Control，2016，41(1)：1-6.

[6] ROUX J N，VUUREN J H.Threat Evaluation and Weapon Assignment Decision Support：A Review of the State of the Art[J].ORiON，2007，23(2)：151-187.

[7] HUMA N，ASIF M.An Optimal Dynamic Threat Evaluation and Weapon Scheduling Technique[J].Knowledge- Based Systems，2010，23(4)：337- 342.

[8] 陈希.多指标双边匹配决策方法研究[D].沈阳：东北大学，2010. CHEN Xi.Research on Two- Sided Matching Decision Making Methods[D].Shenyang：Northeastern University，2010.

[9] 乐琦.基于偏好序信息的满意双边匹配决策方法研究[D].沈阳：东北大学，2011. LE Qi.Research on the Decision Methods for Satisfied Two- Sided Matching Based on Preference Ordinal Information[D].Shenyang：Northeastern University，2011.

[10] KORKMAZ I，GOKCEN H，GETINYOKUS T.Ananalytic Hierarchy Process and Two- Sided Matching Based Decision Support System for Military Personnel Assignment[J].Information Sciences，2008，178(14)：2915-2927.

[11] 文胜.双边匹配理论及其在中国信贷市场中的应用[D].武汉：华中科技大学，2006. WEN Sheng.Two- Sided Matching Theory and Its Application to the Banking Credit Market in China[D].Wuhan：Huazhong University of Science and Technology，2006.

[12] JUNG J J，JO G S.Brokerage Between Buyer and Seller Agent Susing Constraint Satisfaction Problem Models[J].Decision Support Systems，2000，28(4)：293-304.

[13] 赵希男，温馨，贾建锋.组织中人岗匹配的测算模型及应用[J].工业工程与管理，2008，13(2)：112-117. ZHAO Xi- nan，WEN Xin，JIA Jian- feng.Research on the Measuring Models of Person- Post Matching and Its Application in Organizations[J].Industrial Engineering and Management，2008，13(2)：112-117.

[14] 张振华，汪定伟.电子中介中的交易匹配研究[J].控制与决策，2005，20(8)：917-920. ZHANG Zhen- hua，WANG Ding- wei.Research on Matching Problem of Electronic Broker[J].Control and Decision，2005，20(8)：917-920.

[15] 徐晓辉，陈剑.关于产品电子商务匹配度的研究[J].南开管理评论，2000(4)：71-74. XU Xiao- hui，CHEN Jian.Research on Match of Product and Electronic Commerce[J].Nankai Business Review，2000(4)：71-74.

[16] 王烨，梁雨生.稳定匹配中的纳什均衡[J].同济大学学报：自然科学版，2013，41(1)：155-158. WANG Ye，LIANG Yu- sheng.Nash Equilibrium in Stable Matching Problems[J].Journal of Tongji University：Natural Science ed，2013，41(1)：155-158.

Multi- Platform and Multi- Objective Matching of Weapon Channel Organizing in Air Defense Formation Based on Tactics

XU Chi，ZHAO Xiao- zhe，SHI Hong- quan，WANG Yong- chun

(Dalian Naval Academy，Liaoning Dalian 116018，China)

A novel method based on tactics is proposed to solve multi- platform and multi- objective matching of weapon channel organizing in air defense of naval vessel formation. The related description about the problem of multi- platform and multi- objective matching in air defense is provided based on the decision- making theory of two- sided matching. Two kinds of matching tactics of weapon channel organizing based on stability and maximizing effectiveness are proposed，and the intention and corresponding algorithm of the tactic are provided as a way to achieve multi- platform and multi- objective matching plan adopting two- sided matching tactics. An example is given to illustrate the feasibility and validity of the proposed method to solve this kind of problem.

naval vessel formation air defense；two- sided matching；matching strategies；stable matching；maximizing effectiveness；algorithm

2016-05-09；

2016-12-01 基金项目：中国博士后科学基金(2015M582867) 作者简介：许迟(1984-)，男，辽宁抚顺人。博士生，研究方向为舰艇指挥信息系统与作战应用。

10.3969/j.issn.1009- 086x.2017.04.007

E072；E925

A

1009- 086X(2017)- 04- 0037- 07

通信地址：113018 辽宁省大连市中山区解放路667号海军大连舰艇学院研究生管理大队

E- mail：84467056@qq.com；xuchi0429@dingtalk.com