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

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

?

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

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

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

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

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

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

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

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

1　火炮武器-目標分配數(shù)學模型

筆者主要結(jié)合防空反導、遠程壓制兩類典型火炮的作戰(zhàn)任務(wù)或目的，分別進行對應(yīng)的火炮武器-目標分配數(shù)學建模。

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

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

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

(1)

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

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

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

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

(2)

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

2　火炮武器-目標分配優(yōu)化算法

2.1模擬退火算法

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

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

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

2.2領(lǐng)域搜索策略

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

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

2.3算法流程

目標分配優(yōu)化算法流程如圖2所示。

新解的產(chǎn)生和接受主要分為如下幾個步驟：

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

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

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

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

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

5)如果已達到退火結(jié)束溫度，返回最優(yōu)解，算法結(jié)束；否則，重復(fù)步驟2至步驟5。

3　仿真分析

3.1案例假定

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

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

3.2最大威脅法則仿真結(jié)果

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

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

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

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

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

3.3最大毀傷法則仿真結(jié)果

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

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

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

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

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

4　結(jié)束語

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

References)

[1]彭琛, 李建立, 王琦. 基于改進匈牙利算法的自組網(wǎng)火力分配[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]阮旻智, 李慶民, 劉天華. 編隊防空火力分配建模及其優(yōu)化方法研究[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]. 現(xiàn)代防御技術(shù), 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]陳云飛, 劉玉樹, 范潔, 等. 火力優(yōu)化分配問題的小生境遺傳螞蟻算法[J]. 計算機應(yīng)用, 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]. 火炮發(fā)射與控制學報, 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]張凱, 周德云, 潘潛. 基于混合蛙跳算法的協(xié)同空戰(zhàn)火力分配[J]. 計算機工程與應(yīng)用, 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]王光源, 徐鵬飛, 趙勇. 基于粒子群優(yōu)化算法求解火力分配問題[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

兵器支撐預(yù)研項目(62201020101)

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

TJ301

A

1673-6524(2016)02-0041-05