基于并行遺傳算法的艦載機再次出動作業調度

范加利,朱興動,高 偉,王 正

(1.海軍航空大學 青島校區，山東 青島 266041；2.海軍航空大學，山東 煙臺 265200)

根據任務需求，航母上艦載機的出動方式通常按照單波次大批量起降、多波次適當批量起降等多種方式組織實施。為高效使用飛行甲板資源，航母通常按一定時間周期進行作業[1]。在艦載機和航母設計定型后，如何優化配置和合理安排批次艦載機的再次出動保障工作對于提高航母艦載機出動強度的提高具有非常重要的意義。

受作業完成時間的不確定性、艦載機及保障裝設備故障的隨機性、作業環節的多態性等因素的影響，涉及多架艦載機、多種保障資源的艦載機再次出動作業的調度問題屬于典型的動態調度問題。近年來，國內學者在該領域進行了大量的研究工作，針對該問題常用的方法是建模仿真方法[2]，最優化方法[3-5]，以及基于專家方案的逆向強化學習方法等[6]。但多數文獻中仍以靜態調度為研究基礎，通過提高調度結果的魯棒性來保證和自適應性來增強調度系統、算法對動態、隨機環境的響應能力，避免頻繁重調度。在眾多研究文獻中，對甲板站位保障能力和艦載機轉運路徑約束的考慮較少，而實際的甲板作業環境下，必須要考慮站位能力約束和轉運路徑約束。

針對復雜的艦載機艦面航空保障作業調度問題，本文重點研究雙周期出動模式下艦載機再次出動準備的調度，分析再次出動準備的作業過程以及約束條件，建立了艦載機再次出動準備的優調度模型，并采用一種島式并行遺傳算法求解調度模型，最后以庫茲涅佐夫航母上8機雙周期再次出動準備作業為例進行了驗證。

1 艦載機甲板作業調度模型

1.1 艦載機甲板作業過程描述

艦載機在飛行甲板上的相關作業包括機務保障與勤務保障作業，機務保障作業主要機務人員對艦載機及其發動機實施各種不要的檢查與修理，勤務保障主要指為艦載機提供電源、慣性導航基準信號源、氣源、油料、彈藥等各種物資，勤務保障主要由母艦所屬人員完成。所有保障工作必須在航母飛行甲板上的特定站位上完成。以某型俄制航母為例，其飛行甲板布局如圖1所示。

圖1 某航母甲板停機區域分布示意圖

圖1中過渡區、停機區、暖機區均設置有多個艦載機站位，各停機區域均設有類型和數量不等的固定式勤務保障裝置，如加油站、供電口蓋、氣源口蓋、導航對準口蓋等。除暖機區和起飛位上的艦載機可實施起飛前的暖機作業外，其他區域站位上的艦載機均不能起動發動機。受甲板區域大小限制，過渡區與起飛區存在重疊，著艦區與暖機區存在部分重疊。由于重疊區域存在，艦載機甲板作業時，要求任一時刻起飛與著艦不能同時進行，且著艦作業時，暖機區II中停放的艦載機必須轉運至其他位置，并清空著艦區域，起飛作業時，除起飛位上的艦載機，其他待機區的艦載機必須轉運至其他位置。

飛行甲板運轉過程中，艦載機從暖機區的停機位按一定順序滑行至起飛位起飛，位于停機區停機位上的艦載機則需滑行至起飛位或暖機區停機位進行暖機后方可起飛。著艦的艦載機在引導員引導下分別滑行至待機區和暖機區的空閑停機位停放，并接受再次出動準備，等待下一次飛行。艦載機再次出動準備的甲板作業過程如圖2所示。

圖2 艦載機再次出動準備作業時序框圖

圖2中作業集TS1中的加油、掛彈和牽引至暖機位作業的執行順序可任意調換，但受技術和管理性約束，對于某一架飛機這3項作業不能同時進行；作業集TS2中的慣導對準、暖機、滑行、起飛任務必須依次執行；再次出動機務檢修(飛機后的檢修、視情添加輔助油料、充氧充氮等)作業可與作業集TS1和TS2中的部分作業并行執行。作業集中有些需獨占資源、有些需特定資源有些可認為不占資源。

多架艦載機在實施再次出動準備作業過程中，主要存在以下約束：

1)作業順序約束。波次出動艦載機的再次出動保障作業順序約束如圖2所示。其中作業集TS1必須先于作業集TS2實施。

2)甲板保障設備/組約束。甲板保障設備包括固定式和移動式兩種，保障類別包括油、氣、電等。固定式保障設備受管線長度限制，通常只能保障就近的若干停機位，如圖1中的加油站。移動式保障設備包括牽引車、電源車等，受空間資源限制，配置的數量受限。保障組主要包括機務保障組、勤務彈藥保障組，機務保障組數量通常不存在約束，彈藥保障組受艦上編制和掛彈車數量的制約，其配置數量也受限。

3)空間站位約束。如圖1所描述，由于部分區域重疊，使得甲板作業過程中應盡量不占用著艦區，以備艦載機緊急著艦，且同一時刻，只允許一架艦載機起飛。處于停機區和待機區的艦載機不能實施暖機，因此，必須轉運至暖機位進行暖機及其相關保障作業。此外，艦載機轉運作業受空間避免限制，如過渡區的艦載機應從艦艏位置逆序往暖機位轉運。

4)供給資源能力限制。受母艦航空保障裝備技術水平限制，勤務保障資源的油、氣、電供應量存在上限，如同一時刻，甲板上進行加油作業的艦載機數量受限。

1.2 調度模型建立

調度模型的目標函數取為最小化本波次艦載機的再次出動準備時間：

F=minCmax

(1)

約束條件為：

(2)

(3)

(4)

(5)

(6)

sti1jzy≤sti2jzy，?ZWi1,i2∈Hs，Xzwi1≥Xzwi2

(7)

式(2)和式(3)聯合確保每一作業必須只被每一架飛機啟動一次，帶有僅單一資源的特定性任務需要額外執行要求的作業通過式(3)強調。不等式(4)確保作業期間的時序優先級條件，該不等式主要針對作業集TS2。不等式(5)確保僅有有限數量的甲板資源被用于完成不定資源約束型作業，不等式(6)確保對于每一架飛機沒有兩個可以導致安全問題的作業同時進行。不等式(7)表示調運可行路徑約束通，其中ZWi1表示艦載機在甲板的停機站位，Hs表示艦艏區域站位集合；Xzwp表示站位的x坐標，jzy表示轉運作業。

2 調度模型求解算法

基于上述模型與分析，艦載機甲板作業是多架艦載機各作業工序在甲板上各種資源約束下的時序安排和資源分配問題。該問題屬于一類特殊的資源受限多項目調度問題(Resource-Constrained(Multi-)Project Scheduling Problem，RC(M)PSP)。國內外學者對該類問題進行了大量的研究工作，研究熱點是多模式多項目模型求解，以及各種應用場景[7-9]。在求解算法方面，該類問題多采用優先級規則和智能啟發式算法求解。鑒于遺傳算法在該求解該類問題方面的研究成果較多，本文采用一種改進的島式并行遺傳算法(IMGA)框架，在局部采用禁忌搜索進行強化搜索。采用矩陣形式染色體結構，采用串行調度生成機制進行解碼。

2.1 算法總體框架

并行遺傳算法比普通遺傳算法有全局搜索能力強的優點。目前，并行GA算法分為3種模型[10,11]：主-從式，粗細粒度式和島式模型。在第1種模式中，有一個初始種群，計算由多個處理器執行；在第2種模式中，也是產生一個初始種群，但每個個體分配給一個處理器進行運算，選擇和復制僅限于鄰居之間；在第3種模式中，整個初始種群被分成多個獨立的孤島(子種群)，并被分配給各個處理器，在各個處理器中使用其自己的進化過程，探查各自的搜索空間，偶爾通過遷移機制交換信息，該模式也可在單處理器上以偽并行模式運行。本文采用一種混合島模型遺傳算法求解該問題，總體框圖如圖3。

為改進算法效率，算法中加入本質自適應調整階段，該階段具有在分散和強化搜索過程中的平衡能力。在自調整階段最好的個體被用于禁忌搜索，最差的個體被用于執行全局搜索。

算法具體流程如下：

步驟1：輸入待保障的艦載機數量，各艦載機需要完成的作業集，甲板環境參數及資源約束參數，并將艦載機與甲板站位相關聯，標明艦載機在站位上的停放方向

步驟2：采用文獻[2]中的矩陣形編碼方式，每一行代表一架艦載機的作業工序，從艦艏區站位上的艦載機從前往后依次排序。采用隨機方式產生島嶼的各初始種群。

步驟3：各島內進行基本GA算法進化，在進化過程中，采用輪盤賭方法選擇個體，采用基于排序的交叉操作。為避免早熟，文中的自適應策略是對最優個體實施禁忌搜索，對最差個體實施搜索。全局搜索中通過組合交換、插入和逆序算子對個體實施變異。對違反約束的不可行解采用適應度中加入罰函數的辦法進行處理。

步驟4：各島進化完成后，采用遷移策略生成新的初始種群，進一步進化，直到滿足終止條件。

2.2 種群遷移策略

種群遷移策略在并行GA中發揮重要作用，其控制了島間信息交互過程。遷移策略的工作機制主要依賴于4個因素：通訊拓撲、遷移率、選擇方法和代替方法。

圖3 島式并行遺傳算法總體框圖

通訊拓撲結構規范了島間遷移路徑。通常，公共結構是環形、星形、網形、非限制型(完全網)，以及線性矩陣形。通訊代價主要取決于網絡直徑。為了獲得島間直接低代價遷移，我們采用非限制性結構，如圖4所示。

圖4 島間通訊拓撲

遷移率規范了遷移數量和遷移數據。為了獲得較好的收斂性，遷移應采用實時模式，通常是任何一個島收斂時，即發生遷移。當任何一個島的連續5代后代無任何改進時，即讓遷移在島間發生。

為了允許島間分享它們關于有希望出現最優解的區域的信息，輪盤賭方法被用作遷移選擇方法。即個體xj被選擇的概率由下式決定：

(8)

遷移替代方法決定哪一個本地個體將被從他們所在島的種群中移除，為遷入個體騰出空間。在此選擇種群中最差的個體進行替代。

2.3 編碼與解碼

染色體采用矩陣形編碼在處理該調度問題時有直觀性，且能很好地反映工序約束關系。本文的染色體行為矩陣A所示。

(9)

其中aij取[0,J]上的整數，代表艦載機的作業集。0為空工序，矩陣前半部分各元素為0～3之間的整數，代表加油、掛彈和轉運；矩陣后半部分各元素由于表示任務集TS2中的作業。這樣編碼的優勢是在進行進化過程中只需操作前半部分染色體，從而縮小解的搜索空間。

解碼采用串行進度生成機制(SGS)。依次取矩陣A的各列，判斷是否滿足資源和空間約束，若滿足則將該架機上一作業結束時間作為該工序開始，若存在資源或空間約束，則計算資源釋放等待時間。以掛彈作業為例，算法如下：

1：functionCaldt()

2：記錄沒架飛機第j到作業工序為掛彈作業的飛機數為tgd，自增

3：取當前艦載機作業工序j的上一工序結束時間→TempJ

4：若當前為所有飛機的第一道作業工序，且tdg≤NGD(掛彈資源約束)，則dt=0，否則dt=tgdd，tgdd為d區域的預計掛彈作業時間

5：當前已安排掛彈作業的飛機數量ngdTask，并將其預計結束時間按從小到大排序

6：若當前非第一道作業工序，且ngdTask

3 算例仿真

圖5 8機再次出動準備調度時序優化結果圖

從仿真結果可以看出：并行GA算法可以獲得較接近最優解的調度結果。調度模型輸出的作業邏輯符合實際甲板作業環境，方案可行。

4 結論

在考慮甲板站位能力和移動路徑約束的前提下，建立了適用于艦載機甲板作業時序安排調度模型，設計了一種島式并行GA算法對模型求解。在并行框架下，引入自調整策略，增加搜索過程中的分散性與集中性。建立的調度模型符合實際航母甲板作業環境，采用的算法能夠在可接受時間內獲得近似最優解。