應用改進遺傳算法解決武器目標分配問題

閆玉鐸

摘要：在實際作戰過程中，以當前戰場態勢為輸入，特定交戰規則為約束的武器目標分配（Weapon Target Assignment，WTA）問題是指揮員必要的決策行為之一。因此，在作戰仿真系統中，WTA模型是計算機生成兵力（Computer Generated Forces，CGF）決策行為模型的重要組成部分。對WTA進行有效建模有助于提升決策行為模型的逼真性與智能性，以及仿真結果的可信性和有效性。本文主要研究WTA決策行為建模與優化求解問題，主要包括WTA模型建立，以及面向高實時、高可靠性實際應用需求的算法。論文的最后，通過設計對比實驗，驗證了WTA模型及提出的改進遺傳算法的可行性與有效性。

關鍵詞：武器目標分配;建模與優化求解;改進遺傳算法

中圖分類號：TP391.9? ? 文獻標識碼：A? 文章編號：1007-9416（2018）10-0000-00

1 引言

在真實的戰場環境下，WTA問題是指在對敵我雙方當前戰場態勢的獲取與分析下，針對我方多個裝備同類型武器的作戰單元與多個敵方威脅目標，如何把我方具有不同殺傷力的武器及時合理地分配，構成整體優化的火力打擊體系。

WTA問題是一個多參數、多約束的不確定性多項式完全問題[1]。該問題本質上需要依靠完全列舉法來找到優化方法。但隨著作戰規模的不斷增加，其問題的解空間以指數方式上升，并呈現出組合爆炸的趨勢。從是否考慮時間因素的角度，WTA問題的模型研究又可分為靜態WTA（Static Weapon Target Assignment， SWTA）模型與動態WTA（Dynamic Weapon Target Assignment， DWTA）模型研究。靜態的WTA基礎模型如公式（1）所示。現階段絕大多數的研究都是以此模型作為基礎。在模型中，M表示我方的武器平臺種類數，N表示敵方的目標數，W表示敵方目標的威脅值，p表示我方武器對敵方目標的擊毀概率，x表示武器目標分配方案，為優化函數的自變量，F（x）為此優化函數的優化目標，表示我方武器對目標威脅的打擊效果，F（x）越大，表示對敵方的打擊效果越好。

? ?（1）

2 相關工作

最初，解決WTA問題的方法是基于線性規劃，動態規劃，圖論這些傳統算法。在20世紀80年代中期，WTA問題已被證明是一個NP完全問題，這意味著任何確定性算法不能獲得在多項式空間的最優解。

20世紀90年代初以來，國防分析研究所（IDA）一直在研究WTA問題，在這期間他們改進了武器的優化和資源需求模型（WORRDM）[2]。現代戰爭中，隨著C4ISR的廣泛應用，IDA提出對WORRDM模型的進一步改進策略，進而建立C4ISR環境下的作戰資源分配模型（Engagement Resources Allocation Model，ERAM）。余家祥等[3]針對艦艇編隊內多型區域防空武器抗擊來襲導彈的WTA問題展開研究;王波等[4]以反艦導彈打擊敵水面艦船為背景，并應用改進的遺傳算法進行求解;韓松臣等[5]對WTA問題進行描述并提出了基于馬爾可夫決策過程解決動態問題的方法，該方法中將動態的分配策略與靜態模型相結合以求在作戰中對武器進行動態分配。崔莉莉[6]以蟻群算法的信息更新規則為基礎，引入PSO算法中的利用搜索經驗對后續粒子群的指導機制。此方法經過實驗驗證有效擴展了群體的搜索空間，同時對算法效率也有所提高。

3 WTA模型建立

3.1 WTA概念模型的建立

建立WTA模型，要優化的目標包括對我方的資源保存值和對敵方目標威脅的損傷值。

首先建立WTA概念模型，我們的武器概念模型可以表示為：

m表示我方武器平臺的個數，同一武器平臺中的武器種類相同，表示第i個武器平臺擁有武器的數量為。

目標的概念模型如下建立：

n表示敵方目標的總數，表示敵方第j個目標。

武器分配計劃的概念模型如下建立：

表示使用個武器平臺i中的武器來打擊目標j，這里有。

3.2 WTA數學模型的建立

在本文中的WTA問題，目標是在損傷最少的資源以及給敵人的目標威脅造成最大的傷害。因此，我們建立優化目標H（x），以盡量減少敵人的目標威脅程度同時最大限度地保存我方的資源。建立WTA優化模型：

? ? （2）

（3）

下面對模型中的變量與參數加以解釋說明：

如上數學模型中所示，F（x）代表對敵方目標威脅的損傷程度;G（x）代表對我方資源的保存程度;優化目標H（x）=aF（x）+bG（x）綜合考慮了損傷敵人的目標威脅程度同時提高我們保存的資源保存程度，a和b由指揮員很據戰斗的具體目標設定，不同的值反映指揮員對戰斗目標的不同要求，a+b=1，。特殊的，a=0，b=1表示此次作戰行動以最大程度保存我方資源為戰斗目標;a=1，b=0表示此次作戰行動以最大程度打擊敵方威脅為戰斗目標。

模型中，我方武器集合用矩陣表示，其中表示我方第i個武器平臺擁有武器的數量，m表示我方武器平臺的種類數量，我方擁有的武器總數為。在進行武器目標分配中，使用同一種武器對目標打擊的數量總和不能超過該武器平臺的數量上限，由此建立分配的容量約束：

為了保證對于某一敵方目標我方可以分配足夠的武器進行打擊而又沒有武器的過度浪費，模型中引入策略約束，其中表示在正常狀態下我方武器i成功將目標j摧毀的概率。此約束表示對于某一目標j，我方對其進行打擊的武器總的摧毀概率不超過99%，以實現武器的合理分配。

我方資源值用矩陣表示，表示我方第i個資源的價值，l表示我方資源的總數;敵方目標威脅值用矩陣表示，表示敵方第j個目標的威脅值。我方資源與敵方目標威脅的取值均在0到1之間，表示我方每個資源價值占總價值的比例以及敵方每個目標威脅所占的比例，這兩個取值由戰場指揮員根據作戰進程進行評估。

模型中對于武器狀態建立狀態矩陣，其中表示我方第i個武器平臺的狀態向量，表示為：，表示第i個武器平臺中第k個武器的狀態，取值越大，表示該武器的保存狀態越好，模型中為了方便處理，模型中取或，分別表示該武器已經被摧毀或保存完好。

建立通視矩陣表示，該矩陣為三維矩陣，表示第i個武器平臺中第k個武器與目標j之間的通視性，通視性對武器與目標之間的發現概率與打擊概率都有所影響，在本文中對發現概率與打擊概率綜合考慮，均由通視性因子表示。前文已經提到，在真實戰場環境下，武器與目標之間的通視性由多方面因素影響。在本模型中，主要考慮武器與目標所處的地形條件與氣象條件兩方面因素，并建立相應的影響因子，并有。

4 WTA求解算法

4.1傳統遺傳算法求解

遺傳算法為求解復雜系統優化問題提供了一種通用框架，它不依賴于問題的實際意義與應用背景。對于本文中需要解決的WTA優化問題，其求解的流程如圖1所示。

第1步：隨機產生初始種群，種群大小一定，將每個群體中的個體以染色體的基因編碼的形式表現出來;

第2步：對種群中所有個體在WTA問題中的適應度函數值進行計算，并判斷結果是否滿足優化準則，若滿足，則將該個體及其代表的最優解輸出，結束計算，若不符合則執行第3步;

第3步：根據適應度函數值的大小選擇進入子代的個體，適應度函數值高的個體被選中的機會較高，適應度低的個體更容易被淘汰;

第4步：按照設定的交叉概率和交叉操作方法，產生新的個體;

第5步：按照設定的變異概率和變異操作方法，產生新的個體;

第6步：將交叉和變異產生的新一代個體組成新一代種群，執行第2步。

遺傳算法中的優化準則：不同問題的有不同的優化準則。本文研究的優化問題中所采用的優化準則為遺傳迭代次數是否超過預先設定值。

4.2傳統遺傳算法的局限性

遺傳算法這樣的衍生進化類算法采用隨機搜索機理，積累成千上萬代正向的有積極意義的進化方能得到卓有成效的改進[7]。這是對實時性有較高要求的WTA問題所不能接受的弊端。

遺傳算法在每次迭代過程中，選擇、交叉和變異的操作是盲目的[8]，這是算法的機理問題。這也直接導致了遺傳算法在求解過程中效率較低、收斂較慢。同時，傳統遺傳算法在收斂過程中容易陷入局部最優而出現過早收斂，它使得種群演化到非全局最優狀態，進一步迭代已不能產生更佳可行解。

鑒于遺傳算法存在這樣的不足，眾多文獻在解決WTA問題這樣類似的實時性很強的優化問題會選擇啟發式尋優的遺傳算法和一些具有指引性的智能算法相結合的遺傳算法改進策略，以抑制其盲目尋優和過早收斂的局限性。

4.3改進遺傳算法

差分進化算法是一種效率較高的進化搜索算法，其原理和結構類似于遺傳算法，同樣采用遺傳操作（選擇、交叉和變異）。差分進化算法在實際優化問題中能夠表現出色，原因有兩點：首先，差分進化算法將一部分個體的差分信息作為擾動量，使算法在跳躍距離和搜索方向上具有自適應性，從而改善了遺傳算法變異和交叉的盲目性;其次，1V1競爭機制使得進化過程中，整個種群的質量逐步提升，拒絕了遺傳算法盲目選擇導致的質量較差的部分個體遲遲不能淘汰，從而阻礙種群的進化[9]。

針對遺傳算法盲目的隨機尋優和過早收斂，為了平衡計算代價和解的精度，在不追求解全局最優且尋優時間有限的情況下，本文基于遺傳算法給出了針對性的算法改進策略，引入了差分進化算法的1V1競爭機制和差分變異機制以及粒子群算法的更新規則，以期最大程度的克服其盲目尋優和過早收斂的缺陷。具體的本文提出的改進遺傳算法的流程圖如圖2所述。

如2所示，本文提出的改進遺傳算法基本保存了傳統遺傳算法的運算流程，不同的是，在更新種群的環節，本文引入了差分變異與粒子群算法的更新規則產生新的種群并與原傳統遺傳算法產生的種群進行1V1競爭，這種方法雖然在時間消耗上有一定損失，但是可以有效地避免傳統遺傳算法盲目尋優造成的收斂過慢以及樣本多樣性不足造成的陷入局部極小。

5 實驗及結果

為驗證本文提出的改進遺傳算法的性能改進效果，基于實際WTA問題的數學模型，采用本文提出的改進遺傳算法、差分進化算法和傳統遺傳算法分別進行測試，測試的數據與前文的獲取方法相同，首先設計一個簡單的實驗案例，案例中，模型的參數通過人為進行設定，通過設定武器和目標數量m和n的值來設定不同的作戰規模，模型中其他參數由計算機隨機生成。在本節的對比實驗中，為了將不同的智能算法求解效果進行對比，在進行同一組對比實驗中使用的數據是相同的，以下是具體的測試結果。我們基于m，n=5，m，n=10，m，n=15，m，n=20，m，n=25，m，n=30，m，n=35這7種不同作戰規模下各做了10次實驗，以分析在不同作戰規模下，傳統的遺傳算法、差分進化算法和本文提出的改進遺傳算法的性能，這里主要分析算法的適應度函數收斂情況和算法的實際運行時間。適應度函數收斂情況主要表現于算法達到收斂或最大迭代次數時的適應度函數值;算法的實際運行時間體主要表現于算法達到收斂狀態或者達到最大迭代次數的運行時間。本實驗中，將迭代次數設定為100。

由于實驗結果數據量大，為了對實驗結果有更直觀的展示，現將7種作戰規模下，三種智能算法的適應度函數收斂情況和算法的實際運行時間數據分布情況通過箱線圖來進行展示，如圖3和圖4所示。

在圖中，紅色的線表示數據中位數，箱子的上下邊緣分別表示數據的3/4和1/4分位數，箱子兩頭的延伸線表示數據的最大值和最小值，離散的點表示統計意義上的異常值。通過箱線圖，我們可以非常直觀的看到不同算法適應度和實際運行時間上的數據分布，且由圖中可明顯看出看，本文所提出的改進的遺傳算法在適應度收斂情況方面表現明顯優于其他職能算法，且收斂能力極為穩定。在運行時間方面，雖然略高于其他算法，但是仍處于一個量級上，并無明顯差異。

為了進一步分析，我們在三種算法適應度函數收斂情況和算法的實際運行時間數據上進行的簡單的統計分析在原始數據上，分別對7種作戰規模的10次試驗結果的最優結果，最劣結果，平均情況，中位數以及標準差進行統計，由于其包含的數據量較大，在此我們對其中包含的較有價值的信息進行進一步分析。均值和標準差是反映數據整體特征的重要指標，故我們針對三種算法在不同作戰規模下的適應度函數收斂值和實際運行時間的均值和標準差進行可視化處理，如圖5和圖6所示。

從圖中可知，本文提出的改進遺傳算法適應度函數的收斂效果十分理想，且收斂情況十分穩定，基本沒出現達不到收斂狀態的情況，對比之下，差分進化算法和傳統遺傳算法的收斂情況都不是十分理想且遠差于改進遺傳算法，并且兩者的算法性能發揮都十分不穩定，收斂情況波動較大。在算法實際運行時間方面，三種算法都處于一個量級，盡管圖中顯示傳統遺傳算法的運行時間是最短的，但在實驗所設定的100次迭代次數中，由表4.4可知，在規模較大的情況下，傳統遺傳算法有相當一部分實驗中，算法最終沒有達到收斂，因此圖中顯示的運行時間并不能完全說明改進遺傳算法的效率較差，在規模較小的情況下，盡管改進遺傳算法較傳統遺傳算法消耗時間更多，但是在真實的戰場環境下，為了獲得更好的武器目標分配結果而消耗的少量時間代價，是完全可以接受的。

在分析了不同作戰規模下，三種智能算法的性能分析之后，本文提出的改進遺傳算法體現了明顯的優勢。故我們認為，在實際應用過程中，本文提出的方法是非常有競爭力的。

6 結語

在本文中，我們首先建立WTA數學模型，進而對遺傳算法解決WTA問題的求解流程進行介紹，并分析其求解過程中存在的不足，針對于遺傳算法的盲目搜索與易于陷入局部極值兩個問題，本文引入了差分進化算法的1V1競爭機制和差分變異機制以及粒子群算法的更新規則，提出解決WTA問題的改進遺傳算法，并通過實驗驗證了本文提出的改進遺傳算法具有快速且穩定的算法性能與較高的適用性。

參考文獻

[1]Lloyd S P， Witsenhausen H S. Weapons Allocation is NP-Complete[C]// IEEE Summer Conference on Simulation. 1986.

[2]Koleszar G E， Bexfield J N， Miercort F A. A Description of the Weapon Optimization and Resource Requirements Model （WORRM）[J]. A Description of the Weapon Optimization & Resource Requirements Model，1999.

[3]余家祥，趙曉哲，史紅權等.基于遺傳算法的編隊區域防空武器分配方法[J].現代防御技術，2013，41（1）：82-87.

[4]王波，劉小利，胡亮等.基于改進遺傳算法的反艦導彈火力分配研究[J].火力與指揮控制，2015，40（8）：90-93.

[5]韓松臣.導彈武器系統效能分析的隨機理論方法[M].國防工業出版社，2001.

[6]崔莉莉.基于蟻群算法的武器-目標分配問題研究[D].上海：上海交通大學，2011.

[7]徐宗本，高勇.遺傳算法過早收斂現象的特征分析及其預防[J].中國科學：技術科學， 1996，（4）：364-375.

[8]何大闊，王福利.一種提高遺傳算法全局收斂性的方法[J].東北大學學報（自然科學版），2003， 24（6）：511-514.

[9]林川.粒子群優化與差分進化算法研究及其應用[D].西南交通大學，2009.

An Improved Genetic Algorithm for Solving Weapon Target Assignment Problems

YAN? Yu-duo

（PLA Unit 31002， Beijing? 100094）

Abstract： During the actual combat， the Weapon Target Assignment （WTA） problems， with the real-time battlefield condition as input and specific combating engagement rules as constraints， is one of the necessary decision-making behaviors of the commander. Therefore， in the combat simulation system， the WTA model constitutes an important part of the Computer Generated Forces （CGF） decision behavior model. Effective modeling of WTA contributes to improve the intelligence and facticity of decision-making behavior models， as well as the effectiveness and credibility of simulation results. In this paper， the modeling and optimizing solution problem of WTA decision behavior were mainly studied， including the establishment of WTA model and the algorithm for high-real-time and high-reliability application requirements. At the end of the paper， the feasibility and effectiveness of the WTA model and the proposed improved genetic algorithm are verified by designing comparison experiments.

Keywords：Weapon Target Assignment （WTA）; modeling and optimizing solution; improved genetic algorithm