基于并行遺傳算法的艦載機(jī)再次出動(dòng)作業(yè)調(diào)度

范加利,朱興動(dòng),高 偉,王 正

(1.海軍航空大學(xué) 青島校區(qū)，山東 青島 266041；2.海軍航空大學(xué)，山東 煙臺(tái) 265200)

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

受作業(yè)完成時(shí)間的不確定性、艦載機(jī)及保障裝設(shè)備故障的隨機(jī)性、作業(yè)環(huán)節(jié)的多態(tài)性等因素的影響，涉及多架艦載機(jī)、多種保障資源的艦載機(jī)再次出動(dòng)作業(yè)的調(diào)度問(wèn)題屬于典型的動(dòng)態(tài)調(diào)度問(wèn)題。近年來(lái)，國(guó)內(nèi)學(xué)者在該領(lǐng)域進(jìn)行了大量的研究工作，針對(duì)該問(wèn)題常用的方法是建模仿真方法[2]，最優(yōu)化方法[3-5]，以及基于專(zhuān)家方案的逆向強(qiáng)化學(xué)習(xí)方法等[6]。但多數(shù)文獻(xiàn)中仍以靜態(tài)調(diào)度為研究基礎(chǔ)，通過(guò)提高調(diào)度結(jié)果的魯棒性來(lái)保證和自適應(yīng)性來(lái)增強(qiáng)調(diào)度系統(tǒng)、算法對(duì)動(dòng)態(tài)、隨機(jī)環(huán)境的響應(yīng)能力，避免頻繁重調(diào)度。在眾多研究文獻(xiàn)中，對(duì)甲板站位保障能力和艦載機(jī)轉(zhuǎn)運(yùn)路徑約束的考慮較少，而實(shí)際的甲板作業(yè)環(huán)境下，必須要考慮站位能力約束和轉(zhuǎn)運(yùn)路徑約束。

針對(duì)復(fù)雜的艦載機(jī)艦面航空保障作業(yè)調(diào)度問(wèn)題，本文重點(diǎn)研究雙周期出動(dòng)模式下艦載機(jī)再次出動(dòng)準(zhǔn)備的調(diào)度，分析再次出動(dòng)準(zhǔn)備的作業(yè)過(guò)程以及約束條件，建立了艦載機(jī)再次出動(dòng)準(zhǔn)備的優(yōu)調(diào)度模型，并采用一種島式并行遺傳算法求解調(diào)度模型，最后以庫(kù)茲涅佐夫航母上8機(jī)雙周期再次出動(dòng)準(zhǔn)備作業(yè)為例進(jìn)行了驗(yàn)證。

1 艦載機(jī)甲板作業(yè)調(diào)度模型

1.1 艦載機(jī)甲板作業(yè)過(guò)程描述

艦載機(jī)在飛行甲板上的相關(guān)作業(yè)包括機(jī)務(wù)保障與勤務(wù)保障作業(yè)，機(jī)務(wù)保障作業(yè)主要機(jī)務(wù)人員對(duì)艦載機(jī)及其發(fā)動(dòng)機(jī)實(shí)施各種不要的檢查與修理，勤務(wù)保障主要指為艦載機(jī)提供電源、慣性導(dǎo)航基準(zhǔn)信號(hào)源、氣源、油料、彈藥等各種物資，勤務(wù)保障主要由母艦所屬人員完成。所有保障工作必須在航母飛行甲板上的特定站位上完成。以某型俄制航母為例，其飛行甲板布局如圖1所示。

圖1 某航母甲板停機(jī)區(qū)域分布示意圖

圖1中過(guò)渡區(qū)、停機(jī)區(qū)、暖機(jī)區(qū)均設(shè)置有多個(gè)艦載機(jī)站位，各停機(jī)區(qū)域均設(shè)有類(lèi)型和數(shù)量不等的固定式勤務(wù)保障裝置，如加油站、供電口蓋、氣源口蓋、導(dǎo)航對(duì)準(zhǔn)口蓋等。除暖機(jī)區(qū)和起飛位上的艦載機(jī)可實(shí)施起飛前的暖機(jī)作業(yè)外，其他區(qū)域站位上的艦載機(jī)均不能起動(dòng)發(fā)動(dòng)機(jī)。受甲板區(qū)域大小限制，過(guò)渡區(qū)與起飛區(qū)存在重疊，著艦區(qū)與暖機(jī)區(qū)存在部分重疊。由于重疊區(qū)域存在，艦載機(jī)甲板作業(yè)時(shí)，要求任一時(shí)刻起飛與著艦不能同時(shí)進(jìn)行，且著艦作業(yè)時(shí)，暖機(jī)區(qū)II中停放的艦載機(jī)必須轉(zhuǎn)運(yùn)至其他位置，并清空著艦區(qū)域，起飛作業(yè)時(shí)，除起飛位上的艦載機(jī)，其他待機(jī)區(qū)的艦載機(jī)必須轉(zhuǎn)運(yùn)至其他位置。

飛行甲板運(yùn)轉(zhuǎn)過(guò)程中，艦載機(jī)從暖機(jī)區(qū)的停機(jī)位按一定順序滑行至起飛位起飛，位于停機(jī)區(qū)停機(jī)位上的艦載機(jī)則需滑行至起飛位或暖機(jī)區(qū)停機(jī)位進(jìn)行暖機(jī)后方可起飛。著艦的艦載機(jī)在引導(dǎo)員引導(dǎo)下分別滑行至待機(jī)區(qū)和暖機(jī)區(qū)的空閑停機(jī)位停放，并接受再次出動(dòng)準(zhǔn)備，等待下一次飛行。艦載機(jī)再次出動(dòng)準(zhǔn)備的甲板作業(yè)過(guò)程如圖2所示。

圖2 艦載機(jī)再次出動(dòng)準(zhǔn)備作業(yè)時(shí)序框圖

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

多架艦載機(jī)在實(shí)施再次出動(dòng)準(zhǔn)備作業(yè)過(guò)程中，主要存在以下約束：

1)作業(yè)順序約束。波次出動(dòng)艦載機(jī)的再次出動(dòng)保障作業(yè)順序約束如圖2所示。其中作業(yè)集TS1必須先于作業(yè)集TS2實(shí)施。

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

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

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

1.2 調(diào)度模型建立

調(diào)度模型的目標(biāo)函數(shù)取為最小化本波次艦載機(jī)的再次出動(dòng)準(zhǔn)備時(shí)間：

F=minCmax

(1)

約束條件為：

(2)

(3)

(4)

(5)

(6)

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

(7)

式(2)和式(3)聯(lián)合確保每一作業(yè)必須只被每一架飛機(jī)啟動(dòng)一次，帶有僅單一資源的特定性任務(wù)需要額外執(zhí)行要求的作業(yè)通過(guò)式(3)強(qiáng)調(diào)。不等式(4)確保作業(yè)期間的時(shí)序優(yōu)先級(jí)條件，該不等式主要針對(duì)作業(yè)集TS2。不等式(5)確保僅有有限數(shù)量的甲板資源被用于完成不定資源約束型作業(yè)，不等式(6)確保對(duì)于每一架飛機(jī)沒(méi)有兩個(gè)可以導(dǎo)致安全問(wèn)題的作業(yè)同時(shí)進(jìn)行。不等式(7)表示調(diào)運(yùn)可行路徑約束通，其中ZWi1表示艦載機(jī)在甲板的停機(jī)站位，Hs表示艦艏區(qū)域站位集合；Xzwp表示站位的x坐標(biāo)，jzy表示轉(zhuǎn)運(yùn)作業(yè)。

2 調(diào)度模型求解算法

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

2.1 算法總體框架

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

為改進(jìn)算法效率，算法中加入本質(zhì)自適應(yīng)調(diào)整階段，該階段具有在分散和強(qiáng)化搜索過(guò)程中的平衡能力。在自調(diào)整階段最好的個(gè)體被用于禁忌搜索，最差的個(gè)體被用于執(zhí)行全局搜索。

算法具體流程如下：

步驟1：輸入待保障的艦載機(jī)數(shù)量，各艦載機(jī)需要完成的作業(yè)集，甲板環(huán)境參數(shù)及資源約束參數(shù)，并將艦載機(jī)與甲板站位相關(guān)聯(lián)，標(biāo)明艦載機(jī)在站位上的停放方向

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

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

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

2.2 種群遷移策略

種群遷移策略在并行GA中發(fā)揮重要作用，其控制了島間信息交互過(guò)程。遷移策略的工作機(jī)制主要依賴(lài)于4個(gè)因素：通訊拓?fù)洹⑦w移率、選擇方法和代替方法。

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

通訊拓?fù)浣Y(jié)構(gòu)規(guī)范了島間遷移路徑。通常，公共結(jié)構(gòu)是環(huán)形、星形、網(wǎng)形、非限制型(完全網(wǎng))，以及線性矩陣形。通訊代價(jià)主要取決于網(wǎng)絡(luò)直徑。為了獲得島間直接低代價(jià)遷移，我們采用非限制性結(jié)構(gòu)，如圖4所示。

圖4 島間通訊拓?fù)?/p>

遷移率規(guī)范了遷移數(shù)量和遷移數(shù)據(jù)。為了獲得較好的收斂性，遷移應(yīng)采用實(shí)時(shí)模式，通常是任何一個(gè)島收斂時(shí)，即發(fā)生遷移。當(dāng)任何一個(gè)島的連續(xù)5代后代無(wú)任何改進(jìn)時(shí)，即讓遷移在島間發(fā)生。

為了允許島間分享它們關(guān)于有希望出現(xiàn)最優(yōu)解的區(qū)域的信息，輪盤(pán)賭方法被用作遷移選擇方法。即個(gè)體xj被選擇的概率由下式?jīng)Q定：

(8)

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

2.3 編碼與解碼

染色體采用矩陣形編碼在處理該調(diào)度問(wèn)題時(shí)有直觀性，且能很好地反映工序約束關(guān)系。本文的染色體行為矩陣A所示。

(9)

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

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

1：functionCaldt()

2：記錄沒(méi)架飛機(jī)第j到作業(yè)工序?yàn)閽鞆椬鳂I(yè)的飛機(jī)數(shù)為tgd，自增

3：取當(dāng)前艦載機(jī)作業(yè)工序j的上一工序結(jié)束時(shí)間→TempJ

4：若當(dāng)前為所有飛機(jī)的第一道作業(yè)工序，且tdg≤NGD(掛彈資源約束)，則dt=0，否則dt=tgdd，tgdd為d區(qū)域的預(yù)計(jì)掛彈作業(yè)時(shí)間

5：當(dāng)前已安排掛彈作業(yè)的飛機(jī)數(shù)量ngdTask，并將其預(yù)計(jì)結(jié)束時(shí)間按從小到大排序

6：若當(dāng)前非第一道作業(yè)工序，且ngdTask

3 算例仿真

圖5 8機(jī)再次出動(dòng)準(zhǔn)備調(diào)度時(shí)序優(yōu)化結(jié)果圖

從仿真結(jié)果可以看出：并行GA算法可以獲得較接近最優(yōu)解的調(diào)度結(jié)果。調(diào)度模型輸出的作業(yè)邏輯符合實(shí)際甲板作業(yè)環(huán)境，方案可行。

4 結(jié)論

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