吳靳，戴明強(qiáng)，王俊杰，余珊珊，余明暉

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

2 海軍工程大學(xué) 基礎(chǔ)部, 湖北 武漢 430033

3 華中科技大學(xué) 人工智能與自動(dòng)化學(xué)院, 湖北 武漢 430074

0 引 言

艦載機(jī)作為航空母艦（以下簡(jiǎn)稱“航母”）上最重要的戰(zhàn)力組成部分，其出動(dòng)架次率是評(píng)價(jià)航母戰(zhàn)斗力的重要指標(biāo)之一。然而，因航母甲板的空間有限，航行環(huán)境具有不確定性，致使保障作業(yè)調(diào)度效率受到限制[1]。艦載機(jī)保障調(diào)度問(wèn)題的優(yōu)化目標(biāo)是最小化一波次出動(dòng)艦載機(jī)的最大保障完成時(shí)間。

以往，保障作業(yè)調(diào)度計(jì)劃都是由調(diào)度工作人員根據(jù)軍事演習(xí)或是實(shí)戰(zhàn)經(jīng)驗(yàn)制定的[2]。然而，隨著計(jì)算機(jī)技術(shù)的發(fā)展，科研人員為了更加有效地求解保障調(diào)度問(wèn)題，已嘗試過(guò)采用多種智能搜索算法，例如遺傳算法、禁忌搜索算法、貪婪算法及其衍生算法等。

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

因此，為了解決大規(guī)模的艦載機(jī)保障調(diào)度問(wèn)題，并優(yōu)化求解速度，本文將在現(xiàn)有國(guó)內(nèi)外艦載機(jī)保障作業(yè)相關(guān)研究的基礎(chǔ)上，以一波次出動(dòng)艦載機(jī)最大保障完成時(shí)間為優(yōu)化目標(biāo)，將機(jī)器學(xué)習(xí)應(yīng)用于專家示例。然后，再將調(diào)度人員制定的保障調(diào)度方案作為專家示例進(jìn)行學(xué)習(xí)，學(xué)習(xí)他們?cè)谧雒恳徊經(jīng)Q策時(shí)的思路，通過(guò)分析專家示例，構(gòu)造基于成對(duì)比較模型的輸入樣本集，選取最優(yōu)的分類算法來(lái)訓(xùn)練分類器，在此基礎(chǔ)上構(gòu)造學(xué)徒制調(diào)度算法。最后，使用學(xué)徒制算法和遺傳算法分別針對(duì)新實(shí)例問(wèn)題制定保障作業(yè)調(diào)度方案，以驗(yàn)證學(xué)徒制算法與傳統(tǒng)算法效果。

1 艦載機(jī)保障調(diào)度模型建立

1.1 保障戰(zhàn)位分配

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

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

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

1.2 保障作業(yè)調(diào)度

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

圖2 艦載機(jī)保障任務(wù)流程圖Fig. 2 Flow chart of carrier-based aircraft support tasks

1） 并行任務(wù)，即一架艦載機(jī)在同一時(shí)間可以同時(shí)執(zhí)行的任務(wù)。本文保障任務(wù)中的并行任務(wù)對(duì)包括供電和通風(fēng)、充氧加油、軍檢掛彈、特設(shè)外觀檢查、航電外觀檢查以及機(jī)械外觀檢查。

2） 串行任務(wù)，指執(zhí)行順序不可交換且不能同時(shí)執(zhí)行的任務(wù)。這些任務(wù)可以看做是擁有不同的優(yōu)先級(jí)別，例如供電與通風(fēng)的任務(wù)優(yōu)先級(jí)最高，需要最先執(zhí)行，檢查驗(yàn)收任務(wù)的優(yōu)先級(jí)最低，需要最后執(zhí)行。

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

1.3 保障資源約束分析

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

表1 保障班組任務(wù)執(zhí)行時(shí)間表Table 1 Task execution schedule of the supporting teams

1.1 節(jié)中介紹的加油站的位置約束可以描述為如表2 所示，表2 中加油站的加油保障任務(wù)由表1 中的9～12 號(hào)班組完成。其中，S4機(jī)位可使用9 號(hào)或10 號(hào)加油站，S7機(jī)位可使用10 號(hào)或11 號(hào)加油站，S10機(jī)位可使用11 號(hào)或12 號(hào)加油站進(jìn)行加油任務(wù)，其他機(jī)位固定，只能使用一個(gè)加油站。

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

1.4 保障調(diào)度模型建立

本文研究問(wèn)題的數(shù)學(xué)模型建立如下。

1） 目標(biāo)函數(shù)。最小化一波次出動(dòng)艦載機(jī)的保障作業(yè)完成時(shí)間，定義為：

式中：fj為 保障艦載機(jī)j的完成時(shí)間；J為艦載機(jī)（保障戰(zhàn)位）集合目標(biāo)函數(shù)；目標(biāo)函數(shù)F指最后完成的艦載機(jī)保障作業(yè)時(shí)間最短，從而實(shí)現(xiàn)一波次保障完成時(shí)間最短。

2） 約束條件。

（1） 對(duì)艦載機(jī)j的保障作業(yè)完成時(shí)間是其全部保障任務(wù)完成時(shí)間中的最大值。

式中：fi j為 艦載機(jī)（保障戰(zhàn)位）j的保障任務(wù)i的完成時(shí)間；Oj為 艦載機(jī)j包含的保障任務(wù)編號(hào)集合。

（2） 每架艦載機(jī)的所有保障任務(wù)都只需要一個(gè)保障班組完成。

式中：mi為 執(zhí)行保障任務(wù)i的保障班組編號(hào)；Mi為能夠執(zhí)行保障任務(wù)i的保障班組編號(hào)集合；為描述保障班組和保障任務(wù)對(duì)應(yīng)關(guān)系的二元決策變量，如果將保障戰(zhàn)位j分配給保障班組mi執(zhí)行，則結(jié)果為1，否則為0。

（3） 保障班組在戰(zhàn)位之間的移動(dòng)時(shí)間與戰(zhàn)位間隔成正比。

式 中：pj j′為 保 障 班 組mi完 成 保 障 艦 載 機(jī)j的 任 務(wù)后，轉(zhuǎn)移到艦載機(jī)j′的時(shí)間；常數(shù)c為保障班組在相鄰2 個(gè)戰(zhàn)位間移動(dòng)的時(shí)間。

（4） 在任意時(shí)刻每個(gè)保障班組只能執(zhí)行1 架艦載機(jī)的1 項(xiàng)保障任務(wù)。

（5） 保障班組mi并非一直處于執(zhí)行任務(wù)的狀態(tài)，需要考慮其在戰(zhàn)位間的移動(dòng)時(shí)間。

（6） 每個(gè)保障任務(wù)都有一定的時(shí)長(zhǎng)，保障任務(wù)在執(zhí)行的過(guò)程中不能被打斷。

（7） 開(kāi)始執(zhí)行一項(xiàng)保障任務(wù)前，要確保其所有緊前任務(wù)均已完成。這是因?yàn)楸Ｕ狭鞒讨写嬖诓⑿腥蝿?wù)，某項(xiàng)任務(wù)可能會(huì)有多個(gè)緊前任務(wù)，所以選取緊前任務(wù)集合中完成時(shí)間最長(zhǎng)的作為標(biāo)準(zhǔn)。

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

（8） 艦載機(jī)保障流程中存在保障順序可以交換的保障任務(wù)，但是這些任務(wù)不能同時(shí)執(zhí)行。

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

（9） 加油站條件約束，即每個(gè)戰(zhàn)位執(zhí)行加油保障時(shí)，只需一個(gè)加油站供油。

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

2 專家示例樣本集及分類器構(gòu)造

2.1 基于成對(duì)比較模型構(gòu)造的樣本集

本文中用于解決保障戰(zhàn)位分配和保障作業(yè)調(diào)度問(wèn)題的方法，受益于Gombolay 等[9-10]基于VMPTR提出的學(xué)徒制算法，該算法旨在學(xué)習(xí)專家所做的示例，就像學(xué)徒模仿專家行為一樣。目前，向?qū)＜沂纠龑W(xué)習(xí)（learning from human demonstrations，LFD）[15-16]是機(jī)器學(xué)習(xí)領(lǐng)域的一大熱門。同時(shí)，本文還從Page 等[17]提出的網(wǎng)頁(yè)排序算法中總結(jié)出了成對(duì)比較模型，并將其應(yīng)用于學(xué)徒制算法中。使用已執(zhí)行任務(wù)與未執(zhí)行任務(wù)組成的成對(duì)比較模型構(gòu)造樣本集，同時(shí)使用該樣本集訓(xùn)練分類器，最終建立學(xué)徒制算法，進(jìn)而求出調(diào)度問(wèn)題的最優(yōu)解。

假設(shè)給定的專家示例是問(wèn)題的最優(yōu)解，對(duì)于每個(gè)專家示例，可以構(gòu)造一個(gè)時(shí)序的狀態(tài)觀測(cè)集Ω={Ω1，Ω2，···，Ωs}。 通過(guò)觀測(cè)集 Ω可以很容易地得出，在狀態(tài)觀測(cè) Ωm中 ，對(duì)于AgentAi（即保障班組i）來(lái)說(shuō)，最優(yōu)的待執(zhí)行任務(wù)即為 τi，但卻無(wú)法得知任務(wù)集中各任務(wù)間的關(guān)系。由此，本文通過(guò)將狀態(tài)觀測(cè) Ωm中 選定執(zhí)行的 τi與任務(wù)集中剩下的所有未執(zhí)行任務(wù)進(jìn)行兩兩對(duì)比來(lái)構(gòu)造樣本集。

從給定的專家示例中選取全部的任務(wù)構(gòu)成任務(wù)集 τ(τi∈τ)， 任務(wù)集中的每個(gè)任務(wù) τi都有一個(gè)描述任務(wù)特征的實(shí)值特征向量 γτi，其由多個(gè)與調(diào)度問(wèn)題相關(guān)的特征組成。例如，任務(wù)的截止時(shí)間、最早可以開(kāi)始執(zhí)行任務(wù)的時(shí)間以及任務(wù)持續(xù)時(shí)間等，根據(jù)調(diào)度問(wèn)題的不同，這些特征的選取也不同?？傊贿x出來(lái)的特征應(yīng)該是最能夠表現(xiàn)出任務(wù)重要程度的。

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

對(duì)于將選中的任務(wù) τi與 未選中的任務(wù) τj進(jìn)行成對(duì)比較的方法，其旨在向?qū)＜沂纠龑W(xué)習(xí)并通過(guò)分析任務(wù)狀態(tài)，以此確定下一個(gè)待執(zhí)行任務(wù)的策略，最終通過(guò)迭代得到一個(gè)完整的調(diào)度計(jì)劃。為達(dá)此目的，首先將狀態(tài)觀測(cè) Ωm轉(zhuǎn)換成一個(gè)由選中任務(wù) τi與 未選中任務(wù) τj進(jìn)行對(duì)比得到的新觀測(cè)，如式（14）和式（15）所示。式（14）為每個(gè)狀態(tài)觀測(cè)構(gòu)造了一個(gè)正例樣本，其中包括輸入特征向量和 一個(gè)正標(biāo)簽=1， 輸入特征向量的每個(gè)元素由描述選中任務(wù) τi狀態(tài)的 γτi和描述未選中任務(wù) τj狀態(tài)的 γτj相減得到。式（15）為每個(gè)狀態(tài)觀測(cè)構(gòu)造了一個(gè)負(fù)例樣本，由輸入特征向量和負(fù)標(biāo)簽=0組合而成，其中輸入特征向量由 γτj與 γτi相減得到。

考慮到不同問(wèn)題的環(huán)境因素對(duì)調(diào)度計(jì)劃的影響，引入了描述環(huán)境特征的向量 δτ。 由于 δτ對(duì)同一問(wèn)題下的每個(gè)任務(wù)都是一樣的，如果將 δτ放入γτ中 ，在構(gòu)造樣本集時(shí)， γτi與 γτj相減就互相抵消了，因此在輸入特征向量中單獨(dú)加入了 δτ，如式（14）和式（15）所示。

得到t時(shí)刻應(yīng)進(jìn)行保障作業(yè)的戰(zhàn)位后，需將此戰(zhàn)位負(fù)責(zé)的任務(wù)分配給特定的保障班組。同時(shí)，還需預(yù)測(cè)在t時(shí)刻保障班組AgentAi應(yīng)執(zhí)行選出的任務(wù)，還是執(zhí)行任務(wù) τ0（ 空任務(wù)），即Ai空閑。式（16）和式（17）提供了此分類器的訓(xùn)練樣本集。輸入的特征變量act由環(huán)境特征向量 δτ和描述選中任務(wù)τi的 狀 態(tài) 向 量 γτi構(gòu) 成。i為 樣 本 標(biāo) 簽，AgentAi執(zhí)行選出的任務(wù) τ*i時(shí)，=1； AgentAi執(zhí)行空任務(wù)τ0時(shí) ，=0。

2.2 艦載機(jī)保障調(diào)度問(wèn)題特征選取

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

圖3 所示為專家示例中的保障作業(yè)調(diào)度甘特圖。在該示例中，4 架艦載機(jī)均為同一類型，也即保障作業(yè)流程相同，保障戰(zhàn)位分配結(jié)果分別為S4，S7，S10和S11，最長(zhǎng)保障完成時(shí)間為42 min，保障作業(yè)流程如圖2 所示。圖3 中，矩形內(nèi)的標(biāo)簽分別表示艦載機(jī)編號(hào)和保障工序編號(hào)，圖中灰色部分表示保障班組在戰(zhàn)位之間的移動(dòng)時(shí)間（后文同此）。

圖3 專家示例中保障作業(yè)調(diào)度甘特圖Fig. 3 Gantt chart of support task scheduling in expert demonstrations

表3 和表4 所示均為根據(jù)專家示例中保障作業(yè)調(diào)度方案列舉的特征值。其中，表3 所示為t=0時(shí) 刻的環(huán)境特征，表4 所示為t=0時(shí)刻Agent 1選擇執(zhí)行1 號(hào)戰(zhàn)位（S4）的任務(wù)特征，此時(shí)1 號(hào)戰(zhàn)位即為被選中的任務(wù) τi。

表3 t=0 時(shí)刻的環(huán)境特征Table 3 Environmental features at t=0

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

2.3 分類器訓(xùn)練

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

對(duì)于分類器的選取，采用靈敏度（又稱“真陽(yáng)性率”）和特異度（又稱“真陰性率”）這2 個(gè)指標(biāo)進(jìn)行評(píng)估，如圖4 和圖5 所示。最終，選擇SVMRBF 算法和DT 算法分別訓(xùn)練出了保障戰(zhàn)位分配分類器及保障任務(wù)分配分類器。

圖4 使用不同機(jī)器學(xué)習(xí)算法訓(xùn)練的3 個(gè)分類器模型的靈敏度Fig. 4 Sensitivity of three classifier models trained by different machine learning algorithms

圖5 使用不同機(jī)器學(xué)習(xí)算法訓(xùn)練的3 個(gè)分類器模型的特異度Fig. 5 Speifiity of three classifier models trained by different machine learning algorithms

3 基于學(xué)徒制艦載機(jī)保障調(diào)度算法設(shè)計(jì)

首先，分析已有的專家示例，將t時(shí)刻AgentAi選擇執(zhí)行的任務(wù) τi與剩余未執(zhí)行的任務(wù) τj兩兩對(duì)比，獲得學(xué)徒制調(diào)度算法的分類器樣本集；然后，使用機(jī)器學(xué)習(xí)算法訓(xùn)練分類器。有關(guān)樣本集和分類器的構(gòu)造上節(jié)已詳細(xì)介紹。

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

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

學(xué)徒制調(diào)度算法的基本步驟如下：

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

2） 通過(guò)保障戰(zhàn)位分配方案的成對(duì)模型，得到分類器累積優(yōu)先級(jí)最大的結(jié)果，即為第1 個(gè)子問(wèn)題的解，并將其作為第2 個(gè)子問(wèn)題的輸入；

3）在t時(shí)刻，對(duì)AgentAi來(lái)說(shuō)，具有最高累積優(yōu)先級(jí)的即為當(dāng)前保障班組Ai此時(shí)應(yīng)保障的戰(zhàn)位；

4） 通 過(guò) 分 類 器fact()∈{0,1} 判 斷 在t時(shí)刻保障班組Ai能 否保障戰(zhàn)位，若結(jié)果為1，將該保障任務(wù)加入調(diào)度計(jì)劃表中，若結(jié)果為0，則將 τ0（空任務(wù)）加入調(diào)度計(jì)劃表中；

5） 判斷在t時(shí)刻全部保障班組是否都已安排任務(wù)，已完成則繼續(xù)步驟6），若還沒(méi)有，則對(duì)未安排任務(wù)的保障班組重復(fù)步驟3）～5）；

6） 判斷當(dāng)前時(shí)刻t是否為起飛時(shí)刻T，若是，則表示已完成調(diào)度計(jì)劃并將其輸出，若不是，則更新t為下一時(shí)刻，重復(fù)步驟3）～6），繼續(xù)進(jìn)行下一時(shí)刻的調(diào)度計(jì)劃。

4 仿真實(shí)驗(yàn)及結(jié)果分析

4.1 仿真實(shí)驗(yàn)結(jié)果

假設(shè)一波次出動(dòng)的艦載機(jī)數(shù)量為6 架，使用本文設(shè)計(jì)的學(xué)徒制調(diào)度算法來(lái)獲取6 架艦載機(jī)的最佳保障戰(zhàn)位分配結(jié)果，同時(shí)確定最優(yōu)保障作業(yè)調(diào)度計(jì)劃，以使該波次的艦載機(jī)總體保障完成時(shí)間最短。保障作業(yè)調(diào)度計(jì)劃甘特圖如圖7 所示。

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

通過(guò)采用學(xué)徒制調(diào)度算法求解該實(shí)例問(wèn)題，得到6 架艦載機(jī)最優(yōu)保障戰(zhàn)位分配結(jié)果分別為S3，S4，S5，S7，S10，S11，班組工作排布結(jié)果顯示，最長(zhǎng)保障完成時(shí)間為60 min，保障班組平均移動(dòng)時(shí)間為5.5 min，可同時(shí)使用2 個(gè)加油站的戰(zhàn)位數(shù)量為3 個(gè)。該結(jié)果與人工排布策略相契合，即在盡可能縮短保障完成時(shí)間的同時(shí)，提高了加油站的使用效率?？梢?jiàn)，通過(guò)向?qū)＜沂纠▓D3）學(xué)習(xí)，使用學(xué)徒制調(diào)度算法可仿照專家排布策略求解新問(wèn)題。

4.2 對(duì)比試驗(yàn)

4.2.1 分類器性能對(duì)調(diào)度結(jié)果的影響

由分類器構(gòu)造過(guò)程可知，分類器性能受專家示例構(gòu)造的樣本數(shù)量和質(zhì)量的影響，為弄清楚樣本的數(shù)量與質(zhì)量對(duì)學(xué)徒制調(diào)度算法性能所造成的影響，設(shè)計(jì)了基于4.1 節(jié)所述保障調(diào)度問(wèn)題的對(duì)比實(shí)驗(yàn)。使用數(shù)量為原始樣本集的50%、正確率為80%的樣本訓(xùn)練出的新分類器，然后使用新的分類器重新設(shè)計(jì)算法，最后針對(duì)新的實(shí)例問(wèn)題再次求解。所得艦載機(jī)保障調(diào)度結(jié)果如圖8 所示。

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

由圖可知，6 架艦載機(jī)的最優(yōu)保障戰(zhàn)位分配結(jié)果為S1，S2，S7，S8，S10，S12，班組工作排布結(jié)果顯示，最長(zhǎng)保障完成時(shí)間66 min，保障班組平均移動(dòng)時(shí)間（以下稱平均移動(dòng)時(shí)間）7.7 min，可同時(shí)使用2 個(gè)加油站的戰(zhàn)位數(shù)量為2 個(gè)。

4.2.2 基于遺傳算法求解的實(shí)驗(yàn)結(jié)果

為了驗(yàn)證學(xué)徒制調(diào)度算法與傳統(tǒng)算法相比更適于求解保障作業(yè)調(diào)度，本文將遺傳算法作為傳統(tǒng)搜索算法的代表，使用該算法針對(duì)新的問(wèn)題重新進(jìn)行了求解。遺傳算法在迭代過(guò)程中適應(yīng)度最大的個(gè)體對(duì)應(yīng)的最終保障完成時(shí)間如圖9 所示。

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

圖10 所示為使用遺傳算法對(duì)新的實(shí)例問(wèn)題進(jìn)行10 次求解后所得最優(yōu)保障班組甘特圖。由圖可知，其最優(yōu)保障戰(zhàn)位分配結(jié)果為S3～S8，最長(zhǎng)保障完成時(shí)間62 min，平均移動(dòng)時(shí)間3.5 min，可同時(shí)使用2 個(gè)加油站的戰(zhàn)位數(shù)量為2 個(gè)。

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

4.2.3 實(shí)驗(yàn)結(jié)果對(duì)比分析

表5 所示為針對(duì)4.1 節(jié)中新的艦載機(jī)保障調(diào)度問(wèn)題，采用3 種算法進(jìn)行多次求解并取平均值后的匯總結(jié)果。

表5 3 種算法對(duì)艦載機(jī)保障調(diào)度問(wèn)題求解結(jié)果對(duì)比Table 5 Comparison of the solutions of three algorithms to aircraft support scheduling problem

1） 保障總時(shí)間對(duì)比。

遺傳算法是目前應(yīng)用最普遍的智能搜索算法，它搜索全局最優(yōu)解的能力很強(qiáng)。對(duì)于艦載機(jī)保障調(diào)度問(wèn)題，采用學(xué)徒制調(diào)度算法所得解的最長(zhǎng)保障完成時(shí)間少于遺傳算法，這說(shuō)明學(xué)徒制算法的求解效果略優(yōu)于遺傳算法。而采用樣本數(shù)量少且質(zhì)量低的學(xué)徒制調(diào)度算法所得解的保障總時(shí)間是3 種算法中最長(zhǎng)的，這說(shuō)明樣本的數(shù)量和質(zhì)量會(huì)極大地影響解的質(zhì)量。

2） 保障資源利用情況對(duì)比。

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

另外，使用學(xué)徒制調(diào)度算法所得加油站的分配方案相比遺傳算法更為合理，能夠更多地安排可以使用2 個(gè)加油站的戰(zhàn)位。當(dāng)艦載機(jī)數(shù)量增多時(shí)，采用這種策略可以減少等待時(shí)間。

3） 求解時(shí)間對(duì)比。

采用遺傳算法時(shí)收斂速度較慢，其計(jì)算時(shí)間約為學(xué)徒制調(diào)度算法的4.5 倍。另外，學(xué)徒制調(diào)度算法的分類器是提前學(xué)習(xí)好的，可以作為離線工具，在實(shí)際運(yùn)用時(shí)無(wú)需計(jì)入學(xué)徒制調(diào)度算法的求解時(shí)間，從而避免了求解資源的浪費(fèi)。并且，隨著樣本數(shù)的增加，還可以不斷更新。

5 結(jié) 語(yǔ)

學(xué)徒制調(diào)度算法相比常見(jiàn)的智能搜索算法更適用于求解艦載機(jī)保障作業(yè)調(diào)度問(wèn)題。學(xué)徒制調(diào)度算法分類器的分類質(zhì)量依賴于樣本數(shù)量和質(zhì)量，當(dāng)專家示例規(guī)模簡(jiǎn)單或不具備最優(yōu)性時(shí)，就不能保障所提取樣本集的數(shù)量和質(zhì)量，其性能會(huì)大打折扣，且解的質(zhì)量也會(huì)隨之降低。目前，學(xué)徒制調(diào)度算法僅限于靜態(tài)、單目標(biāo)的艦載機(jī)保障調(diào)度問(wèn)題，下一步將針對(duì)動(dòng)態(tài)、多目標(biāo)的新場(chǎng)景和新問(wèn)題開(kāi)展研究。