吳閏平,劉衛(wèi)東,楊 萍,陳 鵬,李晨旭
(火箭軍工程大學(xué),西安 710025)
隨著軍事科技的高速發(fā)展,導(dǎo)彈武器作為集地理學(xué)、物理學(xué)、計算機科學(xué)、化學(xué)、材料學(xué)和軍事戰(zhàn)略學(xué)為一體的高科技作戰(zhàn)武器,作戰(zhàn)距離遠(yuǎn)、隱蔽性強、威力大,已經(jīng)成為各國作戰(zhàn)的首選方式。在導(dǎo)彈武器作戰(zhàn)方式中,大彈量、多波次的常規(guī)導(dǎo)彈打擊策略成為當(dāng)下主要研究方向之一。這就涉及到了作戰(zhàn)區(qū)導(dǎo)彈部隊的任務(wù)分配與機動問題。常規(guī)導(dǎo)彈多波次打擊流程為:中心庫裝彈→待機陣地待機→發(fā)射陣地第1 波次發(fā)射→轉(zhuǎn)載陣地第1 次轉(zhuǎn)載→發(fā)射陣地第2 次發(fā)射→……→發(fā)射陣地第n 次發(fā)射,在機動過程中,如何合理安排各個發(fā)射裝置的機動路徑與相應(yīng)陣地,使的機動路徑總體較短,暴露時間最短,降低被敵偵查設(shè)備發(fā)現(xiàn)的概率,以增大生存概率具有重要意義。
在之前的常規(guī)導(dǎo)彈多波次打擊問題的研究中,汪民樂[7]研究了多波次對地攻擊的火力分配問題;王桐[9]運用馬爾科夫鏈解決了多波次打擊敵方目標(biāo)的效果評判問題;楊萍[5]運用軍事運籌學(xué)與不確定理論,對多波次導(dǎo)彈打擊的戰(zhàn)前運輸問題進行了建模分析,王鵬[11]根據(jù)軍事公路運輸?shù)奶攸c,建立了基于GIS 的路線選擇模型,給出了相應(yīng)的求解方法??傮w來看,前人所做的研究主要集中在導(dǎo)彈發(fā)射裝置的機動路徑優(yōu)化方面,以及在給定機動路徑的基礎(chǔ)上進行機動調(diào)度,解決了多波次導(dǎo)彈作戰(zhàn)的路徑規(guī)劃與機動調(diào)度基本問題。但以上研究基本都是對于較小規(guī)模作戰(zhàn)路徑選擇調(diào)度的研究,而對于大彈量、多波次打擊中的發(fā)射裝置機動問題研究較少。且使用全局優(yōu)化搜索方法會使得算法復(fù)雜度增加,算法效率降低,因此,本文首先采用雙層Voronoi圖模型對發(fā)射陣地進行了動態(tài)聚類,由專門的轉(zhuǎn)載陣地對其發(fā)射陣地轉(zhuǎn)載服務(wù),將多中心優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。其次建立雙層規(guī)劃模型,上層使的總體機動路徑最短,下層使的第1 波次發(fā)射完畢后,導(dǎo)彈發(fā)射裝置從發(fā)射陣地到轉(zhuǎn)載陣地再到發(fā)射陣地的機動距離最短,最后設(shè)計了適用于此問題的遺傳算法進行了求解。
Voronoi 圖模型對于解決較大規(guī)模的路徑優(yōu)化問題具有較大優(yōu)勢,本文運用雙層Voronoi 圖模型對各個發(fā)射陣地進行聚類,并通過雙層規(guī)劃理論構(gòu)建多波次發(fā)射路徑全局優(yōu)化模型,并使的整體算法復(fù)雜度降低,得到最佳的機動路徑。
本文通過構(gòu)建Delaunay 三角網(wǎng)的方式建立Voronoi 圖模型,步驟為:
1)離散的發(fā)射陣地自動構(gòu)建Delaunay 三角網(wǎng)。對離散的發(fā)射陣地和形成的三角形進行編號,并記錄每個三角形是由哪3 個離散的發(fā)射陣地構(gòu)成的。
2)計算并記錄所有三角形的外接圓心。
3)遍歷三角形鏈表,尋找與當(dāng)前三角形的三邊共邊的相鄰3 個三角形。
4)如果找到,則把尋找到的三角形的外心與該三角形的外心連接,存入維諾邊鏈表中。如果沒有找到,則求出最外邊的中垂線射線存入Voronoi 邊鏈表中。
5)遍歷結(jié)束,所有Voronoi 邊被找到,根據(jù)邊畫出Voronoi 圖。
生成Voronoi 圖的基本方法是構(gòu)建Delaunay 三角網(wǎng),基本步驟為:
1)將所有的發(fā)射陣地構(gòu)建超級三角形,并放入三角形鏈表。
2)將發(fā)射陣地依次插入,找到可以將此發(fā)射陣地包含的兩個已存在的三角網(wǎng)的外接圓,刪除公共邊,并將新插入的發(fā)射陣地與其余4 個發(fā)射陣地連接,形成新的Delaunay 三角形鏈表。
3)對新形成的三角網(wǎng)進行優(yōu)化設(shè)計,并置入Delaunay 三角形鏈表。
4)重復(fù)第2)步,使得所有發(fā)射陣地插入。關(guān)鍵步驟2)的實施流程如圖1 所示。
圖1 Delaunay 三角形實施流程
1.2.1 建立雙層Voronoi 圖
本節(jié)通過引入一個點和一條線的K 環(huán)Voronoi鄰居的概念來介紹雙層Voronoi 圖,如下頁圖2 分別表示兩個不同發(fā)射陣地的Voronoi 距離,一個點的Voronoi 鄰居以及一條線的Voronoi 鄰居。
建立雙層Voronoi 圖,上層Voronoi 圖粗略地定義了每個轉(zhuǎn)載陣地的初始覆蓋區(qū)域,較低層次的Voronoi 圖定義了發(fā)射陣地的Voronoi 鄰居,這有助于通過將局部搜索空間限制為K 環(huán)Voronoi 鄰居來優(yōu)化每個轉(zhuǎn)載陣地的發(fā)射裝置路線問題。
1.2.2 算法實施
通過BVDH[1]算法對此問題進行求解,算法基本步驟為:
1)求解初始解
得到此問題的初始解,如果發(fā)射陣地位于上層轉(zhuǎn)載陣地Voronoi 圖的Voronoi 區(qū)域,則該發(fā)射陣地最初被分配到該轉(zhuǎn)載陣地。分配給轉(zhuǎn)載陣地的發(fā)射陣地的路線通過單個轉(zhuǎn)載陣地的“集群優(yōu)先,路線優(yōu)先”VRP[2]算法生成。
圖2 Voronoi 圖
圖3 雙層Voronoi 圖模型
2)初始解改進
運用SA 算法改進初始解,改進階段分為兩部分,為在一個轉(zhuǎn)載陣地的范圍內(nèi)的路線和轉(zhuǎn)載陣地之間的路線。首先為了改善一個轉(zhuǎn)載陣地范圍內(nèi)的路線,該算法通過將局部搜索空間限制為K 環(huán)Voronoi 鄰居內(nèi)并使用3 個流行的鄰居結(jié)構(gòu)1-0 交換移動,1-1 交換移動和2-opt 移動[3]來將發(fā)射陣地從一個路線重新排列到另一個路線。其次為改善在轉(zhuǎn)載陣地交匯間的發(fā)射裝置路徑,本文采用1-0交換方式和1-1 交換方式對初始解進行改進,這兩種方式是在上層Voronoi 圖的Voronoi 邊緣的K 環(huán)Voronoi 鄰居中實現(xiàn)的。不選用2-opt 移動是因為它可能會在站點上生成許多路由而增加當(dāng)前解決方案的總路線長度。算法改進過程如圖4 所示。
圖4 SA 算法改進步驟
BVDH 算法流程如下頁表1 所示。
本文以雙波次打擊為例,建立雙層規(guī)劃模型,上層為整體最短機動路徑,下層為從第1 波次發(fā)射陣地到達(dá)轉(zhuǎn)載陣地進行轉(zhuǎn)載并機動至第2 波次發(fā)射陣地進行第2 波次發(fā)射的最短路徑。即
表1 BVDH 算法流程
其中,l1與l2分別表示第1 波次與第2 波次總的機動距離表示a 類發(fā)射裝置k 從待機陣地d 到發(fā)射陣地f1的距離;表示a 類發(fā)射裝置k 從發(fā)射陣地f1到轉(zhuǎn)載陣地z 的距離;表示a 類發(fā)射裝置k從轉(zhuǎn)載陣地z 到發(fā)射陣地f2的距離;為1 時表示a 類發(fā)射裝置k 從待機陣地d 到發(fā)射陣地f1,為0 時表示a 類發(fā)射裝置k 未從待機陣地d 到發(fā)射陣地f1;為1 時表示a 類發(fā)射裝置k 從發(fā)射陣地f1到轉(zhuǎn)載陣地z,為0 時表示a 類發(fā)射裝置k 未從發(fā)射陣地f1到轉(zhuǎn)載陣地z;為1 時表示a 類發(fā)射裝置k 從轉(zhuǎn)載陣地z 到發(fā)射陣地f2,為0 時表示a 類發(fā)射裝置k 未從轉(zhuǎn)載陣地z 到發(fā)射陣地f2。
在第1 波次齊射過程中,每個發(fā)射點位的使用不得超過一次:
在第1 波次齊射完畢后,通過在轉(zhuǎn)載區(qū)域轉(zhuǎn)載后到達(dá)第2 波次發(fā)射點位,發(fā)射陣地只能使用一次:
第1 波次與第2 波次發(fā)射點位不得重復(fù):
同一時刻,轉(zhuǎn)載陣地容納的發(fā)射裝置數(shù)量上限為s
其中,s 表示轉(zhuǎn)載陣地可以同時作業(yè)的發(fā)射裝置的數(shù)量,對于給定的作戰(zhàn)對象,s 是已知的。參與作戰(zhàn)的發(fā)射裝置總數(shù)少于各個待機陣地的發(fā)射裝置的總數(shù)
其中,S 表示發(fā)射裝置的總數(shù),對于給定的作戰(zhàn)對象,S 是已知的。構(gòu)建雙層規(guī)劃模型為:
設(shè)計適應(yīng)于此問題的遺傳算法求解最佳的機動路徑并進行機動調(diào)度,算法流程為:
Step1:確定染色體配置方案。將兩個波次的打擊任務(wù)分別定義為第1 波次發(fā)射編碼段,第2 波次發(fā)射編碼段及轉(zhuǎn)載陣地編碼段如圖5 所示。
圖5 染色體編碼圖
Step2:確定目標(biāo)函數(shù)。對于不同的發(fā)射裝置,不同的道路情況,求解出所有發(fā)射裝置的最短機動路徑;以所有發(fā)射裝置的最短機動路徑為適應(yīng)度函數(shù),并使得兩個波次發(fā)射點位于同一轉(zhuǎn)載陣地的服務(wù)區(qū)內(nèi),通過求解最小適應(yīng)度值來搜索最優(yōu)的機動方案。染色體編碼如圖6 所示。
圖6 染色體編碼圖
Step3:算法適應(yīng)性改造
1)隨機初始化種群方案;
3)交叉。從種群中隨機選取兩個個體,首先根據(jù)交叉概率判斷是否交叉,然后進行交叉操作。當(dāng)需要對發(fā)射陣地進行交叉時,首先判斷需要交叉的發(fā)射點是否與本染色體的發(fā)射點基因重復(fù),如果重復(fù),則放棄交叉操作;
4)變異。從種群中隨機選擇一個個體進行變異,當(dāng)需要對發(fā)射陣地變異時,首先判斷發(fā)射點位是否重復(fù),如果重復(fù),則放棄變異;
5)算法實施。根據(jù)遺傳算法特點及本問題的特殊性,建立算法實施框架如圖7 所示。
圖7 算法流程圖
對于有2 個待機陣地、5 個轉(zhuǎn)載陣地、60 個發(fā)射陣地及62 個道路節(jié)點的給定路網(wǎng)如圖所示的具體路網(wǎng)進行兩個波次打擊問題的路徑規(guī)劃,每個波次使用24 輛發(fā)射裝置。其中,各個節(jié)點分別表示待機陣地(D)、轉(zhuǎn)載陣地(Z)、發(fā)射陣地(F)和道路節(jié)點(J),藍(lán)色的道路表示單行道,紅色的道路表示雙行道。
圖8 作戰(zhàn)路網(wǎng)
第1 階段:得出初始解[12]。
創(chuàng)建轉(zhuǎn)載陣地、發(fā)射陣地的Voronoi 圖以及發(fā)射陣地分布線的K 環(huán)Voronoi 鄰居。得出每個轉(zhuǎn)載陣地對于發(fā)射陣地的初始配屬如下頁圖9 所示。
初始陣地配屬關(guān)系如下頁表2 所示。
初始機動方案如表3 所示。
機動總距離為5 017.231 km。
第2 階段:改進階段。
運用Voronoi 圖算法改進后的陣地配屬關(guān)系如表4。
圖9 陣地初始配屬圖
表2 初始陣地配屬
表3 初始機動配置
表5 改進機動配置
改進后的機動方案如表5 所示。
機動總距離為4 352.837 km。相比初始方案減少了15.26%。
常規(guī)導(dǎo)彈多波次作戰(zhàn)過程中合理高效的波次轉(zhuǎn)換是取得戰(zhàn)爭主動權(quán)的有效方式,針對全局優(yōu)化過程中出現(xiàn)的算法復(fù)雜度高,優(yōu)化效率低的問題,建立常規(guī)導(dǎo)彈多波次打擊時發(fā)射陣地與轉(zhuǎn)載陣地的雙層Voronoi 圖模型,對各個發(fā)射陣地歸屬于某一特定的轉(zhuǎn)載陣地,將多中心優(yōu)化問題簡化為單中心優(yōu)化問題。在此基礎(chǔ)上構(gòu)建上層為全局最短路徑下層為第2 波次最短路徑的雙層規(guī)劃模型,設(shè)計適合于此模型的遺傳算法,有效降低了算法的復(fù)雜度,求解效率較高。