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

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

0 引 言

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

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

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

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

(2) 當對敵方缺乏先驗知識時,視其為理性對手,以納什均衡解作為反潛資源的調度策略。在攻防規(guī)模較小時,提出了相應的線性規(guī)劃算法計算調度策略的精確解;當攻防規(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、潛艇、蛙人、水下固定或移動傳感設備等;

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

約束假設如下:

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

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

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

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

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

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

敵方活動過程分析如下。

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

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

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

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

我方防御過程如下:

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

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

2 博弈模型

2.1 參數(shù)說明

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

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

:保障基地集合;

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

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

:敵方一次能夠實施水下攻擊的保障基地集合;

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

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

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

2.2 博弈過程建模

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

()=-()

(3)

為了加快后文提出的求解算法的運算速度,本文在實現(xiàn)時先枚舉所有可能序列,把計算得到的期望收益以矩陣形式保存到文件中。在求解博弈策略時再從文件中讀取到內存,作為算法的已知參數(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ī)劃算法求解納什均衡,本文設計了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)算法之前,先做如下定義。設為博弈樹的某一節(jié)點,也可看作從根節(jié)點到當前節(jié)點的一串動作序列,則號玩家在策略下執(zhí)行序列(或可理解為到達節(jié)點)的虛擬價值為

(8)

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

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

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

(9)

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

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

(10)

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

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

(11)

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

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

(12)

322 CFR算法的總體設計

CFR算法的總體思路如下:

初始化遺憾值為0

(13)

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

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

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

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

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

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

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

(14)

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

CFR的步驟5中調用了UpdateTree函數(shù),它以遞歸調用的形式完成了式(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]選擇的攻擊基地集合;

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

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

(15)

323 遺憾值更新及匹配算法的設計

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

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

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

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

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

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

324 效用更新算法的設計

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

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

325 遺憾值更新算法的修改

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

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

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

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

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

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

()≥and()≤

(16)

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

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

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

421 遺憾值匹配算法的修改

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

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

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

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

422 效用更新算法的修改

(17)

約束為

()≤0

(18)

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

(19)

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

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

(20)

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

(21)

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

(22)

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

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

(23)

5 仿真分析

5.1 仿真參數(shù)設置

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

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

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

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

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

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

在敵方行為約束情況下,本文設置的計算時限為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)預警正確概率對博弈結果也具有較大影響,為此本文在基準想定下通過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算法得到的策略質量最高,但它的可擴展性較差,RMCFR算法能夠在可擴展性較好的同時取得不錯的策略。

5.5 算法適應性分析

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

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

6 結 論

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

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