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

吳建剛

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

?

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

吳建剛

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

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

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

Class Number TP301.6

1 引言

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

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

2 艦艇編隊區域防空作戰目標分配模型

2.1 目標分配的原則

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

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

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

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

2.2 目標函數的確立

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

(1)

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

(2)

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

(3)

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

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

(4)

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

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

taij+Δti≤tcij≤tbij+Δti

(5)

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

(6)

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

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

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

3.1 算法實現步驟

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

1) 初始解的選擇

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

2) 目標函數

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

(7)

3) 新解的產生和接受準則

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

(8)

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

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

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

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

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

當溫度很高時,每個狀態接受的頻率基本相同,且幾乎所有狀態都被接受,此時同一溫度迭代步數可相對較少。當溫度降低時,更多的狀態被拒絕,此時迭代步數應盡可能多。給定接受次數U和迭代步長上限Mmax,當在給定溫度迭代次數等于Mmax時,在這一溫度不再迭代,溫度下降;否則,一直迭代至Mmax。

2) 最優解保留策略

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

3.2 算法執行流程

算法執行流程如下:

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

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

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

Step 3:計算解的能量值;

Step 4:若迭代次數大于Mmax,轉Step 9;

Step 5:利用選擇策略產生新解,對新解執行貪心算法;

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

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

Step 8:迭代次數增1,轉Step 4;

Step 9:執行T=T*tr,迭代次數置1,轉Step 3;

Step 10:輸出最優解及其能量值,算法結束。

最優解即是艦艇編隊區域防空目標分配的結果,算法流程如圖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,溫度下降系數Tr=1.0,馬爾科夫鏈長Mmax=40,每個目標最多分配的火力通道數量S=2。仿真結果如表3所示(1表示該火力通道分配給目標,0表示該火力通道不分配給此目標),表3即為最佳目標分配方案。

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

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

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

5 結語

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

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

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

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

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

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

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

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

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

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

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

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

TP301.6

10.3969/j.issn1672-9730.2015.04.009