梁少帥，邱滌珊，楊曉凌

（國防科學(xué)技術(shù)大學(xué) 信息系統(tǒng)工程重點實驗室，湖南 長沙 410073）

武器目標(biāo)分配（Weapon Target Allocation，WTA）問題是軍事運(yùn)籌學(xué)研究的重要理論問題，也是防空作戰(zhàn)指揮決策中迫切需要解決的現(xiàn)實問題。當(dāng)前，對靜態(tài)WTA問題的研究比較深入，而動態(tài)WTA問題，由于需要考慮時間、事件等因素，相對較為復(fù)雜，目前仍無非常有效地解決方法，因而成為當(dāng)前研究的一個熱點。

動態(tài)WTA問題是一個NP-complete問題[1]，并具有離散性、動態(tài)性、非線性、隨機(jī)性、大規(guī)模性等特點，不存在非常有效的優(yōu)化算法。動態(tài)WTA主要分為武器目標(biāo)分配方案和射擊時機(jī)確定兩個方面。目前對于動態(tài)WTA問題的研究主要集中在分配方案的求解方法上[2]，主要有分階段求解方法[3-4]、馬爾可夫過程分析方法[5-6]、anytime算法[7-8]。

從現(xiàn)在已公開發(fā)表的文獻(xiàn)來看，現(xiàn)有的研究方法很少考慮隨機(jī)出現(xiàn)的新目標(biāo)對當(dāng)前正在優(yōu)化中的分配決策的影響，對于事件的處理不夠靈活。新出現(xiàn)的目標(biāo)不能在算法沒有停止的時候動態(tài)地加入當(dāng)前處理過程，算法總是結(jié)束對一批目標(biāo)的分配后再進(jìn)行對后續(xù)目標(biāo)的分配。在射擊時機(jī)確定問題上，有些文獻(xiàn)[9]并沒有考慮動態(tài)WTA的射擊時機(jī)問題，而有些文獻(xiàn)[8]只是簡單考慮武器目標(biāo)分配的截止期，并不能很好反映真實的防空作戰(zhàn)需求。

針對上述文獻(xiàn)的不足，根據(jù)防空作戰(zhàn)中事件對動態(tài)WTA問題的影響，筆者提出了基于事件驅(qū)動的動態(tài)WTA改進(jìn)蟻群算法，通過對事件的處理，動態(tài)地進(jìn)行武器目標(biāo)分配，并在滿足時空約束的前提下，根據(jù)當(dāng)前最優(yōu)解確定目標(biāo)的射擊時機(jī)，在射擊時機(jī)成熟時輸出對目標(biāo)的武器分配方案。

1 動態(tài)WTA問題描述

動態(tài)WTA主要考慮時間因素對WTA的影響，實際上是由一系列的靜態(tài)WTA構(gòu)成。在考慮時空約束的情況下，在一次分配方案中采用靜態(tài)WTA方法，通過對到達(dá)事件的處理，動態(tài)地改變WTA問題的參數(shù)，并根據(jù)當(dāng)前最優(yōu)解判斷是否需要對某一目標(biāo)發(fā)射防空導(dǎo)彈。如果不需要發(fā)射防空導(dǎo)彈，則繼續(xù)優(yōu)化，否則輸出對該目標(biāo)的分配方案，其他目標(biāo)的分配方案繼續(xù)優(yōu)化。

1.1WTA問題描述

WTA問題可以簡單描述為M個防空單元對抗N個空中目標(biāo)。典型WTA問題模型可描述如下：

其中νi為目標(biāo)的威脅度，Pij為防空單元j對目標(biāo)i成功攔截概率。

假定一個防空單元只能同時攔截一個目標(biāo)，一個目標(biāo)只可以同時被一個防空單元攔截，各個防空單元對目標(biāo)的攔截概率都是獨(dú)立的。目標(biāo)函數(shù)的約束條件為：

為簡化模型，需要將防空單元和空中目標(biāo)的數(shù)量調(diào)整到同樣大小。當(dāng)防空單元的個數(shù)小于空中目標(biāo)時，則設(shè)置相應(yīng)數(shù)量的虛防空單元，虛防空單元對各目標(biāo)的攔截概率為0；當(dāng)目標(biāo)數(shù)量小于防空單元時，則設(shè)置相應(yīng)數(shù)量的虛目標(biāo)，虛目標(biāo)的威脅度為0。

另外，當(dāng)防空單元向目標(biāo)發(fā)射導(dǎo)彈后，該目標(biāo)和所分配的防空單元處于分配凍結(jié)狀態(tài)，所分配的防空單元在防空導(dǎo)彈與目標(biāo)遭遇前不再分配給其他目標(biāo)，其他導(dǎo)彈也不會分配給該目標(biāo)。當(dāng)防空單元向目標(biāo)發(fā)射防空導(dǎo)彈后一定時間，如果評估或觀測結(jié)果認(rèn)為該目標(biāo)未被摧毀，則目標(biāo)和所分配的導(dǎo)彈不再處于凍結(jié)狀態(tài)，重新參與武器目標(biāo)分配過程。

1.2 動態(tài)武器目標(biāo)分配流程

動態(tài)WTA由一系列靜態(tài)WTA構(gòu)成，每一次的武器分配方案由靜態(tài)WTA完成，并通過對事件的處理，動態(tài)地調(diào)整靜態(tài)WTA的參數(shù)，從而達(dá)到動態(tài)處理WTA問題的方法。其具體步驟如圖1所示。

圖1 動態(tài)WTA流程Fig.1 Flow chart of dynamic WTA

1.3 防空作戰(zhàn)事件對動態(tài)WTA問題的影響

防空作戰(zhàn)中，不同種類的事件將對武器目標(biāo)分配產(chǎn)生不同影響。對防空作戰(zhàn)過程產(chǎn)生影響的事件主要有：

1）目標(biāo)信息更新 目標(biāo)信息更新使得目標(biāo)的威脅度和防空單元對目標(biāo)的毀傷概率發(fā)生變化，從而改變武器目標(biāo)分配方案。根據(jù)新的目標(biāo)信息，重新計算目標(biāo)的威脅度和各個防空單元對目標(biāo)的攔截概率，使得分配方案體現(xiàn)目標(biāo)信息更新的影響。

2）目標(biāo)消失 當(dāng)某一目標(biāo)消失時，可以將該目標(biāo)設(shè)置為虛目標(biāo)。

3）出現(xiàn)新目標(biāo) 出現(xiàn)新目標(biāo)時，需要增加相應(yīng)數(shù)量的虛防空單元。

4）防空單元的損毀（包括彈藥耗盡）防空單元損毀或者彈藥耗盡，可以將該防空單元設(shè)置為虛防空單元。

處理上述事件并不需要中斷算法重新計算，原有的較優(yōu)方案會對事件處理后的方案產(chǎn)生重要影響。當(dāng)一次迭代后，可以消去相同數(shù)目的虛目標(biāo)和虛防空單元，以降低計算規(guī)模。

2 動態(tài)WTA問題的改進(jìn)蟻群算法求解

動態(tài)WTA問題是一個NP-complete問題，只有通過窮舉方法才能得到最優(yōu)解。但防空作戰(zhàn)行動需要實時提供武器目標(biāo)分配方案，這就需要分配方法能夠?qū)崟r輸出較優(yōu)的分配方案。另外，動態(tài)WTA問題需要考慮防空作戰(zhàn)中目標(biāo)信息更新、目標(biāo)消失與出現(xiàn)、防空單元損毀等問題，需要在不中斷算法執(zhí)行的前提下動態(tài)更新算法參數(shù)。而蟻群算法能夠很好的滿足以上兩個要求。

2.1 求解武器目標(biāo)分配的改進(jìn)蟻群算法

防空單元和目標(biāo)均作為蟻群算法中的節(jié)點。螞蟻依據(jù)目標(biāo)威脅度的大小，運(yùn)用輪盤賭的方法隨機(jī)選擇初始目標(biāo)節(jié)點，并從初始目標(biāo)節(jié)點按照信息素大小隨機(jī)移動到未分配目標(biāo)的防空單元節(jié)點上。然后依據(jù)目標(biāo)威脅度的大小，運(yùn)用輪盤賭的方法隨機(jī)選擇一個未分配防空單元節(jié)點的目標(biāo)節(jié)點，并從該目標(biāo)節(jié)點隨機(jī)移動到未分配目標(biāo)節(jié)點的防空單元節(jié)點上，直到所有目標(biāo)節(jié)點都分配防空單元節(jié)點。螞蟻只能從防空單元節(jié)點移動到目標(biāo)節(jié)點，或者從目標(biāo)節(jié)點移動到防空單元節(jié)點，不能在相同類型的節(jié)點間移動。

根據(jù)以上特點，可以設(shè)計改進(jìn)蟻群算法的節(jié)點間信息素因子 τij和啟發(fā)式因子 ηij。 當(dāng) i為目標(biāo)節(jié)點，j為防空單元節(jié)點，τij為可調(diào)的信息素因子，而ηij為防空節(jié)點對目標(biāo)節(jié)點攔截失敗的概率 1-Pij；其他的情況下，τij和 ηij固定為0，并不參與計算。

改進(jìn)蟻群算法的主要步驟是：

1）初始化操作 節(jié)點間的信息素濃度設(shè)為最小值。為提高算法的初始性能，先根據(jù)貪婪算法得到一個局部最優(yōu)解，并更新信息素濃度，使得算法初期就有較優(yōu)的方案。

2）節(jié)點選擇 在時刻，螞蟻從目標(biāo)節(jié)點轉(zhuǎn)移到防空單元節(jié)點的概率為：

其中allowedk為當(dāng)前未分配目標(biāo)的防空單元節(jié)點，α、β分別為信息素因子和啟發(fā)式因子的重要程度。螞蟻從目標(biāo)節(jié)點移動到防空單元節(jié)點的轉(zhuǎn)移概率由信息素濃度和相應(yīng)的攔截概率共同確定。為降低計算規(guī)模，可以優(yōu)先在對目標(biāo)節(jié)點i毀傷概率最大的K個防空單元節(jié)點中分配武器；若K個防空單元都已經(jīng)分配，則從全局未分配目標(biāo)的防空單元節(jié)點中分配武器。

在t時刻，螞蟻k從防空單元節(jié)點m轉(zhuǎn)移到目標(biāo)節(jié)點n的概率為（t）：

（3）信息素更新

只有本次迭代最優(yōu)解的螞蟻更新局部信息素，加強(qiáng)正反饋的效果。根據(jù)本次迭代最優(yōu)解，目標(biāo)節(jié)點i和防空單元節(jié)點j間的局部信息素濃度更新為：

其中Δτ為和本次迭代最優(yōu)解的目標(biāo)函數(shù)值相的信息素增量。

最后，更新全局信息素濃度。目標(biāo)節(jié)點和防空單元節(jié)點間的全局信息素濃度更新為：

其中ρ為信息素?fù)]發(fā)因子。

2.2 改進(jìn)蟻群算法中的事件處理

當(dāng)目標(biāo)信息更新時，目標(biāo)的威脅度和防空單元對目標(biāo)的毀傷概率發(fā)生變化，從目標(biāo)節(jié)點轉(zhuǎn)移到防空單元節(jié)點的概率隨著毀傷概率的改變而改變，從防空單元節(jié)點轉(zhuǎn)移到目標(biāo)節(jié)點的概率隨著目標(biāo)的威脅度改變而改變。

當(dāng)目標(biāo)消失時，該目標(biāo)設(shè)置為虛目標(biāo)，其威脅度為0，從而改變防空單元轉(zhuǎn)節(jié)點移到該目標(biāo)節(jié)點的概率（t）；當(dāng)新目標(biāo)出現(xiàn)，則增加相應(yīng)數(shù)量的虛防空單元。

當(dāng)防空單元損毀或者彈藥耗盡，可以將該防空單元設(shè)置為虛防空單元，其對所有目標(biāo)的攔截概率0，從而改變目標(biāo)節(jié)點轉(zhuǎn)移到該防空單元節(jié)點的概率

2.3 動態(tài)WTA問題的射擊時機(jī)確定

當(dāng)空中目標(biāo)一旦進(jìn)入防空單元的發(fā)射區(qū)時，理論上可以盡早發(fā)射防空導(dǎo)彈進(jìn)行攔截。但此時防空單元距離目標(biāo)較遠(yuǎn)，對目標(biāo)的毀傷概率較小，并不能發(fā)揮防空單元的最大作戰(zhàn)效益。隨著目標(biāo)的持續(xù)臨近，防空單元對該目標(biāo)的毀傷概率增大，此時發(fā)射防空導(dǎo)彈，雖然毀傷概率增大，但降低了再次攔截的機(jī)會，一旦攔截失敗，可能沒有機(jī)會再次攔截。另外，如果目標(biāo)是攜帶對地攻擊導(dǎo)彈的飛機(jī)，在持續(xù)臨近中有可能構(gòu)成發(fā)射對地攻擊導(dǎo)彈的條件，此時，不但需要攔截飛機(jī)，還需要攔截對地攻擊導(dǎo)彈，直接影響作戰(zhàn)效益。

文中將空中目標(biāo)分為飛機(jī)和對地攻擊導(dǎo)彈兩種類型，并假定防空導(dǎo)彈的射程大于對地攻擊導(dǎo)彈的射程。因為需要考慮飛機(jī)所攜帶的對地攻擊導(dǎo)彈，本文定義威脅躍升點這一概念，如果防空單元在飛機(jī)處于該點時發(fā)射防空導(dǎo)彈，則可以在飛機(jī)所攜帶的對地攻擊導(dǎo)彈的最大發(fā)射距離上遭遇飛機(jī)，如果攔截成功，飛機(jī)無法發(fā)射對地攻擊導(dǎo)彈。

當(dāng)飛機(jī)位于威脅躍升點之外時，如果飛機(jī)i的威脅度和防空單元j對其的毀傷概率的乘積大于一個閾值δ，即νiPij＞δ，則對該目標(biāo)發(fā)射防空導(dǎo)彈。當(dāng)飛機(jī)位于威脅躍升點以內(nèi)時，則盡早發(fā)射防空導(dǎo)彈，以減少飛機(jī)發(fā)射對地攻擊導(dǎo)彈的機(jī)會，減少需要攔截目標(biāo)的數(shù)量，并增加攔截失敗后再次攔截的機(jī)會。

對于對地攻擊導(dǎo)彈，則盡早發(fā)射防空導(dǎo)彈，增加攔截失敗后再次攔截的機(jī)會。

在動態(tài)WTA的改進(jìn)蟻群算法中，如果根據(jù)當(dāng)前最優(yōu)解或者本次迭代最優(yōu)解得到目標(biāo)滿足發(fā)射防空導(dǎo)彈的條件，則分配對應(yīng)的防空單元攔截該目標(biāo)，其他目標(biāo)繼續(xù)持續(xù)優(yōu)化。當(dāng)某一目標(biāo)的射擊條件滿足時，只需要輸出該目標(biāo)的武器分配決策，其他目標(biāo)可能還有充分的優(yōu)化時間，也就是說算法以“一個目標(biāo)接一個目標(biāo)”的方式進(jìn)行武器分配。如果匆匆輸出所有目標(biāo)的分配決策，可能使攔截效果大大下降。

3 仿真結(jié)果

在仿真實驗中，假設(shè)初始時防空單元和空中目標(biāo)的數(shù)量分別為100，目標(biāo)的威脅度在0.0～1.0之間隨機(jī)生成，防空單元對各個目標(biāo)的毀傷概率在0.2～0.9之間隨機(jī)產(chǎn)生。蟻群算法中，信息素因子α、啟發(fā)式因子β、信息素?fù)]發(fā)因子ρ分別為和 1.0、1.0、0.3。 在蟻群算法的 100 次迭代中，在 21、41、61、81次迭代時分別出現(xiàn)目標(biāo)狀態(tài)更新、目標(biāo)消失、新目標(biāo)出現(xiàn)、防空單元損毀等事件。基于事件驅(qū)動的動態(tài)WTA蟻群算法可以平滑地處理事件，算法的目標(biāo)函數(shù)值沒有較大波動；而多階段的動態(tài)WTA蟻群算法在事件發(fā)生時，只是簡單的中斷算法并按照新的數(shù)據(jù)重新進(jìn)行計算，目標(biāo)函數(shù)值會出現(xiàn)較大波動，其整體優(yōu)化性能低于基于事件驅(qū)動的動態(tài)WTA蟻群算法，如圖2所示。另外，當(dāng)?shù)螖?shù)增加時，改進(jìn)蟻群算法的性能優(yōu)于貪婪算法。為降低計算規(guī)模，可以優(yōu)先在對目標(biāo)節(jié)點毀傷概率最大的K個防空單元節(jié)點中分配武器。若K個防空單元都已分配目標(biāo)，則從全局未分配目標(biāo)的防空單元節(jié)點中分配武器。

仿真實驗考查了防空單元和空中目標(biāo)的數(shù)量分別為100的規(guī)模下，蟻群算法迭代200次，K取值對當(dāng)前最優(yōu)解的目標(biāo)函數(shù)值、運(yùn)行時間以及兩者乘積的影響，如圖3、圖4、圖5所示。通過分析可得，當(dāng)K較大時，算法中可優(yōu)先選擇的防空單元節(jié)點較多，收斂較慢，運(yùn)行時間長；當(dāng)較小時，目標(biāo)節(jié)點可以優(yōu)先選擇的防空單元節(jié)點可能已經(jīng)分配目標(biāo)，只能從全局去尋找最優(yōu)解，收斂較慢，運(yùn)行時間長；當(dāng)K取3～7時，目標(biāo)函數(shù)值與運(yùn)行時間都較小，算法能夠得到滿意的性能。

圖2 目標(biāo)函數(shù)值比較Fig.2 Comparing the objective function value

圖3 K對目標(biāo)函數(shù)值的影響Fig.3 The impact of K on the objective function value

圖4 K對運(yùn)行時間的影響Fig.4 The impact of K on the running time

4 結(jié)束語

圖5 K對目標(biāo)函數(shù)值和運(yùn)行時間乘積的影響Fig.5 The impact of K on the product

動態(tài)WTA問題，由于考慮時間等因素，相對復(fù)雜，目前仍無非常有效的解決方法，因而成為當(dāng)前研究的一個熱點。本文針對當(dāng)前動態(tài)WTA問題研究中的不足，提出了基于事件驅(qū)動的動態(tài)武器目標(biāo)分配的改進(jìn)蟻群算法。通過處理事件，動態(tài)地改變蟻群算法的參數(shù)，使算法的優(yōu)化體現(xiàn)動態(tài)特性，并且原有的優(yōu)化方案對事件處理后的方案產(chǎn)生影響。改進(jìn)蟻群算法運(yùn)算速度快，解的質(zhì)量基本令人滿意，可用于解決較大規(guī)模的動態(tài)WTA問題。仿真實驗表明了算法的有效性。

[1]Lloyd S P， Witsenhausen H S.Weapons allocation is NP－complete[C]//Proceedings of the IEEE Summer Simulation Conference， 1986：1054－1058.

[2]劉傳波，邱志明，吳玲，等.動態(tài)武器目標(biāo)分配問題的研究現(xiàn)狀與展望[J].電光與控制， 2010， 17（11）:43－47.LIU Chuan-bo， QIU Zhi-ming， WU Ling， et al.Review on current status and prospect of researches on dynamic weapon target assignment.Electronics optics&control， 2010， 17（11）:43－47.

[3]Hosein P， Walton J， Athans M.Dynamic weapon－target assignment problems with vulnerable C2 nodes[R].LIDS_P_1786，MIT，1988.

[4]Hosein P， Athans M.An asymptotic result for the multistage weapon target allocation problem [R].LIDS－P－945，MIT，1990.

[5]楊祖快，劉鼎臣.基于馬爾可夫決策過程動態(tài)WTA最優(yōu)化模型分析[J].火力與指揮控制， 2003， 28（5）:25－27.YANG Zu-kuai， LIU Ding-chen.Optimization model analysis of dynamic WTA based on Markov Decision-making[J].Fire Control&Command Control， 2003， 28（5）:25－27.

[6]蔡懷平，劉景旭，陳英武.動態(tài)武器目標(biāo)分配問題的馬爾可夫性[J].國防科技大學(xué)學(xué)報， 2006， 28（3）:124－127.CAI Huai-ping， LIU Jing-xu， CHEN Ying-wu.On the markov characteristic of dynamic weapon target assignment problem[J].JournalofNation University ofDefense Technology， 2006， 28（3）:124－127.

[7]Khosla D.Hybrid genetic approach for the dynamic weapontarget allocation problem[C]//Proceeding of SPIE， 2001，4396:248-263.

[8]WU Ling， WANG Hang-yu， LU Fa-xing.An anytime algorithm based on modified GA for dynamic weapontarget allocation problem[C]//WCCI， Hong Kong， China，2008:234-238.

[9]蔡懷平，陳英武，邢立寧.SVNTS算法的動態(tài)武器目標(biāo)分配問題研究[J].計算機(jī)工程與應(yīng)用，2006，42（31）:7-10 CAI Huai-ping， CHEN Ying-wu， XING Li-ning.Research on dynamic weapon target assignment problem based on SVNTS algorithm[J].Computer engineering and applications， 2006，42（31）:7-10.