一種基于蟻群算法的準動態(tài)防空武器分配算法

張彥芳，閆德恒，王冀揚，曹震

（中國電子科技集團公司第二十八研究所，南京210007）

一種基于蟻群算法的準動態(tài)防空武器分配算法

張彥芳，閆德恒，王冀揚，曹震

（中國電子科技集團公司第二十八研究所，南京210007）

武器目標分配問題是一個典型的限制組合優(yōu)化問題，旨在得到在整個防御階段中針對目標函數(shù)的最優(yōu)武器分配方案。分配算法主要分為靜態(tài)和動態(tài)兩大類。針對傳統(tǒng)靜態(tài)分配模型中存在的幾點問題，提出了基于時間窗的準動態(tài)武器目標分配算法，該算法綜合考慮攔截概率、攔截時間和武器耗費多個優(yōu)化指標，并將該算法推廣至多類防空武器的優(yōu)化分配中。通過大量實驗驗證，該算法在性能、時間復雜度等方面均有較大優(yōu)勢，并且能較好地適應戰(zhàn)場態(tài)勢的變化，及時調(diào)整分配方案，具有很好的實用性。

武器目標分配，武器-目標時間窗，蟻群算法

0　引言

武器目標分配作為軍事運籌學理論研究領域的一個重要問題，這方面的研究可以追溯至上世紀50年代。武器目標分配是防御方通過分析敵方來襲武器的威脅等級和己方武器的武器狀態(tài)及武器對目標的殺傷概率等綜合因素，按一定的分配原則和約束條件給出合理的武器目標分配方案，以便達到特定的戰(zhàn)術目標。隨著現(xiàn)代戰(zhàn)爭快速決策以及高技術武器平臺的出現(xiàn)，自動武器目標分配技術已變得不可或缺。至今，武器目標分配可以分為兩大類：靜態(tài)分配模型和動態(tài)分配模型。在靜態(tài)分配模型中，認為武器、目標和保衛(wèi)目標的數(shù)目，以及武器目標的位置等參數(shù)是已知的，決策是在一個階段內(nèi)進行的；動態(tài)分配模型［8］是一個多階段的決策問題，每個階段的結(jié)果會影響后面階段的決策，武器和目標數(shù)量在每個階段都有變化。由于動態(tài)武器目標分配算法復雜度的限制，目前的研究主要集中在靜態(tài)分配算法上。

Hosein，Athans［1］提出了一種基于資源的靜態(tài)武器目標分配模型。Karasakal［2］將來襲目標的概率作為WTA的目標函數(shù)，該模型應用于海軍任務組。另一些學者提出了基于目標的SWTA模型，這些模型不直接利用防御資源的重要程度，每一個目標具有一定的威脅值，模型的優(yōu)化目標是最小化所有目標的威脅值?；谶@些靜態(tài)模型，學者們也提出了一些最優(yōu)化方法解決SWTA問題，隨著計算機技術的發(fā)展，大量的最優(yōu)化算法被用于解決SWTA問題，例如：神經(jīng)網(wǎng)絡（Neural Network）［9］，遺傳算法（Genetic Algorithm）［4-5］，禁忌算法（Tabu Search）［3，14］，模擬退火算法（simulated annealingalgorithms）［10］，蟻群算法（Ant-colony optimization）［17］和粒子群算法（particle swarm optimization）［6-7］。

上述靜態(tài)武器目標分配模型存在一定限制：①未考慮武器和目標的時間窗，武器只能進行一次分配，利用率較低；②多考慮單通道武器，不能對多通道武器進行分配。本文針對SWTA模型存在的上述兩方面限制，提出了一種新的時間復用準動態(tài)武器目標分配算法，并將該模型應用于多通道武器。

1　準動態(tài)武器目標分配模型

傳統(tǒng)的SWTA模型中，所有的防御方的武器和來襲目標狀態(tài)固定，所有的參數(shù)對決策者公開并且恒定。具體來講，SWTA問題是指進攻方使用武器襲擊防御方的資源，防御方根據(jù)情報信息進行武器分配攔截這些目標。各個目標對防御資源的威脅值已知，武器對目標的殺傷概率已知。SWTA有一個基本假設：一個武器-目標對同其他武器-目標對的交戰(zhàn)相互獨立，即武器-目標配對的殺傷概率相互獨立。

防空武器在分配過程中主要受到3個方面的限制：①能力限制，武器是否能夠攔截目標（武器性能、武器狀態(tài)）；②資源限制，武器是否有足夠的彈藥攔截目標；③交戰(zhàn)可行性限制（目標是否在武器的殺傷范圍內(nèi)）。以最小化保衛(wèi)資源受到的威脅為例，優(yōu)化目標函數(shù)如下：

各參數(shù)的物理意義見表1。

第1條限制條件限制了分配給第i個目標的武器數(shù)最多為mi；第2條限制條件限制了某一個武器只能攔截一個目標。

1.1武器-目標配對時間窗

針對上述靜態(tài)SWTA模型中單個武器只能進行一次分配的限制，本文提出了利用建立武器與目標的時間窗，實現(xiàn)武器在時間上的可復用。武器分配給某個特定目標僅需在一段時間內(nèi)攔截該目標，其他時間仍可以分配給其他目標。以防空武器為例，在對前一目標實施攔截后，只要滿足轉(zhuǎn)火時間的要求仍可對后續(xù)目標進行攔截。建立武器-目標時間窗yij（t），t∈［t1，t2］，t1，t2分別是武器j可分配給目標i的起止時間。因此，相比傳統(tǒng)的SWTA模型，武器-目標分配標志xij需要具有時間屬性，即xij（t），若第j個武器分配給第i個目標則xij（t）=1，t∈［t1，t2］。引入時間窗概念后，靜態(tài)武器目標分配模型的限制條件修改為式（2）：

其中，fj（t）表示t時刻武器j最多可分配的目標數(shù)。對于一般的單通道武器fj（t）=1，對于多通道武器平臺fj（t）＞1。如圖1所示，第j個武器在［t1，t3］時刻分配給第i1個目標，［t4，t6］時刻分配給第i2個目標，［t2，t5］時刻分配給第i3個目標，［t7，t8］時刻分配給第i4個目標，但是不能分配給第i5個目標，該時間段內(nèi)武器平臺可攔截目標數(shù)已飽和，不能再次進行分配。

圖1　武器-目標時間窗函數(shù)

1.2準動態(tài)武器目標分配模型

結(jié)合靜態(tài)武器目標分配模型，本文提出基于時間窗的準動態(tài)武器目標分配模型如下：

該模型遵循了：①被摧毀保衛(wèi)資源最小化；②來襲目標被盡早攔截；③最小化武器資源耗費3條原則。其中，以第1條原則為主要原則。對于目標被攔截時間利用函數(shù)進行量化，其中t為目標距離攔截點的時間，max t為所有目標距攔截點時間的最大值。利用該函數(shù)對攔截時間進行重新量化，攔截時間越早使得目標函數(shù)越小，并且攔截時間越大曲線的曲率越小，對目標函數(shù)的影響變化率越小，符合指揮官的經(jīng)驗認識。

第1條限制條件限制了分配給第i個目標的武器數(shù)最多為mi；第2條限制條件限制了同時分配給某一個武器的目標數(shù)不能超過其可用通道數(shù)。

圖2　攔截時間量化圖

表1給出了目標函數(shù)中各參數(shù)的物理意義。

表1　參數(shù)說明表

1.3改進蟻群算法

傳統(tǒng)的WTA問題求解算法，例如：隱枚舉法、分支定界法、割平面法等，算法復雜度較高，難以處理大規(guī)模的WTA問題。隨著計算機技術的發(fā)展，一些新穎的優(yōu)化算法，例如：人工神經(jīng)網(wǎng)絡、遺傳算法、粒子群算法、模擬退火算法等被廣泛應用于WTA問題的求解。將蟻群算法應用于WTA求解，通過螞蟻的搜索構(gòu)造問題的可行解。螞蟻從初始位置開始以不同的概率選擇下一個目標，最終遍歷所有的目標，建立一個可行解。將所有可分配的武器-目標配對作為初始的可行解集合，隨機選擇一個目標，在可行解集合中按概率選擇一個可行的武器，之后更新可行解集合。螞蟻隨機走到下一個未分配的目標，重復上述過程直到遍歷所有目標。在選擇可分配武器的選擇概率可表示如下：

同時將NA只螞蟻隨機投放于各個目標，開始搜索可行分配方案，如圖3所示，每只螞蟻從初始目標開始，按照selij選擇武器，然后在未分配的目標中隨機選取下一目標直到所有目標都進行了武器分配。一輪搜索后可得NA個可行分配方案，分別評估這些分配方案目標函數(shù)值。選擇最優(yōu)分配方案Abest。利用該方案的目標函數(shù)值J（Abest）對該方案中的各武器-目標配對的信息素進行更新：

其中Q為常量，ρ為信息素的揮發(fā)速率。在更新時，需將信息素的值限制在一定范圍內(nèi)，這樣可延遲搜索陷入局部最優(yōu)解。

圖3　蟻群算法求解武器目標分配示意圖

為了避免蟻群算法過早陷入局部最優(yōu)解，利用以下兩個策略，幫助蟻群跳出局部最優(yōu)解。

①變異策略。在整個蟻群搜索一次后，對第n只螞蟻得到的解An，從An中第一個分配的目標開始搜索，直到找到一個與An中所有武器—目標配對都不沖突的配對，替換An中該目標的分配武器，生成新的變異解An'。然后評估所有An，An'，得到當前全局最優(yōu)解，更新信息素。

②重置信息素。如果整個蟻群在多次搜索后，最優(yōu)解對目標函數(shù)的適應程度，即J（Abes）t的值無變化，則所有的信息素ij恢復為初始值，整個蟻群重新開始搜索。該策略有助于逃離搜索空間中的局部最優(yōu)解。

2　仿真實驗

為了驗證上述模型，利用模擬防空戰(zhàn)場軟件，模擬戰(zhàn)場環(huán)境，利用上述模型解決武器分配問題。模擬戰(zhàn)場軟件是在Linux系統(tǒng)開發(fā)平臺上，基于QT工具開發(fā)的一款圖形界面應用軟件。該軟件可實現(xiàn)防空武器部署、敵方航跡模擬以及威脅估計和武器分配等功能，為上述模型的驗證提供了很好的平臺支持。

2.1算法復雜度驗證

利用模擬器產(chǎn)生10批敵機目標相對5個保衛(wèi)資源（A1-A5）的威脅值，以及5個防空武器（HA001-HA005）對各目標的射擊時間和殺傷概率如表2～表5所示：

表2　敵機目標相對各保衛(wèi)目標威脅值

表3　防空武器對各敵機目標射擊時間及殺傷概率

表4　武器目標優(yōu)化分配結(jié)果

表5　與其他優(yōu)化算法性能對比

比較傳統(tǒng)蟻群算法、遺傳算法與改進蟻群算法的算法收斂性和時間性能。3種優(yōu)化算法分別運行20次，求其平均收斂值和收斂時間。從比較結(jié)果可以看出，相同的時間復雜度下，改進后的蟻群算法在算法性能優(yōu)于其他兩種優(yōu)化算法。（改進蟻群算法的分配方案與窮舉法相同，目標函數(shù)值誤差由計算誤差引起）

2.2算法適應性驗證

準動態(tài)武器-目標分配算法綜合考慮了武器優(yōu)化分配中的多個要素，為驗證算法的適應性，模擬戰(zhàn)場態(tài)勢的變化，下頁圖4給出了針對兩批目標，根據(jù)相對位置及射擊時間的變化，給出的不同分配方案。其中紅虛線表示主要分配武器，藍虛線表示次要分配武器。從分配結(jié)果可以看出，該算法能較好地適應態(tài)勢的變化，及時調(diào)整分配方案。

圖4　分配方案

利用模擬軟件產(chǎn)生20批敵目標航跡，并部署8個防空武器，位置信息如圖5所示。

圖5（a）是本文提出的準動態(tài)模型得到的分配結(jié)果，圖5（b）是傳統(tǒng)靜態(tài)模型得到的分配結(jié)果，從以上的優(yōu)化分配結(jié)果中可以看出，在目標數(shù)遠大于武器數(shù)時，該算法能優(yōu)先分配威脅大且臨近的目標，防空武器可在不同時間段攔截多個目標，提高了防空武器的利用率。

圖5　分配方案

3　結(jié)論

本文主要研究了指揮控制領域的武器優(yōu)化分配問題，重點介紹了靜態(tài)武器分配問題，提出了基于時間窗的準動態(tài)武器目標分配模型，解決了靜態(tài)武器分配模型對武器的利用率偏低的問題。同時在優(yōu)化目標函數(shù)中，考慮了攔截時間和武器耗費的因素，并且將分配模型推廣應用于多類型防空武器分配中。最后利用模擬戰(zhàn)場軟件，對本文提出的模型算法進行了驗證，實驗結(jié)果表明，該模型能較好地解決戰(zhàn)場上指揮控制中的武器優(yōu)化分配問題，并能較好地適應戰(zhàn)場態(tài)勢的變化，及時調(diào)整分配方案。但是這種基于時間窗的準動態(tài)武器分配模型，仍未能考慮戰(zhàn)場中各種不確定因素，需要進一步完善分配模型。

［1］HOSEIN P A，ATHANSM.Preferential defense strategies. Part I：The static case［J］.MITLaboratory for Information and decision Systemswith partial support，Cambridge，MA，Tech. Rep.LIPS-P-2002，1990.

［2］KARASAKALO.Air defensemissile-targetallocationmod-els for a naval task group.［J］.Computers&Operations Research，2008，35（6）：1759-1770.

［3］BLODGETTD E，GENDREAUM，GUERTIN F，etal.A tabu search heuristic for resourcemanagementin navalwarfare［J］. JournalofHeuristics，2003，9（2）：145-169（25）.

［4］KHOSLA D.Hybrid genetic approach for the dynamic weapon-targetallocation problem［J］.Proceedings of SPIEThe International Society for Optical Engineering，2001：244-259.

［5］ZHIHUA S，F(xiàn)ASHUN Z，DUOLIN Z.A heuristic genetic algorithm for solving constrained Weapon-Target Assignment problem［C］//IEEE International Conference on Intelligent Computing&IntelligentSystems.IEEE，2009：336-341.

［6］BO Z，F(xiàn)ENG X Z，JIA H W.A novel approach to solving weapon-target assignment problem based on hybrid particle swarm optimization algorithm［J］.International Conference on Electronic and Mechanical Engineering and Information Technology，2011：1385-1387.

［7］ZENG X，ZHU Y，NAN L，et al.Solving weapon-target assignment problem using discrete particle swarm optimization［C］//World Congress on Intelligent Control&Automation. IEEE，2006：3562-3565.

［8］XIN B，CHEN J，ZHANG J，etal.Efficient decisionmakings for dynamic weapon-targetassignmentby virtual permutation and tabu search heuristics［J］.Systems Man&Cybernetics Part C Applications&Reviews IEEE Transactions on，2010，40（6）：649-662.

［9］WACHOLDER E，WACHOLDER E.A neural network-based optimization algorithm for the static weapon-targetassignmentproblem［J］.Informs Journalon Computing，1989，1（4）：232-246.

［10］BISHTS.Hybrid genetic-simulated annealing algorithm for optimalweapon allocation inmultilayer defence scenario［J］. Defence Science Journal，2004，45（3）：395-405.

［11］QIYI Z，LI G.Application of hybrid ACA to solve weapon-targetassignmentproblem［C］//InternationalConference on Information Management Innovation Management&Industrial Engineering.IEEE Computer Society，2010：539-542.

［12］CUNGEN C，XIAORU Z，ZAIYUE Z，etal.Immune genetic algorithm forweapon-targetassignmentproblem［C］//Workshop on Intelligent Information Technology Applications. IEEEComputer Society，2007：145-148.

［13］LECHEVIN N，RABBATH C A，ZHANG Y.Information broadcasting algorithm for finite-time reaching-at-risk consensuswith application toweapon-targetassignment［C］//Proceedings of the American Control Conference，2009：3286-3291.

［14］BLODGETT D E，GENDREAU M，GUERTIN F，et al.A tabu search heuristic for resource management in naval warfare［J］.Journal of Heuristics，2003，9（2）：145-169（25）.

A Quasi-dynam ic DefenseW eapon Assignment Algorithm Based on Ant-colony Optim ization

ZHANGYan-fang，YANDe-heng，WANG Ji-yang，CAO Zhen
（The 28th Research Institute of China Electronics Technology Group Corporation，Nanjing 210007，China）

Weapon-target assignment（WTA）is a typical constrained combinatorial optimization problem，subject tomaximize the total value of surviving assets threatened by hostile targets through all defense stages.It includes two versions-static WTA and dynamic WTA.A quasi-dynamic WTA based on time window is proposed in this paper.The algorithm comprehensively take kill probability，kill time and weapon consume into consideration.And it has been applied tomulti-channel defense weapon.A comparison of the proposed algorithm with several existing search approaches shows that the proposed algorithm outperforms its competitors and it ismore adaptable on WTA problems.

weapon-targetassignment，weapon-target timewindow，ant-colony optimization

TP13

A

1002-0640（2016）09-0112-06

2015-07-05

2015-08-07

張彥芳（1987-），女，山西大同人，碩士研究生。研究方向：指揮控制與輔助決策。