武器-目標分配問題研究*

楊進帥，李 進，王 毅

（空軍工程大學防空反導學院，西安 710051）

0 引言

武器-目標分配[1]（Weapon-Target Assignment，WTA）問題是研究分配武器單元打擊敵方目標，從而取得最佳打擊效果，優化火力打擊體系，也稱目標分配或者火力分配。是現代戰爭中指揮控制的關鍵問題之一。制定合理的火力分配方案，可以優化資源配置，用最小代價獲取最大戰場收益[2]。WTA問題實質是一類非線性組合優化決策問題，解空間大小隨著武器和目標數量的增加而呈指數增加，是一個NP完全問題。

WTA主要在兩個方面進行學術研究，一是模型研究，旨在建立更為合理、貼切實際的模型；二是算法研究，快速有效解決WTA問題，給出分配方案以提供決策支持。

1 基本內容

WTA問題的研究目的是提高戰場指揮控制的自動化水平，快速有效地解決大規模武器目標的分配問題。武器-目標分配問題的研究可以追溯到上世紀五六十年代，最初的研究目的是用于制定作戰計劃、指揮軍官訓練，提高作戰指揮的能力，為武器的選擇以及新武器的研制與采購提供參考，而不是直接用于戰場的作戰指揮。

1.1 WTA分類

根據目標威脅和對抗方式可以劃分出多種WTA類型，如圖1所示。

圖1 WTA分類

考慮目標威脅，武器-目標分配問題劃分為狹義WTA和廣義WTA，狹義WTA中目標一定有威脅，而廣義WTA中目標可能有威脅，也可能沒有威脅[3-4]。考慮作戰雙方的對抗方式，武器-目標分配問題分為直接對抗式WTA和間接對抗式WTA。其中直接對抗式WTA的目的是消滅敵方，以此來進行目標分配，目標打擊對象是防御方的武器；間接式WTA又稱資源防護型WTA，是防御方保護資源不受摧毀或損失最小，選擇性地對敵人的目標進行打擊，目標打擊對象是防御方所保護的資源。

1.2 WTA問題性質與數學模型

武器-目標分配問題的數學描述為T個目標攻擊W個武器平臺，第i個武器平臺被第j個目標毀傷概率是；其中第i個武器平臺的重要性是wi，并且第i個武器平臺可用于防御的武器有mi件，第j個目標被它的第k件武器毀傷概率是rikj。同時，最多使用W個武器平臺上的nj件武器對第j個目標進行還擊。確定武器-目標分配方案是WTA求解的目標，最終目的是使己方損失最小。xikj=1表示第i個武器平臺的第k件武器對第j個目標進行還擊，否則xikj=0。

武器-目標分配問題的數學模型[4-5]抽象為如下形式：

在上述數學模型的基礎上，不同的作戰目的可以建立不同的WTA模型，既可以是單目標的，也可以是多目標的。多目標WTA可以通過權值轉化為單目標WTA，也可以引入罰函數求解非劣解。

WTA問題一般具有下列數學性質：

1）WTA問題是NP完全問題；2）WTA問題具有離散性，難以進行微分；3）WTA問題具有隨機性，需要用隨機模型來描述武器與目標的交戰活動；4）武器與目標的規模較大；5）目標函數是非線性的。

2 WTA問題研究現狀

2.1 模型研究

模型研究主要分以下幾個方面[3-4]：

1）模型假設。合理假設是建模研究的首要問題，WTA問題由于對抗環境的復雜性，必須合理抽象，建立準確模型才能有效解決WTA問題。

2）目標函數選擇準則。不同的決策意圖和不同的交戰策略決定了不同的選擇準則，一般可以采用防御方消耗最小、資源損失最小，敵方潛在威脅最小和敵方剩余目標數最小等選擇準則設計目標函數。

3）約束條件；與決策意圖有關，決定了問題的復雜程度，主要包括武器與目標的數量、毀傷概率、資源價值、目標威脅等因素。

4）時間因素。動態多變的戰場環境對武器射擊提出了時間的要求，不考慮時間因素的影響，不能正確反映實際作戰過程。

圖2 WTA模型分類

因此，不同的出發點可以劃分不同的WTA模型，如上頁圖2所示。靜態WTA模型和動態WTA模型是國內外學者研究最多的兩種模型。

靜態WTA（SWTA）是基于所有武器同時分配發射和武器目標之間交戰相互獨立這兩個假設[6]建立的模型。SWTA中武器和目標狀態固定、參數恒定且已知，其目標是防御方根據進攻方的武器估計類型、預測點影響值，針對暫時防御任務，給出最優分配。

靜態WTA模型是研究的主體，國外學者Patrick A Hosein和 Michael A[7-9]對一般性 WTA 問題進行了系統研究；S.P.Lloyd等[10]證明了WTA問題的NP完全性，指出其求解時間隨問題規模的增加而指數增長；美軍國防分析研究所改進了武器優化與資源需求模型[11]，并在C4ISR環境下建立了作戰資源分配模型。國內學者主要針對特定領域進行研究，如空軍工程大學的邢清華教授[12]等在防空導彈領域，裝甲兵工程學院常天慶教授[13]等的坦克分隊領域和國防科技大學蔡懷平教授[3]等。目前，基本解決了小規模的SWTA問題。

動態WTA（DWTA）模型是在SWTA模型的基礎上，注重考慮分配過程中可能的隨機事件并及時處理，研究動態防御作戰過程中武器目標最優分配。由于時間因素和隨機事件的影響，增加了問題求解的難度[14]。DWTA 的研究主要有 Hosein[15-16]的多級武器-目標分配和韓松臣[17]的基于馬爾可夫決策過程最優化的動態WTA兩種方法。

多級武器-目標分配將動態WTA問題分成許多時間段，是根據來襲目標持續的時間。在每個時間段中，根據目標當前情況，允許防御方發射武器進行迎擊，而且所有武器效能評估由于前一階段襲擊過程中反饋信息的存在，防御方能更好地進行武器分配，提高武器的進攻效果。基于馬爾可夫決策過程最優化的動態WTA方法結合動態分配策略和靜態WTA模型，運用隨機過程理論，為動態WTA提供了理論和方法依據[18]。

2.2 算法研究

求解SWTA的傳統算法主要包括分枝定界法[19]、隱枚舉法[20]、動態規劃法[21]和割平面法，這些算法編程較為繁瑣，難以處理大規模WTA問題。隨著計算機技術的發展，一些啟發式優化算法通過模擬自然現象或過程，為處理復雜問題提供新方法和新思路，比如遺傳算法（GA）、粒子群算法（PSO）、蟻群算法（ACO）、差分進化算法（DE）等。

2.2.1 遺傳算法求解WTA問題

遺傳算法（GA）是 Holland教授[22]于 1975年提出，基于適者生存、優勝劣汰等自然進化規則模擬生物進化過程和基因遺傳操作。遺傳算法由于魯棒性高、適應性強的特點在WTA問題中被廣泛使用，取得了一定效果但也暴露出不少迭代時間長、過早收斂、容易陷入局部最優解和封閉競爭等局限和不足。鑒于此，國內外學者采用不同的方法手段改進遺傳算法，用于求解WTA問題。

曹偉華[23]從問題編碼、初始種群產生、遺傳操作等方面給出了武器-目標分配問題的遺傳算法詳細設計，進而求解WTA問題。王瑋[24]通過設計一種滿足約束條件的染色體編碼格式，把求解問題轉化為無約束組合優化表現形式，利用精華選擇策略、單點隨機定位算術交叉和變異運算進行求解。楊山亮[25]采用精英選擇和動態遺傳算子改進遺傳算法求解多種作戰力量參戰條件下的多武器-多目標的聯合作戰，避免了過早的收斂。常天慶[13]改進了基本遺傳算法的關鍵步驟，設計了基于火力單元排序的戰術種群初始化策略，在進化初期就產生適應度很高的個體，引入了小生境共享函數和參數自適應機制，維持種群的多樣性的同時加速收斂，在坦克分隊的武器-目標分配問題上取得了良好的收斂效果。薛羽[26]根據協同干擾武器-目標分配問題的實際性質，引入啟發式規則，提出了具有貪婪修復過程的免疫遺傳算法，求解大規模CJWTA問題，在較短時間內得到了較高質量的分配方案。吳坤鴻[27]設計了一種分布式遺傳模擬退火算法，采用多目標分布式搜索方式，在交叉算子中引入模擬退火算法，保持算法的廣度和深度搜索平衡，有效求解了火力打擊目標分配的多目標優化問題。余家祥[28]改進了傳統局部搜索遺傳算法，將貪婪構造應用于局部搜索，設計了優秀保留交叉操作方法，獲得了較好的搜索效率，并不改變算法的全局收斂速度。徐加強[29]從火力分配實時性角度出發，考慮常規導彈生存、突防等影響因素，以毀傷下界為約束，建立了時空約束的動態常規導彈火力分配模型，結合遺傳算法和禁忌搜索的特點，構建了遺傳禁忌融合算法，在較短時間內找到最優解。董朝陽[30]基于目標函數的相對大小構造火力分配的適應度函數，采用種群染色體相似度，靈活有針對性地對父代染色體進行交叉或變異操作，防止算法陷入局部最優同時保證更新速度，獲得了高效的尋優能力。

2.2.2 粒子群算法求解WTA問題

近年來，國內外許多學者探索運用粒子群算法求解WTA問題，同遺傳算法比較，粒子群算法[31]（PSO）沒有許多參數需要調整，容易實現。

李欣然[32]提出了一種改進粒子群算法求解多種類型武器-目標分配問題，首先定義粒子聚焦距離變化率，自適應調整慣性權重；其次采用速度最大值線性遞減的策略平衡算法收斂精度與全局尋優能力之間的矛盾；最后使用優勢粒子替換劣勢粒子的策略加快粒子收斂速度，使得算法適合求解各種大規模的武器-目標分配問題。提高武器-目標分配問題的求解效率和性能，曲在濱[33]提出了一種離散粒子群算法，重新定義了粒子群算法中的速度和位置，采用貪心的啟發式策略調整迭代產生的方案，快速找到最優解或次優解。張蛟[34]采用混沌離散粒子群混合優化算法對以毀傷概率為優化目標，兼顧火力資源消耗的多次攔截時機的防空火力分配模型，提高了算法的全局搜索能力，避免陷入局部極值。范成禮[12]運用懷疑因子和斥力因子改進位置和速度更新公式，有效避免發生早熟收斂和陷入局部最優問題，同時保持了PSO固有的收斂速度，有效地處理大規模WTA問題，為現代戰爭進行實時性輔助決策。劉曉[26]通過化解約束條件、修改速度和位置更新改進多目標粒子群優化算法（MOPSO），使之適合求解WTA模型。劉爽英[36]提出了一種改進的量子粒子群優化算法，根據粒子聚集度來判斷早熟停滯，并用慢函數克服，同時保持種群的多樣性，能快速給出WTA的最優或近優分配方案。

2.2.3 蟻群算法求解WTA問題

蟻群算法易于與其他算法相結合，具有分布式、正反饋、魯棒性好的優點和收斂速度較慢的缺點[37-38]。

袁梅[39]通過采用了信息素遞減的信息素更新策略以及隨機數方法的選擇原則，明顯加快解的收斂速度。崔莉莉[6]在蟻群算法信息素的更新規則中引入PS算法，利用局部搜索經驗和去哪聚搜索經驗指導后繼粒子搜索的機制，擴展搜索空間，增強螞蟻局部搜索經驗和群體全局搜索經驗，提高收斂效率。黃國銳[20]運用多目標模糊優選理論建立最佳武器-目標分配模型，采用蟻群算法對分配模型轉化為蟻群網絡進行求解。仿真結果表明，相同的彈藥消耗量、射擊效果和群體規模下，蟻群算法的收斂速度和最優解的性能優于其他算法。武從猛[40]在求解大型水面艦艇編隊防空的武器-目標分配問題時，將遺傳算法融入蟻群算法，運用遺傳算法的全局隨機搜索能力生成一組粗略解，用其作為蟻群算法的初始信息素，運用蟻群算法的并行性、正反饋機制，發揮了遺傳算法和蟻群算法的優點，在最短時間內獲得了最優火力分配方案，縮短了武器反應時間。蘇淼[41]等人利用免疫記憶和克隆選擇的思想方法，引入記憶庫，提出了基于免疫記憶的蟻群算法，通過進行給定數據集和隨機數據集的WTA問題的實驗，結果在不管是解的質量上和時間性能上均取得了較好的效果。

2.2.4 差分進化算法求解WTA問題

差分進化（DE）算法通過個體間的競爭與合作求解高維非線性優化問題[42-43]，實現簡單、搜索能力強，但存在容易陷入局部最優、收斂速度慢等問題。

北京理工大學的張春美博士[44]，設計了離散差分進化算法的差分變異算子和交叉策略，提出了一種新的算法DDE-MRR，求解靜態WTA問題，并與DDE-FBT和DDE-RPI算法進行比較，表明算法更容易求出最優解且收斂性能較好。王少蕾[45]針對水面艦艇編隊防空反導作戰中武器-目標分配問題模型，采取使種群個體滿足約束條件的編碼方式，利用混沌序列初始化種群，加強種群的搜索多樣性，優化改進變異、交叉的動態自適應策略和混沌序列擾動，避免算法陷入局部最優，便捷地解決了多平臺多類型武器-目標分配問題。梅海濤[46]運用算子K調節差分進化算法前后的變異率，增強全局和局部尋優能力，運用直覺模糊知識優化WTA模型。

2.2.5 其他智能優化算法求解WTA問題

許多新型智能算法也在求解WTA問題中嘗試應用，從不同的角度出發，解決不同求解目標的WTA問題。

類電磁算法[47]將種群中的個體模擬為帶電粒子，通過吸引和排斥作用引導個體朝最優解方向移動，全局搜索能力強，初步應用于項目調度和函數優化等領域。楊曉凌[48]改造原始類電磁算法的種群初始化、局部搜索、合力計算及粒子移動等步驟，使之適應武器目標問題的整數解空間。徐克虎[49]提出了一種“（1+λ）選擇”的全局更新技術和Memetic局部更新技術的人工免疫算法，采用最優抗體抑制技術避免AIA陷入局部最優，具有較寬的收斂速度和精度。王邑[50]根據從已知決策中推理生成新的決策，減少重復搜索的思路，利用分支界限法得到分配方案的訓練樣本，通過構造并行運行的類型2區間模糊K近鄰分類器的機器學習方法推導目標分配方案，實現快速決策。

2.3 不足及發展方向

國內外學者從模型抽象和求解算法等角度，對WTA問題進行了許多研究探索，取得了一定的效果，但仍然存在4個不足：1）主要集中在靜態模型的研究，對動態WTA模型研究不夠充分；2）動態與靜態分配結合的研究比較少；3）尚未提出能應用于實際作戰中的大規模WTA問題的有效算法；4）不確定因素的研究較少。

新軍事技術的變革使戰爭形式發生了巨大變化，比如無人機、彈道導彈、高超音速飛機等，傳統的WTA問題模型的適用范圍大大縮小，但要求更為嚴格，要求時間更快、打擊目標更準，這給敵我雙方帶來挑戰和機遇。許多學者已經開始WTA模型的更深一步研究，有的學者以實施一體化聯合作戰[51-52]為戰爭主要形式，研究多軍兵種的多種戰術類型和多種裝備型號防空武器的混合部署條件下，如何進行防空目標的優化分配等問題進行探索；有的學者運用模糊數學[53]和關系算子[54]改進模型，將WTA轉化為無約束優化問題，獲得了更多打擊效率滿意的目標。

WTA的算法研究主要集中于智能算法，且都認為自己的方法具有不錯的收斂性，其實只要初始條件發生改變，則算法可能就不收斂。實際作戰中這是致命的且不被允許的，必須在保證有解的基礎上，提高求解的質量和速度。目前主要解決了規模較小的靜態WTA問題，求解大規模動態WTA問題的算法速度較慢，尚未提出有效的算法。為滿足軍事技術發展的需要，解決大規模動態WTA問題顯得尤為突出和重要。智能算法求解了WTA問題，較為有效地解決了時間和收斂性的問題，且混合智能算法策略也越來越顯示出其有效性。可以說，求解大規模動態WTA問題，多種群智能算法的融合是此類優化問題的研究方向。

從現有文獻看，求解WTA問題的智能算法層出不窮，需要統一的標準評價算法的尋優能力，尋找相對更高精度、更高效率的算法[55]。這一方面的理論研究相對較少，目前只有黃大山等學者從算法代碼編制質量、算法精準度和算法執行效率3個方面對智能算法的尋優能力深入討論，試圖建立評價準則體系。建立完善的智能算法求解WTA問題評價準則體系，有利于針對不同類型的WTA問題選擇合適的智能算法，在理論上有更為清晰的指導。

3 結論

綜上所述，通過梳理WTA問題模型和算法的研究現狀和成果，分析不足問題，探索發展方向，可以指導WTA問題的下一步研究。特別是大規模動態WTA問題的研究，貼近實際作戰，能有效提高指揮控制的自動化水平，為智能決策提供輔助支持，具有重要的理論意義和實際應用價值。