基于改進灰狼算法的艦載機彈藥保障調度優化

劉 哲, 馬俊飛, 陳佳峰, 馬嵩華,*

(1. 山東大學機械工程學院, 山東 濟南 250061; 2. 高效潔凈機械制造教育部重點實驗室,山東 濟南 250061; 3. 山東大學機械工程國家級實驗教學示范中心, 山東 濟南 250061; 4. 湖南云箭集團有限公司, 湖南 長沙 419503)

0 引 言

航空母艦是世界上各軍事強國最重要的海上戰略支撐平臺,其主要的作戰方式是調度起降艦載戰斗機進行對空、對海作戰,因此航空母艦編隊作戰對艦載機彈藥的供應有很高的要求[1]。在供應過程中,需要彈藥升降機、彈藥裝配艙以及彈藥運輸車等保障設備緊密配合,完成彈藥清點、補充、裝配、轉運等復雜工作[2]。其中,耗時最長、涉及人員和設備最多、貫穿于服務保障全程的是航空彈藥轉運流程,其效率直接決定著艦載機的出動架次以及作戰能力[3]。因此,亟需一種有效的調度優化方法來提高彈藥轉運流程的作戰保障效率。

在目前日益緊張的國際局勢下,進一步提高海上作戰能力也成為各國重要的發展任務,對于航空母艦艦載機彈藥保障調度流程的研究得到了國內外學者更多的關注。Smith[4]分析了彈藥存儲倉庫在快速響應多個需求任務時存在的檢索困難問題,將存儲作戰載荷檢索過程建模為并行機動調度問題,并利用綜合需求進行仿真。Yu等[5]建立了彈藥保障及時條件下的航空保障群預調度模型和保障不足時的全反應調度模型,并設計了仿真實驗驗證模型的可行性與有效性。Yuan等[6]提出需要在原有的調度任務事先設計規劃方式的基礎上增加動態飛行甲板環境下的艦載機保障與調度方法,對調度過程中出現的意外中斷實時做出更優的決策,以根據作戰態勢的實時動態性獲得更可靠的艦載機彈藥保障與調度指導。Ryan等[7]開發了一個航空母艦飛行甲板操作決策支持系統,該系統在操作人員為飛行甲板資源保障調度流程設置相應目標和約束后,會通過計算返回建議的時間表,供操作人員參考。Feng等[8]考慮到調度過程中資源沖突的顯著影響,設計了一種基于改進蟻群優化算法的尋優調度策略,有效解決了路徑規劃與資源分配問題。Su等[9]分析了艦載機群出動保障流程的出動時限、保障人員、保障設備等諸多約束,建立了混合整數規劃模型,并通過典型算例完成了模型驗證。Liu等[10]提出了一種改進的可變鄰域搜索算法,用于解決航空母艦甲板固定資源站配置與航空母艦艦載機飛行前準備調度的聯合優化問題。呂曉峰等[11]針對模塊化彈藥調度問題,建立了艦載機模塊化彈藥調度模型,并使用改進的遺傳算法對模型進行了求解。

艦載機彈藥保障這一優化調度問題,經歷了人工經驗調度、計算機輔助調度、智能決策和優化調度3個發展階段[12],目前主要通過智能優化算法和虛擬仿真求解。公開的研究表明[13],人類操作員與智能優化決策系統之間的約束設定、選擇接受等高級交互可以實現整體任務性能的顯著提升。Liu等[14]針對航空母艦飛行甲板航空保障資源站受限于固定位置的問題,提出了一種改進的具有4種原始鄰域結構的可變鄰域搜索算法。經驗證,該算法可以有效求解航空保障資源站保障供應問題。飛行甲板上的彈藥保障調度流程可以抽象類比為一類柔性流水車間調度問題[2],由于這類問題在港口貨運調度、柔性車間生產線、軌道運輸調度等場景中已有成熟應用[15],遷移解決飛行甲板彈藥保障調度仍有較大實用價值。Wang等[16]總結對比了艦載機調度保障路徑規劃的典型技術與算法,并討論了相應的跟蹤控制技術,結合現有技術問題提出了路徑規劃問題的重點改進方向。Yu等[17]利用整數線性規劃公式提出一種有起飛優先級的飛行甲板調度問題,并通過設計一種改進的差分進化算法獲得了較好的調度方案。Ye等[18]將基于案例的推理方法與最鄰近法和層次分析法結合,提出了一種有效挖掘歷史數據的應用方法,為彈藥保障預測性供應提供了指導。

本文針對航空彈藥在航空母艦飛行甲板上轉運過程中的保障調度流程及約束,設計了一種改進的灰狼優化(grey wolf optimizer,GWO)算法。在傳統GWO算法的基礎上,本文改進編碼解碼策略,使用整數編碼方法,并通過將負整數作為分組標記實現整數解向量的多目標分組。在GWO算法跟隨頭狼狩獵靠近的基礎上,改進GWO算法也增加了灰狼個體自由搜索策略以避免算法求解陷入局部最優的問題,保證實時有效的調度優化決策。

1 問題描述

航空彈藥通過彈藥升降機轉運至航空母艦飛行甲板后,需要由彈藥運輸車依次將彈藥運輸到各艦載機停機區域暫存,再按照艦載機出動順序依次完成彈藥掛載工作,主要場景如圖1所示。

圖1 航空母艦飛行甲板彈藥運輸場景Fig.1 Flight deck ammunition transport scenario of aircraft carrier

在彈藥在航空母艦飛行甲板上轉運過程中,建立如下問題模型。

現場有P個彈藥升降機供應航空彈藥;N輛裝載容量為Q的彈藥運輸車,運輸車具備彈藥運輸和裝載的功能。彈藥從彈藥升降機出發,向K個目標工作點運輸并裝載彈藥,包括k個運輸暫存目標工作點和K-k個彈藥裝載目標工作點。各運輸車初始位置可根據整個路徑各目標工作點等待時間最短的要求,在P個彈藥升降機中進行選擇[19]。考慮現場環境復雜多變,補充設計影響運輸過程的相關因素集合U,包括升降機倉儲余量、運輸車工作能力、運輸人員素質、現場環境等參數。同時,要求較高的目標工作點設置嚴格的工作時間窗[sti,fti]。各目標工作點的等待時間是運輸車到達該目標工作點前走過的路程所需的時間。同一運輸車可能經過多個目標工作點,因此同一路徑上的各目標工作點等待時間具有累加的特性。考慮實際作戰情況對保障時間要求極為嚴格,故本問題以滿足優先運輸條件、最短等待時間為目標,設計以目標工作點為中心的保障調度策略。

所建立問題模型的解應為不多于N條的哈密頓回路,應確保這些哈密頓回路經過了所有目標工作點,且所有目標工作點的等待時間總和最少。如果一輛運輸車的路徑同時包含了運輸暫存目標工作點和裝載目標工作點,則必須保證運輸車到達運輸暫存目標工作點的順序早于裝載目標工作點,即運輸車在執行裝載任務前確保全部彈藥已運輸卸載完畢,同時確保運輸車在路徑上所有運輸暫存目標工作點的總需求量不超過其裝載容量。

在彈藥裝載調度保障現場場景中,在任務、資源、環境等情況不確定的情況下,問題存在的難點較多,處理起來比較復雜。為簡化和說明問題,特做如下合理假設[20]:

(1) 彈藥、運輸車沿既定路徑單向運輸,即彈藥只能從彈藥升降機運往各目標工作點,不會重復經過同一路徑;

(2) 運輸車裝載容量有所限制,且容量大于任一個目標工作點的需求量;

(3) 各運輸車在運輸過程中,在無人為干擾的情況下始終以最大轉運速度工作;

(4) 各運輸車均從升降機處出發,完成工作后返回出發升降機位置,即各運輸車路徑的起點、終點都是升降機,運輸路徑構成一條哈密頓回路;

(5) 彈藥升降機、各目標工作點位置確定,且各工作點內容(彈藥數量、工作時間、搬運路線)確定;

(6) 運輸車為多功能車,可分別完成運輸和裝載任務;

(7)運輸車等設備的故障時間和修復時間均服從相互獨立的指數分布。

將本文出現的彈藥飛行甲板保障調度流程相關參數變量列舉為參數變量表,如表1所示。

表1 轉運調度流程相關參數變量表Table 1 Variable table of transfer scheduling process related parameters

2 模型建立

2.1 模型定義

在彈藥調度轉運過程中,任一裝載目標工作點完成補充、裝載任務即進入戰斗待命狀態,因此針對運輸調度過程中同一路徑上多目標工作點應分別單獨計算等待時間,將同一批次全部目標工作點進入戰斗待命狀態后的等待時間之和應評價對問題模型求解的優劣。

在默認狀態下,運輸車以最大速度運行,即運輸車在升降機、目標工作點之間完成轉運任務時花費的時間與路徑路程為正比關系。設運輸車n到達目標工作點i的路徑有向集合為W,則各目標工作點的等待時間如下所示:

(1)

其中,

考慮式(1)中計算路徑路程采用的是相鄰兩目標工作點間的直線距離,且無法保證兩點連線與飛行甲板上其他設備、裝置等不發生干涉。因此,補充中間目標工作點集合WM,將兩點之間的直線距離通過添加至少一個中間目標工作點轉化為若干段直線距離,以避開原定兩點連線經過的障礙物,如圖2所示。對所有路徑目標工作點組合逐一檢查并將各中間目標工作點按照初始首尾目標工作點索引方式添加至中間目標工作點集合WM。

圖2 中間目標工作點距離計算Fig.2 Calculation for middle target working point distance

在復雜的作戰環境中,可能會在特定時間段有執行緊急作戰任務的艦載機。因此,設置部分有較高權重的目標工作點,針對任務緊急程度設置嚴格的工作時間窗,即

(2)

式中:P(tin)是違反時間窗口要求的懲罰成本;atin是未開始接受工作支持的最早臨界時間點;btin是停止接收工作支持的最晚臨界時間點;r1和r2是相應情況下懲罰成本的單位費用。

為方便分析求解算法針對問題模型求解的優劣性,設置解的適應度值F與總體等待時間t成反比,即

(3)

式中:M為一個較大的常數。適應度值越大,表示這一組通過求解算法獲得的解越優質,適應度值收斂即反映求解過程獲得最優解。

綜合上述求解方案,本文針對問題模型優化求解的目標是在保證滿足特定時間要求的任務完成的情況下,盡可能地獲得最短的總體等待時間T,或獲得最優的適應度值Ff,即

(4)

2.2 模型約束

在航空彈藥轉運最優任務目標完成的同時,仍需滿足以下約束條件。

(1) 問題模型中所有的目標工作點必定有一輛運輸車經過,且只會經過一次,即有

(5)

(2) 各運輸車對應一個哈密頓回路,不會出現多于N的路徑數量,即

(6)

(7)

(3) 各運輸車運載彈藥量不超過其容納彈藥的上限,即

(8)

(4) 各運輸車的出發位置根據路徑首個目標工作點的位置確定:首個目標工作點與各升降機距離Lia,Lib,…,Lim,選擇距離最小的升降機作為起點。

L=min{Lia,Lib,…,Lim}

(9)

3 改進的離散GWO算法

GWO[21]算法是通過模擬狼群狩獵時普通灰狼在頭狼的指引下不斷靠近獵物的機制來獲得最優解的一種啟發式算法。其在解決作業車間調度問題等組合優化問題上有出色效果[22-24]。傳統的GWO算法采用實數編碼且多針對單目標問題,難以解決多目標排列次序問題[25]。因此,本文通過對GWO算法進行改進以求解上述問題模型。本文采用的改進GWO算法使用整數編碼方法,并通過將負整數作為分組標記實現整數解向量的多目標分組。在GWO算法跟隨頭狼狩獵靠近的基礎上,改進的GWO算法也增加了灰狼個體自由搜索策略,以避免算法求解陷入局部最優的問題。

上述調度問題模型是典型的組合優化問題,既要確定各運輸車的行駛路徑(即確定目標工作點的排列次序),又要將目標工作點分配給不同的運輸車,即確定目標工作點的分組。

3.1 問題編碼

本文采用離散化的整數編碼,對各目標工作點由1至K依次以連續整數進行編號區分,同時對各運輸車由-N至-1以連續負整數進行編號區分。每一個解向量中都包含對應目標工作點數K的范圍從1到K的正整數,且保證各數都出現且僅出現一次;同時,包含對應運輸車數量N的從-N到-1間的負整數,各數同樣出現且僅出現一次。如此,N+K個整數在各個解向量中的排列順序就對應了一組完成編碼的解。

3.2 解碼思路

在解向量中的正整數對應的實際調度中,編號對應該整數值的目標工作點,其N個目標工作點被負整數分隔為N組,其中-1數值固定為每一解向量的首位。在兩個負整數之間或最后一個負整數之后,一組正整數序列作為其前面一個負數對應標號的運輸車的工作路徑。即對應負數編號的運輸車從彈藥升降機出發,按照正整數序列順序到達相應標號目標工作點完成工作任務,最后再回到彈藥升降機。

3.3 運輸車起點、終點選擇

確定了運輸路徑的一輛運輸車在選取起點和終點時采用虛擬車場解決多車場問題,假設P個升降機均與增加的一個虛擬升降機有一條路徑連通,且路徑長度均為0,即設定所有運輸車均由虛擬升降機處出發,具體通過哪一個實際升降機位置則由其路徑上目標工作點的位置決定。距離路徑上第一個目標工作點最近的升降機作為這一運輸車從虛擬升降機出發經過的第一點,距離路徑上最后一個目標工作點最近的升降機作為回到虛擬升降機經過的最后一點。

3.4 改進GWO算法的應用

GWO算法在求解此類調度問題中有收斂速度快、精度可靠等突出優點。傳統的GWO算法隨機生成初始解,易導致收斂速度慢,且缺少跳出局部最優的必要過程,因此需要對傳統GWO算法進行改進。改進后的GWO算法流程如圖3所示。

圖3 改進后的GWO算法流程圖Fig.3 Flowchart of improved GWO algorithm

GWO算法相較于經典的遺傳算法對于初始解的優化程度要求較高,因此本文改進的GWO算法在生成隨機初始灰狼種群后對種群適應度較差的劣勢個體進行了淘汰;同時,按照輪盤賭的方式選取適應度相對較優的個體相互交叉,獲得新的個體用于補充淘汰劣勢個體后種群的空缺位置[26],如圖4所示。其中,片段長度在解向量長度1/3～2/3范圍內通過隨機向下取整獲得,交叉點位根據片段長度在合理范圍內通過隨機數確定。

圖4 劣勢個體淘汰后的交叉補充Fig.4 Cross-supplementation after elimination of disadvantaged individuals

種群中每個個體更新位置要向頭狼移動,即按照一定的比例向其中一只頭狼靠近。靠近方法為利用適應度差值決定移動距離,如下所示:

(10)

式中:φ表示在區間[0,1]的隨機浮點數;Ψ1和Ψ2表示選擇概率常數,依此來確定每一灰狼個體所選擇跟隨的頭狼概率;li表示灰狼個體向選定頭狼移動的片段長度;lXl表示解向量的總長度;γ為片段選擇系數。

狩獵靠近過程表現為在頭狼個體路徑解中復制相應長度的片段,根據所得長度隨機確定有效的插入點,完成插入后對重復、缺少的數據進行篩選、裁剪和補充[27],如圖5所示。在局部范圍搜索則為單一個體進行自我改進,完成個體內的一定片段的互換、抽取和插入操作,且在完成局部搜索后同樣對重復、缺少的數據進行篩選、裁剪和補充,如圖6所示。

圖5 狩獵靠近過程Fig.5 Hunting approach process

圖6 局部搜索過程Fig.6 Local search process

4 算法驗證

以問題模型中包括3個彈藥升降機、5輛裝載容量為2的彈藥運輸車為例,假設向16個目標工作點完成運輸和裝載任務[28],其中包括運輸暫存目標工作點和彈藥裝載目標工作點各8個,各點位的相關信息如表2所示。在Unity軟件內置的C#腳本中編寫并運行上述改進GWO算法,并與傳統遺傳算法對相同問題模型的處理結果進行對比[29],其適應度隨迭代次數的變化情況如圖7所示。獨立重復使用上述兩種算法分別對問題模型求解20次[30],對比結果如表3所示。獲得的最優調度解及其調度路線方案如圖8所示。

表2 各目標工作點位信息表(3個升降機加16個目標工作點)Table 2 Information table for each site (with 3 lifts and 16 target working sites)

表3 算法優化結果對比(3個升降機加16個目標工作點)Table 3 Comparison of algorithm optimization results (with 3 lifts and 16 target working sites)

圖7 算法適應度值隨迭代次數變化情況(16個目標工作點)Fig.7 Variation of algorithm fitness values with iterations number (with 3 lifts and 16 target working sites)

圖8 最優調度解及其調度路線方案(16個目標工作點)Fig.8 Optimal scheduling solution and its scheduling route scheme (with 16 target working sites)

為進一步驗證算法對更大規模問題模型的優化求解能力,修改問題模型包括3個彈藥升降機和8輛裝載容量為2的彈藥運輸車,向24個目標工作點完成運輸和裝載任務,其中包括運輸暫存目標工作點和彈藥裝載目標工作點各12個,各點位的相關信息如表4所示。采用改進GWO算法與傳統遺傳算法處理結果對比的方式,獲得的適應度隨迭代次數的變化情況如圖9所示,20組獨立重復實驗獲得的對比結果如表5所示,獲得的最優調度解及其調度路線方案如圖10所示。

表4 各目標工作點位信息表(3個升降機加24個目標工作點)Table 4 Information table for each target working site (with 3 lifts and 24 target working sites)

表5 算法優化結果對比(3個升降機加24個目標工作點)Table 5 Comparison of algorithm optimization results (with 3 lifts and 24 target work sites)

圖9 算法適應度值隨迭代次數的變化情況(24個目標工作點)Fig.9 Variation of algorithm fitness values with iterations number (with 24 target worksites)

圖10 最優調度解及其調度路線方案(24個目標工作點)Fig.10 Optimal scheduling solution and its scheduling route scheme (24 target working sites)

由上述結果能夠直觀地看到,本算法對此類運輸調度問題的求解十分有效。經多次實驗對比,本文獲得的問題解較遺傳算法收斂結果更優,且收斂速度更快。多主體虛擬仿真系統實驗證明,所得到的解在大多數情況下是理論情況下的最優路徑解[31],證實所提算法求解精度也十分可靠。

5 結束語

在影響現代戰爭的諸多因素中,保障是一項高度基礎和重要的環節,改進航母飛行甲板上艦載機彈藥調度保障效率有十分重要的戰略意義。為保障艦載機彈藥調度更高效、更可靠地完成,本文通過補充直線轉運路徑中間點定義、整數編碼、負整數標志分組等方法設計了改進GWO算法。通過問題模型實例驗證,本系統能高效地完成調度方案規劃,相比傳統優化算法具備更優秀的效率和精度,對大型作戰場景的優化調度保障有較好的指導意義,未來通過進一步的改進完善定會在高頻次作戰保障上發揮重要作用。