耿修堂，史國(guó)清，王　越，石德乾，何　浩

(西北機(jī)電工程研究所，陜西 咸陽(yáng)　712099)

?

火炮武器-目標(biāo)分配模型及其算法研究

耿修堂，史國(guó)清，王越，石德乾，何浩

(西北機(jī)電工程研究所，陜西 咸陽(yáng)712099)

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

火炮武器-目標(biāo)分配；局部搜索；防空反導(dǎo)；遠(yuǎn)程壓制

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

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

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

1　火炮武器-目標(biāo)分配數(shù)學(xué)模型

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

1.1防空反導(dǎo)火炮武器-目標(biāo)分配模型

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

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

(1)

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

1.2遠(yuǎn)程壓制火炮武器-目標(biāo)分配模型

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

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

(2)

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

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

2.1模擬退火算法

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

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

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

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

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

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

2.3算法流程

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

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

1)按照各武器分配至當(dāng)前威脅最大目標(biāo)的要

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

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

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

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

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

3　仿真分析

3.1案例假定

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

表1　武器對(duì)目標(biāo)毀傷概率、目標(biāo)威脅度權(quán)重及目標(biāo)價(jià)值度權(quán)重

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

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

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

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

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

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

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

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

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

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

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

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

4　結(jié)束語(yǔ)

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

References)

[1]彭琛, 李建立, 王琦. 基于改進(jìn)匈牙利算法的自組網(wǎng)火力分配[J]. 彈箭與制導(dǎo)學(xué)報(bào), 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]阮旻智, 李慶民, 劉天華. 編隊(duì)防空火力分配建模及其優(yōu)化方法研究[J]. 兵工學(xué)報(bào), 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]汲萬(wàn)峰, 王光源, 章堯卿, 等. 基于PSGA的岸基導(dǎo)彈火力分配研究[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]陳云飛, 劉玉樹(shù), 范潔, 等. 火力優(yōu)化分配問(wèn)題的小生境遺傳螞蟻算法[J]. 計(jì)算機(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]郭蘊(yùn)華, 李運(yùn)濤, 楊福緣. 考慮毀傷概率門(mén)限的火力分配變異蟻群算法[J]. 火炮發(fā)射與控制學(xué)報(bào), 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]. 計(jì)算機(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)化算法求解火力分配問(wèn)題[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ù)研項(xiàng)目(62201020101)

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

TJ301

A

1673-6524(2016)02-0041-05