基于學徒制算法的航母艦載機保障作業調度

吳靳，戴明強，王俊杰，余珊珊，余明暉

1 海軍工程大學 電子工程學院, 湖北 武漢 430033

2 海軍工程大學 基礎部, 湖北 武漢 430033

3 華中科技大學 人工智能與自動化學院, 湖北 武漢 430074

0 引 言

艦載機作為航空母艦（以下簡稱“航母”）上最重要的戰力組成部分，其出動架次率是評價航母戰斗力的重要指標之一。然而，因航母甲板的空間有限，航行環境具有不確定性，致使保障作業調度效率受到限制[1]。艦載機保障調度問題的優化目標是最小化一波次出動艦載機的最大保障完成時間。

以往，保障作業調度計劃都是由調度工作人員根據軍事演習或是實戰經驗制定的[2]。然而，隨著計算機技術的發展，科研人員為了更加有效地求解保障調度問題，已嘗試過采用多種智能搜索算法，例如遺傳算法、禁忌搜索算法、貪婪算法及其衍生算法等。

針對航母上艦載機調度這一特殊場景，主要從如下2 個方面開展研究：一是如何對一波次出動艦載機進行保障戰位分配；二是如何安排一波次出動艦載機的保障作業調度計劃，從而令一波次出動艦載機的最大保障完成時間最短。針對艦載機保障戰位分配的 問題，現有研究已涉及艦載機飛行甲板布列[3-4]以及陸基機位分配[5-6]等領域。針對保障作業調度問題，國內外學者也運用數學規劃[7-8]、機器學習[9-11]、模擬仿真[12-13]等技術解決了一些難點。這些方法的使用在一定程度上縮短了艦載機的保障完成時間，提高了保障效率。但是，其基本流程大多是根據各項約束去建模，然后在可行解集合中搜索出問題的最優解，一旦問題的規模變大，全局搜索需要的時間就會成倍增長，且不一定能夠找到最優解。

因此，為了解決大規模的艦載機保障調度問題，并優化求解速度，本文將在現有國內外艦載機保障作業相關研究的基礎上，以一波次出動艦載機最大保障完成時間為優化目標，將機器學習應用于專家示例。然后，再將調度人員制定的保障調度方案作為專家示例進行學習，學習他們在做每一步決策時的思路，通過分析專家示例，構造基于成對比較模型的輸入樣本集，選取最優的分類算法來訓練分類器，在此基礎上構造學徒制調度算法。最后，使用學徒制算法和遺傳算法分別針對新實例問題制定保障作業調度方案，以驗證學徒制算法與傳統算法效果。

1 艦載機保障調度模型建立

1.1 保障戰位分配

新一代的航母大多選擇采用“一站式”保障模式[14]。對于這類采用“一站式”保障的航母，其加油站的位置是固定的，能夠使用該加油站進行加油的機位分布在一個以該加油站為頂點的扇形區域內，因此會出現多個加油站可加油的機位重疊現象，即一個機位可以使用2 個加油站中的任意一個完成加油任務。加油站的數量和位置約束以及其他保障資源約束，會使得艦載機保障戰位分配的結果直接影響到艦載機保障的完成時間。

本文將以“福特”級航母為研究背景，航母甲板平面示意圖如圖1 所示。這里將對所求解的問題進行簡化，僅考慮單一艦載機機種的情況。假設甲板右側有12 個艦載機機位（按逆時針順序，將這些機位依次標號為S1～S12戰位），一般情況下，這12 個機位都停放著艦載機。當接收到一波次出動4 架艦載機的任務時，會從12 架艦載機中任意出動4 架，但因保障資源的限制，為了盡可能縮短保障完成時間，這4 架艦載機的選取需要根據保障任務提前予以預測。本文將從12 架艦載機中選取4 架出動的問題進行轉化，即轉化為從12 個機位中選出4 個，然后將待出動的4 架艦載機停放到這4 個被選中的機位上，最后，在確定保障戰位的基礎上制定最佳保障作業調度方案，其中4 個保障戰位的選擇即為艦載機的保障戰位分配問題。

圖1 “福特”級航母甲板平面示意圖Fig. 1 Deck layout of Ford class aircraft carrier

1.2 保障作業調度

如圖2 所示，基于“福特”級航母的艦載機保障流程，每架艦載機在滑出機位前都要完成圖2中所示的全部保障任務。本文中的保障任務大致分以下為3 類：

圖2 艦載機保障任務流程圖Fig. 2 Flow chart of carrier-based aircraft support tasks

1） 并行任務，即一架艦載機在同一時間可以同時執行的任務。本文保障任務中的并行任務對包括供電和通風、充氧加油、軍檢掛彈、特設外觀檢查、航電外觀檢查以及機械外觀檢查。

2） 串行任務，指執行順序不可交換且不能同時執行的任務。這些任務可以看做是擁有不同的優先級別，例如供電與通風的任務優先級最高，需要最先執行，檢查驗收任務的優先級最低，需要最后執行。

3） 順序可交換任務，即在一架艦載機的保障作業中，執行順序可以交換但不能同時執行的任務。如圖2 所示，虛線連接的充氧和加油這2 個任務的執行順序可以交換，但若是同時加油、充氧可能會造成事故，因此，加油和充氧這2 個任務一定有執行的先后順序。

1.3 保障資源約束分析

影響一波次出動艦載機保障完成時間的因素有很多，其中最重要的是保障資源約束，包括保障班組的數量以及不同班組的保障任務完成時間。本文保障作業中的保障資源約束如表1 所示。

表1 保障班組任務執行時間表Table 1 Task execution schedule of the supporting teams

1.1 節中介紹的加油站的位置約束可以描述為如表2 所示，表2 中加油站的加油保障任務由表1 中的9～12 號班組完成。其中，S4機位可使用9 號或10 號加油站，S7機位可使用10 號或11 號加油站，S10機位可使用11 號或12 號加油站進行加油任務，其他機位固定，只能使用一個加油站。

表2 加油站位置約束Table 2 Constraint of gas station location

1.4 保障調度模型建立

本文研究問題的數學模型建立如下。

1） 目標函數。最小化一波次出動艦載機的保障作業完成時間，定義為：

式中：fj為 保障艦載機j的完成時間；J為艦載機（保障戰位）集合目標函數；目標函數F指最后完成的艦載機保障作業時間最短，從而實現一波次保障完成時間最短。

2） 約束條件。

（1） 對艦載機j的保障作業完成時間是其全部保障任務完成時間中的最大值。

式中：fi j為 艦載機（保障戰位）j的保障任務i的完成時間；Oj為 艦載機j包含的保障任務編號集合。

（2） 每架艦載機的所有保障任務都只需要一個保障班組完成。

式中：mi為 執行保障任務i的保障班組編號；Mi為能夠執行保障任務i的保障班組編號集合；為描述保障班組和保障任務對應關系的二元決策變量，如果將保障戰位j分配給保障班組mi執行，則結果為1，否則為0。

（3） 保障班組在戰位之間的移動時間與戰位間隔成正比。

式 中：pj j′為 保 障 班 組mi完 成 保 障 艦 載 機j的 任 務后，轉移到艦載機j′的時間；常數c為保障班組在相鄰2 個戰位間移動的時間。

（4） 在任意時刻每個保障班組只能執行1 架艦載機的1 項保障任務。

（5） 保障班組mi并非一直處于執行任務的狀態，需要考慮其在戰位間的移動時間。

（6） 每個保障任務都有一定的時長，保障任務在執行的過程中不能被打斷。

（7） 開始執行一項保障任務前，要確保其所有緊前任務均已完成。這是因為保障流程中存在并行任務，某項任務可能會有多個緊前任務，所以選取緊前任務集合中完成時間最長的作為標準。

式中，Pi j為保障任務Oi j的緊前任務集合，其中Oi j為艦載機j的保障任務i。

（8） 艦載機保障流程中存在保障順序可以交換的保障任務，但是這些任務不能同時執行。

式中：Fi為可保障任務i順序可交換的保障任務集合；Yii′j為描述艦載機保障任務順序的二元決策變量，如果保障艦載機j的任務i先 于任務i′執行，則結果為1，否則為0。

（9） 加油站條件約束，即每個戰位執行加油保障時，只需一個加油站供油。

式中：Gx為描述編號為x的加油站使用情況的二元決策變量；Si為保障戰位編號；S為保障戰位集合。

2 專家示例樣本集及分類器構造

2.1 基于成對比較模型構造的樣本集

本文中用于解決保障戰位分配和保障作業調度問題的方法，受益于Gombolay 等[9-10]基于VMPTR提出的學徒制算法，該算法旨在學習專家所做的示例，就像學徒模仿專家行為一樣。目前，向專家示例學習（learning from human demonstrations，LFD）[15-16]是機器學習領域的一大熱門。同時，本文還從Page 等[17]提出的網頁排序算法中總結出了成對比較模型，并將其應用于學徒制算法中。使用已執行任務與未執行任務組成的成對比較模型構造樣本集，同時使用該樣本集訓練分類器，最終建立學徒制算法，進而求出調度問題的最優解。

假設給定的專家示例是問題的最優解，對于每個專家示例，可以構造一個時序的狀態觀測集Ω={Ω1，Ω2，···，Ωs}。 通過觀測集 Ω可以很容易地得出，在狀態觀測 Ωm中 ，對于AgentAi（即保障班組i）來說，最優的待執行任務即為 τi，但卻無法得知任務集中各任務間的關系。由此，本文通過將狀態觀測 Ωm中 選定執行的 τi與任務集中剩下的所有未執行任務進行兩兩對比來構造樣本集。

從給定的專家示例中選取全部的任務構成任務集 τ(τi∈τ)， 任務集中的每個任務 τi都有一個描述任務特征的實值特征向量 γτi，其由多個與調度問題相關的特征組成。例如，任務的截止時間、最早可以開始執行任務的時間以及任務持續時間等，根據調度問題的不同，這些特征的選取也不同?？傊?，被選出來的特征應該是最能夠表現出任務重要程度的。

狀態觀測 Ωm由以下2部分組合而成：1）描述各任務狀態的特征向量γτ={γτ1,γτ2,···,γτn}；2）專家示例中ti時 刻執行的任務 τi（包括Agent 空閑時的 τ0） 。在狀態觀測 Ωm中，將專家示例中已經執行的任務 τi作為模本，將剩下的所有未執行的任務τj依次與 τi進行比較，從而獲得相關模型的參數以及用來訓練模型的樣本集。

對于將選中的任務 τi與 未選中的任務 τj進行成對比較的方法，其旨在向專家示例學習并通過分析任務狀態，以此確定下一個待執行任務的策略，最終通過迭代得到一個完整的調度計劃。為達此目的，首先將狀態觀測 Ωm轉換成一個由選中任務 τi與 未選中任務 τj進行對比得到的新觀測，如式（14）和式（15）所示。式（14）為每個狀態觀測構造了一個正例樣本，其中包括輸入特征向量和 一個正標簽=1， 輸入特征向量的每個元素由描述選中任務 τi狀態的 γτi和描述未選中任務 τj狀態的 γτj相減得到。式（15）為每個狀態觀測構造了一個負例樣本，由輸入特征向量和負標簽=0組合而成，其中輸入特征向量由 γτj與 γτi相減得到。

考慮到不同問題的環境因素對調度計劃的影響，引入了描述環境特征的向量 δτ。 由于 δτ對同一問題下的每個任務都是一樣的，如果將 δτ放入γτ中 ，在構造樣本集時， γτi與 γτj相減就互相抵消了，因此在輸入特征向量中單獨加入了 δτ，如式（14）和式（15）所示。

得到t時刻應進行保障作業的戰位后，需將此戰位負責的任務分配給特定的保障班組。同時，還需預測在t時刻保障班組AgentAi應執行選出的任務，還是執行任務 τ0（ 空任務），即Ai空閑。式（16）和式（17）提供了此分類器的訓練樣本集。輸入的特征變量act由環境特征向量 δτ和描述選中任務τi的 狀 態 向 量 γτi構 成。i為 樣 本 標 簽，AgentAi執行選出的任務 τ*i時，=1； AgentAi執行空任務τ0時 ，=0。

2.2 艦載機保障調度問題特征選取

Cheng 等[18]和 Raghavan 等[19]針對利用專家判斷方式選取特征進行過研究，本文也將采用類似方式。

圖3 所示為專家示例中的保障作業調度甘特圖。在該示例中，4 架艦載機均為同一類型，也即保障作業流程相同，保障戰位分配結果分別為S4，S7，S10和S11，最長保障完成時間為42 min，保障作業流程如圖2 所示。圖3 中，矩形內的標簽分別表示艦載機編號和保障工序編號，圖中灰色部分表示保障班組在戰位之間的移動時間（后文同此）。

圖3 專家示例中保障作業調度甘特圖Fig. 3 Gantt chart of support task scheduling in expert demonstrations

表3 和表4 所示均為根據專家示例中保障作業調度方案列舉的特征值。其中，表3 所示為t=0時 刻的環境特征，表4 所示為t=0時刻Agent 1選擇執行1 號戰位（S4）的任務特征，此時1 號戰位即為被選中的任務 τi。

表3 t=0 時刻的環境特征Table 3 Environmental features at t=0

表4 t=0 時刻Agent 1 選擇執行1 號戰位（S4）任務的特征Table 4 Features of Agent 1 chooses to execute task of 1# action station (S4) at t=0

2.3 分類器訓練

采用分類器算法學習專家在保障戰位分配、作業分配等方面的經驗。本文將使用決策樹（DT）、K-近鄰（KNN）、支持向量機-徑向基函數（SVM-RBF）、邏輯回歸（LR）、樸素貝葉斯（NB）以及隨機猜測（RG）這6 種算法來分別訓練用于艦載機戰位分配的分類器fpriority_site(τi,τj)、保障作業分配的分類器fpriority_schedule(τi,τj)和判斷任務能否執行的分類器fact(τi)。 對于分類器fpriority_site(τi,τj)，通過已有的專家示例構造了4930條樣本作為其樣本集，分類器fpriority_schedule(τi,τj)和fact(τi)的樣本集中包含的樣本數量分別為3 000 和1 500。為了得到穩定、可靠的分類器模型，本文使用樣本集中85%的樣本作為訓練集，剩余的15%作為測試集對模型進行了評估。

對于分類器的選取，采用靈敏度（又稱“真陽性率”）和特異度（又稱“真陰性率”）這2 個指標進行評估，如圖4 和圖5 所示。最終，選擇SVMRBF 算法和DT 算法分別訓練出了保障戰位分配分類器及保障任務分配分類器。

圖4 使用不同機器學習算法訓練的3 個分類器模型的靈敏度Fig. 4 Sensitivity of three classifier models trained by different machine learning algorithms

圖5 使用不同機器學習算法訓練的3 個分類器模型的特異度Fig. 5 Speifiity of three classifier models trained by different machine learning algorithms

3 基于學徒制艦載機保障調度算法設計

首先，分析已有的專家示例，將t時刻AgentAi選擇執行的任務 τi與剩余未執行的任務 τj兩兩對比，獲得學徒制調度算法的分類器樣本集；然后，使用機器學習算法訓練分類器。有關樣本集和分類器的構造上節已詳細介紹。

使用學徒制調度算法解決新問題的基本原理如下：首先，在新問題的任務集τ （ 含有n個任務）中隨機選取一個任務 τi作 為AgentAi下一步要執行的任務，剩余的任務依次作為 τj，將 τi和 τj兩兩組合作為分類器fpriority(τi,τj)∈{0,1}的輸入，該過程如圖6 所示；然后，將得到的n-1個結果求和并儲存到數組H 中，重新選取新的 τi并重復以上步驟，直至無新的 τi可以選取后，再遍歷數組H 找到其中最大的元素hmax，hmax對 應的任務 τi即為新問題中AgentAi下 一步要執行的任務。式（18）表示在新問題的成對模型中，具有最大累積優先級的結果即為AgentAi下 一步要執行的最佳任務。

圖6 分類器 fpriority(τi,τ j)的輸入構成示意圖Fig. 6 Schematic of input structure of classifierfpriority(τi,τ j)

學徒制調度算法的基本步驟如下：

1） 算法的初始化。將戰位分配方案集 τsite、保障班組集A、時間約束集（例如，艦載機最晚起飛時間T、每項任務保障時間等）以及順序可交換的保障任務集作為算法的輸入；

2） 通過保障戰位分配方案的成對模型，得到分類器累積優先級最大的結果，即為第1 個子問題的解，并將其作為第2 個子問題的輸入；

3）在t時刻，對AgentAi來說，具有最高累積優先級的即為當前保障班組Ai此時應保障的戰位；

4） 通 過 分 類 器fact()∈{0,1} 判 斷 在t時刻保障班組Ai能 否保障戰位，若結果為1，將該保障任務加入調度計劃表中，若結果為0，則將 τ0（空任務）加入調度計劃表中；

5） 判斷在t時刻全部保障班組是否都已安排任務，已完成則繼續步驟6），若還沒有，則對未安排任務的保障班組重復步驟3）～5）；

6） 判斷當前時刻t是否為起飛時刻T，若是，則表示已完成調度計劃并將其輸出，若不是，則更新t為下一時刻，重復步驟3）～6），繼續進行下一時刻的調度計劃。

4 仿真實驗及結果分析

4.1 仿真實驗結果

假設一波次出動的艦載機數量為6 架，使用本文設計的學徒制調度算法來獲取6 架艦載機的最佳保障戰位分配結果，同時確定最優保障作業調度計劃，以使該波次的艦載機總體保障完成時間最短。保障作業調度計劃甘特圖如圖7 所示。

圖7 采用學徒制調度算法所得保障班組甘特圖Fig. 7 Gantt chart of supporting teams solved by apprenticeship scheduling algorithm

通過采用學徒制調度算法求解該實例問題，得到6 架艦載機最優保障戰位分配結果分別為S3，S4，S5，S7，S10，S11，班組工作排布結果顯示，最長保障完成時間為60 min，保障班組平均移動時間為5.5 min，可同時使用2 個加油站的戰位數量為3 個。該結果與人工排布策略相契合，即在盡可能縮短保障完成時間的同時，提高了加油站的使用效率?？梢?，通過向專家示例（圖3）學習，使用學徒制調度算法可仿照專家排布策略求解新問題。

4.2 對比試驗

4.2.1 分類器性能對調度結果的影響

由分類器構造過程可知，分類器性能受專家示例構造的樣本數量和質量的影響，為弄清楚樣本的數量與質量對學徒制調度算法性能所造成的影響，設計了基于4.1 節所述保障調度問題的對比實驗。使用數量為原始樣本集的50%、正確率為80%的樣本訓練出的新分類器，然后使用新的分類器重新設計算法，最后針對新的實例問題再次求解。所得艦載機保障調度結果如圖8 所示。

圖8 采用樣本數少、質量低的學徒制調度算法所得保障班組甘特圖Fig. 8 Gantt chart of supporting teams solved by apprenticeship scheduling algorithm with few and low quality samples

由圖可知，6 架艦載機的最優保障戰位分配結果為S1，S2，S7，S8，S10，S12，班組工作排布結果顯示，最長保障完成時間66 min，保障班組平均移動時間（以下稱平均移動時間）7.7 min，可同時使用2 個加油站的戰位數量為2 個。

4.2.2 基于遺傳算法求解的實驗結果

為了驗證學徒制調度算法與傳統算法相比更適于求解保障作業調度，本文將遺傳算法作為傳統搜索算法的代表，使用該算法針對新的問題重新進行了求解。遺傳算法在迭代過程中適應度最大的個體對應的最終保障完成時間如圖9 所示。

圖9 遺傳算法迭代曲線Fig. 9 Iterative curve of genetic algorithm

圖10 所示為使用遺傳算法對新的實例問題進行10 次求解后所得最優保障班組甘特圖。由圖可知，其最優保障戰位分配結果為S3～S8，最長保障完成時間62 min，平均移動時間3.5 min，可同時使用2 個加油站的戰位數量為2 個。

圖10 采用遺傳算法所得保障班組甘特圖Fig. 10 Gantt chart of supporting teams solved by genetic algorithm

4.2.3 實驗結果對比分析

表5 所示為針對4.1 節中新的艦載機保障調度問題，采用3 種算法進行多次求解并取平均值后的匯總結果。

表5 3 種算法對艦載機保障調度問題求解結果對比Table 5 Comparison of the solutions of three algorithms to aircraft support scheduling problem

1） 保障總時間對比。

遺傳算法是目前應用最普遍的智能搜索算法，它搜索全局最優解的能力很強。對于艦載機保障調度問題，采用學徒制調度算法所得解的最長保障完成時間少于遺傳算法，這說明學徒制算法的求解效果略優于遺傳算法。而采用樣本數量少且質量低的學徒制調度算法所得解的保障總時間是3 種算法中最長的，這說明樣本的數量和質量會極大地影響解的質量。

2） 保障資源利用情況對比。

采用遺傳算法所得保障戰位分配結果使得其保障班組平均移動距離與學徒制調度算法結果相比大幅減少，這意味著保障班組處于空閑狀態的時間比較短，保障工序之間銜接的更加緊密，但這種戰位分配方案卻導致1 號加油站不可用，反而增加了其他保障班組的工作量，使得工作分配不均，整體保障完成時間延后。但采用樣本數量少且質量低的學徒制調度算法得出的解則大大延長了保障班組的平均移動距離，在實際場景中，更易受到甲板空間的限制。

另外，使用學徒制調度算法所得加油站的分配方案相比遺傳算法更為合理，能夠更多地安排可以使用2 個加油站的戰位。當艦載機數量增多時，采用這種策略可以減少等待時間。

3） 求解時間對比。

采用遺傳算法時收斂速度較慢，其計算時間約為學徒制調度算法的4.5 倍。另外，學徒制調度算法的分類器是提前學習好的，可以作為離線工具，在實際運用時無需計入學徒制調度算法的求解時間，從而避免了求解資源的浪費。并且，隨著樣本數的增加，還可以不斷更新。

5 結 語

學徒制調度算法相比常見的智能搜索算法更適用于求解艦載機保障作業調度問題。學徒制調度算法分類器的分類質量依賴于樣本數量和質量，當專家示例規模簡單或不具備最優性時，就不能保障所提取樣本集的數量和質量，其性能會大打折扣，且解的質量也會隨之降低。目前，學徒制調度算法僅限于靜態、單目標的艦載機保障調度問題，下一步將針對動態、多目標的新場景和新問題開展研究。