魏娜, 劉明雍
(1.西北工業(yè)大學(xué) 航海學(xué)院, 陜西 西安 710072; 2.西安石油大學(xué) 電子工程學(xué)院, 陜西 西安 710065)
目標(biāo)分配是作戰(zhàn)對(duì)抗過程中的一個(gè)重要因素,是與國(guó)防相關(guān)的運(yùn)籌學(xué)應(yīng)用中出現(xiàn)的基本問題之一。目標(biāo)分配問題的本質(zhì)就是在作戰(zhàn)過程中按照一定的要求,找到針對(duì)敵方目標(biāo)分配的最佳解決方案,合理地將系統(tǒng)的武器單元分配給多個(gè)目標(biāo),降低系統(tǒng)執(zhí)行任務(wù)的代價(jià),獲取最大的對(duì)抗收益[1]。目標(biāo)分配是一種非線性組合優(yōu)化和非確定性多項(xiàng)式完備問題。作為軍事行動(dòng)研究領(lǐng)域經(jīng)典的約束優(yōu)化問題,受到了各國(guó)研究人員的廣泛關(guān)注,關(guān)于這方面的研究也取得了豐碩的成果。
武從猛、王公寶[2]將遺傳算法生成的粗略解作為蟻群算法的初始信息素,結(jié)合蟻群算法中的并行、正反饋機(jī)制求解了水面艦艇編隊(duì)防空武器的目標(biāo)分配問題,縮短了目標(biāo)分配的決策時(shí)間,提高了解的質(zhì)量。Glotzbach等[3]針對(duì)水下無(wú)人武器的協(xié)同攻擊問題,提出了異構(gòu)無(wú)人艦艇編隊(duì)的協(xié)同視線目標(biāo)跟蹤原理,構(gòu)建了無(wú)人艦艇編隊(duì)的整體控制結(jié)構(gòu),提出了自主艦艇編隊(duì)目標(biāo)視線協(xié)同攻擊的控制準(zhǔn)則和算法。田偉等[4]通過引入隨機(jī)時(shí)間影響網(wǎng)絡(luò)來(lái)分析打擊目標(biāo)與任務(wù)之間的關(guān)系,全面深入地分析了動(dòng)態(tài)目標(biāo)分配問題的約束條件,構(gòu)建了聯(lián)合火力打擊的動(dòng)態(tài)目標(biāo)分配模型,結(jié)合遠(yuǎn)程對(duì)海打擊的案例,通過仿真驗(yàn)證了該方法的有效性。Li等[5]采用了基于分解的多目標(biāo)進(jìn)化算法來(lái)解決基于資產(chǎn)配置最優(yōu)的目標(biāo)分配問題,通過重新設(shè)定配對(duì)限制和選擇操作提高了算法的執(zhí)行效率。Liang和Kang[6]采用自適應(yīng)混沌并行克隆選擇算法,結(jié)合混沌理論與并行種群分類的優(yōu)點(diǎn),實(shí)現(xiàn)了種群初始化和種群更新,解決了軍艦編隊(duì)防空應(yīng)用的目標(biāo)分配問題。王瑋等[7]針對(duì)信息化作戰(zhàn)條件下的海上編隊(duì)目標(biāo)分配問題,在多層防御模式下的目標(biāo)分配模型基礎(chǔ)上,提出了一種基于遺傳算法的交互式方法,用來(lái)求解海上編隊(duì)防空目標(biāo)分配問題。Jia等[8]根據(jù)目標(biāo)的位置和防御區(qū)域的半徑進(jìn)行防御區(qū)域分析,結(jié)合覆蓋狀態(tài)和覆蓋層數(shù),提出多階段攻擊規(guī)劃方法,將傳統(tǒng)的武器目標(biāo)分配方法與多階段武器目標(biāo)分配方法進(jìn)行比較,驗(yàn)證了所提方法的有效性。
現(xiàn)有的研究成果大多從參與對(duì)抗的一方角度出發(fā)進(jìn)行分析,而實(shí)際的對(duì)抗是一個(gè)雙方交互的行為。博弈對(duì)抗開始時(shí),對(duì)抗雙方都不知道對(duì)方會(huì)采取何種行動(dòng),在只考慮一方收益最大條件下獲得的最優(yōu)策略,必定是以對(duì)方采取某一特定策略為前提。若這一策略有損對(duì)方自己的利益,則對(duì)方并不會(huì)采取。此時(shí),單方求解得到的最優(yōu)策略并不具備存在條件。另外,交戰(zhàn)雙方各自的AUV都有自己的攻擊力類型,根據(jù)攻擊力的大小可分為高殺傷性類型和低殺傷性類型。因此,不同類型的AUV在進(jìn)行對(duì)抗時(shí),表現(xiàn)出來(lái)的博弈情形也會(huì)不同。雖然敵我雙方交戰(zhàn)時(shí),各方都知道自己的AUV攻擊力類型,但是并不清楚對(duì)方會(huì)選擇哪種攻擊力類型的AUV執(zhí)行打擊任務(wù)。這意味著當(dāng)對(duì)抗真正開始時(shí),對(duì)抗雙方不能完全了解作戰(zhàn)局勢(shì)中的所有信息,并不清楚究竟會(huì)體現(xiàn)為哪種博弈形式。這種在進(jìn)行博弈時(shí),局中人對(duì)除了自己以外的其他局中人的類型、策略空間或收益函數(shù)等信息并不完全了解的情況下進(jìn)行的博弈就屬于不完全信息博弈。
本文針對(duì)AUV博弈對(duì)抗中的信息不完全問題,以不完全信息博弈理論為基礎(chǔ),利用海薩尼轉(zhuǎn)換,通過引入虛擬參與人“自然”[9],先選擇出AUV類型(高殺傷性AUV或低殺傷性AUV),從而將博弈過程中局中人的事前不確定性轉(zhuǎn)變?yōu)椴┺拈_始后的行動(dòng)不確定性,將未知成本的不完全信息博弈轉(zhuǎn)化為關(guān)于“自然”的行動(dòng)不確定博弈。
AUV的博弈對(duì)抗是一種非合作形式、信息不完全、多階段的動(dòng)態(tài)博弈過程。在雙方進(jìn)行攻防對(duì)抗時(shí),參與對(duì)抗的各方并不能完全了解與當(dāng)前博弈相關(guān)的信息。雖然雙方同時(shí)行動(dòng),但各方都沒有機(jī)會(huì)觀察到對(duì)方的行動(dòng)選擇,因此,不可能確切知道對(duì)手究竟會(huì)選擇什么樣的策略,屬于不完全信息博弈問題。
貝葉斯博弈是關(guān)于不完全信息博弈的一種建模方式,也是不完全信息博弈的標(biāo)準(zhǔn)式描述。本文要尋找AUV博弈對(duì)抗不完全信息下的目標(biāo)分配最優(yōu)策略,實(shí)際上就是求解不完全信息博弈下取得的貝葉斯納什均衡。
在一個(gè)貝葉斯博弈過程G={I,T,P,S,U}中,局中人i(i∈I)的一個(gè)策略是從局中人i的類型集Ti到其策略集Si(Ti)的一個(gè)映射。
設(shè)Ui表示除了局中人i的其他局中人采用策略S-i時(shí),局中人i在類型為Ti時(shí),選擇策略Si時(shí)的期望效用收益,則有
Ui=∑Pi(T-i|Ti)Ui(Si,S-i(T-i),Ti)
(1)
式中:S-i(T-i)表示其他局中人在給定類型T-i時(shí),策略S-i確定的行動(dòng)組合。


(2)

本文以對(duì)抗雙方的剩余生存概率和武器消耗量為評(píng)價(jià)指標(biāo),加入位置誤差影響因子,建立了面向不完全信息的AUV博弈對(duì)抗目標(biāo)分配模型。繼而,以貝葉斯納什均衡理論為基礎(chǔ),預(yù)先設(shè)置關(guān)于攻防策略類型的先驗(yàn)概率,選擇出待分配的AUV類型,然后通過后驗(yàn)概率不斷修正關(guān)于對(duì)方采用的目標(biāo)分配策略類型的判斷。
設(shè)不完全信息下的AUV博弈對(duì)抗目標(biāo)分配模型用六元組集合描述,如(3)式所示

(3)
I={A,D}為博弈局中人的空間,A為攻擊方,D為防御方,這里的博弈空間中還引入了一個(gè)“自然(Nature)”作為虛擬參與人。
T={TA,TD}為AUV博弈對(duì)抗中A方和D方的目標(biāo)分配策略類型空間。其中,TA為A方采取的策略類型集,TD為D方采取的策略類型集。TA對(duì)于攻擊方A而言已知,但對(duì)于防御方D而言,其所選的策略類型為一個(gè)隨機(jī)變量,即參與博弈對(duì)抗的局中人i(i∈I={A,D}),觀測(cè)到“自然(Nature)”對(duì)于自己目標(biāo)分配策略類型Ti的選擇,而對(duì)于其他局中人選擇何種策略類型局中人i并不知道。同理,TD對(duì)于防御方D而言已知,但對(duì)于攻擊方A而言,其所選的策略類型為一個(gè)隨機(jī)變量。但是,TA,TD的概率分布情況對(duì)于雙方而言是共同知識(shí),即局中人i(i∈I={A,D})具有其他局中人(用-i表示)選擇類型的推斷。
S={SA,SD}是AUV博弈對(duì)抗目標(biāo)分配的策略集,SA={SA1,SA2,…,SAn}是A方的目標(biāo)分配策略集,SD={SD1,SD2,…,SDn}是D方的目標(biāo)分配策略集。




(4)
式中:ShA(k)為A方在第k個(gè)戰(zhàn)斗步之前的歷史策略集合;SAi(k)為A方在第k個(gè)戰(zhàn)斗步的策略;P(TAi|ShA(k))為A方在歷史策略集ShA(k)的條件下,對(duì)選取類型TAi的先驗(yàn)推斷;P(SAi(k)|TAi,ShA(k))為A方在第k個(gè)戰(zhàn)斗步時(shí),在采取歷史策略集ShA(k)的前提下,選取策略SAi(k)的概率。


(5)
式中:ShD(k)為D方在第k個(gè)戰(zhàn)斗步之前的歷史策略集合;SDj(k)為D方在第k個(gè)戰(zhàn)斗步的策略。P(TDj|ShD(k))為D方在歷史策略集ShD(k)的條件下,對(duì)選取類型TDj的先驗(yàn)推斷;P(SDj(k)|TDj,ShD(k))為D方在第k個(gè)戰(zhàn)斗步時(shí),在采取歷史策略集ShD(k)的前提下,選取策略SDj(k)的概率。
U={UA,UD}是攻擊方A和防御方D的效用收益。
AUV博弈對(duì)抗目標(biāo)分配一個(gè)戰(zhàn)斗步的博弈樹如圖1所示。

圖1 AUV博弈對(duì)抗目標(biāo)分配一個(gè)戰(zhàn)斗步的博弈樹
從圖1可以看出,在博弈對(duì)抗開始前,引入了一個(gè)虛擬參與人,我們稱之為“自然”。它以PA1,PA2,…,PAn的概率對(duì)A方的AUV類型進(jìn)行選擇,這個(gè)概率分布是A、D方的共同知識(shí)。接下來(lái),在A方選定類型下的AUV中選擇合適的AUV對(duì)D方目標(biāo)進(jìn)行選擇打擊,D方在下一步觀察到A方的攻擊策略后,對(duì)A方的類型進(jìn)行概率修正,并以此為基礎(chǔ)對(duì)A方進(jìn)行目標(biāo)分配。雙方就在這樣的交互過程中完成目標(biāo)分配策略的選擇。
把AUV博弈對(duì)抗的目標(biāo)分配過程看做是一個(gè)不完全信息的多階段博弈過程,整個(gè)博弈過程分為k個(gè)階段,k∈N+,A方和D方關(guān)于目標(biāo)分配的策略選擇交互進(jìn)行。在進(jìn)行效用收益計(jì)算時(shí),如果第k個(gè)戰(zhàn)斗回合的博弈結(jié)果達(dá)到了所在階段的最優(yōu)效果,則該戰(zhàn)斗回合的效用收益可以完全計(jì)入到博弈對(duì)抗的總效用收益,即不存在博弈效用收益折扣。反之,如果第k個(gè)戰(zhàn)斗回合的博弈結(jié)果未達(dá)到所在階段的最優(yōu)效果,則在計(jì)算博弈對(duì)抗的總效用收益時(shí),需要去除掉該戰(zhàn)斗回合的效用收益折損,即博弈效用收益具有折扣率。不失一般性,本文中討論的對(duì)抗雙方在博弈過程中沒有收益折扣,即博弈收益沒有折損。
定義決策變量δij來(lái)表征AUVi和目標(biāo)AUVj之間的映射關(guān)系。攻擊方的AUV編隊(duì)由WA個(gè)AUV組成,防御方的AUV編隊(duì)由WD個(gè)AUV組成。即,分配執(zhí)行攻擊任務(wù)的AUV總數(shù)量為WA,分配執(zhí)行防御任務(wù)的AUV總數(shù)量為WD。目標(biāo)分配方案可以用決策向量矩陣δ表示,分量δij=1時(shí)表示第i個(gè)AUV被分配給第j個(gè)攻擊目標(biāo),δij=0時(shí)表示第i個(gè)AUV未分配給第j個(gè)攻擊目標(biāo),且滿足

(8)
選擇敵方剩余威脅概率最小和AUV數(shù)量消耗最少作為評(píng)價(jià)目標(biāo)分配策略效用收益的指標(biāo),則第k個(gè)戰(zhàn)斗回合下的目標(biāo)分配策略效用收益為
UD(k)為第k個(gè)戰(zhàn)斗回合對(duì)抗后D方的剩余生存概率,UA(k)為第k個(gè)戰(zhàn)斗回合對(duì)抗后A方的剩余生存概率。WA為整個(gè)對(duì)抗過程中A方總的AUV消耗,WD為整個(gè)對(duì)抗過程中D方總的AUV消耗。WA(k)為第k個(gè)戰(zhàn)斗回合時(shí)A方消耗的AUV數(shù)量,WD(k)為第k個(gè)戰(zhàn)斗回合時(shí)D方消耗的AUV數(shù)量。KP是毀傷閾值。γ為位置誤差影響因子,定義為目標(biāo)實(shí)際位置與探測(cè)到的位置的比值,通過位置誤差影響因子取值的不同,來(lái)反映位置誤差對(duì)AUV目標(biāo)分配策略選擇結(jié)果的影響。
本節(jié)針對(duì)不完全信息下AUV對(duì)抗目標(biāo)分配的最優(yōu)策略選擇問題,結(jié)合其離散化的特點(diǎn),在上述建立的不完全信息目標(biāo)分配模型的基礎(chǔ)上,提出了以多目標(biāo)離散粒子群為基礎(chǔ)的面向不完全信息目標(biāo)分配貝葉斯納什均衡策略的求解算法。
AUV博弈對(duì)抗期間,每個(gè)AUV被分配一次,每個(gè)目標(biāo)至少被一個(gè)AUV攻擊。通過使用自然數(shù)編碼的形式,將自然數(shù)編碼與分配給攻擊目標(biāo)的AUV編號(hào)相對(duì)應(yīng),確立粒子與待求解目標(biāo)分配策略之間的映射關(guān)系。每個(gè)粒子按照待攻擊目標(biāo)順序排列的AUV標(biāo)號(hào)組成,其列向量上的數(shù)值與優(yōu)化過程中分配給目標(biāo)的AUV標(biāo)號(hào)相對(duì)應(yīng)。每個(gè)粒子都是一種可能的目標(biāo)分配方案,其長(zhǎng)度等于待攻擊目標(biāo)的總數(shù)。
因?yàn)槟繕?biāo)分配問題中的變量不具備連續(xù)的性質(zhì),所以將適用于求解連續(xù)變量的基本粒子群算法中的粒子速度更新公式進(jìn)行重新定義,將粒子速度定義為粒子位置改變的概率[11],使其適用于求解離散問題的情況。
粒子位置的更新由三部分組成,分別為:慣性部分、自我認(rèn)知部分、社會(huì)認(rèn)知部分,如(15)式所示
pid(t)),pg(t))
(15)

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

圖2 粒子位置置換操作示意圖
在進(jìn)行目標(biāo)交叉操作時(shí),需要引入第二個(gè)中間變量Ψ(t),令Ψ(t)=F2(Φ(t),pid(t))。然后產(chǎn)生一個(gè)[0,1]之間的隨機(jī)數(shù)r2,將r2與c1相比較,如果r2 (17) 粒子自我認(rèn)知部分與個(gè)體極值的交叉過程如圖3所示。 圖3 粒子與個(gè)體極值的交叉操作 (18) 粒子社會(huì)認(rèn)知部分與全局極值的交叉過程如圖4所示。 圖4 粒子與全局極值的交叉操作 在迭代過程中,pid(t)和pg(t)持續(xù)更新,最終輸出值pg(t)即為全局最優(yōu)解。 算法程序流程圖如圖5所示。 圖5 不完全信息下目標(biāo)分配策略的貝葉斯納什均衡求解 假設(shè)A方AUV編隊(duì)由15艘攻擊力不同的AUV組成,要對(duì)D方10個(gè)目標(biāo)(這10個(gè)目標(biāo)已經(jīng)由傳感器探測(cè)得到)進(jìn)行攻擊,按照毀傷能力的大小將AUV分為高殺傷性和低殺傷性2種類型。仿真參數(shù)如表1所示。 仿真中AUV的毀傷概率值是作為基礎(chǔ)數(shù)據(jù)讀取的,其取值不會(huì)對(duì)文中所提算法產(chǎn)生實(shí)質(zhì)性影響。另外,由于獲取實(shí)際的水下AUV毀傷概率參數(shù)存在較大困難,所以對(duì)本論文中的毀傷概率參數(shù)進(jìn)行了模擬設(shè)定。設(shè)定每個(gè)AUV對(duì)不同目標(biāo)的毀傷概率如表2所示(表2中上一行為A方對(duì)D方的毀傷概率,下一行為D方對(duì)A方的毀傷概率)。 表1 AUV不完全信息博弈目標(biāo)分配仿真參數(shù) 表2 A方、D方的毀傷概率 在相同初始環(huán)境條件、不同種群規(guī)模和迭代次數(shù)下,采用基于MODPSO算法和基于NSGA-Ⅱ算法求解算例,分別運(yùn)行50次后,得到的算法平均運(yùn)行時(shí)間如表3所示。 表3 平均運(yùn)行時(shí)間 由表3可以看出,在不同種群規(guī)模和迭代次數(shù)下,基于MODPSO算法的求解運(yùn)行時(shí)間均小于基于NSGA-Ⅱ算法的求解運(yùn)行時(shí)間。 在相同初始條件下,迭代次數(shù)都是100次時(shí),采用基于MODPSO的算法和基于NSGA-Ⅱ的算法求解算例得到的適應(yīng)度函數(shù)平均值曲線如圖6所示。 圖6 適應(yīng)度函數(shù)平均值曲線 從圖6中可以看出,基于MODPSO算法的適應(yīng)度函數(shù)平均值曲線在40代附近趨于收斂,基于NSGA-Ⅱ算法的適應(yīng)度函數(shù)平均值曲線在40代處仍有下降趨勢(shì),尚未收斂。從求解快速性的角度上來(lái)講,基于MODPSO的算法比基于NSGA-Ⅱ的算法更具優(yōu)勢(shì)。 不同種群規(guī)模下,分別采用2種算法得到的目標(biāo)分配策略,A方和D方的剩余生存概率情況如表4所示。(為了消除仿真模擬中的隨機(jī)特性,對(duì)每種算法都進(jìn)行了100次的獨(dú)立試驗(yàn),統(tǒng)計(jì)得到2種算法下對(duì)抗雙方剩余生存概率的平均值)。 表4 A方和D方的剩余生存概率 由表4可以看出,在不同種群規(guī)模下,基于MODPSO算法求解得到的A、D方的剩余生存概率值比基于NSGA-Ⅱ算法得到的A、D方的剩余生存概率值小,說明采用MODPSO算法得到的對(duì)抗雙方目標(biāo)分配策略方案對(duì)敵方的攻擊力更強(qiáng),對(duì)抗毀傷效果更好。由表4中還可以看出,無(wú)論采用哪種算法,A方的剩余生存概率始終高于D方的剩余生存概率,因此,A、D雙方的對(duì)抗結(jié)果為A方獲勝。 SP測(cè)度是一種衡量所得到的非劣解在解空間均勻分布情況的指標(biāo)。SP值越小,表明Pareto解分布越均勻。在群體規(guī)模為100,迭代次數(shù)為100的條件下,算法分別獨(dú)立運(yùn)行50次,SP測(cè)度值的統(tǒng)計(jì)結(jié)果如圖7所示: 圖7 帕累托最優(yōu)解集的分布均勻性 由圖7所示的箱體圖可以看出,基于MODPSO算法得到的箱體圖區(qū)間比基于NSGA-Ⅱ算法得到的箱體圖區(qū)間小。基于MODPSO算法得到的SP測(cè)度均值為0.040 6,方差為0.005 9,基于NSGA-Ⅱ算法得到的SP測(cè)度均值為0.070 3,方差為0.013 1。因此,基于MODPSO算法求解面向不完全信息的AUV對(duì)抗目標(biāo)分配問題得到的Pareto最優(yōu)解分布,相較基于NSGA-Ⅱ算法得到的Pareto最優(yōu)解分布更加均勻和穩(wěn)定。 1.2節(jié)中建立的面向不完全信息的目標(biāo)分配模型中加入了位置誤差影響因子,其值越大表示目標(biāo)位置的測(cè)量值與實(shí)際值的偏差越嚴(yán)重。圖8給出了位置誤差影響因子的取值在不同范圍內(nèi),滿足毀傷閾值0.9的條件下,對(duì)AUV對(duì)抗目標(biāo)分配策略選擇的影響。 圖8 不同位置誤差影響因子下的AUV消耗 圖8中的橫坐標(biāo)為位置誤差影響因子的變化情況,縱坐標(biāo)為消耗的AUV數(shù)量。可以看出,當(dāng)位置誤差影響因子低于0.005時(shí),其策略選擇近似等于理想狀態(tài),此時(shí)分配10個(gè)AUV就可以達(dá)到作戰(zhàn)預(yù)期。當(dāng)位置誤差影響因子在0.005~0.024 5時(shí),需要增加AUV數(shù)量至12。當(dāng)位置誤差影響因子在0.024 5~0.027 4時(shí), 需要增加AUV數(shù)量至14。當(dāng)位置誤差影響因子為0.027 5時(shí),需要將編隊(duì)中的15個(gè)AUV全部分配出去才能完成打擊任務(wù)。若位置誤差影響因子高于0.027 5時(shí),即使將整個(gè)編隊(duì)中的AUV全部分配對(duì)目標(biāo)進(jìn)行打擊,也不能完成對(duì)目標(biāo)的預(yù)期毀傷效果。位置誤差影響因子取值越大,在進(jìn)行目標(biāo)分配時(shí),達(dá)到同樣的毀傷效果消耗的AUV數(shù)量越多。 本文對(duì)面向不完全信息博弈的AUV對(duì)抗目標(biāo)分配決策問題進(jìn)行了研究。把對(duì)抗雙方看作博弈的局中人,將AUV對(duì)目標(biāo)的映射關(guān)系作為局中人博弈可選的策略集合。基于貝葉斯納什均衡的非合作博弈模型,建立了不完全信息下的AUV博弈對(duì)抗目標(biāo)分配模型。根據(jù)AUV目標(biāo)分配策略不連續(xù)的特點(diǎn),提出了一種基于多目標(biāo)離散粒子群的不完全信息目標(biāo)分配貝葉斯納什均衡策略的求解算法,用粒子位置代表目標(biāo)的候選策略,將粒子速度定義為粒子位置改變的概率,以適應(yīng)決策變量的離散特征。仿真結(jié)果表明,所建立的面向不完全信息的AUV博弈對(duì)抗目標(biāo)分配模型能夠較好地反映AUV的對(duì)抗局勢(shì),所得到的目標(biāo)分配策略可以根據(jù)指揮官的決策偏好為其提供策略選擇幫助。




3 仿真結(jié)果與分析


3.1 算法比較及目標(biāo)分配結(jié)果分析



3.2 貝葉斯納什均衡解分布均勻性的SP測(cè)度評(píng)價(jià)

3.3 位置誤差對(duì)目標(biāo)分配策略選擇的影響

4 結(jié) 論