基于動態規劃-遺傳算法的防空部署優化模型

顏培遠, 劉 曙, 王 君

(空軍工程大學防空反導學院, 陜西 西安 710051)

0 引 言

在防空作戰領域,防空部署方案優化問題是現代防空研究的熱點之一。防空部署方案的優劣直接決定作戰效能的高低。目前，國內的研究多是把部署優化問題變成非線性優化問題。文獻[1]建立了以掩護價值為目標函數的區城防空優化部署模型,提出一種啟發式方法解決部署優化問題;文獻[2]提出了一種基于風險決策的區域防空部署方案優選方法,適于快速進行決策的場合;文獻[3]將改進的模糊層次分析法應用于彈炮混編防空群機動部署方案的優化與評估,但使用中還需考慮更實際的因素；文獻[4]建立了混編群兵力部署優化模型,提出了一種改進的粒子群算法,但還需要提高優化精度;文獻[5]提出使用并行改進遺傳算法求解組合優化問題,克服了編碼時的缺點,提高了搜索速度和解的質量。

以上文獻都是在防御方的角度考慮部署優化問題。但是單純地從防御方的角度考慮部署優化問題,而完全忽略進攻方可能采取的進襲航線,未必是防空問題研究的理想模式。在進攻方實施空襲的過程中,由于兵器性能、防御方雷達主動搜索等客觀條件限制,通常會“智能”地選擇受雷達照射最少的路徑,即選擇防御方部署方案中薄弱環節最少的方案。因此,部署優化問題中,充分考慮進攻方的影響是有必要的。本文從進攻方的角度對影響要地防空部署的主要因素[6-9]進行分析,假設進攻方是智能的,能夠選擇危險最小的航線進攻。由于遺傳算法能夠較好地解決組合優化問題[10-12],本文提出一種將動態規劃算法[13]與遺傳算法相結合的防空部署優化模型,將智能算法與非智能算法相結合,對要地防空部署進行優化,取得了較理想的結果。

1 影響要地防空部署的主要因素

1.1 防空武器的類型、數量和性能

防空武器的作戰效能主要受雷達的覆蓋范圍、導彈殺傷區和單發殺傷概率的影響[14]。雷達的覆蓋范圍越大,越有利于探測和跟蹤空襲兵器。防空武器的殺傷區遠界和近界是一條閉合的曲線,殺傷區越大,空襲兵器的攔截范圍越大,掩護同樣區域,需要的防空武器數量就越少。同時,殺傷區還與空襲兵器的類型和飛行特性、雷達散射面積、干擾性能等有關。圖1所示為某型飛機以某一固定速度接近某型防空武器時殺傷概率分布情況。當殺傷區域重疊時,同一區域重疊殺傷區域數目越高,目標殺傷概率越高,防空效果越好。

圖1 地空導彈殺傷區殺傷概率分布Fig.1 Probability distribution of killing zone of ground to air missile

1.2 地理特征

地理特征有地形地貌、水系、地物等[15]。防空武器的部署受地形起伏的影響。首先,高山等地形可以遮蔽雷達的“視線”,使雷達不能探測、跟蹤遮蔽高度以下的空襲兵器;其次,防空武器陣地應盡量平坦,而且避開湖泊、林地、居民區等。

地形對雷達視線的遮蔽如下所示:以海平面為基準面,設雷達天線高于地面,由圖2可見,雷達能探測(跟蹤)的目標最小高度htmin為

htmin=(O′T′tanεV+hR)-ha

(1)

式中,O′T′表示雷達與空襲兵器的水平距離;hR表示雷達天線的海拔高度;ha表示空襲兵器在地面投影點的海拔高度;εV表示雷達對空襲兵器觀測角。

圖2 地形對雷達視線遮蔽情況示意圖Fig.2 Sketch map of the terrain to the radar line of sight

為有效地探測和攔截空襲兵器,雷達都需要在一定范圍內規定最小的遮蔽角εVmin,確定部署點時,雷達對目標觀測角必須滿足:

εV<εVmin

(2)

1.3 被掩護對象的性質和面積

在空襲時,進攻方總會選擇具有較高作戰價值的關鍵目標進行打擊,如重要的交通樞紐、指揮中心和防空陣地。因此,要重點針對這些關鍵目標進行防空武器部署,防止兵力分散,降低防御效能。

按照目前世界防空學說,一般將被掩護對象分為3類:戰略性、作戰性和戰術性被掩護對象。確定被掩護對象的邊界線時,要對被掩護對象的性質、面積、形狀等綜合分析,對被掩護對象的重要度進行量化。當保衛多個相鄰掩護對象時,根據上級意圖和被掩護對象的具體情況劃定邊界線。只有科學合理地確定被掩護對象的范圍,才能集中力量確保其不受損失或減少損失,以滿足高技術條件下空襲的特點,提高防御效能。

2 要地防空部署優化模型

2.1 基本概念描述

根據影響防空部署諸多因素,要地防空部署優化模型的建模思路是:先確定若干個武器的部署區域(由上級確定),然后在每個區域內選擇一個適合部署的陣地進行武器部署,從而形成一套部署方案[16]。由于每個武器部署區域都有很多陣地,可供選擇,因此會產生多套部署方案。優化時,假設進攻方足夠“智能”,能夠知悉防御方武器配置,可以選擇一條最優的進攻路徑,即使用動態規劃-遺傳算法可以找到部署方案防守最薄弱的一條路徑,繼而找到最優部署方案,如圖3所示。

圖3 建模思路示意圖Fig.3 Sketch map of modeling ideas

可以看出,這是一個求防空武器和部署陣地之間組合的優化問題。本文將遺傳算法與動態規劃算法相結合,從大量部署形式中選出最優方案,從而確定防空武器的數量和最佳部署形式。

定義1易受攻擊區(vulnerable zone,VZ):空襲兵器投彈或發射空地導彈時,距要地的可能最遠位置線,稱為空襲兵器的投彈線。這條投彈線是一條閉合曲線,為保證要地的安全,應將空襲兵器在投彈前或發射空地導彈前殺傷。空襲兵器的投彈線以及其內部區域共同構成VZ,其中,空襲兵器的投彈線是VZ的邊界。如圖4所示。

定義2危險區(danger zone,DZ):空襲兵器在飛向VZ過程中,可被遠程預警雷達(CSR)或跟蹤制導雷達可發現并跟蹤的區域,遠程預警雷達和所有跟蹤制導雷達所覆蓋區域的邊界稱為DZ邊界。如圖4所示。

圖4 防空武器系統的不同區域Fig.4 Different areas of air defense weapon system

定義3殺傷區(kill zone,KZ):由所有防空武器的KZ組合而成的區域。如圖4所示,在一個防空系統中,KZ邊界是一條閉合曲線。防空武器的KZ應處于DZ(雷達的探測跟蹤區域)之內,VZ應處于KZ之內。

2.2 部署優化模型建立

定義4設空襲兵器選擇從DZ邊界到VZ邊界的進襲航線中,將面臨防空武器的攔截危險,地域特征、防空武器殺傷概率分布、空襲兵器的飛行時間等都將影響航線上所面臨危險的大小。每種部署方案必有一條或多條航線,使空襲兵器遇到的危險最小,這個最小危險值可用來確定部署形式的防空效能,即防御方需要找到一種部署形式,使防御的整體有效性最大。為此,將航線上空襲兵器面臨的危險在一定條件下進行量化,該量化在二維空間中展開,用水平線和垂直線構成一系列一定大小的方格[17-18],如圖5所示,方格的大小由地形的粒度決定。這樣,空襲兵器從DZ邊界到VZ邊界,其航線要經過一系列小方格,每一個小方格與一個經驗危險值相關,稱之為防空系統對目標所造成的危險指數(danger index,DI),防空系統對空襲兵器航線上產生的危險指數總和,稱為累積危險指數(cumulative danger index,CDI),它由航線經過的所有小方格的危險指數相加得到。

圖5 方格標識Fig.5 Square identification

部署形式的集合記為P,給定一種部署形式p(p∈P)下,目標某一可行航線記為r,可行航線集合記為R(p),則目標函數可表示為

(3)

認為空襲兵器從DZ邊界上某點處進襲,從此點向前,有多條到達VZ邊界的航線可供選擇[19],每條航線都有累積危險指數,累積危險指數最小的航線即為最優航線,稱為局部最小累積危險指數(local minimum cumulative danger index,LMCDI),它與組成DZ邊界的每一個方格相關。所有的局部最小累積危險指數中,最小的稱為全局最小累積危險指數(global minimum cumulative danger index,GMCDI)。這樣,目標函數可表示為

(4)

對于給定的部署形式p∈P,如果DZ邊界內全部小方格集合為G(p),則

(5)

式中,R0(g)是對于一個給定DZ邊界上的方格g(g∈G(p)),空襲兵器所有可能飛行航線的集合。以這種方式,全局最小累積危險指數也表示為

(6)

局部最小累積危險指數也表示為

(7)

定義5對圖5中的小方格g(i,j),給一個可見值Vij(Vij∈[0,1]),它表示了雷達探測和跟蹤此方格內空襲兵器的能力。如果此方格不在雷達的探測跟蹤范圍內或完全被地形遮蔽,則Vij=0;如果雷達可以探測到該方格上任意飛行高度的空襲兵器,則Vij=1。如果該方格位于至少一個KZ內,則分配相應的殺傷概率;如果該方格不被KZ覆蓋,相應的殺傷概率為零。殺傷概率表示為Kij,概率分布如圖1所示。對某方格g(i,j)的危險指數Dij表示為

Dij=Vij(1+Kij)

(8)

對位于DZ內的空襲兵器,雖然Kij=0,但Vij≠0,則Dij≠0。如果一個方格位于兩個KZ的重疊部分,當重疊區內只有一個防空武器(例如,危險指數值最大的防空武器)被分配了射擊目標的任務時,較大的一個危險指數可作為與此方格相關聯的危險指數;當兩個防空武器都指定射擊方格內的目標,則此方格的Dij值按下式計算:

Dij=[Vij1+Vij2(1-Vij1)][1+Kij1+Kij2(1-Kij1)]

(9)

式中,Vij1、Vij2分別為防空武器1、2雷達對方格g(i,j)內目標的可見度;Kij1、Kij2分別為防空武器1、2對方格g(i,j)內目標的殺傷概率。

設飛機飛行的最高高度hmax,則方格g(i,j)的可見值為

Vij=Max{0,1-[htmin/(hmax-ha)]}

(10)

將全部方格g(i,j)的高度存于計算機數據庫中,該高度由g(i,j)方格4個頂點的高度加權平均得到。

3 要地防空部署優化算法設計

3.1 動態規劃算法求解單個方案的最小危險航線

算法的基本思路是,已知部署地區的海拔信息和殺傷概率的分布情況,從進攻方的角度出發,對被掩護對象攻擊時必然選擇危險性最小的航線。將部署方案中每個方格g(i,j)的危險指數記為Dij,所有二維方格的危險指數矩陣記為D。局部最小累積危險指數矩陣記為L,從方格g(i,j)到VZ邊界的局部最小累積危險指數記為Lij。動態規劃算法的目標是獲得矩陣L,其中優化的初始區域是DZ內的方格的集合,結束區域是VZ邊界內的方格的集合。初始化時,VZ內方格的Lij賦值為0,其他方格的Lij賦值為相應的K值。矩陣D、L都是p×q維。每一個方格(i,j)都有一層方格將其包圍,該包圍方格層記為Eij,即

Eij={(K,L):(i-1)≤k≤(i+1),(j-1)≤l≤

(j+1),1≤k≤p,1≤l≤q,(k,l)≠(i,j)}

(11)

顯然,對于一個方格,包圍方格層中最多只有8個方格,如果(k,l)∈Eij,則(i,j)∈Ekl。

(12)

式中

(13)

當執行到第n步時,在確定此步一個方格的局部最小累積危險指數前,必須先確定哪些方格屬于第n步。這里為了縮小計算時間,對動態規劃算法進行改進,認為第n步一般是形成第(n-1)步中方格集合的外層包絡方格集合。記第n步的方格集合由Sn給出,則動態規劃算法的主要步驟如圖6所示。

圖6 動態規劃算法流程Fig.6 Dynamic programming algorithm flow

3.2 遺傳算法求解單個方案的最小危險航線

3.2.1 遺傳算法求解最優部署方案

要地防空部署優化問題的可行解是一組部署方案,包括防空武器類型及確定的精確部署陣地位置[20]。假設要對m套防空武器進行部署(針對單一武器類型),現有m個武器部署的大概地點,每個大概地點附近有n個精確部署陣地,且每個大概地點附近僅選擇一個精確部署陣地進行部署,每個陣地僅支持部署一套防空武器。由于武器數目和精確地點數目均為整數,所以采用整數進行編碼較為合理。

圖7 生成最佳航線Fig.7 Generating the best route

編碼時,染色體的長度為m,染色體的每一個基因與解的每一維變量相同。優化問題的一個有效解為X=(x1,x2,…,xk,…,xm),其中k為1～m的整數,表示武器部署大概地點的標號,xk為1～n之間的整數,表示武器部署精確地點的標號,xk=1表示防空武器部署在第k個大概地點附近的標號為1的精確地點。

3.2.2 種群初始化

在遺傳算法用于種群進化之前,需要建立初始種群。初始種群的選取將直接影響算法搜索全局最優解的能力。這里針對m套防空武器和n個精確部署陣地位置產生初始種群,初始種群的規模應適應于問題的難度[21],假設規模為N。

3.2.3 適應度評價

3.2.4 選擇算子

3.2.5 交叉算子

在種群交配時,指定一個交配概率(Pc,一般取0.4～0.99)決定每條染色體是否能進行交配。對于每條染色體產生[0,1]的隨機數(用A表示),若A小于Pc,則該染色體進行交配,否則不參與交配,并將其直接復制到新種群中。將Pc選擇出來的每兩條染色體的部分基因交換,產生兩個子代染色體。染色體的交配位置是隨機產生的,交換的基因為該位置后的所有基因。新種群規模仍為N。

3.2.6 變異算子

染色體的變異作用于基因上,變異時指定一個變異概率(Pm,一般取0.001～0.1)決定種群中染色體的每一位基因是否進行變異。對于染色體的每一位基因產生[0,1]的隨機數(用B表示),若B小于Pm,則該基因進行變異,否則該基因不發生變異。根據染色體的編碼,變異的取值為1～n之間的整數。

3.2.7 求解步驟

運行過程如下:

步驟1根據問題確定初始種群的規模N,當前進化代數G=0;

步驟2用適應度函數評價全部染色體,計算各染色體的適應度值,并保存適應度值最大的染色體Best;

步驟3按照輪盤賭選擇算法對種群進行選擇;

步驟4根據交配概率Pc從種群中選擇染色體進行交配操作;

步驟5根據變異概率Pm從種群中選擇染色體進行交配操作;

步驟6產生的新種群取代原有種群,并計算新種群中各染色體的適應度值。如果新種群的最大適應度值大于Best的適應度值,則更新Best,用新種群中的最大適應度值對應的染色體代替Best,否則不更新;

步驟7當前進化代數G加1。算法結束條件為Best達到規定要求或G超過最大進化代數,若不滿足結束條件,則返回步驟3。

4 算例仿真及分析

4.1 算 例

如圖8所示,假設根據上級意圖(已確定進攻方的空襲兵器)在保衛要地周圍確定5個武器部署的大概地點(1、2、3、4、5),每個大概地點附近規定范圍內有5個精確地點可供武器部署,求解針對單一武器類型時的最佳部署形式。

圖8 算例示意圖Fig.8 Example diagram

4.2 仿真實驗及結果分析

仿真實驗使用Matlab2013軟件進行,遺傳算法中相關參數設置如下:種群規模為N=100,最大進化代數為1 000,交配概率Pc=0.95,變異概率Pm=0.1。

根據算例對染色體進行編碼,有效解為X=(x1,x2,x3,x4,x5),其中xi=1,2,3,4,5(i=1,2,3,4,5)。然后生成初始種群,計算每條染色體的適應度值,如表1所示。

表1 初始種群及適應度值

仿真實驗的目標是求出適應度值最大的種群,下面僅對1號染色體(3、2、1、4、5;如圖8中陰影所示)的適應度值求解過程進行說明,其余染色體適應度值的求解與1號染色體相同。根據定義1～7及部署方案,假定將整個區域離散成50×50的二維方格,每個方格的邊長為10 km。確定DZ、KZ、VZ以及相應高程的數據,經計算得到如圖9所示的危險指數矩陣D(50×50),圖中用顏色區分危險指數的不同。

圖9 危險指數矩陣DFig.9 Risk index matrix D

將矩陣D代入動態規劃算法程序中運行,得到局部最小累積危險指數矩陣L,如圖10所示,圖中用顏色區分局部最小累積危險指數的不同。最后得到全局最小累積危險指數為L29,1=22.650 0,即適應度值為22.650 0。同時,也得到了航線矩陣P,如圖11所示,圖中方格內的數字表示下一步前進的方向。最終該適應度值對應的航線為(29,1)→(29,2)→(29,3)→ (29,4)→(29,5)→(29,6)→(29,7)→(29,8)→(29,9)→(29,10)→(29,11)→(29,12)→(29,13)→(29,14)→(29,15)→(29,16)→(29,17)→(29,18)→(29,19),如圖11中黑框所示。

圖10 局部最小累積危險指數矩陣LFig.10 Local minimum cumulative hazard index matrix L

圖11 航線矩陣PFig.11 Route matrix P

初始種群確定后,運行程序,通過選擇、交配、變異,得到Best適應度值為26.731 8,Best適應度值與進化代數的關系如圖12所示,進化代數在0～100代時,Best適應度值變化明顯,但隨著進化代數的增加,適應度逐漸收斂到一個固定值。

最終Best適應度值對應的染色體(5、3、2、1、4)即為最佳部署方案,其對應的最佳航線為(5,39)→(6,39)→(7,39)→(8,38)→(9,37)→(10,36)→(11,35)→(12,34)→(13,33)→(14,32)→(15,32)→(16,31)→(17,31)→(18,31)→(19,30),其中方塊(5,39)在DZ邊界上,從正方形邊界到方塊(5,39)的航線,只需保證其經過的每一個方塊的危險指數為0即可。通過對算例的仿真實驗可以看出,本文所設計的優化模型能夠得到基于進攻方的最優部署方案,為指揮人員進行防空武器部署提供參考和決策依據。

圖12 Best適應度值的收斂過程Fig.12 Convergence process of the fitness value of Best

5 結束語

本文以“智能敵人”在進攻時航線上累計危險指數為指標,將動態規劃算法與遺傳算法相結合,提出的一種基于動態規劃-遺傳算法的模型,很好地解決了防空部署優化問題。然而,將本文的模型運用于工程實踐,還需要考慮更多的影響因素和具體參數設定。由于抗擊空襲兵器飽和進攻、電子戰設備以及抗擊隱身目標等典型作戰想定并不是僅僅通過改變部署方式就可以解決的,所以本文并沒有提及,下一步會將其重點研究。為了精確地進行防空部署,將二維平面拓展至三維空間將會是下一步的研究方向。