許遲,趙曉哲,史紅權,王永春
(海軍大連艦艇學院,遼寧 大連 116018)
編隊防空多通道-多目標匹配策略研究*
許遲,趙曉哲,史紅權,王永春
(海軍大連艦艇學院,遼寧 大連 116018)
針對艦艇編隊防空武器組織中的多通道與多目標的匹配問題,提出一種基于策略的方法。根據雙邊匹配決策理論,給出防空多通道-多目標匹配問題的相關描述,進一步提出基于穩定性和效益最大的2種匹配策略,并闡述了策略意圖和相應的實現算法,以此得到通過定制雙邊匹配策略來獲得編隊防空多通道與多目標匹配方案的方法。最后通過一個實例來說明使用該方法解決此類問題的可行性和有效性。
艦艇編隊防空;雙邊匹配;匹配策略;穩定匹配;效益最大;算法
隨著信息技術的快速發展和在軍事領域的普遍應用,軍事斗爭已經體現出了整體與整體、系統與系統之間成體系的對抗。海上艦艇編隊面臨著日益嚴峻的空中威脅,需要全面調度編隊內部各種資源,以此提高編隊攔截威脅目標的能力。這就要求指揮員能夠根據當時的作戰環境,不僅能夠組織起指控、傳感器、武器各節點相互密切合作的武器通道,而且在編隊統一安排和調度全部通道資源的基礎上,迅速形成各個武器通道對指定目標的交戰關系[1]。如何科學合理地組織好通道與目標的匹配是編隊防空武器組織中面臨的最為關鍵的環節之一。
傳統的通道與目標的匹配方法只考慮了單邊主體的需求。主要分為2種:一種是基于目標威脅的,即依據空中目標對編隊各平臺威脅程度的大小,按照序列來選擇武器通道抗擊,對于編隊平臺,也就是“誰(空中威脅)打我(平臺),我打誰”、“誰對我威脅大,我打誰”,這種組織方式只考慮了受主要威脅平臺對來襲目標的抗擊愿望和需求,沒有考慮平臺抗擊效果如何,是不可取的。第2種是基于抗擊效果的,依據編隊內各武器通道對目標抗擊效果的排序,來選擇抗擊效果好的通道抗擊,也就是“誰(平臺)打的好(對象是空中威脅),由誰來打”,這種組織方式考慮了編隊抗擊目標武器通道的能力,優先保障抗擊效果,在某種意義上是可行的,但從艦艇防空決策者的角度來講,忽視了主要受威脅者的抗擊訴求,并且對于受威脅艦艇在區域防御階段結束后需展開末端防御時在技戰術上將產生一定的影響,因此是有缺陷的。
雙邊匹配決策理論是指在決策過程中充分考慮各方匹配主體的滿意度要求,盡量使雙方主體間形成穩定的匹配對,其目的在于通過合理的匹配方法使雙方主體都達到滿意的結果[2]。雙邊匹配決策研究起源于古典婚姻匹配問題[2-3]。目前較好地解決了醫院與實習生、學生入學、人與組織、電子中介交易、風險投資和企業并購等匹配問題,以及產業鏈供需匹配、體育比賽場上隊員安排、高考志愿填報等問題[4]。
根據系統科學相似性原理,將雙邊匹配理論擴展到軍事領域,能夠解決相似問題。雙邊匹配應用領域的顯著特征主要體現在:資源有限,需求特定,且有實現雙邊匹配的必要和可能[5]。Roux[6]將威脅評估(threat evaluation,TE)與武器分配(weapon assignment,WA)過程進行組合,分析了TE,WA與指揮控制、數據融合、態勢感知、決策支持、網絡中心戰和交戰過程的關系。Huma[7]提出了基于穩定婚姻算法的空中威脅評估與武器分配方法,將TE和WA過程看作是兩階段有約束匹配問題。考慮了通過匹配在多個武器與多個目標之間建立關聯,但沒有對作戰資源組織進行有效的建模與分析。目前國內還沒有查到在艦艇編隊防御作戰研究中關于雙邊匹配理論應用的相關文獻。
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.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 前面內容闡述了雙邊匹配的基本概念以及編隊防空武器通道與目標的匹配問題,因此分別基于匹配結果的穩定性和匹配效益,提出穩定匹配和效益最大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等優化軟件求解,如遇復雜約束條件也可采用遺傳算法等智能優化算法加以求解。根據模型求解結果,可得目標與通道的匹配方案。 假設我方艦艇編隊(編號為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種策略為追求匹配結果的效益而犧牲了匹配的穩定性。 本文將艦艇編隊協同防空時空中威脅目標這一“任務需求”和區域防空武器抗擊通道“能力供給”視作雙邊匹配原理中的匹配組合,通過闡述基本原理,說明兩者內含機制的相似性,提出編隊協同防空武器組織的雙邊匹配策略,并通過實例驗證能夠求得有效的匹配結果,證明了運用雙邊匹配方法來研究艦艇編隊區域協同防空的武器組織問題是切實可行的。但本文在研究過程中,對編隊的協同抗擊通道能力的評估與空中目標的威脅程度進行了假設,而實際中這些信息可能是不確定的。因此,如何處理不確定的抗擊能力與威脅程度信息條件下的匹配問題,是下一步研究的方向。 [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.com3 武器通道的匹配策略及算法





4 實例分析


5 結束語