火炮武器-目標分配模型及其算法研究

耿修堂，史國清，王　越，石德乾，何　浩

(西北機電工程研究所，陜西 咸陽　712099)

?

火炮武器-目標分配模型及其算法研究

耿修堂，史國清，王越，石德乾，何浩

(西北機電工程研究所，陜西 咸陽712099)

根據火炮不同作戰任務或作戰目的，防空反導火炮作戰目標分配需遵循最大威脅法則，而遠程壓制火炮作戰目標分配需遵循最大毀傷法則。針對火炮武器-目標分配問題，提出了兩種典型的火炮武器-目標分配模型，分別為防空反導、遠程壓制目標分配。針對上述模型提出了基于模擬退火的目標分配優化算法，并通過嵌入局部領域貪婪搜索策略，提高了該算法的收斂速度和搜索效率。仿真結果表明，該算法具有收斂速度快、分配偏差低的優點，在軍事領域具有潛在的應用價值。

火炮武器-目標分配；局部搜索；防空反導；遠程壓制

為了有效解決火力單元與毀傷目標的合理匹配，火炮武器-目標分配NP優化問題被提出。目標分配是火力打擊作戰指揮決策過程中的重要內容，是信息化條件下協同作戰中的一項重要任務。

目標分配問題一直是軍事研究領域的熱點問題，求解目標分配常用方法包括全局搜索算法、動態規劃算法、匈牙利算法[1]和軟計算方法等。近年來各種軟計算方法被頻繁地用于求解火力分配問題，如遺傳算法[2-5]、混合跳蛙算法[3]、捕食搜索算法[4]、蟻群算法[5-7]、人工免疫算法[8]和粒子群優化算法[9]等。同時，各種算法混合應用以提高搜索效率被不斷嘗試。例如，在文獻[3]中遺傳算法和跳蛙算法被混合用于求解火力分配問題；文獻[4]中遺傳算法和捕食搜索算法被混合用于求解火力分配問題；文獻[5]中遺傳算法和蟻群算法被混合用于求解火力分配問題，仿真結果表明能在一定程度上彌補單個算法存在收斂速度或精確度的缺陷。

通過描述火炮武器-目標分配模型，分別建立基于最大威脅法則的防空火炮-目標分配模型及基于最大毀傷法則的壓制火炮-目標分配模型。運用一種簡單的模擬退火算法[10]并進行改進，開展火炮武器-目標分配研究，嘗試用更短時間得到更低分配偏差率，為火炮武器實時火力分配提供參考。

1　火炮武器-目標分配數學模型

筆者主要結合防空反導、遠程壓制兩類典型火炮的作戰任務或目的，分別進行對應的火炮武器-目標分配數學建模。

1.1防空反導火炮武器-目標分配模型

假設在有效的作用區域和時間內，防空反導編隊共有W門防空高炮，T個來襲敵目標，某門防空高炮只能分配給某個來襲目標。假定所有的防空高炮必須分配給來襲目標，分配時刻每門防空高炮對來襲目標的毀傷概率已知，每個來襲目標的威脅度已知。

防空反導火炮防御作戰時，其任務主要是保護軍事要地，故基于最大威脅法則的防空反導火炮武器-目標分配的數學模型為

(1)

式中：X為初始解或決策矩陣；xij為第i門防空高炮對第j個來襲目標的分配結果，xij=0表示未分配，xij= 1表示分配;kij為第i門防空高炮對第j個來襲目標的毀傷概率;wj表示第j個來襲目標的威脅度。

1.2遠程壓制火炮武器-目標分配模型

同樣地，假設在有效的作用區域和時間內，遠程壓制編隊共有W門壓制地炮，T個地面目標，某門壓制地炮只能分配給某個地面目標。假定所有的壓制地炮必須分配給前方地面目標，分配時刻每門壓制地炮對地面目標的毀傷概率已知，每個地面目標的威脅度已知。

壓制火炮遠程壓制作戰時，其任務主要是摧毀前方的地面目標，故基于最大毀傷法則的遠程壓制火炮-目標分配的數學模型為

(2)

類同防空反導模型中的參數定義，X為初始解或決策矩陣；xij為第i門壓制地炮對第j個地面目標的分配結果，xij=0表示未分配，xij=1表示分配;kij為第i門壓制地炮對第j個地面目標的毀傷概率;cj表示第j個地面目標的價值度。

2　火炮武器-目標分配優化算法

2.1模擬退火算法

20世紀80年代，模擬退火思想被成功地引入到組合優化領域。特別是進入21世紀，伴隨著計算機技術發展和計算機的普及，模擬退火算法在工程中得到了廣泛應用。

模擬退火算法來源于固體退火原理，是一種基于概率的算法，將固體加溫至充分高，再讓其逐漸冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而逐漸冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。

模擬退火算法實現時，是從某一較高初溫出發，伴隨溫度參數不斷下降，結合概率突跳特性在可行解空間中隨機尋找目標函數的全局最優解，即局部最優解理論上存在概率性地跳出并最終趨于全局最優的可能。

2.2領域搜索策略

如圖1所示，其中矩陣X[i][j]為初始解，矩陣中元素xij=1表示第i武器分配第j目標，xij=0表示第i武器沒有分配第j目標，這里i=7表示武器數量為7，j=15表示目標數量為15。

圖1中基于某個初始解，領域搜索策略首先隨機選擇第b1武器，再把該武器已分配目標a1變換為新的目標a2，這里a1≠a2。這樣，原來的領域狀態為xb1a1=1、xb1a2=0，領域搜索后，新的領域狀態為xb1a1=0、xb1a2=1。

2.3算法流程

目標分配優化算法流程如圖2所示。

新解的產生和接受主要分為如下幾個步驟：

1)按照各武器分配至當前威脅最大目標的要

求，生成初始解X[i][j]，防空反導火炮武器-目標分配按式(1)計算目標函數，遠程壓制火炮武器-目標分配按式(2)計算目標函數。

2)按照圖1所示的領域搜索策略，隨機生成新解X′[i][j]，按式(1)或(2)計算新目標函數。

3)緩慢降低退火溫度，計算目標函數值增量Δf=f(X′)-f(X)。

4)如果Δf>0或達到貪婪搜索次數，接受新解，X=X′且f(X)=f(X′)；否則，按Metropolis接受新解。

5)如果已達到退火結束溫度，返回最優解，算法結束；否則，重復步驟2至步驟5。

3　仿真分析

3.1案例假定

假設火炮武器的數量為i=7，來襲目標的數量為j=15。武器對目標毀傷概率、目標威脅度權重及目標價值度權重如表1所示。表1中前7行矩陣表示7個武器對15個目標的毀傷概率kij，且0

表1　武器對目標毀傷概率、目標威脅度權重及目標價值度權重

3.2最大威脅法則仿真結果

基于表1案例的最大威脅法則及對應模型的全局搜索計算結果如表2所示。

表2　最大威脅法則全局搜索仿真結果

基于表1案例的防空反導火炮武器-目標分配的最大威脅法則及對應模型的仿真計算和結果如表3所示。其中偏差率=(次優解-最優解)/最優解×100%。

表3　最大威脅法則局部搜索仿真結果

如表2、3所示，當采用全局搜索求解最優解需耗時53 916 ms；而采用本文算法求解最優解只需26.733 ms，偏差率為0.0%；求解次優解分別需耗時19.260、13.688和4.4767 ms(偏差率分別為1.38%、2.58%和5.88%)。對應的最優解矩陣如圖3所示。

3.3最大毀傷法則仿真結果

基于表1案例的最大毀傷法則及對應模型的全局搜索計算結果如表4所示。

表4　最大毀傷法則全局搜索仿真結果

基于表1案例的遠程壓制火炮武器-目標分配的基于最大毀傷法則及對應模型的仿真計算和結果如表5所示。其中偏差率=(最優解-次優解)/最優解×100%。

表5　最大毀傷法則局部搜索仿真結果

如表4、5所示，當采用全局搜索求解最優解需耗時57 541 ms；而采用本文算法求解最優解需時25.828 ms，偏差率為0.0%；求解次優解分別需18.727、12.928和4.283 2 ms(偏差率分別為1.03%、1.03%和2.55%)。對應的最優解矩陣如圖4所示。

4　結束語

現代戰爭越來越重視火控協同和系統作戰，武器系統越來越復雜，指揮決策的時效性越來越重要。在此背景之下，目標分配面臨速度和精度雙重挑戰。傳統的全局搜索算法在有限的時間內已不能求解目標分配問題，而各種啟發式算法能在有限的時間內求解出能夠接受的次優解，在軍事信息處理領域具有潛在的應用價值，提出的火炮武器-目標分配模型及改進模擬退火啟發式優化算法，僅僅從基礎理論角度進行初步的分析和驗證，毀傷概率、威脅度、價值度等都是隨機生成的，旨在驗證算法的有效性。而要實現火炮武器-目標分配工程化應用需要對目標特性、分配模型進行更深入的研究和適應性改進，特別是威脅度、毀傷度建模，并建立對應的特性專家庫，這是下一步工作研究重點。

References)

[1]彭琛, 李建立, 王琦. 基于改進匈牙利算法的自組網火力分配[J]. 彈箭與制導學報, 2014, 34(5): 169-172,179.

PENG Chen, LI Jianli, WANG Qi. Firepower assignment by improved Hungarian algorithm based on ad hoc networks[J]. Journal of Projectiles, Rockets, Missiles and Gui-dance, 2014, 34(5): 169-172,179. (in Chinese)

[2]LEE Znejung, SU Shunfeng, LEE Chouyuan. Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics[J]. IEEE Transactions on Systems, Man, and Cybernetics，Part B: Cybernetics, 2003, 33(1): 113-121.

[3]阮旻智, 李慶民, 劉天華. 編隊防空火力分配建模及其優化方法研究[J]. 兵工學報, 2010, 31(11):1525- 1529.

RUAN Minzhi, LI Qingmin, LIU Tianhua. Modeling and optimization on fleet antiaircraft firepower allocation[J]. Acta Armamentarii, 2010, 31(11): 1525-1529. (in Chinese)

[4]汲萬峰, 王光源, 章堯卿, 等. 基于PSGA的岸基導彈火力分配研究[J]. 現代防御技術, 2014, 42(2): 77-83, 94.

JI Wanfeng, WANG Guangyuan, ZHANG Yaoqing, et al. Fire distribution for shore-based missiles based on PSGA[J]. Modern Defence Technology, 2014, 42(2): 77-83, 94. (in Chinese)

[5]陳云飛, 劉玉樹, 范潔, 等. 火力優化分配問題的小生境遺傳螞蟻算法[J]. 計算機應用, 2005, 25(1): 206- 209.

CHEN Yunfei, LIU Yushu, FAN Jie, et al. Niche-based genetic & ant colony optimization algorithm for generalized assignment problem[J]. Computer Applications, 2005, 25(1): 206-209. (in Chinese)

[6]LEE Znejung, SU Shunfeng, LEE Chouyuan. An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem[J]. Applied Soft Computing, 2002(2): 39-47.

[7]郭蘊華, 李運濤, 楊福緣. 考慮毀傷概率門限的火力分配變異蟻群算法[J]. 火炮發射與控制學報, 2006(4): 1-5,11.

GUO Yunhua, LI Yuntao, YANG Fuyuan. Mutation ant colony algorithm for weapon target assignment problem based on threshold of damage probability[J]. Journal of Gun Launch & Control, 2006(4): 1-5,11. (in Chinese)

[8]張凱, 周德云, 潘潛. 基于混合蛙跳算法的協同空戰火力分配[J]. 計算機工程與應用, 2014, 50(17):263- 266.

ZHANG Kai, ZHOU Deyun, PAN Qian. Weapon-target assignment based on shuffled frog leaping algorithm in cooperative air combat[J]. Computer Engineering and Applications, 2014, 50(17): 263-266. (in Chinese)

[9]王光源, 徐鵬飛, 趙勇. 基于粒子群優化算法求解火力分配問題[J]. 艦船電子工程, 2013, 33(11):34- 36.

WANG Guangyuan, XU Pengfei, ZHAO Yong. A solution of weapon-target assignment problems based on particle swarm optimization[J]. Ship Electronic Engineering, 2013, 33(11): 34-36.(in Chinese)

[10]GENG Xiutang, XU Jin, XIAO Jianhua, et al. A simple simulated annealing algorithm for the maximum clique problem[J]. Information Sciences, 2007, 177(22): 5064-5071.

Research on Model and Algorithm for Artillery Weapon-target Assignment

GENG Xiutang, SHI Guoqing, WANG Yue, SHI Deqian, HE Hao

(Northwest Institute of Mechanical & Electrical Engineering, Xianyang712099, Shaanxi, China)

According to the different operational tasks and purposes of artillery, weapon-target assignment for air defense and anti-missile artillery needs to follow maximum threat principles, while weapon-target assignment for remote attacking artillery needs to follow maximum damage principles. With regard to the artillery weapon-target assignment problem, two models for air defense and anti-missile and remote attacking are proposed. The weapon-target assignment optimization algorithm based on simulated annealing is presented, and the convergence rate and searching efficiency for the algorithm are enhanced by means of embedding greedy search strategy in local area. Computational results indicate that the proposed algorithm has the advantage of fast convergence rate and low allocation deviation, and can find potential application value in military field.

artillery weapon-target assignment; local search; air defense and antimissile; long range neutralization

10.19323/j.issn.1673-6524.2016.02.009

2015-10-19

兵器支撐預研項目(62201020101)

耿修堂(1975—)，男，博士，高級工程師，主要從事火炮信息與控制技術研究。E-mail：gxt1028@163.com

TJ301

A

1673-6524(2016)02-0041-05