一種基于模擬退火的編隊(duì)區(qū)域防空目標(biāo)分配方法*

吳建剛

(海軍駐武漢三江航天集團(tuán)軍代室 武漢 430040)

?

一種基于模擬退火的編隊(duì)區(qū)域防空目標(biāo)分配方法*

吳建剛

(海軍駐武漢三江航天集團(tuán)軍代室 武漢 430040)

目標(biāo)分配是編隊(duì)對(duì)空防御指揮決策中的一個(gè)重要環(huán)節(jié)。通過(guò)對(duì)艦艇編隊(duì)區(qū)域防空目標(biāo)分配影響因素的分析,建立編隊(duì)區(qū)域防空目標(biāo)分配問(wèn)題的數(shù)學(xué)模型,然后基于混合優(yōu)化算法思想,將啟發(fā)式搜索機(jī)制與模擬退火算法結(jié)合起來(lái),提出一種改進(jìn)的貪心模擬退火算法,給出了算法求解流程。仿真結(jié)果表明該算法是有效的和可行的,能夠給出具有較好的優(yōu)化分配方案。

目標(biāo)分配; 編隊(duì)防空; 模擬退火

Class Number TP301.6

1 引言

在網(wǎng)絡(luò)中心戰(zhàn)環(huán)境下,海上戰(zhàn)場(chǎng)態(tài)勢(shì)復(fù)雜多變,艦艇編隊(duì)面臨日益嚴(yán)重的空中威脅,如何將編隊(duì)內(nèi)多個(gè)平臺(tái)上的多種武器有效地協(xié)同作戰(zhàn)是一個(gè)極其復(fù)雜的問(wèn)題,也是作戰(zhàn)指揮決策中迫切需要解決的現(xiàn)實(shí)問(wèn)題。編隊(duì)區(qū)域防空作戰(zhàn)目標(biāo)分配主要研究在一定約束條件下,按照給定的目標(biāo)函數(shù)對(duì)艦空導(dǎo)彈射擊方案進(jìn)行優(yōu)化決策,確立艦空導(dǎo)彈武器資源的最優(yōu)配置,從而最大限度地發(fā)揮編隊(duì)防空體系的作戰(zhàn)效能[1]。

目標(biāo)分配屬于NP問(wèn)題,其求解方法有整數(shù)規(guī)劃、神經(jīng)網(wǎng)絡(luò)、回溯算法、非線性網(wǎng)絡(luò)流法等,這些方法存在指數(shù)計(jì)算的復(fù)雜度,當(dāng)武器及目標(biāo)數(shù)目增加時(shí)很難求解[2]。模擬退火算法[3]作為一種用于求解大規(guī)模組合優(yōu)化問(wèn)題通用而有效的全局優(yōu)化解法,尋優(yōu)時(shí)間并不令人滿意。為此,本文在綜合分析編隊(duì)區(qū)域防空目標(biāo)分配影響因素的基礎(chǔ)上,建立編隊(duì)區(qū)域防空作戰(zhàn)目標(biāo)分配模型,通過(guò)引入啟發(fā)式規(guī)則提出一種改進(jìn)的貪心模擬退火算法,以期提高算法的求解效率,優(yōu)化目標(biāo)分配決策。

2 艦艇編隊(duì)區(qū)域防空作戰(zhàn)目標(biāo)分配模型

2.1 目標(biāo)分配的原則

傳統(tǒng)的目標(biāo)分配是在單平臺(tái)下進(jìn)行的,在編隊(duì)作戰(zhàn)環(huán)境下,編隊(duì)內(nèi)有多個(gè)作戰(zhàn)平臺(tái)且各自載有多型艦空導(dǎo)彈,需要綜合考慮目標(biāo)的威脅程度大小、艦空導(dǎo)彈對(duì)目標(biāo)的殺傷概率、艦空導(dǎo)彈的殺傷區(qū)以及開始目標(biāo)分配的時(shí)機(jī)等因素,制定科學(xué)合理的目標(biāo)分配方案,以便更好地配置編隊(duì)內(nèi)傳感器、艦空導(dǎo)彈等資源,高效完成整個(gè)編隊(duì)的防空任務(wù)。目標(biāo)分配在編隊(duì)區(qū)域防空作戰(zhàn)中是實(shí)時(shí)動(dòng)態(tài)完成的,優(yōu)選方案時(shí),應(yīng)先選擇未遭攔截目標(biāo)數(shù)最少的方案,然后再選擇攔截效果最大的方案。此外,目標(biāo)分配應(yīng)遵循如下原則:

1) 對(duì)于單個(gè)火力通道,進(jìn)行一次射擊后,如果目標(biāo)被擊毀,分配給該目標(biāo)的火力通道立即轉(zhuǎn)向其它目標(biāo),目標(biāo)分配進(jìn)入下一個(gè)階段,則使用空閑的艦空導(dǎo)彈對(duì)可以攔截的未分配目標(biāo)進(jìn)行攔截;如果目標(biāo)未被擊毀,則火力通道繼續(xù)射擊直到該目標(biāo)被擊毀或飛離火力殺傷區(qū)。

2) 當(dāng)有新目標(biāo)進(jìn)入攔截區(qū)域時(shí),如果有空閑武器,則進(jìn)行目標(biāo)分配,否則等待武器空閑。

3) 目標(biāo)分配優(yōu)先級(jí):上級(jí)指定的目標(biāo)、重點(diǎn)目標(biāo)、威脅度大的目標(biāo)、射擊有利的目標(biāo)、先到達(dá)的目標(biāo)。目標(biāo)分配方案可以人工干預(yù),以達(dá)到整體毀傷效果最優(yōu)。

2.2 目標(biāo)函數(shù)的確立

假設(shè)我方艦艇編隊(duì)有m個(gè)艦空導(dǎo)彈火力通道,敵方有n個(gè)空中來(lái)襲目標(biāo),目標(biāo)的威脅度分別為wj(j=1,2,…,n),第i個(gè)火力通道對(duì)第j批目標(biāo)的命中概率為Pij(i=1,2,…,m;j=1,2,…,n)。各艦空導(dǎo)彈火力單元可以重復(fù)使用,重復(fù)使用次數(shù)由武器備彈量決定,每個(gè)火力通道只能攔截一批目標(biāo),每批目標(biāo)最多可以分配Sj(j=1,2,…,n)個(gè)火力通道。若分配第i個(gè)火力通道攔截了第j批目標(biāo)則用Xij=1表示,否則Xij=0?？紤]攔截之后目標(biāo)總的期望剩余威脅值最小作為目標(biāo)函數(shù),建立如下目標(biāo)分配數(shù)學(xué)模型:

(1)

但是式(1)還不能作為最佳分配方案的充分條件,還需要考慮未遭到攔截的目標(biāo)數(shù)最少[4],即:

(2)

式中:Uj表示第j批目標(biāo)是否遭到攔擊的指示數(shù)。如果第j批目標(biāo)未遭到攔截,則Uj=1,否則Uj=0。而Uj的定義如下:

(3)

動(dòng)態(tài)目標(biāo)分配考慮分配過(guò)程中的動(dòng)態(tài)隨機(jī)因素,如上一階段的打擊效果或者新目標(biāo)的出現(xiàn)等,需要重新產(chǎn)生新的目標(biāo)分配方案。因此,目標(biāo)分配問(wèn)題還應(yīng)考慮到空間約束、時(shí)間約束和資源約束等條件[5]。

1) 空間約束條件。航路捷徑、目標(biāo)速度和高度是決定不同高度層目標(biāo)的三個(gè)重要參數(shù),只有滿足條件時(shí)火力通道才能被分配給目標(biāo)。

(4)

其中,dij表示目標(biāo)j相對(duì)于火力通道i的航路捷徑,火力通道i能夠攔截目標(biāo)的最大航路捷徑為dimax;目標(biāo)的速度為Vj,火力通道i能夠攔截目標(biāo)的最大速度為Vimax;目標(biāo)的高度為Hj,火力通道i能夠攔截目標(biāo)的最大、最小高度為Himax,Himin。

2) 時(shí)間約束條件。目標(biāo)進(jìn)入武器發(fā)射區(qū)的遠(yuǎn)界且未離開發(fā)射區(qū)近界這段時(shí)間之內(nèi),武器對(duì)目標(biāo)開火才能奏效。假設(shè)第j批目標(biāo)到達(dá)第i個(gè)火力通道發(fā)射區(qū)遠(yuǎn)界、近界的時(shí)間分別為taij和tbij,Δti為火力通道i的響應(yīng)時(shí)間,則火力通道i攔截目標(biāo)j的發(fā)射時(shí)間tcij必須滿足的條件為

taij+Δti≤tcij≤tbij+Δti

(5)

3) 資源約束條件?；鹆νǖ揽臻e、無(wú)故障以及有可用導(dǎo)彈,才能發(fā)生導(dǎo)彈,火力通道狀態(tài)Qi必須滿足如下條件:

(6)

式(6)中:1為準(zhǔn)備好狀態(tài),0為未準(zhǔn)備好狀態(tài)。

3 基于改進(jìn)貪心模擬退火算法的目標(biāo)分配

對(duì)目標(biāo)分配問(wèn)題的求解,本文采用改進(jìn)的貪心模擬退火算法,算法借助貪心機(jī)制將啟發(fā)式規(guī)則引入到模擬退火算法產(chǎn)生新解的過(guò)程中,采用對(duì)模擬退火算法中產(chǎn)生的新解進(jìn)行多次貪心局部尋優(yōu)過(guò)程,以保證每個(gè)產(chǎn)生的新解都是“優(yōu)良解”,從而提高最優(yōu)解的質(zhì)量。同時(shí),通過(guò)合理選擇冷卻進(jìn)度表中的初始溫度、終止溫度、衰減系數(shù)、馬爾可夫鏈長(zhǎng)和結(jié)束準(zhǔn)則,提高算法的求解效率。

3.1 算法實(shí)現(xiàn)步驟

根據(jù)貪心模擬退火算法的特點(diǎn),需要進(jìn)行以下步驟[6]:

1) 初始解的選擇

初始解是算法搜索尋優(yōu)的出發(fā)點(diǎn),由目標(biāo)分配問(wèn)題的約束可知,初始解是每一行僅有一個(gè)元素1,每一列最多有S個(gè)元素1,其余都為0的n×m矩陣。模擬退火算法的最終優(yōu)化解與初始解的選取無(wú)關(guān),但為了提高解空間的搜索效率,借助貪心機(jī)制選取,對(duì)于有n個(gè)目標(biāo)的目標(biāo)分配,按目標(biāo)威脅程度由大到小排列,當(dāng)火力通道數(shù)量小于目標(biāo)數(shù)量時(shí)(m≤n),威脅值大的目標(biāo)優(yōu)先分配給可用的火力通道;當(dāng)火力通道數(shù)量大于目標(biāo)數(shù)量時(shí)(m>n),可以用多個(gè)火力通道打擊目標(biāo)。

2) 目標(biāo)函數(shù)

根據(jù)目標(biāo)分配模型的目標(biāo)函數(shù),可以將其轉(zhuǎn)化為求解能量值E:

(7)

3) 新解的產(chǎn)生和接受準(zhǔn)則

新解的產(chǎn)生采用以下策略,選擇解中被分配多于一個(gè)火力通道數(shù)量的目標(biāo),將解中任意一個(gè)該目標(biāo)變?yōu)?～n中的其它目標(biāo)。同時(shí),對(duì)于產(chǎn)生的新解需要進(jìn)行約束條件檢查,使每個(gè)目標(biāo)被分配的火力通道數(shù)量滿足分配模型中的最大分配數(shù)量。算法采用Metropolis接受準(zhǔn)則,即

(8)

其中,t為控制參數(shù);Δf為新解和當(dāng)前解的目標(biāo)函數(shù)差。當(dāng)Δf<0時(shí),接受新解;Δf≥0時(shí),進(jìn)行如下判斷:產(chǎn)生一個(gè)(0～1)之間的隨機(jī)變量rand,若r≥rand,則接受新解,否則不接受。

4) 冷卻進(jìn)度表參數(shù)的選取

冷卻進(jìn)度表是一組控制此算法進(jìn)程的參數(shù),包括初始溫度、終止溫度、衰減系數(shù)、Markov鏈的長(zhǎng)度和停止準(zhǔn)則,它是影響模擬退火算法試驗(yàn)性能的重要因素,其合理選取是算法應(yīng)用的關(guān)鍵。仿真中,初始溫度T對(duì)仿真結(jié)果幾乎沒(méi)有影響,終止溫度Tstop最好固定在0.01以下,衰減系數(shù)tr最好固定在0.9以上,Markov鏈一般取20～40。采用一個(gè)常用的衰減函數(shù)tk+1=tk×tr。

對(duì)上述算法作如下改進(jìn)[7]:

1) 不同溫度下迭代長(zhǎng)度規(guī)則

當(dāng)溫度很高時(shí),每個(gè)狀態(tài)接受的頻率基本相同,且?guī)缀跛袪顟B(tài)都被接受,此時(shí)同一溫度迭代步數(shù)可相對(duì)較少。當(dāng)溫度降低時(shí),更多的狀態(tài)被拒絕,此時(shí)迭代步數(shù)應(yīng)盡可能多。給定接受次數(shù)U和迭代步長(zhǎng)上限Mmax,當(dāng)在給定溫度迭代次數(shù)等于Mmax時(shí),在這一溫度不再迭代,溫度下降;否則,一直迭代至Mmax。

2) 最優(yōu)解保留策略

保留每個(gè)溫度的最優(yōu)解,對(duì)下一溫度解的搜索自上一溫度的最好解而非上一溫度的最后解開始。這樣,更利于加快搜索速度,找到最優(yōu)解。

3.2 算法執(zhí)行流程

算法執(zhí)行流程如下:

圖1 改進(jìn)的貪心模擬退火算法流程

Step 1:確定可以分配的火力通道數(shù)量m,再根據(jù)目標(biāo)威脅評(píng)估的結(jié)果,確定武器需要打擊的目標(biāo)數(shù)量n;

Step 2:把m個(gè)武器對(duì)n個(gè)目標(biāo)的單發(fā)命中概率從大到小進(jìn)行排列,放在一個(gè)二維數(shù)組Allocation[m][n]中,確定算法的參數(shù)S、T、Tstop、tr、Mmax;

Step 3:計(jì)算解的能量值;

Step 4:若迭代次數(shù)大于Mmax,轉(zhuǎn)Step 9;

Step 5:利用選擇策略產(chǎn)生新解,對(duì)新解執(zhí)行貪心算法;

Step 6:計(jì)算新解的能量值,執(zhí)行Metropolis接受準(zhǔn)則;

Step 7:記錄接受次數(shù)和當(dāng)前最好解;

Step 8:迭代次數(shù)增1,轉(zhuǎn)Step 4;

Step 9:執(zhí)行T=T*tr,迭代次數(shù)置1,轉(zhuǎn)Step 3;

Step 10:輸出最優(yōu)解及其能量值,算法結(jié)束。

最優(yōu)解即是艦艇編隊(duì)區(qū)域防空目標(biāo)分配的結(jié)果,算法流程如圖1所示。

4 仿真分析

假設(shè)我艦艇編隊(duì)有6個(gè)火力通道,敵方共有8個(gè)空中來(lái)襲目標(biāo),目標(biāo)的威脅度wj(j=1,2,…,8)、我方艦空導(dǎo)彈對(duì)目標(biāo)的毀傷概率Pij(i=1,2,…,6;j=1,2,…,8)分別如表1、表2所示。

表1 目標(biāo)的威脅度

表2 我方艦空導(dǎo)彈對(duì)目標(biāo)的毀傷概率

設(shè)初始溫度T0=1.0,終止溫度Tstop=0.01,溫度下降系數(shù)Tr=1.0,馬爾科夫鏈長(zhǎng)Mmax=40,每個(gè)目標(biāo)最多分配的火力通道數(shù)量S=2。仿真結(jié)果如表3所示(1表示該火力通道分配給目標(biāo),0表示該火力通道不分配給此目標(biāo)),表3即為最佳目標(biāo)分配方案。

為驗(yàn)證算法計(jì)算時(shí)間的優(yōu)越性,通過(guò)增加火力通道數(shù)量和目標(biāo)數(shù)量,采用遺傳算法、神經(jīng)網(wǎng)絡(luò)算法與本文所提算法分別求解,各算法的求解計(jì)算時(shí)間如表4所示。

表4 不同算法計(jì)算時(shí)間的對(duì)比

通過(guò)計(jì)算結(jié)果可以看出本文提出的改進(jìn)貪心模擬退火算法對(duì)遺傳算法和神經(jīng)網(wǎng)絡(luò)算法在計(jì)算時(shí)間上有很大優(yōu)勢(shì),能夠在較短的時(shí)間內(nèi)獲得目標(biāo)分配的最優(yōu)解。

5 結(jié)語(yǔ)

目標(biāo)分配是網(wǎng)絡(luò)化條件下作戰(zhàn)指揮決策中的重要研究?jī)?nèi)容,針對(duì)艦艇編隊(duì)防空作戰(zhàn)中目標(biāo)分配問(wèn)題的特點(diǎn)和需求,在建立編隊(duì)防空作戰(zhàn)目標(biāo)分配模型的基礎(chǔ)上,利用模擬退火算法并結(jié)合貪心機(jī)制,提出了一種基于改進(jìn)的貪心模擬退火目標(biāo)分配算法,通過(guò)算例驗(yàn)證了該算法的優(yōu)越性。防空作戰(zhàn)具有實(shí)時(shí)性和動(dòng)態(tài)性特征,作戰(zhàn)過(guò)程中的典型動(dòng)態(tài)事件包括目標(biāo)未被摧毀、新目標(biāo)出現(xiàn)、某個(gè)火力單元受損或性能嚴(yán)重下降等動(dòng)態(tài)隨機(jī)因素影響下的目標(biāo)分配問(wèn)題需要下一步重點(diǎn)研究。

[1] 姚躍亭,趙建軍,尹波波,等.艦艇編隊(duì)防空目標(biāo)分配優(yōu)化算法研究[J].計(jì)算機(jī)與數(shù)字工程,2011,39(1):31-34.

[2] 張毅,周紹磊,孫保良.一種求解武器—目標(biāo)分配問(wèn)題的新方法[J].海軍航空工程學(xué)院學(xué)報(bào),2005,20(5):530-532.

[3] 吳平,梁青.武器—目標(biāo)分配問(wèn)題的模擬退火算法[J].計(jì)算機(jī)工程與應(yīng)用,2006(4):87-90.

[4] 姜會(huì)霞,黃考利,侯繼業(yè),等.混編防空導(dǎo)彈火力群目標(biāo)分配模型仿真[J].軍械工程學(xué)院學(xué)報(bào),2006,18(1):46-49.

[5] 蔡懷平,陳英武,邢立寧.SVNTS算法的動(dòng)態(tài)武器目標(biāo)分配問(wèn)題研究[J].計(jì)算機(jī)工程與應(yīng)用,2006(31):7-10.

[6] 駱文輝,劉少偉,周建美,等.目標(biāo)分配問(wèn)題的模擬退火算法[J].上海航天,2008(1):61-64.

[7] 李洪瑞,苗艷.擊毀概率最大的目標(biāo)武器分配的模擬退火算法[C]//中國(guó)造船工程學(xué)會(huì)電子技術(shù)學(xué)術(shù)委員會(huì)指控與計(jì)算機(jī)專業(yè)委員會(huì),2000年學(xué)術(shù)交流會(huì),2000.

[8] 李丹,王巨海,陳振雷.基于神經(jīng)網(wǎng)絡(luò)TSP算法的防空作戰(zhàn)火力分配[J].火力與指揮控制,2006,31(4):42-45.

[9] 羅紅英,劉進(jìn)忙.遺傳算法在目標(biāo)優(yōu)化分配中的應(yīng)用[J].電光與控制,2008,15(3):18-20.

[10] 趙晨光,耿奎,李為民,等.防空導(dǎo)彈武器系統(tǒng)目標(biāo)分配的多種算法[J].現(xiàn)代防御技術(shù),2001,29(3):7-9.

Target Allocation Algorithm for Naval Fleet Air Defense Based on Simulated Annealing

WU Jiangang

(Military Representative Office of Navy in Sanjiang Aerospace Corp, Wuhan 430040)

Target allocation is an important part of command and decision-making in formation air defense. The mathematical model of target allocation is established through the analysis of targets assigned influencing factors for area air defense of surface warship formation. Based on the ideology of hybrid optimization algorithm, an improved greedy simulated annealing algorithm is put forward by introducing the heuristic search mechanism, and the algorithm process is given. The simulation results show that the algorithm is effective and feasible which can give an optimal allocation scheme.

target assignment, formation air defense, simulated annealing

2014年10月8日,

2014年11月29日

吳建剛,男,碩士,工程師,研究方向:導(dǎo)彈裝備質(zhì)量監(jiān)管。

TP301.6

10.3969/j.issn1672-9730.2015.04.009