基于MGP算法的艦載機回收排序調度技術

崔凱凱, 崔榮偉, 韓 維, 郭 放, 王毓麟, 劉 潔

(1. 海軍航空大學航空基礎學院, 山東 煙臺 264001; 2. 中國人民解放軍92942部隊, 北京 100161; 3. 軍事科學院戰爭研究院, 北京 100850)

0 引 言

由于艦載機通常采用大機群回收的方式,其在進入最終的著艦下滑道之前必須要根據相應的指標要求進行回收排序,以確定機群中各架艦載機的著艦順序。因此,對著艦回收排序算法的研究有利于減少艦載機的回收耗時,提高回收任務的效能,保證飛行安全,同時也有利于后續保障和再出動任務的進行。飛機著陸調度(aircraft landing scheduling, ALS)是空中交通管制領域中的一個復雜問題[1],目前相關的研究主要集中在民用航空領域[2-6]。

文獻[2]通過序列二次規劃確定了高密度運行條件下的最優飛機著陸序列及相應的飛行時間,并基于對排序結果的分析提出了3種排序規則。相關的蒙特卡羅模擬結果表明,通過2次簡單的著陸順序交換,最多可節省17%的燃油消耗。文獻[3]基于任務完成總時間最短的目標和滾動時域思想設計了一種結合人工魚群和粒子群優化(artificial fish particle swarm optimization, AFPSO)的飛機降落排序算法。與先到先服務方法相比,AFPSO算法在單跑道情況下可以使航班隊列著陸的總延遲時間減少36%。文獻[4]設計了一種用于減小飛機著陸總延遲時間的線性規劃方法,該方法通過貪婪式啟發算法給出了最大延遲時間上界的估計值,確保了混合整數線性規劃模型具有可行解,且該算法采用分枝定界策略對搜索樹節點進行了修剪,提高了搜索效率,機場實際數據驗算結果表明該算法相對于普通的線性規劃算法具有更強的優化能力。文獻[5]借助單機調度中的準則選擇方法確定了ALS問題中的多個待優化目標函數,并采用包括帝國競爭算法(imperialist competitive algorithm, ICA)在內的多種求解算法對多目標ALS問題進行了求解。仿真計算結果表明,該方法能夠有效解決ALS多目標優化問題,在提高航班的準點率和跑道利用率的同時減少了空中交管人員的工作量。文獻[6]基于ALS復合分派規則,設計了針對ALS問題的啟發式算法。仿真計算結果表明其所提出的算法相較于Lingo軟件的求解結果而言,平均每架航班的降落時間可以提前2.4 min。而文獻[7]則提出了一種CGIC(costs, generation rule, improvement heuristic, connection rule)啟發式算法以解決ALS問題。CGIC基于4種操作規則將ALS問題分解為兩個或多個子問題,從而降低了ALS問題的復雜性。仿真結果表明,即使在動態情況下,CGIC依然可以獲得高質量的調度求解方案,且計算時間滿足實時性要求。

與民航飛機有所不同,艦載機著艦時只有一條著艦跑道可以使用,且跑道的距離遠遠短于陸基機場,發生逃逸或者復飛的概率要遠遠大于陸基飛機。同時,艦載機執行的是戰斗任務,其在返航時很有可能存在戰損,且由于戰場形勢的多變,作戰任務時長可能會超出預期,這將導致返航油量過低的情況。相比于經濟效益,航母艦載機在進行回收著艦時更加注重著艦方案是否有利于后續作戰和保障任務的高效執行。目前來看,艦載機機群的著艦回收排序主要依靠人工調度實現,即空管人員利用其所掌握的回收機群信息和以往的經驗綜合進行判斷[8]。但采用人工調度的方式不僅增加了航母空管人員的負擔,且當待回收的艦載機種類較多、數量規模較大時,該方式難以在短時間內給出高效的著艦方案。此時,空管人員為了保證回收安全,往往采用讓剩余油量少的艦載機先行著艦的方式[9],該方式雖然簡單易行,但無法從整體上綜合考慮機群的著艦回收效能,局限性較大。

因而近年來,部分學者針對艦載機著艦回收調度問題也進行了一定的研究。文獻[10]考慮了艦載機回收時的排隊特性以及著艦失敗的可能,對艦載機的著艦回收調度問題進行了分析。文獻[11]針對艦載機回收時甲板跑道容量受限問題,比較了先到先服務、依據最早到達時間、滑動時間窗口等3種算法的回收排序效果。仿真結果顯示滑動時間窗口排序法計算量較小且具有較好的優化效果,但文獻中所用的排序算法均利用了艦載機的預計到達時間,難以適用于艦載機大機群到達的情況[12]。文獻[13]針對典型的艦載機回收模式提出了一種考慮著艦失敗架次飽和度的回收調度策略,解決了著艦失敗隊列與首次著艦待機隊列之間可能出現的資源點爭奪問題。文獻[11,13]所提到的幾種排序算法以及空管人員所使用的“油少先著艦”排序方式本質上都屬于啟發式算法,此類算法具有快速的響應能力,但求解效果受主觀確定的啟發式規則的影響較大,且不能夠進行迭代優化。文獻[14]針對機群著艦回收排序問題,提出了一種基于蟻群算法的動態排序算法,使艦載機機群能夠以最優順序著艦。通過與最少燃料優先服務的方法和靜態蟻群排序算法相比較,驗證了基于蟻群算法的動態排序算法的優勢。文獻[15]綜合考慮了著艦返航時艦載機的剩余油量、戰損情況等隨機性因素的影響,建立了相應的著艦回收模型,用于對回收著艦的風險成本進行優化,并提出了一種帶有模擬退火機制的粒子群算法以對著艦回收排序問題進行求解。文獻[16]將艦載機著艦回收調度問題抽象為隨機規劃問題,并提出了一種基于著艦優先序指標的蒙特卡羅-差分進化實時排序調度算法。仿真結果顯示在相同的初始條件下,利用蒙特卡羅-差分進化算法求解得到的目標函數值呈現出了較好的統計特性,且算法的收斂速度較快。文獻[12]針對艦載機著艦回收調度問題,構造了一種考慮加權完成時間的目標函數,并設計了一種經過改進的人工蜂群算法對該問題進行求解,經仿真對比驗證了其所提出的算法具備較強的優化能力和魯棒性。

上述研究很少考慮空中加油對著艦方案的影響,使得其對返航艦載機油量有著較大的限制,適用場景相對受限。且上述調度求解方法從本質上而言大多屬于元啟發式算法,而元啟發式算法在迭代求解的過程中需要進行大量的隨機搜索操作,當問題規模較大時,其搜索效率和搜索穩定性會變差[17]。

針對啟發式算法以及元啟發式算法的不足,文獻[18]提出了超啟發式算法的概念,超啟發式算法的提出為復雜調度問題提供了一種新的求解思路。該算法通過高層次的啟發式策略來操縱若干個低層次啟發式方法,從而生成新的尋優算法,超參少且實用性較強[19],在近年來引起了廣泛的關注。其已被用于求解航母甲板作業調度[20]、自動化碼頭箱位分配[21]、車輛取送貨路徑規劃[22]以及云計算調度[23]等眾多工程實踐領域,取得了理想的效果。進一步,學者們將遺傳算法的優化過程模擬到超啟發式算法上,形成了遺傳規劃(genetic programming, GP)算法[24],并將其廣泛應用于項目調度問題。文獻[25]首次將超啟發式調度算法應用于具有隨機工時的項目調度問題中,提出一種超啟發式集成遺傳規劃方法,通過進化優先級規則組合來求解隨機資源受限的項目調度問題。該算法通過3種不同的局部搜索方法來增加各代種群的多樣性。此外,算法還設計了一種序列投票機制來處理隨機資源受限的項目調度過程中的協同決策問題,仿真驗證表明該算法相對于啟發式、元啟發式和單一超啟發式算法具有一定的優勢。文獻[26]提出一種基于遺傳規劃的動態車間調度算法,對最長完工時間和平均延遲時間進行了優化,并借助排序規則的自動生成機制,提高了車間調度算法在不同場景中的動態適應性。文獻[27]針對多技能資源約束項目調度問題提出了一種遺傳規劃超啟發式算法,其通過使用單個任務序列向量進行編碼,并基于修復的解碼方式來生成可行的調度方案,仿真對比實驗驗證了該算法在求解效果和收斂速度方面的優勢。除此之外,GP算法在其他一些項目調度問題中也獲得了良好的效果[28-30]。但目前尚未見有利用超啟發式算法對著艦回收調度問題進行求解的相關文獻。

針對當前艦載機著艦回收調度問題研究過程中存在的不足,本文建立了考慮空中加油條件的艦載機機群著艦回收調度問題模型,同時基于超啟發式思想設計了一種帶強制著艦規則的GP (GP with mandatory landing rules, MGP)算法,用于對著艦回收排序問題進行求解。

1 艦載機機群回收排序問題模型

1.1 艦載機著艦回收排序問題分析

通常而言,艦載機返航的過程可分為4個階段,即引導段、待機段、進場段和著艦段[31]。在通常情況下,當艦載機飛行至距航母200 n mile的位置后,艦上的航管中心開始接管艦載機。

一般情況下,根據不同的天氣狀況及晝夜情況,固定翼艦載機的回收著艦模式可分為3類。其中,第一類回收著艦模式要求晝間天氣狀況良好,能見度大于5 km,此時可采用目視進場以及人工著艦的方式;當航母上方云層的遮擋范圍大于5/8時,一般采用第二類回收著艦模式,即采用儀表引導系統進場,并利用自動著艦系統進行著艦;當航母上空300 m以上有云層或夜間著艦時,通常采用第三類回收著艦模式。可見,第三類回收方式適用于夜間和惡劣氣象條件下的著艦回收任務,因此本文以第三類回收著艦模式為例研究艦載機的回收排序問題。

第三類回收著艦模式的飛行航線如圖1所示。通常情況下,在航母左側距離航母約20 n mile的位置設置馬歇爾等待航線,即在1 800 m以上的空域按照300 m的高度差設計多層等待航線。相鄰馬歇爾等待航線之間的水平間隔為1 n mile。在未接到著艦指令時,艦載機在馬歇爾等待航線上盤旋飛行,當接到著艦許可指令后,艦載機從等待航線偏離點A處離開當前等待航線,并以20 m/s的下滑速度經過最底層等待航線的脫離點B(馬歇爾點)后飛至進場始發點C,之后以10 m/s的下滑速度左盤旋飛行,當飛至艦尾后方約10 n mile的位置D時,飛機的高度降至365 m,飛機轉入平飛狀態,直至飛到艦尾后方3 n mile處的E點時,自動著艦系統開始工作,艦載機進行下滑著艦飛行。如出現逃逸或復飛的情況,艦載機需要再次爬升至365 m的高度,之后按照復飛航線飛行并再次進行著艦。

圖1 第三類回收著艦模式下的飛行航線圖Fig.1 Flight route map under the third type of carrier landing recovery mode

1.2 機群回收約束條件分析

為了保證機群的安全,艦載機在進行回收排序的過程中,會面臨許多限制條件,本節將對該問題所涉及的限制條件逐個進行分析。

1.2.1 完整度約束條件

艦載機在執行作戰任務的過程中,經常會出現一定程度的損傷,若損傷情況較為嚴重,則可能會影響艦載機的正常飛行或操縱。當出現艦載機無法穩定飛行或不能正常操縱艦載機的情況時,通常需要聯系陸基機場進行降落,但當航母艦隊執行遠海作戰任務且在艦載機航程內無可用的陸基機場時,只能在航母甲板上進行緊急降落。在緊急降落時,需要將跑道附近的艦載機迅速轉運至安全區域,并架起尼龍阻攔網,待故障機拋掉其所搭載的武器燃料后實施緊急著艦。在故障機完成著艦后,甲板上的人員還要針對可能出現的突發狀況進行滅活和人員救助等工作。由此可見,若將無法正常著艦的故障機安排在著艦回收序列中,會使機群著艦的連續性受到較大影響。因此,通常的處理方式是:① 若故障機具備空中逗留能力,則先讓其在空中盤旋等待,待其他正常機完成著艦后再安排故障機進行著艦;② 若故障機無法在空中穩定飛行,則將其安排在大機群之前進行著艦。

本文中,用完整度WZi表示艦載機i的受損程度。完整度越高,表示受損程度越小,且只有當完整度滿足一定的條件時,才能將其安排進著艦序列中,即WZi>WZmin。本文中,取WZmin=60%。

1.2.2 剩余油量約束條件

受艦載機起落架以及阻攔索承載能力的限制,艦載機在進行著艦時通常面臨最大油量限制,即著艦載機i在其著艦時刻的剩余油量Ozj,i必須小于最大允許著艦油量Omax。同時,由于艦載機在著艦過程中無法保證一次著艦成功,且當前序飛機在著艦失敗后進行二次著艦時有可能會占據后續飛機的航線。因此,在初始的著艦方案中,Ozj,i均應大于某一最小安全裕度值Osafe。當著艦方案生成后,由于著艦隊列內可能會出現復飛或者逃逸的情況,這將會導致后續艦載機的實際著艦時刻較原有著艦方案有所推遲,但無論如何應保證艦載機在進行著艦時,其剩余油量大于最小極限油量Omin。若經判斷當前飛機i的Ozj,i

Osafe=Off+Ocr+Omin

(1)

式中:Off、Ocr分別表示最長復飛航線所需油耗和前序某一架次飛機復飛可能給后續飛機帶來的額外最大油耗。按照式(1)選取Osafe的實際意義在于:初始著艦方案中的飛機在不依賴空中加油的條件下,當前序飛機中出現一次著艦失敗并重新著艦后,該架次飛機仍有一次著艦失敗并重新著艦的機會,且其剩余油量可以保證艦載機在二次著艦仍然失敗后可以安全抵達空中加油位置,而不會出現油量耗盡的情況。考慮到機群回收過程涉及到多種機型,且各機型的油耗速率不同,式(1)中的變量數值與飛機機型直接相關。為了便于處理,后續將剩余燃油油量轉換為剩余燃油可用時間來進行處理。相應地,Omin、Omax、Osafe、Off、Ocr可轉換為TOmin、TOmax、TOsafe、TOff、TOcr,即在后續的研究中,用剩余燃油可用時間來描述艦載機的剩余油量約束條件。記TOi為艦載機i在初始時刻的剩余燃油可用時間,則有:

(2)

式中:Oi表示艦載機i在初始時刻的剩余油量;yhi表示艦載機i的耗油率,其具體數值與艦載機的類型有關。

1.2.3 尾流間隔時間約束條件

艦載機在進行順序著艦的過程中,為了避免由前序艦載機i所產生的飛行尾流對后續飛機j的影響,相鄰兩架飛機經過航線上相同位置的時間必須滿足一定的間隔要求,這一限制即尾流間隔時間限制。一般情況下,尾流間隔時間的限制要求與前后兩架次飛機的類型有關,表1給出了不同類型飛機之間的尾流間隔時間限制要求[8]。

表1 尾流間隔時間限制Table 1 Wake interval time limit

表1中的S、M和L分別表示小型、中型和大型艦載機。在實際著艦過程中,當前續飛機完成著艦后,甲板上的工作人員需要進行跑道清空以及阻攔索復位的工作。在此期間,不允許其他艦載機進行著艦,但由于跑道清空的時間一般要小于艦載機尾流間隔時間限制[16],所以可認為該約束已包含于尾流間隔約束中,而無需再進行單獨考慮。

1.3 基于加權等待時間的回收調度評價指標

第1.2節對艦載機機群回收排序問題中的約束條件進行了分析,本節基于前述分析,建立了基于艦載機完整度、任務優先級、剩余油量飛行時間、回收等待時間以及空中加油次數的回收排序調度評價指標。下面對上述因素展開分析。

(1) 剩余油量飛行時間

基于第1.2節中的分析可知,在艦載機進行著艦時,其剩余油量必須滿足一定的限制,設有n架艦載機需要進行回收,則在回收起始時刻,各架艦載機的剩余油量可飛行時間應滿足TOsafe+TML

(3)

式中:j=1,2,…,n,表示艦載機的編號。由式(3)可知,艦載機的剩余油量可飛行時間越短,其著艦的緊迫度越高。

(2) 艦載機完整度

基于第1.2節中的分析可知,各架艦載機在參與回收時,其完整度必須滿足WZi>WZmin,i=1,2,…,n。與剩余油量可飛行時間類似,當艦載機的受損情況較為嚴重(即艦載機的完整度較小)時,其所對應的著艦緊迫度較高。所以,由WZi所決定的第i架艦載機的著艦緊迫度可表示為

(4)

(3) 后續任務優先級

當艦載機完成回收任務后,一般需要進行機務檢查和保障,以使其快速恢復作戰能力并等待下次出動。同時,當前波次返回的艦載機在后續階段可能需要執行不同的任務,而這些任務的緊迫程度往往也存在差異。這里將艦載機后續任務的緊迫程度用優先級YXJi來表示,其中YXJi的取值為1～5的整數,且取值越小,表示任務的緊迫程度越高,YXJi的具體數值可提前由艦面調度指揮人員根據任務的執行需求情況給出。考慮YXJi對著艦回收排序方案的影響,要求后續任務優先級高的艦載機盡量先著艦。基于此,可以給出由YXJi所決定的第i架艦載機的著艦緊迫度:

(5)

(4) 回收等待時間

在艦載機機群進行回收著艦的過程中,艦載機在著艦前的等待時間DTi是一項極為重要的指標。嚴格來講,艦載機的等待時間應記為從其進入返航待機區開始到完成著艦的時間,但這樣一來,就需要考慮艦載機從進入返航等待區到進入相應的馬歇爾等待航線的具體路線,這一過程的隨機性較大,且不屬于本文的研究范疇。進一步,考慮到機群返回時各架飛機進入返航區的時間差異較小,這里為了簡化問題,以首架著艦機經過馬歇爾點的時刻T0為計時起點,計算艦載機的等待時間,即DTi=ZTi-T0。其中,ZTi表示第i架艦載機的著艦時刻。

基于上述指標影響因素,設計如下回收著艦排序評價指標:

(6)

(5) 空中加油次數

雖然在剩余油量飛行時間部分已經對艦載機的油量進行了一定的限制,但是上述限制并不能保證每一架飛機都能夠實現安全油量著艦,尤其是在機群規模較大或艦載機剩余油量普遍較少的情況下。此時,在生成著艦排序方案時,就極有可能出現部分艦載機燃油不足,無法實現安全油量著艦的情況。在不考慮前序飛機著艦失敗的情況下,若著艦方案中仍有艦載機無法實現安全油量著艦,則需要在著艦方案執行的同時安排油量不足的艦載機進行空中加油,待空中加油完畢后令其重新返回著艦序列,待未加油的艦載機完成著艦后再進行著艦。

(7)

式中:nkj表示在著艦方案中需要進行空中加油的艦載機數量。

1.4 艦載機機群回收排序調度模型

基于第1.2節和第1.3節的分析,可以將艦載機機群回收著艦排序調度問題概括為在保證飛行安全的前提下,通過合理安排艦載機的著艦順序,使得著艦排序評價指標式(7)盡可能小。其決策變量可以用混合整數規劃(mixed integer programming, MIP)模型表示如下:

(8)

為了表達方便,式(8)中引入了編號i=0的虛擬機Jzj0,該虛擬機作為著艦序列的首架機,且真實飛機k在虛擬機后的安全尾流間隔時間WLT0,k均相同,具體數值WLT0為

(9)

借助式(8)可以將艦載機機群回收調度問題的數學模型表示為

MinJ(xi,j)=

(10)

(11)

TOsafe+DTi

(12)

TOmin

(13)

xi,j=0,i∈N1;j∈N0

(14)

minDTi≥JTmin+TML,i∈N1

(15)

(16)

(17)

其中,式(11)表示著艦方案中前后兩架相鄰的艦載機之間要滿足尾流安全要求;式(12)表示在不進行空中加油的艦載機集合N0中,所有的艦載機都必須滿足安全油量著艦的要求;式(13)表示在著艦方案中,只有當艦載機無法實現安全油量著艦的情況下才會進行空中加油,且在著艦方案開始時刻,在需要進行空中加油的艦載機集合N1中,艦載機都必須有充足油量以滿足空中加油航線的需求;式(14)表示在著艦方案中需要進行空中加油的艦載機在完成加油后需排在未加油的艦載機之后進行著艦;式(15)表示進行空中加油的艦載機著艦等待時間大于馬歇爾點至著艦點的飛行時間與完成空中加油的時間之和。其中,JTmin表示完成空中加油任務的最短耗時;式(16)表示除了虛擬機,每架飛機緊鄰的前序飛機有且只有一架;式(17)表示包括虛擬機在內,每架飛機緊鄰的后續飛機不多于一架(即最后著艦的飛機后續無緊鄰飛機)。

2 基于MGP的艦載機機群回收排序方法

艦載機機群回收調度從本質上而言屬于作業車間調度問題(job shop scheduling problem, JSSP),當返航艦載機數量為n時,共有n!種方案可供選擇,當艦載機數量較多時,很難采用枚舉法求得最佳的著艦方案。當前,針對JSSP的求解方法主要有啟發式算法和元啟發算法,啟發式算法通過制定啟發式優先規則可以快速生成調度方案,計算效率高,但是由于在規則制定過程中存在較大的主觀性,且算法過于貪婪,容易陷入局部最優解,導致其最終的優化效果無法保證。元啟發式算法將調度方案映射為某些特定的對象(如生物群中的個體或多維抽象空間中的微粒),并通過模擬自然界的某些過程或生物的群體行為對最優個體進行搜索,具備一定的跳出局部最優解的能力,但是在尋優過程中,存在大量的隨機搜索行為,當問題規模增大時,其搜索效率較低。

超啟發式算法的主要思想是通過某種高層管理策略對一系列底層的啟發式算法進行處理和操縱。GP算法作為超啟發式算法的一種,實際上就是通過上層的遺傳算法操作規則對底層的調度優先規則進行重新整合,以生成最優的組合優先規則,用于產生調度方案的算法。與以遺傳算法(genetic algorithm, GA)為代表的元啟發式算法相比,其給出的結果是用于求解調度問題的調度規則,而不是針對特定問題的某一調度方案。GP算法解決了純啟發式算法不具備優化功能的問題,當問題規模較大時,其在搜索空間和搜索效率方面均具備明顯優勢。

2.1 調度優先規則的選取

GP算法可以通過底層的啟發式規則不斷生成新的組合調度優先級規則,并對組合規則進行迭代優化,且調度優先規則通常可以用一個調度優先級函數來表示。因此,對調度規則的優化等同于對優先級函數的優化。在應用GP算法之前,首先需要確定底層的啟發式調度規則,針對艦載機機群的回收排序問題,本文選擇以下4種啟發式調度規則:

(1) 油少先著艦規則,相應的優先級函數為YX1=TO;

(2) 優先級高先著艦規則,相應的優先級函數為YX2=YXJ;

(3) 完整度低先著艦規則,相應的優先級函數為YX3=WZD;

(4) 與前序艦載機尾流間隔要求短的機型先著艦規則,相應的優先級函數YX4=WLJ。

由于在后續的遺傳規劃操作中需要對上述啟發式規則所對應的優先級函數進行相應的加減乘除或極值運算,為了避免優先級函數量級不同對計算結果的影響,此處對優先級函數的數值進行了歸一化處理:

(18)

2.2 編碼設計與種群初始化

與GA類似,在利用GP算法進行調度方案求解時,也需要對種群中的個體進行編碼。但有所不同的是,GP算法中的個體是一種由底層調度優先規則所構成的組合調度規則,其不同的個體可以用不同的GP樹來表示。如圖2所示,GP樹是一種由計算符節點和終端規則函數節點所組成的一種樹狀結構。圖2中,虛線圓節點表示深度為0的順序判斷編碼[25],rise(升序)表示組合優先級函數的值越大,優先級越高;fall(降序)表示組合優先級函數的值越小,優先級越高。圓節點表示計算符節點(也可稱為根節點),這里選擇+,-,×,÷,max,min這6種計算符形式。矩形節點為終端規則函數節點(也可稱為葉節點),可從第2.1節中所設計的4種歸一化優先級函數中進行選擇。

圖2 GP樹調度規則編碼結構Fig.2 GP tree scheduling rule coding structure

圖2中給出的兩個GP樹的深度均為4,即GP樹中第4層中的節點均為葉節點。在進行GP樹種群初始化時,為了保證種群的多樣性,通常不希望事先指定GP樹的具體層數和結構。因此,這里只對GP樹的深度進行限制。考慮到機群回收排序問題中終端優先級規則函數的可選數量,這里將GP樹的最大深度限制為Lmax=4,同時為了保證最終的組合調度規則中至少含有兩個終端規則函數,GP樹的最小深度Lmin=2。GP樹個體的生成過程可分為以下兩個步驟。

步驟 1確定2Lmax-1個節點的類型,首先,將第Lmax層的所有節點確定為葉節點;進一步,將剩余的節點隨機確定為根節點或葉節點,得到“滿節點數”的GP樹個體;最后,對葉節點下層所連接的節點結構予以刪除,確保葉節點上層所連接的節點全部為根節點。

重復步驟1和步驟2共Npop次,便可得到種群規模為Npop的初始GP樹種群。

2.3 調度方案生成與適應度評價

在獲得初始的GP樹種群后,需要確定種群中各個個體的適應度值,以便進行后續的遺傳操作。與傳統的遺傳算法不同,GP樹個體只對應于某種組合調度規則,而并非直接對應于某種特定的調度方案,因而在對GP樹的適應度進行計算之前應先確定GP樹規則所對應的調度方案。如圖2所示,GP樹所對應的組合調度規則可表示為

(19)

即需要根據式(19)所給出的組合調度規則生成相應的著艦回收調度方案,在介紹調度方案生成算法之前,需要引入當前安全油量著艦(current safe fuel landing, CSFL)和強制提前著艦(mandatory landing ahead, MLA)兩個判斷性條件。

(1) CSFL條件

CSFL條件是指在著艦方案設計過程中,當前序著艦序列已確定,而在選擇某架艦載機作為下一架次著艦機時,被選中的艦載機到達著艦點時的剩余油量應大于安全著艦油量Osafe。轉化為剩余油量飛行時間,可將CSFL條件表示為

DTj+WLJj,i

(20)

式中:i表示被選中的當前飛機編號;Ωzj表示已安排著艦次序的艦載機集合;Ωust表示尚未確定著艦次序的艦載機集合。

(2) MLA條件

MLA條件是指在著艦方案設計過程中,若按照一定規則選取某架艦載機j作為當前著艦機,則未安排著艦次序的艦載機i必然無法實現安全油量著艦,為避免空中加油情況的出現,在條件允許的情況下需要將i的著艦次序提前,即滿足:

DTj+WLJj,i>TOi-TOsafe,i,j∈Ωust

(21)

在滿足式(21)時,需要考慮將i的著艦次序提前。

下面借助CSFL條件和MLA條件,給出基于組合調度規則生成著艦回收排序方案的算法步驟如下。

步驟 1首先選擇虛擬機Jzj0作為著艦方案中的首架機,并設置其虛擬著艦等待時間DT0=TML-WLT0(因所有真實飛機與虛擬機之間的尾流安全間隔時間均為WLT0,所以著艦方案中在虛擬機之后的首架飛機的著艦等待時間為TML)。令待安置集合Ωust=Ωall,其中,Ωall表示全部待回收艦載機的集合;

步驟 2按照GP樹中的組合調度規則,計算集合Ωust中各架艦載機的組合優先級函數值,然后將組合優先級函數值按照[rise]或[fall]規則進行排序;

步驟 3選擇排序最靠前的艦載機作為待選著艦機Jzjud。首先,計算將Jzjud安排在當前架次是否滿足CSFL條件,若不滿足,則判定Jzjud需要進行空中加油,并將其從集合Ωust轉移到待加油集合Ωjy中,按照排序結果選擇下一位次的艦載機作為新的Jzjud。重復此操作,直至新的Jzjud滿足CSFL條件;

步驟 4將Jzjud暫定為當前架次的著艦機,判斷Ωust中的各架飛機是否滿足MLA條件。若滿足,則將相應的飛機放入到優先著艦集合Ωyx中;判斷Ωyx是否為空集,若Ωyx為空集,則將Jzjud正式確定為當前架次的著艦機Jzjc,轉至步驟6;若Ωyx不為空集,則轉至步驟5;

步驟 5將Ωyx中的艦載機按組合優先級函數值進行排序,按順序依次判斷其是否滿足CSFL條件,若不滿足則將其放入到集合Ωjy中,若滿足則將其直接確定為當前架次著艦機Jzjc;若集合Ωyx中的艦載機均不滿足安全油量著艦條件,則將Jzjud正式確定為當前架次的著艦機Jzjc;

步驟 6將當前架次的著艦機放入到著艦集合Ωzj中,并根據前一架次的著艦等待時間以及尾流間隔時間要求確定當前架次著艦機Jzjc的著艦等待時間DTc,更新Ωyx=?,更新待安置集合Ωust=Ωall-Ωjy-Ωzj;

上述著艦調度方案生成過程中,在步驟4～步驟5中引入了強制著艦規則,盡可能避免了艦載機出現空中加油的情況。為了更清楚地展現算法的邏輯結構,帶強制著艦規則的回收排序調度方案生成算法如算法1所示。

算法1 帶強制著艦規則的回收排序調度方案生成算法輸入 GP樹個體,Ωall中各架飛機的狀態信息輸出 艦載機機群回收著艦排序方案1 初始化:確定虛擬機Jzj0為首架著艦機,DT0=TML-WLT0,Ωust=Ωall。確定Ωust中所有飛機的YXiu,i=1,2,3,42 While Ωust=? then 3 根據GP樹編碼計算Ωust中個飛機的組合優先級函數,并按[rise]或[fall]規則排序,選擇序列中的首架機為Jzjud 4 While Jzjud不滿足CSFL條件 then 5 將Jzjud從Ωust轉移到集合Ωjy 6 選擇序列中下一架飛機作為Jzjud 7 end 8 for Jzji in Ωust do 9 if Jzji滿足MLA條件 then 10 將Jzji放入集合Ωyx 11 end 12 計算Ωyx中各架艦載機的組合優先級函數,并按[rise]或[fall]規則排序,得到序列XLyx 13 for Jzji in XLyx do 14 if Jzji 滿足CSFL條件 then 15 確定Jzji為當前架次著艦機Jzjc 16 else 17 將Jzji放入集合Ωjy 18 end 19 end 20 if Ωyx中沒有艦載機滿足CSFL條件 THEN 21 將Jzjud作為當前架次的著艦機Jzjc 22 end 23 end 24 將當前架次的著艦機Jzjc放入集合Ωzj,更新著艦序列XLzj=[XLzj;Jzjc] 25 更新Ωyx=?,Ωust=Ωall-Ωjy-Ωzj26 end27 將Ωjy中的艦載機的油量更新為maxj=1,2,…,nTOj28 計算Ωjy中各架艦載機的組合優先級函數,并按[rise]或[fall]規則排序,得到序列XLjy29 更新XLzj=[XLzj;XLjy]

2.4 種群的多樣性操作

與普通的GA類似,在GP算法中,為了保證種群的多樣性,對GP樹種群引入了遺傳、交叉和變異3種形式的遺傳操作,遺傳操作主要是為了選出合適的GP樹個體作為父代進行遺傳操作。此處,為了選擇適應度值相對較優的個體作為父代進行遺傳操作,采用二元錦標賽模式對父代個體進行選取,即“兩兩比較,擇優選擇”。交叉操作即選擇兩個不同的父代個體,隨機選擇其中的某一節點連同其全部的子節點進行交換,從而得到新的子代個體,如圖3所示。

圖3 GP樹交叉操作示意圖Fig.3 Schematic diagram of GP tree crossing operation

本文選取3種變異操作模式,如圖4所示。第1種為刪除子樹操作,選擇GP樹中的某一根節點及其全部子節點進行刪除,并隨機生成一個葉節點用于代替原根節點的位置;第2種變異操作為節點突變,選擇GP樹中的任意節點,對這一節點中的取值進行修改,而節點類型不變;第3種操作為隨機子樹替代,任選一個節點,用隨機生成子樹代替該節點,從而得到新的子代個體。

圖4 GP樹變異操作示意圖Fig.4 GP tree mutation operation schematic diagram

3種不同的變異方式可以通過對其設置相應的發生概率予以控制,進一步在進化的過程中引入精英個體保留策略,以保證適應度最優的GP樹個體可以保留到下一代種群中。圖5給出了本節所建立的基于MGP的艦載機機群回收排序算法的框架圖。

圖5 基于MGP的艦載機機群回收排序調度算法框架Fig.5 Framework for carrier aircraft fleet recovery sequencing scheduling algorithm based on MGP

3 機群回收仿真分析與對比

3.1 機群回收著艦仿真條件設置

在仿真過程中,設置MGP算法中的種群數量為100,最大迭代次數為80,個體變異概率為0.2,頂點變異概率為0.5,假設待回收機群共有30架飛機,各架飛機的初始狀態信息如表2(部分信息參考文獻[8])所示。

表2 待回收機群的初始狀態信息Table 2 Initial status information of the carrier aircraft fleet to be recovered

在仿真過程中,假設S、M、L、N型飛機的油耗速率分別為0.6 L/s、0.9 L/s、1.2 L/s、0.6 L/s,在仿真過程中有關的時間常數項取值如表3所示,不同機型間的尾流安全間隔時間在表1中已經給出。

表3 仿真中時間常數變量的取值Table 3 Value of time constant variable used in simulation

3.2 仿真結果分析與對比

利用本文所設計的MGP算法對表2中需要回收的機群進行著艦排序,所得到的排序結果如表4所示。從表4可以看出,其著艦安全時間裕度均大于0 s,即在此著艦方案中需要進行空中加油的艦載機數量為0架。最終所得到的評價指標函數值為19 570 s,著艦回收任務的完成時間為3 299 s,算法的計算求解時間為16.4 s。

表4 著艦排序方案結果Table 4 Landing sequencing scheme results

續表4Continued Table 4

為了展示著艦方案中不同時刻各艦載機的飛行位置,圖6給出了表4中艦載機著艦調度方案所對應的時序甘特圖。其中,不同顏色的圖例所對應的字母與圖1中的字母含義相同,用以表示艦載機在返航航線中所處的位置。

圖6 調度方案中各艦載機的飛行狀態甘特圖Fig.6 Gantt chart of flight status of each carrier aircraft in the scheduling scheme

作為比較,利用普通的GP算法、GA對上述著艦回收案例進行優化調度,所得的迭代收斂曲線如圖7所示。

圖7 不同算法的迭代收斂曲線Fig.7 Iterative convergence curves of different algorithms

從圖7可以分析出,無論是算法的收斂速度還是算法的優化效果,本文所設計的MGP算法都是3種方法中最優的。這主要得益于MGP算法引入了強制優先著艦規則,使得油量不足的艦載機可以不受組合優先級規則的限制而實現提前著艦。引入強制優先著艦規則后,在相同的情況下,可以降低著艦方案中艦載機出現空中加油的可能性,避免了部分組合規則因出現空中加油而獲得較大的評價指標函數,從而被過早淘汰的情況,變相地增加了種群的多樣性,因此其優化效果相對于普通的GP算法有較為明顯的改善。另一方面,在此案例中,機群的回收數量較多(30架),在利用GA進行方案優化時,其搜索空間的規模為30!,因而搜索效率較低,且極易陷入局部最優,從而影響了最終的優化效果。

圖8中給出了利用GP算法、GA進行調度優化時所得到的著艦方案甘特圖,兩種算法的計算求解時間分別為12.6 s和23.2 s。可見在算法的求解速度方面,GP算法的求解耗時最短,MGP算法的求解時間較GP算法長3.8 s,但這一時間差距相較于著艦回收任務的總時長(55 min)而言,可忽略不計;GA的求解時間最長,其計算耗時約為GP算法的兩倍。

圖8 不同調度方案中艦載機的飛行狀態甘特圖Fig.8 Gantt chart of aircraft flight status in the different scheduling schemes

為了進一步驗證本文所設計的MGA算法的有效性,此處選取GP算法、GA以及油少先著艦(less fuel first served, LFFS)啟發式算法和優先級高先著艦(higher priority first served, HPFS)啟發式算法作為對比。構建機群規模分別為15架、25架、35架、45架的回收案例,在每種機群規模下各進行30次仿真實驗,將不同機群規模條件下的實驗結果取平均值,獲得的調度方案指標統計結果如表5所示,加粗字體的數值表示各組仿真結果中的最優值。

表5 不同機群規模條件下的算法優化結果統計結果Table 5 Algoribhm optimization statistic results under different aircraft fleet sizes

從表5可以看出,在4種機群規模條件下,本文所設計的MGP算法的調度結果均為最優。利用MGP算法和GP算法求解所得的著艦回收方案,其任務完成時間較另外3種算法而言更短。當機群數量較少時,GA的結果要優于純啟發式算法,但是隨著機群規模的增加,GA的相對優化效果逐漸變差,且當艦載機機群規模增加到45架時,利用GA所獲得的著艦方案中出現了空中加油的情況,且從適應度函數值來看,此時GA的優化效果差于LFFS算法。這是由于當機群規模增加時,GA算法的解空間將按照階乘的方式急劇增大,其尋優性能相應變差。在全部的5種算法中,HPFS算法所得的著艦方案效果最差,且方案中出現空中加油的架次最多。HPFS算法和LFFS算法均屬于啟發式算法,其調度方案的合理性完全依賴于主觀確定的啟發式規則,且不具備迭代優化能力。但相對而言,LFFS算法可以保證著艦方案中的空中加油架次盡可能地少,從而使適應度函數中的懲罰項獲得較小的值。除了LFFS算法,采用MGP算法和GP算法在4種不同機群規模的情況下所獲得的著艦方案均不需要進行空中加油。

表5還給出了各種算法單次迭代的計算耗時,即算法的求解總耗時除以算法的迭代次數所得到的結果。從表5可以看出,HPFS算法和LFFS算法作為純啟發式算法,求解速度最快,單次迭代的計算耗時較另外3種算法小2個數量級,且由于HPFS算法和LFFS算法不需要迭代優化,因而其單次迭代的計算耗時即為算法求解的總耗時。在所有的算法當中,GA的單次迭代求解耗時最長,MGP算法的單次迭代求解耗時略長于GP算法,但MGP算法與GP算法的單次迭代求解耗時相差不超過15%。

3.3 逃逸復飛對著艦方案的影響分析

本文所設計的MGP著艦排序方法可以給出經過優化后的著艦方案,但在實際情況中,艦載機著艦存在一定的失敗概率。艦載機著艦失敗后需要重新進行著艦,因此必須有相應的著艦失敗應對策略。本文采用著艦失敗的艦載機優先著艦的策略,即當出現逃逸或復飛的情況時,著艦失敗的艦載機立即轉入復飛航線,并在當前時刻已經經過馬歇爾點的飛機全部完成著艦后再進行著艦,而未經過馬歇爾點的艦載機利用其下層等待航線進行盤旋等待,待與二次著艦機的尾流間隔滿足要求后再進行著艦。本文將最短復飛航線的飛行時間取為417 s。

在表4中的原有著艦方案的基礎上,需考慮艦載機出現逃逸復飛時對著艦任務完成時間以及評價指標函數所產生的影響。此處在原方案中隨機選擇不同的艦載機,假設其出現了逃逸或復飛的情況,此時經過應急調整后的著艦方案所對應的任務完成時間以及評價指標函數如表6所示。由表6可見,與原著艦方案相比,當出現一架次艦載機著艦失敗時,著艦任務的完成時間平均增加了139.3 s,指標評價函數平均增加了595.6 s,而當出現兩架次艦載機著艦失敗時,著艦任務的完成時間平均增加了273.0 s,指標評價函數平均增加了1 071.4 s。由此可見,提高艦載機的著艦成功率對于縮短回收任務完成時間以及增強回收任務效能而言有著重要意義。

表6 復飛逃逸對著艦排序方案的影響Table 6 Influence of wave off and escape on the landing sequencing scheme

4 結 論

本文首先對航母甲板環境以及艦載機的返航回收進場模式進行了分析,建立了基于加權等待時間的回收排序評價指標模型,并根據艦載機回收著艦問題中的各項約束,建立了考慮空中加油條件下的艦載機著艦回收排序調度問題模型。進一步,借助于超啟發式算法思想,設計了一種基于MGP算法的艦載機機群回收排序調度方法,最后通過回收仿真算例驗證了本文中模型和算法的有效性。本文的研究內容以及方法的優勢主要體現在:

(1) 在著艦回收調度模型中充分考慮了空中加油對著艦方案的影響,并給出了加油返航機的著艦回收方案,這使得調度模型對于返航艦載機的油量限制大大減小,提高了文中所建模型的適用范圍。

(2) 通過GP算法進行組合調度規則優化,該方法與傳統的遺傳算法相比,最大的優勢是其在機群規模增大的情況下可以保證解空間的搜索范圍不變,因而具有較高的算法搜索效率。

(3) 在傳統的GP算法中引入了強制優先著艦規則,盡可能地避免了著艦方案中出現空中加油的情況,同時也避免了部分組合規則因出現空中加油而獲得較大的評價指標函數,從而被過早淘汰的情況,變相地增加了種群的多樣性,這也使得MGP算法相較于GP算法而言具有更好的優化效果。