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

吳建剛

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

?

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

吳建剛

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

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

目標分配; 編隊防空; 模擬退火

Class Number TP301.6

1 引言

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

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

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

2.1 目標分配的原則

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

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

2) 當有新目標進入攔截區(qū)域時,如果有空閑武器,則進行目標分配,否則等待武器空閑。

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

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

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

(1)

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

(2)

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

(3)

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

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

(4)

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

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

taij+Δti≤tcij≤tbij+Δti

(5)

3) 資源約束條件。火力通道空閑、無故障以及有可用導彈,才能發(fā)生導彈,火力通道狀態(tài)Qi必須滿足如下條件:

(6)

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

3 基于改進貪心模擬退火算法的目標分配

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

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

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

1) 初始解的選擇

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

2) 目標函數(shù)

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

(7)

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

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

(8)

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

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

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

對上述算法作如下改進[7]:

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

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

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

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

3.2 算法執(zhí)行流程

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

圖1 改進的貪心模擬退火算法流程

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

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

Step 3:計算解的能量值;

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

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

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

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

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

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

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

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

4 仿真分析

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

表1 目標的威脅度

表2 我方艦空導彈對目標的毀傷概率

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

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

表4 不同算法計算時間的對比

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

5 結語

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

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

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

[3] 吳平,梁青.武器—目標分配問題的模擬退火算法[J].計算機工程與應用,2006(4):87-90.

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

[5] 蔡懷平,陳英武,邢立寧.SVNTS算法的動態(tài)武器目標分配問題研究[J].計算機工程與應用,2006(31):7-10.

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

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

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

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

[10] 趙晨光,耿奎,李為民,等.防空導彈武器系統(tǒng)目標分配的多種算法[J].現(xiàn)代防御技術,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日

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

TP301.6

10.3969/j.issn1672-9730.2015.04.009