導彈機動路徑的差分聚類最優(yōu)規(guī)劃*

王凱光，高岳林

(北方民族大學 數學與信息科學學院,寧夏 銀川 750021)

0 引言

目前,戰(zhàn)時導彈火力打擊問題的主要表現為無障礙機車機動路徑優(yōu)化分配研究較多,而含路徑威脅的機車機動路徑優(yōu)化研究偏少,模型構造方面,李敏[1]做了基于車載導航系統(tǒng)的路徑規(guī)劃方法研究,鄧必年[2]建立了基于蟻群優(yōu)化算法的物流配送路徑規(guī)劃方案,周慧子[3]等建立了面向自動駕駛的動態(tài)路徑規(guī)劃避障算法,李進龍[4]等介紹了基于改進蟻群和免疫算法融合的多配送中心路徑優(yōu)化模型。這些規(guī)劃模型的建立在整體上僅考慮了導彈本身機動過程,割離實戰(zhàn)威脅和路徑規(guī)劃之間的關系,從而忽略了多威脅的實戰(zhàn)環(huán)境對機動路徑的影響,而差分進化算法[5-6]可以對全局環(huán)境進行整體尋優(yōu)，可以利用差分進化算法的全局尋優(yōu)能力對機動路徑進行系統(tǒng)整合。本文在前人研究基礎上,結合數字模擬技術刻畫發(fā)射車在含路徑威脅路段的路徑軌跡,運用差分聚類分析和Floyd路徑算法構建戰(zhàn)時含威脅路徑的導彈機動路徑最優(yōu)規(guī)劃的數學模型,彌補無路徑威脅條件下路徑規(guī)劃的單一性,提升了導彈在聯(lián)合指揮作戰(zhàn)體系下的安全性、時效性、穩(wěn)定性、合理性。

1 問題要素描述

針對n(n≤5)個波次的戰(zhàn)時打擊任務,假設戰(zhàn)時導彈類型集合為Ω={甲，乙，丙，…},待打擊目標集合為Ψ={A，B，C，…,N},彈目匹配函數映射關系為f:Ω→Ψ,假設第i個轉載地域導彈數量為Xi,戰(zhàn)時軍事物流倉庫、戰(zhàn)時轉載地域、導彈機動發(fā)射點、火力待打擊目標為Dq(xq,yq),Zi(xi,yi),Fj(xj,yj),Nq(xN,yN),戰(zhàn)時作戰(zhàn)區(qū)域相關要素及其道路分布假設為加權圖G=(V,E,μ),V為加權圖中的任意一點,E表示圖中任意兩點間線段,μ表示線段權重,現在假設有k輛發(fā)射車,平均部署在戰(zhàn)時物流倉庫{D1,D2,…,Dq}、轉載地域{Z1,Z2,…,Zi}、導彈發(fā)射點{Z1,Z2,…,Zj},第n波次對目標進行打擊的導彈總數為{An，Bn，Cn，…,Nn}。既要考慮到在含威脅路徑上機動的整體暴露時間盡可能短,也要規(guī)避敵方的火力偵查和打擊,同時要縮短單臺發(fā)射裝置的最長暴露時間,要求整體暴露時間X和單輛發(fā)射車最大暴露時間Y盡可能短。

2 聚類分析和Floyd最短路徑算法階段

鑒于路徑威脅的不確定性和多變性,采用多層次聚類分析和動態(tài)聚類法對含威脅的路徑段進行算法研究,首先對含威脅的路徑進行多層次化類,提取主要影響因子,運用動態(tài)分析法進行歸類,在初始狀態(tài)給出路徑數據在可視化環(huán)境下的圖像分類,隨后給出基于某計數原則在化類間重新組合的數據樣本。路徑規(guī)劃屬于大樣本數據的聚類分析,其操作方法是:先粗略分類,后逐漸調整，結合Floyd算法原理進行導彈機動最優(yōu)路徑算法設計。

算法流程如下

Step 1:在控制數據表中輸入機動波次、導彈型號與彈目類別匹配函數、導彈數據參量、物流參量以及機動射擊點和目標位置Dq(xq,yq),Zi(xi,yi),Fj(xj,yj),N(xN,yN)。

Step 2:輸入Floyd算法程序,利用其短距原理計算機動發(fā)射點與機動起始點間距。

Step 3:提取所有機動間距中路徑長度最短的作為導彈運輸路徑,一般路徑數量為大于等于某一常數m(m為機車數量與物流倉庫數量的數量比)。

Step 4:剔除所選的最短間距中的m個機動起始點,同時進行同參數聚類分析,經聚類對照后機動起始點數量小于出發(fā)點總數,則返回Step 3,否則進入Step 5。

Step 5:計算最大暴露時長,取所有機動路徑中間距最長路徑除以機動平均速度即得最大暴露時長,為保證導彈機動的統(tǒng)一性,設置0時刻為機動路徑的出發(fā)時刻,同時設置最大暴露時長為齊射時刻,齊射時刻與出發(fā)時刻的時長正向差值為相應路徑導彈機車運輸時長,然后計算機動節(jié)點處的間隔時長。

Step 6:作空集判斷,即判斷是否存在某2條路徑中的機動機車在某一非主干道路徑段反向行駛的時長區(qū)間為空,若空集成立,則取其較短路徑中的機車起始點作為出發(fā)起始點并返回Step 6,否則進入Step 7。

Step 7:對導彈打擊目標進行縱向排序,分為N個點以保證打擊目標不在同一點,同時按照如此次序對k個導彈發(fā)射點進行橫向排序,將打擊目標與導彈發(fā)射點按照匹配關系對應為N個區(qū)域,N個區(qū)域所包含的導彈發(fā)射點與目標間距的地面連線為導彈投射間距。

Step 8:對已完成的導彈打擊波次進行程序性終止判斷,若波次數小于n，則進入Step 9,否則終止算法,同時對所有導彈機動路徑以及相應節(jié)點時刻進行輸出作統(tǒng)計處理。

Step 9:輸入Floyd算法程序,計算物流配送中心與導彈發(fā)射地點的最短路徑及其間距。

Step 10:為方便考慮物流配送與導彈發(fā)射點間路徑狀況,在這里假設任意物流配送與相應導彈發(fā)射點間路徑數量小于上線數值Xi，同時選取最短路徑作為運輸路徑。

Step 11:剔除Step 10 所選的導彈發(fā)射點,對導彈發(fā)射點數量進行判斷,若小于k，則返回Step 10,否則進入Step 12。

Step 12:對Step 5中的齊射時刻作預處理,即將其作為新一出發(fā)點的出發(fā)時刻,并計算經過各節(jié)點時刻以及到達目標點時刻,同時為保證機車在轉載區(qū)域時長較短,仍需判斷Step 6中的空集情況。

Step 13:對于空集不成立的情況,則順次延后任一2條路徑中較短路徑的出發(fā)時刻并返回Step 12,否則進入Step 14。

Step 14:判斷時刻差值,即判斷是否存在導彈發(fā)射車到達某一物流配送點的時刻差值小于10 min的情況,若存在,則順次延后任一2條路徑中較短路徑的出發(fā)時刻,并返回Step 14,否則進入Step 15。

Step 15:將物流配送點作為下一次機車初始點,將前一波次所剩導彈發(fā)射點作為機動終點,返回Step 2。

3 差分進化算法階段

3.1 差分算法一般模型

3.2 差分進化算法偽代碼

4 數學模型

4.1 模型假設

(1) 作戰(zhàn)區(qū)域各道路節(jié)點及道路交通狀況已知,且除主干道可以雙向通行之外,其他車道只能單向通行。

(2) 每一輛導彈發(fā)射車原則上只能連載1枚導彈,要多波次連射,每個發(fā)射點位使用不超過1次,且需要返回導彈轉載地域進行實時裝彈,各轉載地域彈種類型和數量滿足需求。

(3) 每輛發(fā)射車車速平均設置為50 km/h,每一發(fā)射點位只能容納1臺發(fā)射裝置,各轉載地域最多容納2臺發(fā)射裝置,單臺轉載作業(yè)耗時10 min。

4.2 評價指標

本文擬從安全性、時效性、穩(wěn)定性、合理性4個方面對戰(zhàn)時環(huán)境中多波次條件下關于含有路徑威脅的導彈機動路徑的最優(yōu)規(guī)劃問題進行建模和。

(1) 安全性評價指標:導彈運輸屬于軍事物資配送范疇,物資運送時間與機件損耗呈正相關,導彈運輸的安全問題應當重視,確保打擊任務順利完成。

(2) 時效性評價指標:導彈戰(zhàn)略運輸過程最重要的就在于,軍事物流的保障能力要緊跟戰(zhàn)時變化。在本文所研究的問題中,要求同一波次導彈齊射而且要求整體暴露時間(所有發(fā)射裝置的暴露之和)最短,由于每一輛導彈發(fā)射車的出發(fā)時刻均不相同,因此導彈戰(zhàn)略運輸的時效性就表現為每輛發(fā)射車最大暴露時長。

(3) 穩(wěn)定性評價指標:戰(zhàn)時導彈機動路徑規(guī)劃的穩(wěn)定性主要取決于戰(zhàn)時物資運輸水平、指令決策、人機調配、機件故障等可控因素。本文研究的問題中,為了使得戰(zhàn)時各要素整體暴露時間最短,戰(zhàn)時各要素必須穩(wěn)定在一定的可控范圍。

(4) 合理性評價指標:戰(zhàn)時火力打擊任務分配的合理性主要取決于戰(zhàn)時地貌、戰(zhàn)時部署、戰(zhàn)時結構、作戰(zhàn)對象、作戰(zhàn)效率、作戰(zhàn)意義等[7-8],本文考慮到導彈發(fā)射點和待打擊目標之間的關系,圍繞彈目匹配函數關系f:Ω→Ψ進行合理性研究。

4.3 模型構建

針對n個波次的戰(zhàn)時打擊任務,可以將其分為奇數個(即2n-1)個階段,前2個波次分別為待機區(qū)域攜帶導彈沿道路機動到各自指定發(fā)射點位實施第1波次導彈機動發(fā)射,從第1波次導彈發(fā)射點位返回轉載地域、從轉載地域機動至第2波次導彈發(fā)射點位實施第2波次導彈發(fā)射,則多目標優(yōu)化問題可轉化為單目標優(yōu)化問題[7-8],設目標函數為

(1)

4.3.1 階段性約束條件

第1階段

(2)

(3)

(4)

(5)

(6)

(7)

第2階段

(8)

(9)

(10)

(11)

(12)

(13)

(14)

式(9)，(10)分別表示第2階段起點為第1波次導彈發(fā)射點,終點為第1波次導彈轉載地域;式(11)表示所列路徑的相鄰節(jié)點2個符合戰(zhàn)場實際情況且道路相通;式(12)表示任意單行道節(jié)點的反向行駛時間區(qū)間交集為φ;式(13)表示在第1階段存在前提條件下,第k輛車在第2階段的出發(fā)時刻非負;式(14)表示到達任意物資配送中心的導彈發(fā)射車數目不大于最大導彈數目Xi;式(15)表示對每一導彈發(fā)射車駛離第1次導彈發(fā)射點的時間進行調控并使其滿足到達同一轉載地域的任意2輛導彈發(fā)射車的時間差不小于10 min。

第3階段

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

4.3.2 算法結果

(24)

(25)

(26)

(27)

根據上述模型,我們可以確定打擊目標ψ∈{A,B,C,…,N}的位置N(xN,yN)可按縱坐標分為N個區(qū)域,每個波次k個發(fā)射點的位置Fj(xj,yj)也可以按其縱坐標分為一一對應的N個區(qū)域,同時可以確定導彈發(fā)射任務的機動方案。

5 算法測試

現有A，B，C3類發(fā)射機車,符合模型假設條件，各轉載地域彈種類型和數量滿足需求。相關道路情況如圖1所示(道路節(jié)點J01～J62),相應位置坐標由隨機函數按照仿真模擬圖給出。

5.1 差分聚類算法流程

Step 1：初始化參數：種群規(guī)模NP；縮放因子F；變異概率CR；空間維數D；迭代次數T。

(1) 對每個樣本Jk,k∈D計算tk，即樣本個體到每個機動點的聚類距離；

(3) 計算適應度函數值Z(xi)。

Step 4:變異操作、交叉操作按3節(jié)流程進行。

Step 6:終止檢驗：如果達到最大進化代數或滿足誤差要求，則輸出最優(yōu)質列表；否則轉Step 3。

5.2 問題求解

對問題所描述的兩個火力打擊波次進行系統(tǒng)性分析,種群規(guī)模NP為60,變異因子和交叉概率分別為0.5和0.1,進化代數選擇為不超過最優(yōu)值得最大進化代數。從變量參數選擇上屬于多目標優(yōu)化問題,因此可以轉化為單目標優(yōu)化問題,設目標函數為

(28)

根據前面2個階段的算法分析及其數學模型的建立,將表1中數據及相關參數代入公式,通過TerrainView-Lite地理仿真模擬[9-11]對含威脅路徑進行可視化模擬仿真,含威脅路徑仿真模擬結果如圖1所示,含威脅路徑段的階段性規(guī)避演化如圖2所示,再利用差分聚類算法法和Floyd最短路徑路徑算法[12-17],通過Matlab編程進行求解,最終得到路徑規(guī)劃的最優(yōu)分配方案,表1給出了第1波次12輛導彈發(fā)射車在含有威脅路徑機動規(guī)劃中的最優(yōu)分配方案。

圖1 TerrainView-Lite地理仿真模擬圖Fig.1 Terrain analogue simulation by Terran View-Lite

圖2 3個聯(lián)合作戰(zhàn)方案關于一級評價指標SI1的優(yōu)度Fig.2 Superiority of the three joint operations plan on thefirst level evaluation index SI1

導彈發(fā)射車待命地域發(fā)射基地出發(fā)時刻/min彈種類型打擊目標A01D1F1824.47甲AA02D2F1518.69甲AA03D1F1915.25甲AB01D2F070乙BB02D1F0813.69乙BB03D2F2120.96乙BC01D1F3425.31丙CC02D2F4520.88丙CC03D1F3524.22丙CC04D2F479.98丙CC05D1F3614.33丙C

6 結束語

本文對戰(zhàn)時多波次導彈火力打擊任務條件下含威脅路徑的導彈機動路徑的規(guī)劃方案的問題進行了系統(tǒng)研究,采集相關數據,運用TerrainView-Lite地理仿真技術進行含威脅路徑的可視化模擬,在算法方面,分析了含威脅路徑規(guī)避算法階段、Floyd最短路徑算法階段這2個算法階段,利用差分聚類算法從系統(tǒng)性角度建立了戰(zhàn)時導彈火力打擊任務在含有威脅路徑的機動規(guī)劃的數學模型,從合理性、穩(wěn)定性、時效性、安全性4個方面的指標進行了分析評價。最后通過算法實例對文中所涉及到的數學模型進行測試,結果表明,該數學模型能夠較好求解出含路徑威脅的導彈機動路徑最優(yōu)規(guī)劃問題。