基于貝葉斯納什均衡的不完全信息博弈目標分配決策

魏娜, 劉明雍

(1.西北工業大學 航海學院, 陜西 西安 710072; 2.西安石油大學 電子工程學院, 陜西 西安 710065)

目標分配是作戰對抗過程中的一個重要因素，是與國防相關的運籌學應用中出現的基本問題之一。目標分配問題的本質就是在作戰過程中按照一定的要求，找到針對敵方目標分配的最佳解決方案，合理地將系統的武器單元分配給多個目標，降低系統執行任務的代價，獲取最大的對抗收益[1]。目標分配是一種非線性組合優化和非確定性多項式完備問題。作為軍事行動研究領域經典的約束優化問題，受到了各國研究人員的廣泛關注，關于這方面的研究也取得了豐碩的成果。

武從猛、王公寶[2]將遺傳算法生成的粗略解作為蟻群算法的初始信息素，結合蟻群算法中的并行、正反饋機制求解了水面艦艇編隊防空武器的目標分配問題，縮短了目標分配的決策時間，提高了解的質量。Glotzbach等[3]針對水下無人武器的協同攻擊問題，提出了異構無人艦艇編隊的協同視線目標跟蹤原理，構建了無人艦艇編隊的整體控制結構，提出了自主艦艇編隊目標視線協同攻擊的控制準則和算法。田偉等[4]通過引入隨機時間影響網絡來分析打擊目標與任務之間的關系，全面深入地分析了動態目標分配問題的約束條件，構建了聯合火力打擊的動態目標分配模型，結合遠程對海打擊的案例，通過仿真驗證了該方法的有效性。Li等[5]采用了基于分解的多目標進化算法來解決基于資產配置最優的目標分配問題，通過重新設定配對限制和選擇操作提高了算法的執行效率。Liang和Kang[6]采用自適應混沌并行克隆選擇算法，結合混沌理論與并行種群分類的優點，實現了種群初始化和種群更新，解決了軍艦編隊防空應用的目標分配問題。王瑋等[7]針對信息化作戰條件下的海上編隊目標分配問題，在多層防御模式下的目標分配模型基礎上，提出了一種基于遺傳算法的交互式方法，用來求解海上編隊防空目標分配問題。Jia等[8]根據目標的位置和防御區域的半徑進行防御區域分析，結合覆蓋狀態和覆蓋層數，提出多階段攻擊規劃方法，將傳統的武器目標分配方法與多階段武器目標分配方法進行比較，驗證了所提方法的有效性。

現有的研究成果大多從參與對抗的一方角度出發進行分析，而實際的對抗是一個雙方交互的行為。博弈對抗開始時，對抗雙方都不知道對方會采取何種行動，在只考慮一方收益最大條件下獲得的最優策略，必定是以對方采取某一特定策略為前提。若這一策略有損對方自己的利益，則對方并不會采取。此時，單方求解得到的最優策略并不具備存在條件。另外，交戰雙方各自的AUV都有自己的攻擊力類型，根據攻擊力的大小可分為高殺傷性類型和低殺傷性類型。因此，不同類型的AUV在進行對抗時，表現出來的博弈情形也會不同。雖然敵我雙方交戰時，各方都知道自己的AUV攻擊力類型，但是并不清楚對方會選擇哪種攻擊力類型的AUV執行打擊任務。這意味著當對抗真正開始時，對抗雙方不能完全了解作戰局勢中的所有信息，并不清楚究竟會體現為哪種博弈形式。這種在進行博弈時，局中人對除了自己以外的其他局中人的類型、策略空間或收益函數等信息并不完全了解的情況下進行的博弈就屬于不完全信息博弈。

本文針對AUV博弈對抗中的信息不完全問題，以不完全信息博弈理論為基礎，利用海薩尼轉換，通過引入虛擬參與人“自然”[9]，先選擇出AUV類型(高殺傷性AUV或低殺傷性AUV)，從而將博弈過程中局中人的事前不確定性轉變為博弈開始后的行動不確定性，將未知成本的不完全信息博弈轉化為關于“自然”的行動不確定博弈。

1 面向不完全信息的AUV目標分配模型的構建

1.1 AUV博弈對抗中的不完全信息博弈

AUV的博弈對抗是一種非合作形式、信息不完全、多階段的動態博弈過程。在雙方進行攻防對抗時，參與對抗的各方并不能完全了解與當前博弈相關的信息。雖然雙方同時行動，但各方都沒有機會觀察到對方的行動選擇，因此，不可能確切知道對手究竟會選擇什么樣的策略，屬于不完全信息博弈問題。

貝葉斯博弈是關于不完全信息博弈的一種建模方式，也是不完全信息博弈的標準式描述。本文要尋找AUV博弈對抗不完全信息下的目標分配最優策略，實際上就是求解不完全信息博弈下取得的貝葉斯納什均衡。

在一個貝葉斯博弈過程G={I,T,P,S,U}中，局中人i(i∈I)的一個策略是從局中人i的類型集Ti到其策略集Si(Ti)的一個映射。

設Ui表示除了局中人i的其他局中人采用策略S-i時，局中人i在類型為Ti時，選擇策略Si時的期望效用收益，則有

Ui=∑Pi(T-i|Ti)Ui(Si,S-i(T-i),Ti)

(1)

式中：S-i(T-i)表示其他局中人在給定類型T-i時，策略S-i確定的行動組合。

(2)

本文以對抗雙方的剩余生存概率和武器消耗量為評價指標，加入位置誤差影響因子，建立了面向不完全信息的AUV博弈對抗目標分配模型。繼而，以貝葉斯納什均衡理論為基礎，預先設置關于攻防策略類型的先驗概率，選擇出待分配的AUV類型，然后通過后驗概率不斷修正關于對方采用的目標分配策略類型的判斷。

1.2 面向不完全信息的AUV目標分配模型的構建

設不完全信息下的AUV博弈對抗目標分配模型用六元組集合描述，如(3)式所示

(3)

I={A,D}為博弈局中人的空間，A為攻擊方，D為防御方，這里的博弈空間中還引入了一個“自然(Nature)”作為虛擬參與人。

T={TA,TD}為AUV博弈對抗中A方和D方的目標分配策略類型空間。其中，TA為A方采取的策略類型集，TD為D方采取的策略類型集。TA對于攻擊方A而言已知，但對于防御方D而言，其所選的策略類型為一個隨機變量，即參與博弈對抗的局中人i(i∈I={A,D})，觀測到“自然(Nature)”對于自己目標分配策略類型Ti的選擇，而對于其他局中人選擇何種策略類型局中人i并不知道。同理，TD對于防御方D而言已知，但對于攻擊方A而言，其所選的策略類型為一個隨機變量。但是，TA,TD的概率分布情況對于雙方而言是共同知識，即局中人i(i∈I={A,D})具有其他局中人(用-i表示)選擇類型的推斷。

S={SA,SD}是AUV博弈對抗目標分配的策略集，SA={SA1,SA2,…,SAn}是A方的目標分配策略集，SD={SD1,SD2,…,SDn}是D方的目標分配策略集。

(4)

式中：ShA(k)為A方在第k個戰斗步之前的歷史策略集合；SAi(k)為A方在第k個戰斗步的策略；P(TAi|ShA(k))為A方在歷史策略集ShA(k)的條件下,對選取類型TAi的先驗推斷；P(SAi(k)|TAi,ShA(k))為A方在第k個戰斗步時,在采取歷史策略集ShA(k)的前提下,選取策略SAi(k)的概率。

(5)

式中：ShD(k)為D方在第k個戰斗步之前的歷史策略集合；SDj(k)為D方在第k個戰斗步的策略。P(TDj|ShD(k))為D方在歷史策略集ShD(k)的條件下,對選取類型TDj的先驗推斷；P(SDj(k)|TDj,ShD(k))為D方在第k個戰斗步時,在采取歷史策略集ShD(k)的前提下,選取策略SDj(k)的概率。

U={UA,UD}是攻擊方A和防御方D的效用收益。

AUV博弈對抗目標分配一個戰斗步的博弈樹如圖1所示。

圖1 AUV博弈對抗目標分配一個戰斗步的博弈樹

從圖1可以看出,在博弈對抗開始前,引入了一個虛擬參與人,我們稱之為“自然”。它以PA1,PA2,…,PAn的概率對A方的AUV類型進行選擇,這個概率分布是A、D方的共同知識。接下來,在A方選定類型下的AUV中選擇合適的AUV對D方目標進行選擇打擊,D方在下一步觀察到A方的攻擊策略后,對A方的類型進行概率修正,并以此為基礎對A方進行目標分配。雙方就在這樣的交互過程中完成目標分配策略的選擇。

把AUV博弈對抗的目標分配過程看做是一個不完全信息的多階段博弈過程,整個博弈過程分為k個階段,k∈N+,A方和D方關于目標分配的策略選擇交互進行。在進行效用收益計算時,如果第k個戰斗回合的博弈結果達到了所在階段的最優效果,則該戰斗回合的效用收益可以完全計入到博弈對抗的總效用收益,即不存在博弈效用收益折扣。反之,如果第k個戰斗回合的博弈結果未達到所在階段的最優效果,則在計算博弈對抗的總效用收益時,需要去除掉該戰斗回合的效用收益折損,即博弈效用收益具有折扣率。不失一般性,本文中討論的對抗雙方在博弈過程中沒有收益折扣,即博弈收益沒有折損。

定義決策變量δij來表征AUVi和目標AUVj之間的映射關系。攻擊方的AUV編隊由WA個AUV組成,防御方的AUV編隊由WD個AUV組成。即,分配執行攻擊任務的AUV總數量為WA,分配執行防御任務的AUV總數量為WD。目標分配方案可以用決策向量矩陣δ表示,分量δij=1時表示第i個AUV被分配給第j個攻擊目標,δij=0時表示第i個AUV未分配給第j個攻擊目標,且滿足

(8)

選擇敵方剩余威脅概率最小和AUV數量消耗最少作為評價目標分配策略效用收益的指標,則第k個戰斗回合下的目標分配策略效用收益為

UD(k)為第k個戰斗回合對抗后D方的剩余生存概率,UA(k)為第k個戰斗回合對抗后A方的剩余生存概率。WA為整個對抗過程中A方總的AUV消耗,WD為整個對抗過程中D方總的AUV消耗。WA(k)為第k個戰斗回合時A方消耗的AUV數量,WD(k)為第k個戰斗回合時D方消耗的AUV數量。KP是毀傷閾值。γ為位置誤差影響因子,定義為目標實際位置與探測到的位置的比值,通過位置誤差影響因子取值的不同,來反映位置誤差對AUV目標分配策略選擇結果的影響。

2 不完全信息下目標分配貝葉斯納什均衡策略求解

本節針對不完全信息下AUV對抗目標分配的最優策略選擇問題,結合其離散化的特點,在上述建立的不完全信息目標分配模型的基礎上,提出了以多目標離散粒子群為基礎的面向不完全信息目標分配貝葉斯納什均衡策略的求解算法。

AUV博弈對抗期間,每個AUV被分配一次,每個目標至少被一個AUV攻擊。通過使用自然數編碼的形式,將自然數編碼與分配給攻擊目標的AUV編號相對應,確立粒子與待求解目標分配策略之間的映射關系。每個粒子按照待攻擊目標順序排列的AUV標號組成,其列向量上的數值與優化過程中分配給目標的AUV標號相對應。每個粒子都是一種可能的目標分配方案,其長度等于待攻擊目標的總數。

因為目標分配問題中的變量不具備連續的性質,所以將適用于求解連續變量的基本粒子群算法中的粒子速度更新公式進行重新定義,將粒子速度定義為粒子位置改變的概率[11],使其適用于求解離散問題的情況。

粒子位置的更新由三部分組成,分別為:慣性部分、自我認知部分、社會認知部分,如(15)式所示

pid(t)),pg(t))

(15)

(16)

粒子慣性部分位置置換過程如圖2所示。

圖2 粒子位置置換操作示意圖

在進行目標交叉操作時,需要引入第二個中間變量Ψ(t),令Ψ(t)=F2(Φ(t),pid(t))。然后產生一個[0,1]之間的隨機數r2,將r2與c1相比較,如果r2

(17)

粒子自我認知部分與個體極值的交叉過程如圖3所示。

圖3 粒子與個體極值的交叉操作

(18)

粒子社會認知部分與全局極值的交叉過程如圖4所示。

圖4 粒子與全局極值的交叉操作

在迭代過程中,pid(t)和pg(t)持續更新,最終輸出值pg(t)即為全局最優解。

算法程序流程圖如圖5所示。

圖5 不完全信息下目標分配策略的貝葉斯納什均衡求解

3 仿真結果與分析

假設A方AUV編隊由15艘攻擊力不同的AUV組成，要對D方10個目標(這10個目標已經由傳感器探測得到)進行攻擊，按照毀傷能力的大小將AUV分為高殺傷性和低殺傷性2種類型。仿真參數如表1所示。

仿真中AUV的毀傷概率值是作為基礎數據讀取的，其取值不會對文中所提算法產生實質性影響。另外，由于獲取實際的水下AUV毀傷概率參數存在較大困難，所以對本論文中的毀傷概率參數進行了模擬設定。設定每個AUV對不同目標的毀傷概率如表2所示(表2中上一行為A方對D方的毀傷概率，下一行為D方對A方的毀傷概率)。

表1 AUV不完全信息博弈目標分配仿真參數

表2 A方、D方的毀傷概率

3.1 算法比較及目標分配結果分析

在相同初始環境條件、不同種群規模和迭代次數下，采用基于MODPSO算法和基于NSGA-Ⅱ算法求解算例，分別運行50次后，得到的算法平均運行時間如表3所示。

表3 平均運行時間

由表3可以看出，在不同種群規模和迭代次數下，基于MODPSO算法的求解運行時間均小于基于NSGA-Ⅱ算法的求解運行時間。

在相同初始條件下，迭代次數都是100次時，采用基于MODPSO的算法和基于NSGA-Ⅱ的算法求解算例得到的適應度函數平均值曲線如圖6所示。

圖6 適應度函數平均值曲線

從圖6中可以看出，基于MODPSO算法的適應度函數平均值曲線在40代附近趨于收斂，基于NSGA-Ⅱ算法的適應度函數平均值曲線在40代處仍有下降趨勢，尚未收斂。從求解快速性的角度上來講，基于MODPSO的算法比基于NSGA-Ⅱ的算法更具優勢。

不同種群規模下，分別采用2種算法得到的目標分配策略，A方和D方的剩余生存概率情況如表4所示。(為了消除仿真模擬中的隨機特性，對每種算法都進行了100次的獨立試驗，統計得到2種算法下對抗雙方剩余生存概率的平均值)。

表4 A方和D方的剩余生存概率

由表4可以看出，在不同種群規模下，基于MODPSO算法求解得到的A、D方的剩余生存概率值比基于NSGA-Ⅱ算法得到的A、D方的剩余生存概率值小，說明采用MODPSO算法得到的對抗雙方目標分配策略方案對敵方的攻擊力更強，對抗毀傷效果更好。由表4中還可以看出，無論采用哪種算法，A方的剩余生存概率始終高于D方的剩余生存概率，因此，A、D雙方的對抗結果為A方獲勝。

3.2 貝葉斯納什均衡解分布均勻性的SP測度評價

SP測度是一種衡量所得到的非劣解在解空間均勻分布情況的指標。SP值越小，表明Pareto解分布越均勻。在群體規模為100，迭代次數為100的條件下，算法分別獨立運行50次，SP測度值的統計結果如圖7所示：

圖7 帕累托最優解集的分布均勻性

由圖7所示的箱體圖可以看出，基于MODPSO算法得到的箱體圖區間比基于NSGA-Ⅱ算法得到的箱體圖區間小。基于MODPSO算法得到的SP測度均值為0.040 6，方差為0.005 9，基于NSGA-Ⅱ算法得到的SP測度均值為0.070 3，方差為0.013 1。因此，基于MODPSO算法求解面向不完全信息的AUV對抗目標分配問題得到的Pareto最優解分布，相較基于NSGA-Ⅱ算法得到的Pareto最優解分布更加均勻和穩定。

3.3 位置誤差對目標分配策略選擇的影響

1.2節中建立的面向不完全信息的目標分配模型中加入了位置誤差影響因子，其值越大表示目標位置的測量值與實際值的偏差越嚴重。圖8給出了位置誤差影響因子的取值在不同范圍內，滿足毀傷閾值0.9的條件下，對AUV對抗目標分配策略選擇的影響。

圖8 不同位置誤差影響因子下的AUV消耗

圖8中的橫坐標為位置誤差影響因子的變化情況，縱坐標為消耗的AUV數量。可以看出，當位置誤差影響因子低于0.005時，其策略選擇近似等于理想狀態，此時分配10個AUV就可以達到作戰預期。當位置誤差影響因子在0.005～0.024 5時，需要增加AUV數量至12。當位置誤差影響因子在0.024 5～0.027 4時, 需要增加AUV數量至14。當位置誤差影響因子為0.027 5時，需要將編隊中的15個AUV全部分配出去才能完成打擊任務。若位置誤差影響因子高于0.027 5時，即使將整個編隊中的AUV全部分配對目標進行打擊，也不能完成對目標的預期毀傷效果。位置誤差影響因子取值越大，在進行目標分配時，達到同樣的毀傷效果消耗的AUV數量越多。

4 結 論

本文對面向不完全信息博弈的AUV對抗目標分配決策問題進行了研究。把對抗雙方看作博弈的局中人，將AUV對目標的映射關系作為局中人博弈可選的策略集合。基于貝葉斯納什均衡的非合作博弈模型，建立了不完全信息下的AUV博弈對抗目標分配模型。根據AUV目標分配策略不連續的特點，提出了一種基于多目標離散粒子群的不完全信息目標分配貝葉斯納什均衡策略的求解算法，用粒子位置代表目標的候選策略，將粒子速度定義為粒子位置改變的概率，以適應決策變量的離散特征。仿真結果表明，所建立的面向不完全信息的AUV博弈對抗目標分配模型能夠較好地反映AUV的對抗局勢，所得到的目標分配策略可以根據指揮官的決策偏好為其提供策略選擇幫助。