二分圖匹配模型下的武器目標分配問題

呂 娜, 王茂桓, 鐘元芾, 張英朝, 孫 蕾

(中山大學系統科學與工程學院, 廣東 廣州 510275)

0 引 言

武器目標分配(weapon target assignment, WTA)是軍事運籌學領域經典的組合優化問題,其研究的是如何將武器合理分配給對方目標,從而實現理想的作戰打擊效果。近年來,作戰指控人機結合程度不斷提高,現代軍事對抗需要指揮員在人工智能的輔助下更快、更好地做出決策,這對人工智能在復雜多變的戰場態勢下的求解能力提出了要求。對于WTA問題,這種求解能力體現在模型和算法對最優解的搜索能力和求解速度兩個方面。

WTA問題的求解難點在于隨著武器和目標數量的增加,分配方案的數量將呈指數級增加。Lloyd等[1]證明了WTA問題是一個多參數、多約束的整數規劃問題,是非確定性多項式(non-deterministic polynomial, NP)完全問題,這意味著目前沒有一個確定性算法能在多項式時間內找到問題的最優解。

Manne[2]于1958年提出WTA問題的數學模型,并對其進行線性近似求解。至今,WTA問題的算法研究一直是熱點問題之一。根據優化方法的迭代方式不同,求解WTA問題的算法可以分為精確算法和近似算法[3]。使用精確算法如Soland[4]研究了用隱枚舉和分支定界方法求解保護目標的反導彈防御問題。Sikanen[5]提出使用動態規劃的方法求解小規模的WTA問題,提高了求解效率和解的質量。Kim等[6]采用拉格朗日松弛法對問題進行改造,將目標函數分解為3個子問題后進行求解,在一些問題上能夠找到邊界解。Lu等[7]在求解大規模WTA問題中引入了分配上下界,確定了武器支配關系,縮短了列枚舉和分支定界的求解時間。使用近似算法如Wang等[8]通過結合編碼方法和局部搜索算法,提出了離散的灰狼優化算法,適用于不同規模的WTA問題。Chang等[9]對動態WTA問題采用了改進的人工蜂群優化算法,并在種群初始化中引入啟發式因子,提高了求解精度。Kong等[10]提出了改進的多目標粒子群優化算法解決多目標的動態WTA問題,得到的解具有更好的收斂性和分布性。Huangfu等[11]在模型中考慮自適應分組和視場角約束,再采用帶有精英保留策略的遺傳算法求解最優分配問題,證明了該算法求解具有較好的魯棒性。也有部分學者將精確算法與近似算法結合,Ahuja等[12]先借用分支定界算法確定問題下界,再提出了基于網絡流的構造式啟發算法和大規模鄰域搜索方法,實現了對不同規模武器資源的合理分配。常雪凝等[13]將模擬退火(simulated annealing, SA)算法與匈牙利算法結合,求解多階段WTA問題,在保證求解質量的同時減少了求解時間。Leboucher等[14]先使用匈牙利算法求解武器與目標的分配對,再使用遺傳算法與粒子群算法的混合算法求解分配的發射順序。由上述研究可以看出,當前算法在兼顧WTA問題求解的準確性和高效性上有待進一步提高[15]。

近年來,圖論在網絡通信、線性規劃等優化領域中應用廣泛,使用基于圖論的建模方法求解實際問題往往能夠簡化模型,降低計算復雜度,因此,圖論受到眾多研究者的青睞。其中,基于圖論的二分圖匹配建模方法常用于任務分配和調度等優化問題。Huo等[16]從二分圖匹配的角度提出了云工廠間的協作模型,在Kuhn-Munkres(簡稱為KM)算法下可以求出高效的協作策略。Wang等[17]用二分圖匹配輔助空間全卷積網絡進行紅外小目標檢測。Man等[18]在大數據任務的人機協同問題上應用二分圖最優匹配算法,提高了計算機資源的利用率。Chen等[19]利用二分圖匹配提高了自動分配網絡請求與服務的準確性。Ma等[20]將二分圖匹配用于個人社交網絡賬號匹配,具有更高的準確率。Sun等[21]在三維模型的視圖檢索中應用了二分圖匹配方法,有效提高了三視圖與模型匹配的效率。Hashemi等[22]在圖像的多標簽特征選擇問題中使用二分圖匹配,提高了分類的準確性。Beiranvand等[23]提出在圖像的無監督特征選擇上采用二分圖匹配建模,提高了圖像特征選擇的有效性。綜上所述,對實際問題進行二分圖建圖,再使用二分圖匹配模型求解,是一種有效的求解思路。

基于圖論基礎,本文創新性地提出一種精確求解WTA問題的求解框架:首先,使用二分圖匹配建模方法,構建了WTA的二分圖匹配模型。其次,提出一種改進的Kuhn-Munkres WTA(簡稱為KM-WTA)算法,用于對目標模型進行求解。該框架巧妙地利用了WTA問題中主體的可分離性,簡化了原WTA模型中目標函數非線性帶來的難點。同時,KM-WTA算法可以在對WTA問題進行精確求解的基礎上,進一步提升計算速度。對于戰場這種強對抗性和復雜多變的應用環境,本文提出的求解框架具有更好的求解效率和可解釋性。

本文的結構安排如下:第1節在簡要介紹相關圖論基礎后,提出了基于二分圖匹配的WTA模型,并對模型進行優化;第2節給出了結合貪心策略的KM-WTA算法,以及相應的求解流程;第3節通過仿真實驗驗證模型和算法的有效性,并對本文算法和其他算法的計算能力進行分析對比;第4節對全文做出總結,提出了對WTA問題的研究展望。

1 基于二分圖匹配的WTA模型構建

由于WTA問題是多項式復雜程度的非確定性(non-deterministic polynomial, NP)完全問題,傳統的精確算法計算時間太長,以元啟發式算法為代表的近似算法求解精度又無法保證。本文提出基于二分圖匹配,對WTA問題構建模型,可以將模型自然簡化為無約束規劃問題。

1.1 圖論基礎

圖論[24]是研究離散對象間關系的一個數學分支,圖論中的圖并不只局限于描述幾何中的圖像,某些具體事物及其之間的聯系也可以抽象為圖,這種圖一般由一些點和點之間的連線構成。在圖中,將這些點叫做頂點,將頂點間的連線叫做邊,一般頂點的集合用V表示,邊的集合用E表示,因此圖G可以簡記為G=(V,E)。而二分圖是圖論中一種特殊的模型,若簡單圖G的頂點集合可以分為兩個互不相交的非空集合V1和V2,使得圖G中每一條邊與其關聯的兩個頂點分別在X和Y中,則稱圖G為一個二分圖,記作G=(X,Y,E)。若X中的每個頂點與Y中的每個頂點相關聯,且只與Y中的頂點相關聯,則稱該圖為完全二分圖。一個簡單的完全二分圖如圖1所示。

圖1 完全二分圖Fig.1 Complete bipartite graph

從圖G=(V,E)的邊集E中選取一個子集M,若M中任意兩條邊互不相鄰,則稱M是G的一個匹配;若對圖G的任何匹配M′,均有|M′|≤|M|,則稱M為G的最大匹配。進一步地,若圖G是二分圖,可以表示為G=(X,Y,E),且其中X的每一個頂點都與M中的一條邊相關聯,則稱M是二分圖G的完全匹配。特別地,當|X|=|Y|時,M是G的完美匹配?？紤]一個加權的完全二分圖G=(X,Y,E,W),其中X={x1,x2,…,xt},Y={y1,y2,…,ys},W=(wij),i=1,2,…,t,j=1,2,…,s,表示邊xiyj的權重,滿足匹配中所有邊權之和最大的匹配M即為最優匹配。

1.2 問題分析與建模

WTA問題假設現有己方武器m個,需要在較短時間內完成對n個對方目標的打擊,每個目標的威脅程度記為vj;Pij表示己方武器i對目標j的毀傷效率。WTA問題要確定的是武器與目標間的分配關系,使作戰打擊后對方目標對己方可產生的威脅程度最小化。

WTA問題與二分圖模型的對應關系如圖2所示。參與分配的主體可以明確分為兩類,己方武器集合W和敵方目標集合T,等價于完全二分圖G=(X,Y,E,W)中的兩個獨立點子集X和Y。武器與目標之間的連線代表了不同武器打擊不同目標的毀傷效率,在二分圖中體現為X與Y之間有權重W的邊集E。

圖2 WTA問題與二分圖的對應關系Fig.2 Corresponding relationship of WTA problem and bipartite graph

基于二分圖匹配的WTA模型構建的核心在于決策變量的轉換。傳統的WTA問題的變量是m×n個0-1決策變量Xij,Xij取值為1時代表將武器i分配給目標j,否則武器i與目標j之間沒有打擊關系,在確定所有打擊關系后再計算總體威脅,得到目標函數值。而基于二分圖匹配的WTA模型將目標威脅的計算提前到決策變量的確定階段,先計算每個目標分別被每個武器打擊后的威脅,將其作為加權二分圖的權重,接下來只需要選擇E的子集M,并對M中的邊權求和,即可得到目標函數值。

1.3 符號說明和假設

為了便于模型的描述與分析,相關的參數和變量說明如表1所示。

表1 參數與變量符號說明

同時為了便于模型求解,本文提出以下假設:

假設 1在求解過程中,目標和武器數量均已知并不會發生變化。

假設 2每個武器對每個目標的毀傷概率已知。

假設 3每個武器只打擊一個目標,每個目標也只被打擊一次。

1.4 數學模型構建

由于本文所構建的模型是通過將武器分配打擊目標,盡可能減少對方可能造成的威脅,下面給出了以最小化對方目標被打擊后的總體威脅程度為優化目標函數的數學模型:

(1)

wij=vj(1-Pij)

(2)

M={xiyj|Xij=1}

(3)

(4)

(5)

Xij∈{0,1},?i∈{1,2,…,m};?j∈{1,2,…,n}

(6)

模型中,式(1)為目標函數,表示所有目標被打擊后的總體威脅程度;式(2)～式(6)為約束條件,其中式(2)表示目標j被武器i打擊后的威脅程度,式(3)表示集合M由具有打擊關系的邊構成,式(4)和式(5)約束了每個武器只打擊一個目標,且每個目標只被打擊一次,式(6)是0-1決策變量約束。

1.5 模型優化改進

考慮到二分圖匹配問題的特殊性,為了便于進一步求解,對上述數學模型提出進一步優化改進。

(1) 根據第1.1節中匹配的定義,匹配中的任意兩條邊都不相鄰,因此當集合M是一個匹配時,自然滿足了上述模型中的式(4)和式(5),即每個武器打擊一個目標且每個目標只被一個武器打擊。

(2) 為了便于應用二分圖匹配模型的算法求解,需要滿足條件|X|=|Y|,于是本文提出了一種補全方法,如圖3所示。當武器數量與目標數量不等時,通過補全矩陣使對應二分圖的邊權矩陣為方陣。

以圖3為例,當武器數(m=4)大于目標數(n=3)時,增加(m-n)個虛擬目標,在邊權矩陣中增加(m-n)列,其中每一列取值均為0(由于虛擬目標并不存在實際的威脅)。若最后得到的匹配中包含某條邊頂點為該虛擬目標,則表示這條邊上的相應武器不需要打擊。當武器數(m=3)小于目標數(n=4)時,增加(n-m)個虛擬武器,在邊權矩陣中增加(n-m)行,其中每一行的第j個值為vj(虛擬武器對目標沒有毀傷概率)。若最后得到的匹配中包含某條邊頂點為該虛擬武器,則表示這條邊上的相應目標未被打擊。

圖3 邊權矩陣的補全Fig.3 Completion of margin weight matrix

最后,由于通常完全加權二分圖最優匹配所求得的是具有最大權的匹配,而WTA問題的目標是最小化函數值,因此對上述矩陣W取相反數,即可將其轉化為最大化問題。

綜上所述,本文提出的模型式(1)～式(6) 可以進一步簡化為

(7)

(8)

式中:a=max{m,n};M是完全二分圖G=(X,Y,E,W)的一個匹配。

2 KM-WTA求解算法

KM算法是求解二分圖最優匹配的經典算法,但在大規模匹配問題中,該算法計算效率太低。為提高算法求解不同規模問題的速度,本文將在求解加權完全二分圖的最優匹配的KM算法的基礎上求解WTA問題,下面首先對KM算法的原理和算法流程進行介紹,再提出對該算法的改進和相應的計算流程。

2.1 KM算法原理

KM算法是由Kuhn和Munkres提出的在加權完全二分圖中求取最優匹配的有效算法[24]。算法采用給圖中頂點賦值的方法,即圖論中的可行點標號,從圖中任一頂點開始賦值,使得一條邊上的兩個頂點被賦值之和恰好等于邊權(即相等子圖)。在該相等子圖中用匈牙利算法尋找最大匹配,若該匹配恰好是完美匹配,那么該匹配就是待求問題的最優匹配;否則需要對可行點標號進行更新再重復上述過程,直至找到最優匹配。

KM算法的步驟如下。

步驟1以任取的可行點標號l作為開始,確定l相等子圖Gl,且在Gl中選取任一匹配M。

步驟2從M出發,利用匈牙利算法求相等子圖Gl的最大匹配M′。若M′是完美匹配,則M′就是最優匹配,計算結束;否則,進入步驟3。

再返回步驟1。

KM算法的流程圖如圖4所示。

圖4 KM算法流程圖Fig.4 Flowchart of the KM algorithm

其中,匈牙利算法是二分圖求最大匹配問題的經典算法之一,由匈牙利數學家Egervary提出。這一算法基于Berge匹配定理,對于任意一個二分圖G,從任意一個匹配M開始,通過尋找M的非飽和點,并確定M可擴路取對稱差的方法,對匹配M進行擴充,直到不存在M可擴路為止,屆時已找到G的最大匹配。對于滿足|X|=|Y|的加權完全二分圖,該最大匹配也是完美匹配。

2.2 KM-WTA算法及其流程

在實際應用中,WTA問題具有極高的時效性,如果求解過程耗時太久,則有可能導致結果與戰況不匹配。因此,該分配問題對算法求解速度有更高的要求。本文在KM算法中引入了貪心策略,能夠有效減少計算量,加快計算速度。KM-WTA算法的流程圖如圖5所示。

圖5 KM-WTA算法流程圖Fig.5 Flowchart of KM-WTA algorithm

首先,根據貪心策略獲得初始可行點標號:分別令子點集X中點的初始可行點標號為以該點為端點的所有邊中的最大權重值,同時選擇每個點對應的權重最大的邊組合成為初始邊集合M0,這樣減少了隨機確定初始可行點標號和由初始匹配導致的計算量增加。

其次,依次判斷初始邊集合M0中的每條邊能否加入匹配M,如果M中的邊一直互不相鄰,則可以繼續添加;若出現兩邊相鄰的情況,則不滿足匹配的定義,需要根據貪心策略調整可行點標號,選擇權值最大且滿足相等子圖條件的邊加入匹配。這種方法與根據匈牙利算法尋找可擴路并確定最大匹配相比,計算更加簡單高效。

引入貪心策略的KM算法偽代碼如算法1所示。

算法 1 KM-WTA算法輸入 武器數量m、目標數量n、毀傷效率矩陣P、目標威脅向量v輸出 最優匹配M并根據式(7)計算相應的目標函數值01 根據第1節中的式(8)計算邊權矩陣02 初始化:l(xi)=maxj=1,2,…,n(wij),i=1,2,…,m,l(yj)=0,j=1,2,…,n,每個點對應的權重最大的邊組合成為初始邊集合M0,初始匹配M=?,記與M中的邊相連的點集與子點集X的交集為P,與子點集Y的交集為Q03 for i=1:m04 if與xi相連的點yj不與M中的邊相鄰05 M=M∪{xiyj}06 Break07 else更新可行點標號08 d=min(l(xp)-w(xpyq')),其中xp∈P,xq'∈Y-Q09 l(xp)=l(xp)-d,l(xq)=l(xq)+d,其中xp∈P,xq∈Q10 連接可行點標號更新后的匹配11 返回04重新判斷12 end13 end

2.3 改進算法的復雜度分析

下面對該改進算法的計算復雜度進行分析。

從時間復雜度來看,根據上述算法流程可以看出,在貪心初始化的前提下,只需對點子集X中的點進行討論,若記a=max{m,n},遍歷子集中所有點需執行a次計算;在每次計算中,在最好的情況下,不需要對可行點標號進行調整,權重最大的邊可以直接列入匹配M,只嵌套了兩層循環,時間復雜度為Ο(a2);在最差的情況下,需要對可行點標號進行調整,對相鄰邊連接的點子集X中的點重新進行檢查,相當于嵌套三層循環,時間復雜度為Ο(a3)。

從空間復雜度來看,在算法執行過程中,需要6個大小為a的向量空間,其中2個用于記錄可行點標號,4個用于記錄檢查匹配關系,其余為一些常數值的記錄,盡管算法過程中有循環,但并不需要占用額外的計算空間,因此計算的空間復雜度為O(a)。

綜上所述,該算法的計算復雜度不高,可以在短時間內快速準確求解。

3 仿真實驗驗證與分析

3.1 實驗結果

為驗證本文所提出的模型與算法的有效性,在運行環境為Windows 11系統,AMD Ryzen9 5950X 16-Core處理器,32GB運行內存的計算機上進行實驗分析。

由于WTA問題目前尚未形成一致的基準問題數據集,因此本文實驗在20個不同維度的問題上進行,武器對目標的毀傷概率由在0.6～0.9內均勻分布的隨機數生成,目標的威脅程度由在25～100內均勻分布的隨機數生成。其中,WTA1～WTA12問題借鑒了文獻[25]中的問題實例,毀傷概率矩陣和目標的威脅向量也采用文獻[25]中的設置,每個問題的武器數與目標數相等。WTA13～WTA20問題的毀傷概率矩陣和目標威脅向量按上述規則隨機生成,為體現第1.5節中二分圖權重向量補全的方法,每個問題武器數與目標數之比分布在[1/4,4]范圍內。20個問題的維度如表2所示,其中WTA1、WTA2、WTA13和WTA14屬于小規模實驗,WTA3～WTA10和WTA15～WTA20屬于中等規模實驗,WTA11和WTA12屬于大規模實驗[3]。

表2 問題維度

將本文提出的模型與算法簡記為KM-WTA,使用該算法對上述實例問題求解。為了保證算法的有效性,每個問題的實驗結果取10次計算的平均值,并記錄每次計算的平均運行時間,如表3所示。

表3 實驗結果與運行時間

續表3

從表3中可以看出,KM-WTA算法運行時間很短。按問題規模來看,在小規模和中等規模問題中,大多數問題運行時間都不超過1 s,在大規模問題中運行時間也不超過30 s。按武器與目標數量之比來看,在小規模問題上,武器與目標數量不等,比同等規模的武器數與目標數相等的問題求解時間更長。通過對比WTA1與WTA13和WTA14可以看出,原因是當問題規模不大時,由補全圖的權重矩陣導致的計算時間延長。而在大規模問題上,當武器與目標數量不等時,相比同等規模的武器數與目標數相等的問題求解時間更短,通過對比WTA9與WTA18和WTA20看出,原因是補全的權重矩陣中有大量0元素,減少了計算時間。

3.2 實驗對比

本節主要圍繞本文提出的模型算法與其他模型與算法在相同數據下的實驗結果對比展開。下面依次進行不同模型求解結果的對比、KM-WTA算法與KM算法的求解結果對比,以及改進KM-WTA算法與并行SA(parallel SA, PSA)算法[25]和改進的烏鴉搜索算法(modified crow search algorithm, MCSA)[26-27]的求解結果對比和分析。

3.2.1 不同模型對比

傳統WTA數學模型可以表示如下:

(9)

(10)

(11)

Xij∈{0,1},?i∈{1,2,…,m}; ?j∈{1,2,…,n}

(12)

其中,式(9) 為非線性目標函數,表示每個目標被打擊后的存活概率,其與相應的目標威脅程度相乘后求和,得到所有目標總體威脅程度;式(10)和式(11) 表示武器與打擊目標間的一一對應關系;式(12) 表示決策變量約束。

為了驗證本文對WTA模型改進的有效性,用式(9)～式(12)基于20組實驗數據進行求解,計算求解器選擇“Optimization Toolbox”中的“fmincon”函數,計算結果見表4中“FMINCON”所在行的數值。由于該求解器的計算原理為分支定界算法,屬于精確算法,因此多次計算結果都相同,略去中位數、平均數以及標準差部分,僅計算時間取10次計算的平均值,運行時間超過3 600 s的視為未能得到計算結果,記作“-”。

表4 多種算法實驗結果對比

續表4

續表4

從表4可以看出,采用分支定界算法求解有約束的非線性規劃式(9)～式(12)的難度更大,用時更長。在小、中規模的問題上求解精度也明顯低于其他幾種算法,在有限時間內很難找到大規模問題的最優解。

3.2.2 與KM算法對比

為了驗證本文對KM算法改進的有效性,將KM-WTA算法與原KM算法在同一組實驗數據上的運行結果和運行時間進行對比,計算結果如表4所示。

從表4計算結果可以看出,KM算法在問題規模達到70時計算時間已超過1 min,而改進KM-WTA算法在大規模問題上計算時間不超過0.5 min;在求解精度上,由于兩種算法尋求最優解的原則思路相近,只是探索方式不同,因此運行結果基本相同。

兩種算法的縱向對比可以說明,隨著問題規模的增加,計算時間會變長,但KM-WTA算法的優勢體現在其明顯縮短了計算時間,能夠快速求解規模較大的問題。

3.2.3 與PSA算法和MCSA算法對比

下面選取同樣以WTA1～WTA12為數據集進行實驗的兩種近似算法與本文提出的方法進行實驗對比,即PSA算法和MCSA算法。選擇PSA算法的原因是該算法基于SA算法,是用于求解WTA問題的經典算法,PSA對SA的改進基于更優的算力,對本文所提算法的計算能力具有較好的參照性。選擇MCSA算法的原因是該算法是典型的群體智能算法,也是目前元啟發式算法中占比較大的算法種類,體現了種群進化過程中群體信息共享的作用,可以對本文所提算法的求解能力提供較好的對比。除此之外,這兩種算法的實驗模型與本文所研究的模型類似,盡量排除了模型不同對實驗造成的影響。

同時,為了排除實驗環境和編碼語言不同對求解產生的影響,本文將PSA算法和MCSA算法在同一臺計算機上進行復現,實驗參數分別以相應參考文獻中提供的參數為準,具體參數設置如表5所示。每個算法對每個問題計算10次后記錄結果的最優值、平均值、中位數和標準差,每次計算的平均運行時間記錄在表4中。

表5 兩種算法的參數設置

在表5中,PSA[25]和MCSA[26]表示該行數據分別來源于文獻[25]和文獻[26],PSA和MCSA表示該行數據是與KM-WTA算法采用同一設備復現這兩種近似算法的結果。但本文復現的結果與參考文獻中提供的最優結果和運行時間數據都有較大差距。原因之一是實驗環境與編程軟件的差異,如文獻[26]中PSA的實驗環境為NVIDIA GeForce GTX Titan X(3072 cores, 1.0 GHz),MCSA的實驗運行環境為Intel(R) Core(TM) i7-5600U CPU @ 2.60 GHz, with 8.00 GB of RAM,代碼開發環境為CodeBlocks IDE v17.12;原因之二是隨機算法求解效果受初始化、參數設置等因素影響較大,很難達到100%的復現效果。

因此,下面主要采用參考文獻中提供的數據對結果進行分析,KM-WTA、PSA[25]和MCSA[26]在WTA1～WTA12問題上多次計算求得的平均值和標準差如圖6所示。從標準差角度來看,KM-WTA是精確算法,每次計算結果都相同,其結果在圖6中表示為一個紅色圓點,標準差為0;而PSA算法和MCSA算法的結果只有在WTA1～WTA3上是一個點,在其他問題上都形成了長短不一的線段,說明多次計算存在標準差,求解結果不穩定。從平均值的角度來看,KM-WTA在WTA1～WTA5以及WTA9～WTA12上都得到了最優結果,平均值點都低于其他兩種算法的平均值點或與其平均值點水平;在問題WTA6～WTA8中, KM-WTA的計算結果略差于PSA和MCSA,為了探究產生差距的原因,將式(7)和式(8)使用線性規劃求解函數“intlinprog”進行計算,計算結果如表6所示,與KM-WTA算法得到的結果完全一致。由此可以斷定,WTA6～WTA8計算結果較差的主要原因在于在簡化模型過程中產生了誤差,盡管KM-WTA算法是精確算法,但將非線性模型轉化為線性模型時并非等價轉換,導致未能找到原問題的最優解。

表6 WTA6～WTA8問題與intlinprog計算結果對比

圖6 3種算法的計算結果對比Fig.6 Comparison of calculation results for three algorithms

同樣地,將3種算法對12個問題的平均計算時間表示如圖7所示。

圖7 3種算法的平均求解時間Fig.7 Average running time of three algorithms

從圖7中可以看出,KM-WTA算法的計算時間遠少于PSA算法和MCSA算法的用時,只有在大規模問題中,KM-WTA算法的運行時間才有明顯增加,但依然低于其他兩種算法。這也證明了KM-WTA算法計算復雜度低于近似算法,在求解速度上占有很大優勢。

綜上所述,本文提出的式(7)和式(8)是原問題模型式(9)～式(12) 的近似模型,需配合本文提出的KM-WTA算法求解,在20個實驗問題中的17個問題上都取得了最優解,在未取得最優解的問題上僅比最優解差0.52%,并且比其他模型算法的計算耗時更短,說明本文提出的模型和算法在求解精度和求解速度上都具有一定的優越性。

4 結束語

本文首次將圖論中的二分圖匹配模型用于求解WTA問題,通過將WTA問題映射到加權二分圖模型中,構建了一個新的數學模型,將非線性規劃問題簡化為線性規劃問題,降低了模型的復雜度。為了進一步快速求解,在原始KM算法的基礎上結合了貪心策略,極大地降低了計算的計算復雜度。通過在20個不同規模的問題實例上計算,分別對比了本文提出的模型與算法與初始的問題模型、KM算法以及兩種啟發式算法的計算結果和計算時間。實驗數據說明,本文提出的模型與算法求解效率高,求解精度較高且求解速度快,同時多次實驗也說明了該模型與算法計算結果穩定,適用于不同規模的問題。綜上,本文提出的模型與算法可以滿足實戰中快速做出最優決策的要求,具有較強的實用性。

事實上,目前的研究重點逐漸轉移到更加復雜的WTA模型。動態WTA問題需要考慮隨著時間推移雙方戰力戰況的變化,考慮多約束的WTA問題在離散解空間中添加更多武器或目標間的相互牽制關系,以及不確定的WTA模型需要在武器充足性不確定的情況下最大化總毀傷等各種復雜情況。研究的模型越復雜,研究結果對實際問題的指導價值也越高,如何用圖論中的模型解決更加復雜的WTA問題,可以作為下一步研究的重點。