曾 斌, 王 睿, 李厚樸, 張鴻強(qiáng)

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

0 引 言

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

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

針對(duì)保障基地的反潛問(wèn)題,本文主要思路如下:

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

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

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

1 問(wèn)題描述

我方對(duì)象包括:

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

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

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

敵方對(duì)象包括:

(1) 水下滲透兵力:對(duì)我方保障基地實(shí)施水下滲透?jìng)刹?包括UUV、潛艇、蛙人、水下固定或移動(dòng)傳感設(shè)備等;

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

約束假設(shè)如下:

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

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

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

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

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

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

敵方活動(dòng)過(guò)程分析如下。

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

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

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

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

我方防御過(guò)程如下:

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

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

2 博弈模型

2.1 參數(shù)說(shuō)明

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

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

:保障基地集合;

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

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

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

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

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

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

2.2 博弈過(guò)程建模

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

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

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

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

2.3 攻防博弈樹(shù)模型的分析說(shuō)明

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

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

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

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

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

(1)

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

(2)

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

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

()=-()

(3)

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

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

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

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

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

目標(biāo)函數(shù):min()

約束條件如下:

()=1

(4)

()≥0

(5)

(6)

(7)

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

我方均衡策略可以通過(guò)計(jì)算的對(duì)偶值得到。

3.2 納什均衡的CFR迭代算法

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

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

(8)

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

在當(dāng)前節(jié)點(diǎn)下沒(méi)有執(zhí)行動(dòng)作的虛擬遺憾值為

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

(9)

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

在信息集下沒(méi)有執(zhí)行動(dòng)作的虛擬遺憾值為

(10)

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

迭代后累計(jì)虛擬遺憾值表示為

(11)

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

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

(12)

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

CFR算法的總體思路如下:

初始化遺憾值為0

(13)

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

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

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

如果沒(méi)有滿足終止條件則返回至步驟2。

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

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

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

(14)

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

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

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

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

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

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

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

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

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

(15)

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

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

if player()=then∥判斷序列對(duì)應(yīng)的玩家;

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

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

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

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

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

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

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

325 遺憾值更新算法的修改

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

修改后UpdateRegret的計(jì)算步驟如下:

4 敵方行動(dòng)約束下的策略求解

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

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

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

()≥and()≤

(16)

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

4.2 對(duì)手行為約束下的CFR算法

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

421 遺憾值匹配算法的修改

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

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

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

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

422 效用更新算法的修改

(17)

約束為

()≤0

(18)

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

(19)

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

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

(20)

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

(21)

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

(22)

例如本文實(shí)驗(yàn)中對(duì)敵方策略的約束主要為式(16)描述的兩種形式,可進(jìn)一步表達(dá)為

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

(23)

5 仿真分析

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

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

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

圖5 基準(zhǔn)想定的歸一化利益區(qū)域分布和對(duì)應(yīng)價(jià)值Fig.5 Normalized interest area distribution and corresponding value of the benchmark scenario

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

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

5.2 算法時(shí)間開(kāi)銷分析

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

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

圖6 敵方理性情況的計(jì)算時(shí)間開(kāi)銷Fig.6 Computation cost with rational opponent

圖7描述了NLP和NCFR計(jì)算出的我方效用,因?yàn)榇嬖跀撤匠晒θ肭值娘L(fēng)險(xiǎn),所以我方效用為負(fù)值,從圖7可以看出,NCFR在問(wèn)題規(guī)模較小時(shí)能夠取得與NLP基本相同的效用。

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

在敵方行為約束情況下,本文設(shè)置的計(jì)算時(shí)限為30 min,迭代次數(shù)為25 000次,閾值減小為5×10。從圖8可以看出,CFR算法時(shí)間開(kāi)銷大于線性規(guī)劃,但線性規(guī)劃算法在利益區(qū)域數(shù)量大于13后無(wú)法收斂,而且因?yàn)閿撤椒抢硇郧闆r下算法復(fù)雜度提高,所以計(jì)算時(shí)間要明顯大于敵方理性的情況。

圖8 敵方行為約束下的計(jì)算時(shí)間開(kāi)銷Fig.8 Computation cost with behavior constraints

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

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

5.3 算法敏感性分析

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

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

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

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

5.4 算法性能比較分析

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

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

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

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

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

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

表1為基準(zhǔn)想定下各算法的平均相對(duì)利用率和平均相對(duì)被利用率,對(duì)應(yīng)的效益分布如圖13所示。

表1 算法相對(duì)利用率和被利用率的比較

圖13 不同算法對(duì)應(yīng)的效用分布Fig.13 Utility distribution of different algorithms

其中,相對(duì)利用率的計(jì)算步驟如下:

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

隨機(jī)生成敵方策略;

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

5.5 算法適應(yīng)性分析

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

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

6 結(jié) 論

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

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