曾 斌, 王 睿, 李厚樸, 張鴻強

(1. 海軍工程大學管理工程與裝備經(jīng)濟系, 湖北 武漢 430033; 2. 海軍工程大學教研保障中心,湖北 武漢 430033; 3. 海軍工程大學導航工程系, 湖北 武漢 430033)

0 引 言

隨著我國海外利益的拓展,海上安全形勢逐漸受到重視,海軍執(zhí)行遠洋任務的強度也相應增大,現(xiàn)有的以伴隨保障為主的保障方式難以滿足遠海任務的需求,需要建立海上保障基地進行配合。例如“?；笄凇崩碚搹娬{(diào)預置海上浮動平臺作為前置保障基地,對海上利益區(qū)域?qū)嵤┛焖俸笱b保障。這也導致這些保障基地、運輸航路以及海上補給區(qū)成為重點打擊目標,近年來特別是來自水下的探測及攻擊已經(jīng)構(gòu)成主要威脅。為此,要求保障基地必須具備一定的水下預警能力以便及時發(fā)現(xiàn)敵情,但隨著“分布式海上作戰(zhàn)”模式的應用,基地級的預警系統(tǒng)不能完全滿足安全防護要求,必要時需要派遣反潛分隊護航或?qū)嵤┲攸c警戒,增強保障基地的水下防護能力。

近年來反潛兵力的分配使用逐漸得到重視,文獻[4]認為反潛作戰(zhàn)的主要任務是稀缺反潛資源的調(diào)度及路徑規(guī)劃,并利用隱馬爾可夫模型對反潛調(diào)度進行了數(shù)學建模,并提出了一個2階段進化算法對模型進行求解;文獻[5]利用時序相關(guān)策略解決反潛資源的分配問題,它基于零和博弈理論建立了反潛資源調(diào)度模型,利用整數(shù)規(guī)劃算法對其求解;文獻[6]針對反潛資源分配問題,建立了一個非零和雙人網(wǎng)絡(luò)阻斷博弈模型,并采用強斯塔克爾伯格均衡策略進行了求解;文獻[7-8]運用解析法建立了區(qū)域防潛的兵力配置模型;文獻[9]設(shè)計了無人潛航器的優(yōu)化反潛路徑;文獻[10-11]利用多目標規(guī)劃算法解決作戰(zhàn)資源分配問題。以上文獻對本文具有較大的啟發(fā),但都沒有從保障基地角度來研究反潛資源分配問題。

針對保障基地的反潛問題,本文主要思路如下:

(1) 把保障基地的水下攻防看作不完全信息的動態(tài)博弈過程,建立擴展形式博弈模型。

(2) 當對敵方缺乏先驗知識時,視其為理性對手,以納什均衡解作為反潛資源的調(diào)度策略。在攻防規(guī)模較小時,提出了相應的線性規(guī)劃算法計算調(diào)度策略的精確解;當攻防規(guī)模較大時,提出了改進虛擬遺憾最小(counterfactual regret minimization,CFR)迭代算法計算近似解。

(3) 如果對敵方攻擊策略具有一定了解或敵方攻擊具有一定約束時,視其為有限理性對手,以魯棒性最優(yōu)反應解作為我方反潛資源的推薦策略,同樣提出了求解精確解的線性規(guī)劃算法和求解近似解的迭代算法。

1 問題描述

我方對象包括:

(1) 海上利益區(qū)域:包括油氣田、沖突島礁、海上交戰(zhàn)區(qū)域、海上基地等;

(2) 保障基地:前進基地或預置基地,甚至可擴展為運輸航路以及海上補給區(qū)等,為海上利益區(qū)域提供支持;

(3) 反潛資源:由多個反潛分隊組成,當保障基地受到水下滲透或攻擊時,提供搜潛和反潛支持,其組成包括反潛直升機、潛艇、無人潛航器(unmanned underwater vehicle, UUV)等。

敵方對象包括:

(1) 水下滲透兵力:對我方保障基地實施水下滲透偵察,包括UUV、潛艇、蛙人、水下固定或移動傳感設(shè)備等;

(2) 攻擊兵力:敵方艦艇部隊,對我方海上利益區(qū)域?qū)嵤┕?損壞我方利益。

約束假設(shè)如下:

(1) 保障基地就近保障,可簡化為對保障半徑之內(nèi)海區(qū)提供后裝或兵力支持;

(2) 為了就近保障,保障基地可以直接部署在海上利益區(qū)域內(nèi),本身也可看作我方利益區(qū)域;

(3) 保障基地也具有反潛反滲透能力,例如裝備有水下聲納陣列等傳感器設(shè)備,并能夠定期巡航搜潛,但是,由于存在水下惡劣環(huán)境及敵方破壞等因素干擾,聲納設(shè)備可能失效,另外搜潛也存在時間間隔,這些情況都會導致預警誤差;

(4) 專設(shè)反潛資源有限,本文假設(shè)我方反潛資源能夠同時提供支持的基地數(shù)量不超過;

(5) 敵方水下滲透兵力有上限,能夠同時突破我方防護而滲透成功的保障基地數(shù)量不超過;

(6) 敵方攻擊兵力有上限,能同時攻擊我方利益區(qū)域的數(shù)量為。

敵方活動過程分析如下。

敵方在對我方利益區(qū)域攻擊前,為削弱破壞我方防御能力,首先對我方保障基地實施滲透,滲透過程包括:

(1) 試探階段:分派水下滲透兵力對我方保障基地試探偵察,尋找水下防御漏洞,該階段甚至可能包含佯攻;

(2) 潛伏階段:如果試探失敗,意味滲透兵力被基地防護層發(fā)現(xiàn)定位后捕獲或驅(qū)逐;如果試探成功,則表明滲透兵力成功突破我方基地反潛防護,成功實施潛伏,并能夠?qū)ξ曳交剡M行監(jiān)視,甚至在必要時發(fā)動主動攻擊;

(3) 攻擊階段:敵方攻擊兵力從我方利益區(qū)域中選擇目標實施破壞或攻擊。

我方防御過程如下:

保障基地平時依靠自身裝備的水下防御體系實施預警及反潛。當發(fā)現(xiàn)可疑通信信號或水下不明物體時,則有可能被敵方試探,如果無法通過基地附屬預警系統(tǒng)定位敵方目標,需要向反潛指揮部門請求支援,由其派遣專設(shè)反潛兵力前來搜索。

從以上敵我雙方攻擊防御過程可以看出,圍繞保障基地展開的水下攻防存在較大不確定性,當有多個保障基地發(fā)出支援請求時,反潛指揮部門需要有一種高效的調(diào)度方法,分配有限的反潛資源增援保障基地。

2 博弈模型

2.1 參數(shù)說明

:利益區(qū)域集合;

:敵方攻擊目標集合,為我方利益區(qū)域集合的子集;

:保障基地集合;

:發(fā)出反潛請求的保障基地集合;

:可能受到滲透的保障基地集合;

:敵方一次能夠?qū)嵤┧鹿舻谋Ｕ匣丶?

:我方專設(shè)反潛分隊的數(shù)量;

:保障基地防護系統(tǒng)預警成功概率。

為了更好地反映水下攻防過程的不確定性,本文引入了2個集合和。由于水下環(huán)境惡劣以及海況變化較大,保障基地水下防護系統(tǒng)(由聲納陣等組成)的預警精度會受到不同程度影響,可能會出現(xiàn)預警漏洞。在我方察覺并修復漏洞之前,敵方有可能發(fā)現(xiàn)利用這些漏洞進行滲透,因此本文把這些出現(xiàn)預警漏洞的保障基地用表示。同樣,保障基地也難以預知自己對未來滲透的防護能力,為此本文用表示需要反潛支援的基地集合,另外用表示保障基地成功檢測到敵方一次滲透行為的概率。

2.2 博弈過程建模

水下攻防過程可以用擴展形式的零和博弈表示,該過程可以劃分為4個階段:① 我方選址部署保障基地;② 敵方從保障基地集合中選擇滲透目標;③ 我方分配反潛分隊;④ 敵方選擇我方利益區(qū)域發(fā)動攻擊。為了反映攻防的不確定性,本文在敵我雙方?jīng)Q策之間增設(shè)了機會玩家,由其表示敵我雙方信息的不對稱,如圖1所示。

圖1 水下攻防博弈樹模型Fig.1 Underwater game tree model

該過程也可以用不完全信息擴展形式建模,雖然這樣建立的博弈樹層次較少,問題描述更為簡潔,但每一層的動作空間更為復雜,因此整個博弈樹的規(guī)模并未得到減小,而且導致運算復雜性更高。

圖1中方塊為玩家1,表示我方,即防守方;三角形為玩家2,表示敵方,即攻擊方;圓形為玩家0,表示機會玩家。

2.3 攻防博弈樹模型的分析說明

本節(jié)利用一個基準想定對圖1提出的博弈樹模型進行說明。在基準想定中:設(shè), 為博弈樹第層第方玩家(=0,1,2;=0,1,…,6)可執(zhí)行的動作集合。在本文的基準想定中,設(shè)||=10,即存在10個利益區(qū),={,,…,};設(shè)||=6,即存在6個保障基地,={,,…,};設(shè)||=4,表示可能出現(xiàn)防守漏洞的基地數(shù)量為4;設(shè)||=4,它表示可能會發(fā)出增援請求的基地數(shù)量為4;設(shè)||=2,它表示敵方能夠攻擊的基地數(shù)量為2;設(shè)=2,它表示我方專設(shè)反潛分隊數(shù)量為2,即我方可調(diào)度對象數(shù)量為2;我方利益區(qū)數(shù)量||=10。

博弈樹第4層反映基地水下防護系統(tǒng)預警能力的不確定性,主體為機會玩家,無決策能力,所以不設(shè)置信息集,動作數(shù)量為2||。對于基準想定,||=2=4,=[[1,1], [1,2], [2,1], [2,2]],其中1表示預警正確,2表示預警錯誤。如果第3層敵方選擇滲透的基地為[,],則第4層如果選擇動作為[1,2],表示只觀察到被滲透,動作[2,2]則表示沒有一個預警正確,即沒有觀察到任何一個基地被滲透。

2.4 收益函數(shù)的設(shè)計

收益函數(shù)表達式為()=((),()),其中=(,),為玩家1即我方的動作序列或策略,為玩家2即敵方的動作序列,根據(jù)擴展形式博弈的性質(zhì),非完全動作的收益為0,即博弈樹中非葉子節(jié)點的收益()=(0,0)。

設(shè)為保障矩陣,如果基地負責保障第號利益區(qū)域,則=1,否則為0,一個基地可以保障多個利益區(qū)域,一個利益區(qū)域也可以被多個基地保障。另外設(shè)為利益區(qū)域的重要性或價值,()表示序列攻擊的利益區(qū)域集合,()表示序列攻擊的基地集合,()表示序列防守的利益區(qū)域集合,()表示序列防守的基地集合,則敵方收益函數(shù)設(shè)計如下:

(1)

式中:為保障基地保障利益區(qū)域的概率,其定義如下:

(2)

式中:第1項=0表示配屬關(guān)系中基地不保障利益區(qū)域;第2項∈()且?()表示基地被敵方攻擊且未得到增援,此時基地無法保障利益區(qū)域;第3項表示基地沒有被敵方滲透攻擊,表示基地對利益區(qū)域保障成功的概率;第4項表示基地被敵方攻擊且同時被我方反潛支隊增援的情況,表示敵方有效攻擊的概率,表示我方有效防御的概率,、和可以通過歷史數(shù)據(jù)或?qū)＜以u估得到。

由于水下攻防作戰(zhàn)為零和博弈,所以我方收益與敵方收益相反,即有

()=-()

(3)

為了加快后文提出的求解算法的運算速度,本文在實現(xiàn)時先枚舉所有可能序列,把計算得到的期望收益以矩陣形式保存到文件中。在求解博弈策略時再從文件中讀取到內(nèi)存,作為算法的已知參數(shù)。

本文中,我方的動作數(shù)量為||×||,基準想定中為330×6=1 980,敵方最后一層葉子節(jié)點動作數(shù)量為||×||,基準想定中為1 350×120=16 200,所以最后的收益矩陣大小為1 980×16 200。隨著問題規(guī)模增大,收益矩陣所占空間呈指數(shù)增長,計算復雜度也會呈指數(shù)增加,所以針對中小規(guī)模問題可以采用線性規(guī)劃計算精確解,而對于大規(guī)模問題則需要采用動態(tài)規(guī)劃方法計算近似解。

3 敵方理性情況下的策略求解

3.1 納什均衡的線性規(guī)劃算法

為了采用線性規(guī)劃算法求解納什均衡,本文設(shè)計了3個函數(shù):inf()返回玩家的序列到達的信息集,seq()返回玩家到達信息集的序列,ext()返回玩家從信息集出發(fā)往下走1步的序列集合,在第2節(jié)的博弈樹建立完成后,這3個函數(shù)也容易實現(xiàn)。由于采用純策略(確定性策略)容易被對手發(fā)現(xiàn),所以本文計算混合策略(),它可以看作是玩家在每一個信息集下選擇某動作的條件概率,為規(guī)劃模型的決策變量。求解敵方納什均衡問題的緊湊型線性規(guī)劃模型如下。

目標函數(shù):min()

約束條件如下:

()=1

(4)

()≥0

(5)

(6)

(7)

敵方策略目的是使我方收益最小,即最小化我方總體期望價值,用表示,它也可看作第0層信息集(最高層,樹根)的期望價值,式(4)表示敵方的第1層動作序列只有1個,概率為1。式(5)表示行為策略(執(zhí)行某個動作的概率)大于等于0。式(6)中,為我方處于某一信息集的價值,敵方的每一步動作都是削弱我方價值,所以對于我方而言,我方的上一層信息集價值減去敵方行動方案收益后,大于等于其后擴展信息集集合的價值之和。式(7)用于約束緊接某一信息集所有序列的實現(xiàn)概率之和與進入其父信息集的實現(xiàn)概率相等。式(5)～式(7)實際表示的是約束集合,例如式(7)表示的約束集合中約束數(shù)量為敵方的信息集數(shù)量之和。

我方均衡策略可以通過計算的對偶值得到。

3.2 納什均衡的CFR迭代算法

321 算法的數(shù)學描述

CFR算法通過反復迭代計算各博弈玩家的近似優(yōu)化策略,在描述其實現(xiàn)算法之前,先做如下定義。設(shè)為博弈樹的某一節(jié)點,也可看作從根節(jié)點到當前節(jié)點的一串動作序列,則號玩家在策略下執(zhí)行序列(或可理解為到達節(jié)點)的虛擬價值為

(8)

式中：()表示假設(shè)其他玩家在策略下執(zhí)行序列的概率,這里假設(shè)當前玩家執(zhí)行概率為1,因此結(jié)果為虛擬價值;為葉子節(jié)點;(,)表示從當前節(jié)點執(zhí)行完畢到達葉子節(jié)點的概率;()表示號玩家在葉子節(jié)點的收益。

在當前節(jié)點下沒有執(zhí)行動作的虛擬遺憾值為

(,)=(→,)-(,)

(9)

式中:→表示在到達的信息集下強制執(zhí)行動作的策略,因此稱之為虛擬遺憾值。

在信息集下沒有執(zhí)行動作的虛擬遺憾值為

(10)

式(9)把到達信息集的所有序列的虛擬遺憾值累加,即為該信息集的虛擬遺憾值。

迭代后累計虛擬遺憾值表示為

(11)

式中:為當前迭代次數(shù)。

因為虛擬遺憾值必須為正值,所以調(diào)整后得到玩家的最后虛擬遺憾值為

(12)

322 CFR算法的總體設(shè)計

CFR算法的總體思路如下:

初始化遺憾值為0

(13)

當遺憾值為0時,隨機生成當前策略,否則根據(jù)式(13)生成當前策略,完成步驟2功能的函數(shù)為MatchRegret;

按當前策略進行博弈,生成經(jīng)歷的信息集及信息集下動作的效用,實現(xiàn)該功能的函數(shù)為UpdateUtility;

計算新的遺憾值,實現(xiàn)該功能的函數(shù)為UpdateRegret;

如果沒有滿足終止條件則返回至步驟2。

設(shè)和為2維數(shù)組,分別表示每個信息集下所有可選動作對應的遺憾值和策略。CFR的偽代碼如下:

1: 數(shù)組R和S初始化為02: while(!converged&& (now()-tstart)

CFR開始運行時,數(shù)組初始化為0,意味著起始時的策略為隨機選擇動作,隨著迭代次數(shù)增加,每次調(diào)用UpdateTree函數(shù)后都會使和的值逐步優(yōu)化。這里一個重要問題是如何確定迭代的終止條件,本文采用了相對效用閾值和最大運算時間的混合終止規(guī)則。當我方估算效用的梯度逼近為0時,我方效用取得極值,本文中,估算效用的平滑采樣梯度計算公式如下:

(14)

式中:為迭代次數(shù),當小于某個閾值(本文實驗中設(shè)置為5×10)時,converged變量修改為true。

CFR的步驟5中調(diào)用了UpdateTree函數(shù),它以遞歸調(diào)用的形式完成了式(8)描述的博弈樹中節(jié)點的虛擬價值計算。UpdateTree函數(shù)流程圖如圖2所示。

圖2 UpdateTree函數(shù)流程圖Fig.2 Flow chart of UpdateTree function

圖2中LeafValue算法實現(xiàn)第24節(jié)收益函數(shù)功能,計算步驟如下:

←[6],即中第6層動作選擇的利益區(qū)集;

←[1]和[5]選擇的增援基地集合;

←[2]和[3]選擇的攻擊基地集合;

如果為我方玩家,調(diào)用式(2)返回收益=();如果為敵方玩家,調(diào)用式(1)返回收益=()。

對于機會玩家的動作選擇函數(shù)SelNextAct,本文的實現(xiàn)方法是:如果處于博弈樹第1或2層,從可選動作中隨機選擇;如果處于博弈樹第4層,設(shè)為選擇動作后對應的檢測成功次數(shù),則選擇的概率權(quán)重公式如下:

(15)

323 遺憾值更新及匹配算法的設(shè)計

圖2中UpdateRegret完成式(9)～式(11)的計算,計算步驟如下:

if player()=then∥判斷序列對應的玩家;

for∈() do∥遍歷信息集下所有動作;

[]←[]+[]-∥更新遺憾值;

[]←[]+[]×∥更新策略。

圖2中MatchRegret完成了式(12)和式(13)的計算,由于2維數(shù)組中存儲了迭代后累計虛擬遺憾值(見式(11)),所以按照式(12)從中取出大于0的遺憾值,并按式(13) 生成當前策略并返回。

324 效用更新算法的設(shè)計

圖2中UpdateUtility函數(shù)流程圖如圖3所示,根據(jù)式(8)計算虛擬價值。

圖3 UpdateUtility函數(shù)流程圖Fig.3 Flow chart of UpdateUtility function

325 遺憾值更新算法的修改

第323節(jié)采用了相等權(quán)重的遺憾值更新步長,相對于可調(diào)節(jié)步長的CFR改進算法,例如CFR+,其收斂速度相對較慢。本文在CFR+算法基礎(chǔ)上做了進一步改進,CFR+算法在CFR算法的迭代之間修改步長,沒有充分利用信息集的決策能力,為此本文在信息集決策級別調(diào)節(jié)步長,引入了3個預設(shè)調(diào)節(jié)參數(shù),即,和,利用(1+)調(diào)節(jié)正遺憾值的累加,利用(1+) 調(diào)節(jié)負遺憾值的累加,利用(1+)調(diào)節(jié)策略的更新。

修改后UpdateRegret的計算步驟如下:

4 敵方行動約束下的策略求解

第3節(jié)提出的計算方法適用于理性對手,即研究如何在最壞情況下取得最優(yōu)效果。但在某些情況下,例如受到我方基地選址、海洋氣候、戰(zhàn)略戰(zhàn)術(shù)選擇以及武器裝備等因素限制,導致敵方行為受到某種約束,這時應該采取對手理性受限時的最優(yōu)反應規(guī)劃算法,以期取得更大效果。

4.1 對手行為約束下的最優(yōu)反應線性規(guī)劃

這種情況下,我方雖然不能取得對方的精確策略,但可以從戰(zhàn)例數(shù)據(jù)或反潛專家經(jīng)驗等多種渠道獲取一定的先驗知識。為了反映這種對敵方行動的先驗預判,本文在第31節(jié)納什均衡線性規(guī)劃算法的約束條件下增設(shè)了以下1個約束集:

()≥and()≤

(16)

也就是表示對手策略(),即執(zhí)行某動作的概率分布,處于某一范圍。

4.2 對手行為約束下的CFR算法

本文主要從以下3個方面對第32節(jié)的CFR算法進行了修改。

421 遺憾值匹配算法的修改

在零和博弈中一個好的優(yōu)化策略應該做到兩方面的平衡:當對手是理性對手時(最壞情況),也可理解為對對手行為沒有了解時,盡量減少己方弱點的曝露,即減少自己的被利用率;當對手非理性(存在行為約束時),也可理解為對對手行為具有一定了解,能夠建立一定的對手行為模型,則應該盡量增加對對手弱點的利用率,提高效用。

本文采取的方法就是在納什均衡策略和最優(yōu)反應策略之間折中,即建立這樣一個策略:概率采用最優(yōu)反應策略,(1-)概率采用納什均衡策略,通過修改來改變策略性能,可以在對對手的利用率和己方被利用率之間平衡。

為此設(shè)置了對手預估策略()和調(diào)整權(quán)重(),當敵方對手到達某信息集時,它有()概率的可能按()預估的策略行動,也有(1-())的可能按其他策略行動,修改后MatchRegret的流程圖描述如圖4所示。其中為||維數(shù)組,表示不同信息集下實現(xiàn)納什均衡策略和最優(yōu)反應策略之間的調(diào)整權(quán)重。為||×|()|的矩陣,表示敵方對手不同信息集下執(zhí)行動作∈()的預估概率,即敵方行為模型。

圖4 修改后MatchRegret函數(shù)流程圖Fig.4 Flow chart of modified MatchRegret

422 效用更新算法的修改

(17)

約束為

()≤0

(18)

式中:函數(shù)集表示式(4)～式(7)以及式(16)的約束關(guān)系。為了方便在虛擬遺憾值最小算法中計算該優(yōu)化問題,本文利用拉格朗日算子對式(17)和式(18)進行轉(zhuǎn)換,把約束優(yōu)化問題轉(zhuǎn)換為無約束優(yōu)化問題:

(19)

式中:為個約束關(guān)系(()表示)對應的拉格朗日算子矢量；為第13節(jié)收益函數(shù)表示的收益矩陣。

下面對式(19)按、和共3個方向計算梯度。

(20)

式中:為迭代次數(shù);可以用梯度下降方式進行迭代更新:

(21)

同時也需要對圖3描述的UpdateUtility函數(shù)進行修改,當為對手玩家時,第3步[]←′替換為

(22)

例如本文實驗中對敵方策略的約束主要為式(16)描述的兩種形式,可進一步表達為

()=-()+≤0 and()=()-≤0

(23)

5 仿真分析

5.1 仿真參數(shù)設(shè)置

仿真硬件平臺采用聯(lián)想ThinkSystem SR650,CPU為Xeon 4210R 2.4 GHz 20核,內(nèi)存容量為256 GB。軟件采用了C++/Python并行優(yōu)化工具箱(pagmo)作為計算平臺。

仿真基準想定的參數(shù)設(shè)定如第23節(jié)所述,為了計算第24節(jié)描述的收益矩陣,基地對利益區(qū)域保障成功的概率設(shè)置為09,敵方有效攻擊的概率設(shè)置為02,我方有效防御的概率設(shè)為07,保障基地成功檢測到敵方一次滲透行為的概率設(shè)為08。利益區(qū)域的分布及對應的重要性價值如圖5所示,為了計算方便,利益區(qū)域之間距離進行了歸一化處理,其中三角形符號表示的利益區(qū)域代表其同時部署了保障基地。通過圖5以1次博弈過程為例進行說明。假設(shè)根據(jù)圖1博弈樹,第1階段和第2階段機會玩家隨機策略影響的基地為{,,,},考慮基地增援概率較低,基地離其他基地較遠,第3階段敵方選擇攻擊這2個基地。第4階段機會玩家代表保障基地預警系統(tǒng)的檢測概率,假設(shè)沒有檢測到水下攻擊。第5階段我方采取保守策略,因為和的價值較高,所以選擇增援和。第6階段時,考慮到受到水下攻擊,所以敵方選擇攻擊保障的利益區(qū)域,即、和(與合駐)。

圖5 基準想定的歸一化利益區(qū)域分布和對應價值Fig.5 Normalized interest area distribution and corresponding value of the benchmark scenario

在敵方非理性策略模擬方面,采用純策略,每一個信息集下采取第1個動作的概率為1,為了增加不確定性,為其增加了一個均值為0,標準差為002的抖動,在實戰(zhàn)仿真環(huán)境下,敵方純策略及不確定性集可以由仿真數(shù)據(jù)或?qū)＜乙詤^(qū)間集的形式提供。

為了描述,第31節(jié)描述的納什均衡線性規(guī)劃算法簡寫為NLP,第32節(jié)描述的納什均衡虛擬遺憾最小算法簡寫為NCFR,第4.1節(jié)描述的最優(yōu)反應線性規(guī)劃算法簡寫為BRLP,第4.2.1節(jié)描述的改進算法簡寫為RMCFR, 第4.2.2節(jié)描述的改進算法簡寫為UUCFR。

5.2 算法時間開銷分析

利用第51節(jié)描述的仿真平臺,約3 h能夠計算出基準想定的收益矩陣。收益矩陣的預計算結(jié)束后,策略的計算時間可控制在秒級。

對于虛擬遺憾最小算法,仿真實驗設(shè)置的時限為12 min,式(14)中當閾值設(shè)置為5×10。在敵方理性情況下,圖6描述了隨著問題規(guī)模變化,即利益區(qū)域數(shù)量從7增加到15,NLP和NCFR的計算時間。對于基準想定,NLP在46 s內(nèi)完成計算,NCFR算法在29 s內(nèi)完成計算。當利益區(qū)域數(shù)量超過13時,NLP算法無法在12 s內(nèi)收斂。

圖6 敵方理性情況的計算時間開銷Fig.6 Computation cost with rational opponent

圖7描述了NLP和NCFR計算出的我方效用,因為存在敵方成功入侵的風險,所以我方效用為負值,從圖7可以看出,NCFR在問題規(guī)模較小時能夠取得與NLP基本相同的效用。

圖7 敵方理性情況下的效用Fig.7 Utility value with rational opponent

在敵方行為約束情況下,本文設(shè)置的計算時限為30 min,迭代次數(shù)為25 000次,閾值減小為5×10。從圖8可以看出,CFR算法時間開銷大于線性規(guī)劃,但線性規(guī)劃算法在利益區(qū)域數(shù)量大于13后無法收斂,而且因為敵方非理性情況下算法復雜度提高,所以計算時間要明顯大于敵方理性的情況。

圖8 敵方行為約束下的計算時間開銷Fig.8 Computation cost with behavior constraints

從圖9可以看出CFR計算得到的我方效用與線性規(guī)劃非常接近,不高于3%,所以CFR算法更適用于問題規(guī)模較大的場景。

圖9 敵方行為約束下的效用Fig.9 Utility value with behavior constraints

5.3 算法敏感性分析

為了加快標準CFR算法的收斂,如第321節(jié)所述,本文對遺憾值更新算法進行了改進,引入了3個參數(shù),和。為了檢驗算法的性能改進程度,對這3個參數(shù)的不同組合分別進行了實驗,每種組合運行50次,對計算出的我方效用值取平均,圖10為其中3種組合的敏感性分析。從圖中可以看出=05,=20和=20時算法的收斂速度較快。

圖10 迭代次數(shù)對我方效用的影響Fig.10 Impact of iteration number on our utility

另外,保障基地防護系統(tǒng)預警正確概率對博弈結(jié)果也具有較大影響,為此本文在基準想定下通過NCFR算法測算了當值不同時我方效益的變化情況,如圖11所示,隨著預警正確率的提高,我方效用逐漸增大。

圖11 預警正確率對我方效益的影響Fig.11 Impact of alert accuracy on our utility

5.4 算法性能比較分析

利用第41節(jié)描述的敵方策略模擬方法,分別采用NLP、BRLP、RMCFR和UUCFR進行計算,得到我方策略和對應的期望效用,并以利用率和被利用率作為指標,對以上4種改進算法的性能進行了比較。理性策略應該在具有高利用率的同時還具備較低的被利用率。絕對被利用率的計算公式如下:

式中:(,)為納什均衡下的我方效用,,為對應的策略,可利用第2節(jié)描述的線性規(guī)劃算法或CFR算法得到;(,)為我方采用序列時,敵方采取最優(yōu)反應得到的效用值。因此,相對被利用率計算步驟如下:

分別采用NLP、BRLP、RMCFR和UUCFR算法計算我方策略,且記NLP得到的效用值為;

其中,最優(yōu)反應的計算算法約束公式與納什均衡相同,但目標函數(shù)不同,最優(yōu)反應算法的目標是在給定對方策略情況下最大化我方的期望效用。

圖12顯示了隨著迭代次數(shù)的增加,標準CFR算法在基準想定下的相對被利用率變化情況,迭代次數(shù)越多,優(yōu)化程度越高,被利用率也就隨之降低。

圖12 相對被利用率的變化情況Fig.12 Change of relative exploitability

表1為基準想定下各算法的平均相對利用率和平均相對被利用率,對應的效益分布如圖13所示。

表1 算法相對利用率和被利用率的比較

圖13 不同算法對應的效用分布Fig.13 Utility distribution of different algorithms

其中,相對利用率的計算步驟如下:

與被利用率計算步驟1相同的方式計算得到,且記NLP得到的效用值為;

隨機生成敵方策略;

BRLP線性規(guī)劃算法的利用率和被利用率之比將近10∶1,這表示在對手非理性時,BPLR算法能夠利用對手的弱點,同時在對手完全理性時,所承擔的風險也較小。RMCFR算法的利用率和被利用率基本相等,這表示它與BRLP算法相比,承擔更多風險的同時,得到的效益也較低。UUCFR算法的利用率與被利用率之比接近1∶2,承擔的風險比較大,但它的利用率比RMCFR算法高。NLP最為安全,盡可能防止出錯,但它也無法利用對手的錯誤?？傊?BPLR算法得到的策略質(zhì)量最高,但它的可擴展性較差,RMCFR算法能夠在可擴展性較好的同時取得不錯的策略。

5.5 算法適應性分析

除了性能上的提高,相比標準CFR算法,本文提出的算法在某些關(guān)鍵的決策點上魯棒性更好,即計算出的策略更加明確(信息熵更低)且主動性更強。例如,在基準想定下,具有10個利益區(qū)域和5個保障基地,在博弈樹第4階段機會玩家給出基地防護系統(tǒng)的預警正確率后,我方需要在第5階段計算出反潛分隊的調(diào)度策略,即決定采用6種分配方案(第2.3節(jié)博弈樹第5層描述)的概率。圖14分別給出了標準CFR、RMCFR和UUCFR這3種算法針對這6種分配方案(決策行動)的概率分布。

從圖14可以看出,無論第4階段輸出的結(jié)果如何,標準CFR都在其中3種分配方案上給出較大概率,另外3種方案的執(zhí)行概率基本為0。而RMCFR和UUCFR算法則充分利用了可信程度較高的先驗知識,即敵方會大概率攻擊1號和3號利益區(qū)域,因此不管預警信息結(jié)果如何,在1號分配方案(保護1號和3號利益區(qū)域)上給出較大的執(zhí)行概率。從結(jié)果可以得出結(jié)論,在對敵方行為有較大把握時,從指揮員的角度來看,隨機性較大的方案并不一定最優(yōu),它增加了指揮員的選擇難度。但當敵方行為不確定性較大時,隨機性較大的混合策略意味著少犯錯誤,可能更加合適。

6 結(jié) 論

保障基地的反潛資源調(diào)度問題可以看作是一個大型非完全信息的混合策略博弈,在實際作戰(zhàn)中我方不僅需要考慮預警系統(tǒng)的不確定性誤差,同時也需要面臨不完全情報信息和具有自適應能力對手的挑戰(zhàn)。本文嘗試利用博弈論計算方法解決這2方面問題,并在仿真實驗中取得了預期效果。

本文研究成果還可進一步擴展應用到航母編隊的協(xié)同反潛作戰(zhàn)中,而且本文設(shè)計的博弈結(jié)構(gòu)也適用于實戰(zhàn)中利用統(tǒng)計數(shù)據(jù)學習方法來預測敵方的攻防策略和漏洞。