劉玉杰, 崔凱凱, 韓 維, 李 樾
(1. 海軍航空大學航空基礎學院, 山東 煙臺 264001; 2. 海軍招收飛行學員工作辦公室, 北京 100071; 3. 中國人民解放軍92942部隊, 北京 100161; 4. 中國人民解放軍92728部隊, 上海 200436)
艦載機作為航母最關鍵、最核心的攻防武器,其出動回收效率將直接影響整個航母戰(zhàn)斗群的作戰(zhàn)能力。目前,世界各航母強國均基于自身航母及航空保障裝備性能,積極開展航母出動回收流程規(guī)劃研究。航母從回收著艦[1]至再次出動之前,通常需要經歷甲板轉運、出入庫、機務勤務保障[2]、武器掛載、出動離場等工序。出動離場作為艦面保障與離艦升空的銜接環(huán)節(jié),對編隊任務的執(zhí)行效能有著直接影響。
針對艦載機出動離場流程,文獻[3]設計了一種面向出動離場任務的T-Petri網模型,對不同的出動離場任務進行仿真,同時研究人員還研究了粒子群優(yōu)化(particle swarm optimization, PSO)算法[4]在離場出動問題上的應用。文獻[5]將出動離場規(guī)劃問題分解為起飛位選擇和各起飛位上的艦載機排序兩個階段決策過程,分別設計了規(guī)劃決策規(guī)則和自動規(guī)劃方法。Liu等[6]將艦載機出動建模為混合流水車間規(guī)劃問題,考慮了航母甲板上多架艦載機滑行協(xié)同軌跡規(guī)劃問題,基于預設的艦載機出動離場滑行路徑庫,設計了一種雙層遺傳算法對問題進行求解。蘇析超等[7]同樣將出動離場過程建模為混合流水車間規(guī)劃問題,并設計了一種混合差分進化算法,通過規(guī)劃艦載機飛行前準備作業(yè)過程中多階段工位上作業(yè)的保障順序,提升了艦載機的出動效能。萬兵等[8]進一步在混合流水車間規(guī)劃模型的基礎上,引入了間隔變量和邏輯約束,建立了一種約束規(guī)劃模型,設計了一種多機出動離場規(guī)劃啟發(fā)式規(guī)則,將多機規(guī)劃問題轉化為單機規(guī)劃問題,并提出一種單機約束引導啟發(fā)式搜索與約束規(guī)劃二分法迭代算法對艦載機出動離場流程進行優(yōu)化。此外,研究人員還分析了起飛位對艦載機出動離場效能的貢獻問題。
PSO算法是一種較為常用的智能優(yōu)化算法[9],具有概念簡單、所需調節(jié)參數(shù)少等優(yōu)勢[10],其在任務資源分配[11-12]、航跡規(guī)劃等[13]領域都有著廣泛的應用。但標準的PSO算法收斂精度較低且容易陷入局部最優(yōu),針對標準PSO算法的不足,學者們進行了相應的改進。文獻[14]將混沌優(yōu)化思想與PSO算法相結合,對粒子群的最優(yōu)位置進行了混沌優(yōu)化,提高了PSO算法跳出局部極值的能力。文獻[15]通過將自適應策略與精英學習策略引入標準PSO算法,有效地提高了算法跳出局部最優(yōu)的能力。文獻[16]的并行免疫PSO算法利用免疫算子克服了PSO算法的局部收斂問題。
研究人員雖然對艦載機出動離場規(guī)劃問題進行了一定的研究,但出動離場規(guī)劃問題約束較為復雜且存在路徑干涉問題,相關規(guī)劃算法的優(yōu)化性能仍存在進一步提升的可能性。本文設計了一種改進的PSO(improved PSO, IPSO)算法,該算法通過在參數(shù)自適應PSO算法的基礎上引入基于萊維飛行擾動的模擬退火(simulated annealing, SA)機制,以提高PSO的局部搜索能力。將IPSO用于出動離場規(guī)劃問題,取得了良好的規(guī)劃效果。
艦載機位甲板負責完成機務勤務保障和武器掛載任務,飛行員接受任務登機后,艦面指揮規(guī)劃轉入出動離場階段[17]。艦載機在執(zhí)行出動離場任務時,需要按以下5個步驟執(zhí)行任務,如圖1所示。

圖1 艦載機機隊出動流程示意圖Fig.1 Schematic diagram of carrier aircraft fleet dispatch process
(1) 出動艦載機選擇
通常甲板上停放的艦載機數(shù)量多于需要出動的艦載機數(shù)量,因此在制定出動計劃之前需要選擇執(zhí)行出動任務的艦載機(或其停機位置)。同時,發(fā)動機在起飛出動前需在其停機位上完成暖機工作,本文假設出動前艦載機均已完成發(fā)動機暖機,且暖機時艦載機處在低速運行狀態(tài),忽略其對艦面設備的干擾[18]。
(2) 轉運滑行
當艦載機完成暖機后,需要根據(jù)出動方案滑行進入相應的等待位或起飛位,為后續(xù)離場做準備。在該階段需要考慮不同艦載機轉運路徑之間可能存在的干涉情況,制定避碰規(guī)則。
(3) 入位等待與起飛準備
當艦載機所分配到的起飛位有前序出動艦載機時,需要先滑行至偏流板后方的起飛等待位處,待前序艦載機出動起飛和偏流板冷卻完畢后再滑行至起飛位進行起飛準備。當艦載機進入起飛位后,飛行員和艦面保障人員將會對艦載機執(zhí)行最后的檢查工作。
(4) 滑距起飛
當保障人員和飛行員檢查艦載機完畢,確定無故障隱患后,將信息反饋給起飛助理員,起飛助理員檢查起飛跑道并確認其滿足起飛要求后給出起飛指令,飛行員在相應的跑道上完成起飛。
(5) 偏流板復位與冷卻
艦載機完成起飛后,偏流板需要復位并冷卻,待該工序結束后,單架艦載機的起飛離場階段結束。
在建立艦載機機隊的出動離場模型前,根據(jù)問題實際做出如下假設:① 對于單架艦載機,其起飛離場各作業(yè)子階段不可中斷;② 忽略轉運滑行子階段的隨機影響因素,默認轉運時長只與轉運路徑的距離有關;③ 當不同的艦載機在轉運過程中存在碰撞風險時,則兩機的轉運任務不能同時進行(需待前機轉運完成后,后機的轉運任務才能開始);④ 轉運方案中,各機的暖機時間和起飛準備時間均設定為定值。
1.2.1 數(shù)學符號及其含義
Ej:待出動艦載機集合;
nj:待出動艦載機數(shù)量;
Ei:艦載機出動工序集合;
ni:艦載機出動工序數(shù)量;
Li:工序i可操作位置的集合;
j:艦載機編號,j=1, 2, 3,…,nj;
i:出動流程工序編號,i=1, 2, 3,…,ni;

np:停機位數(shù)量;
P:停機位編號,P=1, 2, 3,…,np;
T:起飛位編號,T=1, 2, 3;
D:等待位編號,與起飛位一一對應,D=1, 2, 3;
PD:跑道編號,與起飛位一一對應,PD=1, 2, 3;
PLB:偏流板編號,與起飛位一一對應,PLB=1, 2, 3;
TRPD:從停機位P到起飛位T的轉運路徑;
ΔtPD:從停機位P到起飛位T的轉運時間;
tN:暖機所需時間;
tZ:起飛準備時間;
ΔTf:同一停機位上先后兩架飛機的起飛時間最小間隔(由艦載機尾流間隔、偏流板復位及冷卻時間決定);
ΔTt:同一停機位先后被兩架飛機使用且能夠確保安全的最小間隔時間;
dsafe:轉運過程中不同飛機之間必須要滿足的安全距離間隔;
Bji:艦載機j的第i個工序的開始時刻;
DTji:艦載機j的第i個工序的最短執(zhí)行時長;
Eji:艦載機j的第i個工序的結束時刻;
1.2.2 目標函數(shù)與決策變量
本文中,艦載機機群出動調度問題的決策變量為
考慮到艦載機機群出動任務所用時間越少,其后續(xù)回收保障任務可以越早開始,本文中所選擇的目標函數(shù)為最小化出動完成時間,即
(1)
1.2.3 艦載機出動模型約束
(1) 對于某架艦載機j的任意一個工序i,其必須選擇且只能選擇一個操作位置執(zhí)行,即
(2)
(2) 對于某架艦載機j的任意一個工序i,其完工時刻不小于該工序的開始時刻與工序最短執(zhí)行時長之和,即
Eji≥Bji+DTji,?i∈Ei;?j∈Ej
(3)
(3) 對于某一操作位置,其任意時刻最多只允許一個工序在該位置執(zhí)行,即
(4)
(4) 在甲板布列選擇階段,也即出動工序1階段,單個停機位最多只能停放一架艦載機,即
(5)
(5) 對于某架艦載機而言,除工序1,其他工序的開始時間應滿足如下關系:
Bji≥Ej(i-1)≥Bj(i-1)+DTji,i>1
(6)
(6) 對于某架艦載機,其轉運滑行與入位等待工序之間的時長間隔必須超過轉運耗時,即
Bj3-Bj2≥ΔtPD, TRPD,j=1
(7)
(7) 同一個起飛位前后兩架艦載機的放飛時間間隔必須滿足艦載機尾流間隔、偏流板復位及冷卻時間限制,即
|Bj5-Bh5|≥ΔTf,?l∈L5;WPj5,l=WPh5,l
(8)
(8) 一旦艦載機i的起飛位在工序3中被確定,則其工序4和工序5的執(zhí)行位置也被確定,且與起飛位保持一致,即
WPj3,l=WPj4,l=WPj5,l,?j∈Ej
(9)
(9) 對于某一個停機位,當艦載機進入該停機位時,前序艦載機已經從停機位離開,且時間間隔大于最小安全間隔時間,即
Eh3-Bj3≥ΔTt,?l∈L3;WPj3,l=WPh3,l;Bj3>Bh3
(10)
(10) 對于某一個起飛位,當艦載機進入該起飛位對應的停機位時,前序艦載機已經離場,且偏流板已完成復位冷卻,即
Ej3>Eh5,?l∈L5;WPj5,l=WPh5,l;Bj5>Bh5
(11)
(11) 為保證轉運安全,文中默認艦面轉運過程是不可中斷的,即某機的轉運過程一旦開始,就要按預先的轉運路徑轉移至預定的等待位上,即
(12)
(12) 在第2階段的轉運滑行過程中,在不同艦載機的轉運路徑之間要防止發(fā)生碰撞,即
(13)
1.2.4 艦載機滑行避碰策略
一般情況下,當任務要求出動的艦載機數(shù)量較多時,飛行甲板上會出現(xiàn)多架艦載機同時滑行的情況,而飛行甲板空間相對狹小,在進行多架艦載機同時滑行操作時必須要考慮避碰問題,本文采用如下避碰策略:
(1) 采用文獻[19]中的牛頓保辛偽譜(Newton symplectic pseudospectral, NSP)法計算離線轉運路徑庫,該路徑庫包括了從某停機位滑行至所有準備位的路徑軌跡及時間點信息。
(2) 根據(jù)機群出動任務規(guī)劃模型,獲得機群出動方案,該方案包括了所有艦載機出動流程工序的先后順序以及對應的加工位置序號。
(3) 根據(jù)從停機位滑行至起飛準備位工序的加工順序,基于NSP-Dubins-相對速度障礙(reciprocal velocity obstacle, RVO)協(xié)同路徑規(guī)劃方法依次更新各架艦載機的實際路徑和到達時間。具體步驟如下:
1) 對于優(yōu)先級排序為K(優(yōu)先級K由艦載機在出動方案中的順序決定)的艦載機,假設其按照預規(guī)劃的路徑以及滑出時間開始滑出;
2) 獲取當前時刻(優(yōu)先級排序為K的艦載機開始滑出的時間)正在執(zhí)行從停機位滑行至起飛準備位工序的工件(艦載機)數(shù)量以及各自的位置、姿態(tài)、速度;
3) 采用文獻[6]中的避碰策略處理艦載機轉運滑行階段可能會出現(xiàn)的路徑干涉問題,其主要思想是:依據(jù)離線路徑庫和轉運滑行開始時間檢測當前滑行的艦載機是否會與其他艦載機發(fā)生碰撞。若無碰撞風險,則甲板上正在轉運滑行的艦載機均按照離線路徑庫以及原方案滑行;若存在碰撞風險,則記錄甲板上正在轉運滑行的艦載機的起始狀態(tài)及其目標滑行的終點位置,保證滑行優(yōu)先級最高的艦載機仍按照原方案計劃的時間滑出。對當前甲板上正在滑行的全部艦載機進行協(xié)同路徑規(guī)劃,得到考慮避碰條件下艦載機的滑行路徑以及到達時間,更新出動方案中艦載機的實際滑行路徑以及滑行結束時間。
考慮到本文所研究的艦載機出動離場規(guī)劃問題可以抽象為一個帶有動態(tài)干擾約束的混合流水車間規(guī)劃問題,流水車間規(guī)劃問題中必須要確定每個工件所對應工序的加工先后順序,以及各個工序所對應的加工機器。因此,編碼的形式在能夠表示式(2)~式(13)中全部決策變量信息的前提下應盡量簡潔且利于優(yōu)化算法的處理操作。本文采用連續(xù)編碼矩陣的形式來表示艦載機機群的出動回收規(guī)劃方案,對于單架艦載機的出動離場規(guī)劃問題,其編碼的具體表示形式如圖2所示。

圖2 編碼矩陣示意圖Fig.2 Schematic diagram of coding matrix
由于在實際出動離場問題中存在流程及資源約束,采用圖2中所示的編碼形式時,必須要對編碼基因進行如下的限制,以生成合理可行的編碼方案。
(1) 編碼的整數(shù)部分必須小于該工序的可用加工機器數(shù)量,以保證出動方案中的加工機器存在。
(2) 工序3~工序5的加工機器應一一對應。
根據(jù)編碼中未完成工序的優(yōu)先級生成待執(zhí)行工序隊列,從隊列中按順序選擇待加工工序,判斷是否滿足式(2)~式(13)的約束條件。若滿足則執(zhí)行該工序,若不滿足則按隊列順序選擇執(zhí)行下一工序,直至全部工序執(zhí)行完畢,得到最終的出動離場執(zhí)行方案,并計算離場任務完成時間。
考慮到經典的PSO算法的尋優(yōu)策略適應能力不強且缺乏局部尋優(yōu)機制,本文基于萊維飛行公式和SA思想對經典的PSO算法加以改進,并將IPSO算法用于艦載機的出動離場規(guī)劃問題。
2.3.1 標準PSO算法
標準PSO算法[19]的主要思想為:在整個D維尋優(yōu)空間中隨機生成一組(共m個)粒子,粒子i在尋優(yōu)空間中的位置向量為Xi(0)=[xi1,xi2,…,xiD]T,速度向量為Vi(0)=[vi1,vi2,…,viD]T,粒子利用個體極值和種群極值信息在尋優(yōu)空間中進行飛行,其飛行速度和空間位置更新如下:
(14)
式中:i∈[1,m],d∈[1,D];w為慣性權重系數(shù),c1和c2為學習因子;r1和r2為[0,1]區(qū)間內的隨機數(shù);n為粒子群迭代次數(shù);Pi=[Pi1,Pi2,…,PiD]為粒子i的歷史最優(yōu)位置,即個體極值點;Pg=[Pg1,Pg2,…,PgD]表示整個粒子群的歷史最優(yōu)位置。
2.3.2 參數(shù)自適應
從式(14)可以看出,在標準的PSO算法[20]中,參數(shù)w、c1和c2的值對粒子的運動行為會有較大影響,而標準PSO算法中的參數(shù)均設置為常數(shù),不利于調整粒子的運動趨勢。為此,本文借鑒文獻[21]中的控制參數(shù)自適應思想,對參數(shù)w、c1和c2引入如下的自適應規(guī)則:
(15)
式(15)的主要作用是在算法的前期增加粒子飛行的全局遍歷能力,而在算法的后期提升粒子的局部搜索能力。下標max、min分別表示對應變量的最大值和最小值。
2.3.3 基于SA和萊維飛行的鄰域搜索機制
除了對標準的PSO算法進行參數(shù)自適應設置,本文基于萊維隨機飛行和SA機制設計了一種粒子鄰域搜索機制,以進一步增強算法的尋優(yōu)性能,其主要思想在于將萊維飛行搜索機制優(yōu)秀的鄰域搜索能力應用到SA算法的鄰域搜索中。
首先引入SA的概念[22],SA是一種基于蒙特卡羅思想的啟發(fā)式隨機尋優(yōu)算法。其通過模擬固體降溫的熱力學過程,利用Metropolis準則的概率突跳特性在尋優(yōu)過程中跳出局部最優(yōu)解。徐小琴等[23]在利用布谷鳥搜索算法對電力系統(tǒng)資源進行優(yōu)化配置的過程中,引入了SA機制來提高算法的全局和局部搜索能力。此外,SA算法在用戶任務卸載[24]、導引車任務分配[25]以及旅行商等問題[26]中也取得了良好的效果。Metropolis準則的核心思想是在溫度下降的過程中能以一定的概率接受較差的解,即在不同的情況下,算法對于新解的接受概率為
(16)
式中:E(x)表示能量值(也即適應度值);xold和xnew分別表示擾動前和擾動后的解;Temp表示退火溫度。
本文采用萊維飛行對粒子進行擾動,萊維飛行的隨機步長滿足萊維分布,而萊維分布屬于厚尾分布,其與Gauss分布相比尾翼更寬,擾動能力也更強[27]。當前,萊維飛行策略已經被廣泛應用到各種尋優(yōu)算法中。文獻[28]針對風電場中的風機渦輪布局優(yōu)化問題,設計了一種基于萊維飛行的野草(Levy flight invasive weed optimization, LFIWO)算法。文獻[29]設計了一種基于萊維飛行的改進樽海鞘(Salp-Swarm)特征選擇算法。Zhang等[30]將萊維飛行應用到雙種群果蠅優(yōu)化算法中,也取得了良好的效果。萊維隨機步長依靠計算機編程語言實現(xiàn)時,一般采用Mantegna公式[31]:
(17)
式中:s表示萊維飛行的步長;參數(shù)β通常取為1.5;μ和ν為隨機變量,滿足正態(tài)分布:
(18)
式中:δμ和δν滿足
(19)
式中:Γ為標準Gamma函數(shù)。
800代萊維飛行的隨機路線如圖3所示。

圖3 800次萊維飛行路線圖Fig.3 Routes of 800 times Levy flight
在粒子群的第k次迭代過程中,粒子Xi(k)=[xi1,xi2,…,xiD]T經過萊維飛行擾動后變?yōu)?/p>
(20)

以某彈射型航母的出動離場任務作為仿真案例,該航母共有3個起飛位可用,編號分別為A、B、C,航母的甲板布置如圖4所示。1~13號停機位至A、B、C后方的起飛等待位的轉運路徑,以及起飛等待位至相應起飛位的轉運路徑均已提前通過計算獲得,并儲存在轉運路徑庫中,出動過程中各機的轉運路線均從轉運路徑庫中選擇。基于文獻[6]中的避碰策略處理艦載機轉運滑行階段的路徑干涉,待出動的艦載機類型相同,且認為均已完成艦面保障工作。

圖4 算例航母甲板布置示意圖Fig.4 Deck layout schematic diagram of example aircraft carrier
設置IPSO的種群規(guī)模為50,最大的迭代次數(shù)為50,萊維飛行的擾動尺度因子設為0.2。自適應參數(shù)的取值為c1max=2.5,c1min=1.25,c2max=2.5,c2min=1.25,wmax=0.9;wmin=0.15;擾動尺度因子θ=0.2。
仿真環(huán)境為Windows 10操作系統(tǒng),采用Matlab 2016b仿真軟件,仿真平臺為8 G內存、主頻2.30 GHz的PC機。
首先,給出共有8架艦載機進行出動的條件下,采用IPSO算法進行離場規(guī)劃時所得到的艦載機離開停機位的出動順序,即1→7→2→13→6→10→5→4,其出動工序完工時間為389.7 s,算法求解時長為207.74 s,出動方案甘特圖如圖5所示。

圖5 8架機出動方案甘特圖Fig.5 Gantt chart of eight aircraft’s deployment plan
甘特圖中的數(shù)字表示艦載機出動過程中的子工序編號,由于工序1為出動艦載機選擇,屬于虛擬工序,所以此處僅給出了工序2~工序5的加工時間情況。
出動艦載機數(shù)量規(guī)模為8架時,各個加工位置的工序占用時間甘特圖如圖6所示。其中,甘特圖中的數(shù)字表示艦載機的編號及其工序編號,如“603”表示艦載機6的第3道子工序。

圖6 8架機出動時加工位置的使用情況甘特圖Fig.6 Gantt chart of the processing positions working when eight aircraft are dispatched
為了驗證算法的效果,這里選擇文獻[6]中的雙層編碼遺傳算法(double-layer coding genetic algorithm, DL-GA)進行對比,當出動艦載機數(shù)量規(guī)模為8架時,IPSO算法與DL-GA算法的迭代收斂曲線對比圖如圖7所示。

圖7 8架機出動迭代曲線對比圖Fig.7 Comparison diagram of iteration curve when eight aircraft are dispatched
從圖7可以看出,采用本文所提IPSO算法可以顯著提高艦載機的出動效率。與文獻[6]中的算法相比,在有8架艦載機出動的情況下,采用本文所設計的IPSO算法優(yōu)化得到的出動方案完成時間比文獻[6]中算法的出動完成時間減少了32.9 s。
考慮艦載機出動規(guī)模增加時算法的規(guī)劃效果,假設出動的艦載機數(shù)量規(guī)模增加至10架,采用IPSO算法得到的出動方案如圖8所示。在所得到的出動方案中,各艦載機出動的順序為13→2→5→3→4→9→11→6→12→7,其出動工序完工時間為490.3 s。

圖8 10架機出動方案甘特圖Fig.8 Gantt chart of 10 aircraft’s deployment plan
當出動艦載機數(shù)量規(guī)模為10架時,各個加工位置的工序占用時間甘特圖如圖9所示。

圖9 10架機出動時加工位置的使用情況甘特圖Fig.9 Gantt chart of the processing positions working when 10 aircraft are dispatched
當出動艦載機數(shù)量規(guī)模為10架時,算法的迭代收斂曲線如圖10所示。

圖10 10架機出動方案迭代曲線Fig.10 Iteration curve of 10 aircraft’s dispatching plan
進一步,當所需出動的艦載機數(shù)量為12時,采用IPSO算法得到的出動方案如圖11所示。在所得到的出動方案中,各艦載機出動的順序為6→1→7→3→9→5→11→8→4→2→12→13,其出動工序完工時間為587.5 s。

圖11 12架機出動方案甘特圖Fig.11 Gantt chart of 12 aircraft’s deployment plan
當出動艦載機數(shù)量規(guī)模為12架時,各個加工位置的工序占用時間甘特圖如圖12所示。

圖12 12架機出動時加工位置的使用情況甘特圖Fig.12 Gantt chart of the processing positions working when 12 aircraft are dispatched
當出動艦載機數(shù)量規(guī)模為12架時,算法的迭代收斂曲線如圖13所示。

圖13 12架機出動方案迭代曲線Fig.13 Iteration curve of 12 aircraft’s dispatching plan
當艦載機出動規(guī)模分別為10架和12架時,算法的仿真計算時長分別為319.33 s和414.05 s。據(jù)此可以計算,當艦載機數(shù)量分別為8、10、12時,算法中種群進化一代所需要的計算時長分別為4.15 s、6.39 s和8.28 s。由此可見,當艦載機數(shù)量增加0.5倍后(由8增加至12),其單代進化耗時增加近1倍。
本文針對艦載機出動離場規(guī)劃問題提出了一種IPSO算法,該算法通過在參數(shù)自適應粒子群算法的基礎上引入基于萊維飛行擾動的SA機制來提高標準PSO算法的局部搜索能力。與已有文獻中的DL-GA算法在同條件下進行仿真對比,仿真結果表明本文所提出的IPSO算法較DL-GA算法而言具有更好的尋優(yōu)效果。
但本文假設出動前艦載機均已完成發(fā)動機暖機,且暖機時艦載機處在低速運行狀態(tài),可忽略其對艦面設備的干擾。后續(xù)將進一步把暖機對艦面設備的干擾考慮在內,研究其對出動效率的影響,以及如何進一步提高出動效率。此外,本文當前僅針對有人艦載機模式進行了研究,為有效應對當前人工智能高速發(fā)展趨勢,后續(xù)將梳理艦載無人機甲板出動流程,并針對有人/無人機協(xié)同出動離場和無人機機群出動離場規(guī)劃特點,對該算法做出適應性改進研究。