應(yīng)用改進遺傳算法解決武器目標(biāo)分配問題

閆玉鐸

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

關(guān)鍵詞：武器目標(biāo)分配;建模與優(yōu)化求解;改進遺傳算法

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

1 引言

在真實的戰(zhàn)場環(huán)境下，WTA問題是指在對敵我雙方當(dāng)前戰(zhàn)場態(tài)勢的獲取與分析下，針對我方多個裝備同類型武器的作戰(zhàn)單元與多個敵方威脅目標(biāo)，如何把我方具有不同殺傷力的武器及時合理地分配，構(gòu)成整體優(yōu)化的火力打擊體系。

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

? ?（1）

2 相關(guān)工作

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

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

3 WTA模型建立

3.1 WTA概念模型的建立

建立WTA模型，要優(yōu)化的目標(biāo)包括對我方的資源保存值和對敵方目標(biāo)威脅的損傷值。

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

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

目標(biāo)的概念模型如下建立：

n表示敵方目標(biāo)的總數(shù)，表示敵方第j個目標(biāo)。

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

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

3.2 WTA數(shù)學(xué)模型的建立

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

? ? （2）

（3）

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

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

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

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

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

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

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

4 WTA求解算法

4.1傳統(tǒng)遺傳算法求解

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

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

第2步：對種群中所有個體在WTA問題中的適應(yīng)度函數(shù)值進行計算，并判斷結(jié)果是否滿足優(yōu)化準(zhǔn)則，若滿足，則將該個體及其代表的最優(yōu)解輸出，結(jié)束計算，若不符合則執(zhí)行第3步;

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

第4步：按照設(shè)定的交叉概率和交叉操作方法，產(chǎn)生新的個體;

第5步：按照設(shè)定的變異概率和變異操作方法，產(chǎn)生新的個體;

第6步：將交叉和變異產(chǎn)生的新一代個體組成新一代種群，執(zhí)行第2步。

遺傳算法中的優(yōu)化準(zhǔn)則：不同問題的有不同的優(yōu)化準(zhǔn)則。本文研究的優(yōu)化問題中所采用的優(yōu)化準(zhǔn)則為遺傳迭代次數(shù)是否超過預(yù)先設(shè)定值。

4.2傳統(tǒng)遺傳算法的局限性

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

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

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

4.3改進遺傳算法

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

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

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

5 實驗及結(jié)果

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

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

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

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

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

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

6 結(jié)語

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

參考文獻

[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]余家祥，趙曉哲，史紅權(quán)等.基于遺傳算法的編隊區(qū)域防空武器分配方法[J].現(xiàn)代防御技術(shù)，2013，41（1）：82-87.

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

[5]韓松臣.導(dǎo)彈武器系統(tǒng)效能分析的隨機理論方法[M].國防工業(yè)出版社，2001.

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

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

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

[9]林川.粒子群優(yōu)化與差分進化算法研究及其應(yīng)用[D].西南交通大學(xué)，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