基于Memetic算法的艦載機艦面一站式保障調度

蘇析超, 韓　維, 蕭　衛, 蔣婷婷

(1. 海軍航空工程學院飛行器工程系, 山東 煙臺 264001; 2. 中國船舶工業系統工程研究院,北京 100094; 3. 海軍航空工程學院研究生管理大隊, 山東 煙臺 264001)

?

基于Memetic算法的艦載機艦面一站式保障調度

蘇析超1, 韓維1, 蕭衛2, 蔣婷婷3

(1. 海軍航空工程學院飛行器工程系, 山東 煙臺 264001; 2. 中國船舶工業系統工程研究院,北京 100094; 3. 海軍航空工程學院研究生管理大隊, 山東 煙臺 264001)

面向艦載機艦面保障效率和資源利用率等效能指標,系統分析了一站式保障流程約束和資源約束條件,建立了艦載機多機艦面一站式保障調度的數學優化模型。針對傳統優化算法難以求解大規模調度問題,提出了一種Memetic算法。首先,為了使可更新類資源負載均衡化,采用一種嵌入資源分配策略的串行調度方案;其次,設計了一種基于子拓撲結構的自適應變異策略以提升算法的探索能力,并引入基于模擬退火機制的局部搜索方法;最后，基于不同調度規模案例的仿真結果驗證了模型和算法的可行性和有效性。

艦載機; 艦面一站式保障;Memetic算法; 優化

0　引　言

作為航母作戰編隊攻防體系的核心,艦載機承擔了航母全系統和航母戰斗群的絕大多數作戰使命,其艦面保障是影響出動架次率乃至航母編隊作戰效能的關鍵因素。艦載機艦面保障涉及復雜的流程約束、資源約束和環境約束,隨著艦載機機群規模的增加,傳統的人工調度已難以滿足其實時性、魯棒性和優化性能。因此,對艦載機多機艦面保障流程安排和資源分配進行科學的規劃和決策具有重要意義[1]。

近年來,艦載機調度已成為國內外研究的一個新興的熱點。針對艦載機艦面調運規劃,文獻[2]提出了基于改進A*算法的甲板滑行路徑規劃方法;文獻[3]在艦載機運動約束模型的基礎上,引入了“凸殼模型”和碰撞檢測以實現調運的安全性。美國的麻省理工學院通過對一款名為DCAP(deckoperationcourseofactionplanner)[4]的飛行甲板輔助決策平臺的開發,建立了甲板周期內艦載機調度的線性整數規劃模型,并研究了基于分支定界的精確算法[5]、基于逆向強化學習的機器學習方法[6]和基于差分進化算法的智能優化[7]等方法在艦載機機群全流程調度問題中的應用。文獻[8]引入Multi-agent技術并基于艦載機作業流程建立了3層混合控制模型架構,研究了考慮故障擾動等因素的艦載機動態調度問題。文獻[9]針對單機機組保障模式的不足,建立了多機一體化機務保障調度模型,可有效提升保障人員的利用率。

但是,由于目前航母資源設置的局限性,無法滿足各停機位均能供給各類資源,使得艦載機在航空保障過程中需要頻繁的調運作業,從而降低了保障作業效率和艦載機的出動架次率。

為此,本文針對艦載機一站式保障的發展趨勢和其技術特征[10],建立了艦載機機群的艦面一站式保障調度模型,并設計了一種基于子拓撲網局部災變策略的Memetic算法,以提升針對中、大規模調度問題的求解性能。

1　艦載機艦面一站式保障問題建模

1.1一站式保障流程分析與問題描述

艦載機艦面一站式保障是指艦載機在航空保障流程約束和資源配置約束條件下,不需要往返地調運即可在甲板同一個停機站位集中完成各項出動前保障作業,從而提升機群的快速出動能力。一站式保障實現的前提和關鍵在于各類保障資源的優化配置。根據資源的性質和作用,可將其分解為:可更新資源、消耗類資源、空間資源。

(1) 可更新資源,主要包括保障人員和保障設備/設施。其中保障人員按照保障作業的性質可劃分為機械、軍械、航電、特設等專業類型,每一類保障人員均包含若干組保障人員;保障設備則包括提供電燃氣液等消耗類資源的固定站點和移動保障車。與移動保障車的甲板機動保障不同,固定資源站僅可對以管線長度為半徑的圓域內的艦載機提供保障,圖1為庫茲涅佐夫號航母某類資源站覆蓋的停機位示意圖。

(2) 消耗類資源,指保障過程中不斷消耗的電燃氣液和彈藥等物資資源。這類資源不僅總量有限制,而且由于航母技術和空間布局制約,存在任意時刻供應量的限制,如額定燃油壓力僅能滿足一定數量的艦載機同時進行加油作業。

(3) 空間資源,主要考慮對艦載機實施保障作業所需的諸如座艙、起落架倉等的站位空間。

圖1　庫茲涅佐夫號航母某類資源站覆蓋停機位示意圖Fig.1　Distribution map of some resource stations on the admiral Kuznetsov aircraft carrier

對任一艦載機i,其保障工序流程可表示為有向網絡圖Di=(Vi,Ai),其中,節點Vi表示保障工序集合,有向弧Ai表示各工序間的緊前緊后約束關系。本文研究的目的,即在保證流程約束條件下,對各類資源進行合理地分配和調度,以實現機群快速保障和保障資源均衡使用,進而提升艦載機多機的出動效能。

1.2一站式保障調度數學模型

首先定義模型參數如下:

I={1,2,…,n}為艦載機集合,其中n為艦載機數量；

Ji={1,2,…,|Ji|}為艦載機i的工序集,其中|Ji|為工序數；

Kp={1,2,…,|Kp|}為保障專業種類集合；

Ks={1,2,…,|Ks|}為站位空間種類集合；

Kr={1,2,…,|Kr|}為保障設備種類集合；

Kw={1,2,…,|Kw|}為消耗性資源種類集合；

Lpk={1,2,…,|Lpk|}為第k(k∈Kp)種專業保障人員集合；

Lsk={1,2,…,|Lsk|}為第k(k∈Ks)類空間集合；

Lrk={1,2,…,|Lrk|}為第k(k∈Kr)種保障設備集合；

Rkl為第k(k∈Kr)種第l個保障設備所覆蓋到的艦載機集合；

rpijk為艦載機i的第j道保障工序對第k(k∈Kp)類專業保障人員的需求量；

rsijk為艦載機i的第j道保障工序對第k(k∈Ks)類空間站位的需求變量；

rijk為艦載機i的第j道保障工序對第k(k∈Kr)種保障設備的需求量；

rwijk為艦載機i的第j道保障工序對第k(k∈Kw)類消耗性資源的需求量；

Pij為工序Oij的緊前工序集合；

Tij為工序Oij的保障作業時間；

Sij、Eij分別為第i架艦載機第j道工序的開始保障時間和結束保障時間；

Eopk、Eork′分別為第k(k∈Kp)類專業保障人員和第k′(k′∈Kr)類保障設備的閑忙比方差；

Bpkl、Brk′l′分別為為第k(k∈Kp)類專業中第l個保障人員和第k′(k′∈Kr)類第l′個保障設備的工作時間。

決策變量定義為

根據艦載機調度的指標要求,優化的目標選取分層雙目標,即在滿足最小化最大保障完工時間的前提下,使得可更新資源的閑忙比方差和最小

(1)

式中,第k類專業的閑忙比方差

(2)

工作時間Bpkl可表示為

(3)

第k類設備的閑忙比方差Eork和其第l個設備的工作時間Brkl可分別參照式(2)和式(3)給出。

約束條件包括

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

表示艦載機i中同時進行保障的不同工序均對某類設備有需求時,僅需一個設備即可滿足,如一個供電設備可滿足若干并行通電作業工序;式(10)為消耗性資源約束,即任意時刻對某消耗性資源的需求不大于其供給量。

2　Memetic算法設計

由上述模型可以看出,艦載機多機一站式保障調度問題本質上屬于一類具有非確定性多項式-難(non-deterministicpolynomial-hard,NP-hard)特性的資源受限多項目調度問題(resource-constrainedmulti-projectschedulingproblem,RCMPSP)[11-12]。若按照各類資源的選擇和工序保障順序逐一編碼,不僅編碼復雜度高,且求解效率隨著艦載機保障數量規模增大而急劇下降,計算量耗費大。因此,本文借鑒RCMPSP的群智能優化求解方法,并嵌入可更新性資源選擇的啟發式規則,在確保求解精度的前提下提升了解算的效率。

Memetic算法是一種基于種群的全局搜索和基于個體的局部搜索的混合算法,自1989年由Moscato提出后,已經在諸多領域得到了廣泛的應用[13],特別是在解決具有多極值特性的調度問題具有很強的尋優能力和普適性[14-15]。本文在求解RCMPSP問題的標準遺傳算法(geneticalgorithm,GA)的基礎上,設計了改進的Memetic算法如下。

2.1解的編碼

編碼方案是影響算法搜索效果和效率的重要因素,求解RCMPSP問題的主要編碼策略包括任務列表編碼、優先數編碼和優先規則編碼。其中,任務列表編碼相對于后兩者具有更有效的搜索空間,因此本文采用任務列表的編碼策略。染色體個體可表示為滿足流程約束關系的作業排列X=[x1,x2,…,xk,…,xnm],其中,xk為二元數組(i,j)分別表示艦載機編號及其工序號,nm為所有工序數總和。

2.2解碼操作

解碼是實現染色體編碼向調度方案映射的關鍵步驟,通過解碼確定各艦載機工序的保障開始/結束時間以及資源的分配。然而經典的串行調度生成機制和并行調度生成機制僅考慮任意時刻資源占用量,而不考慮資源的具體分配[16]。為了更均衡地利用各類資源,分別設計保障人員和保障設備的分配規則:

(2) 基于覆蓋范圍內剩余工序作業時間最少優先(minimumtotalprocessingtimeremainingincoveringarea,MTRCA)的保障設備分配規則,表示當工序Oij需要第k類設備進行保障,則對覆蓋到艦載機i的所有k類設備,分別計算其覆蓋范圍內對應的艦載機待保障工序時間和

并選取最小值所對應的保障設備。其中令Sg表示已調度集合,則覆蓋域內待分配工序集

通過MTRCA分配,一方面緩解覆蓋較多艦載機工序的設備的使用沖突,使工作負載均衡;另一方面避免設備使用過度集中造成保障總時間的延遲。當存在待保障工序時間和相同的設備時,采用MATF規則進行分配。

Initialization:g=1,Sg=?;

While|Sg|

(i*,j*)=xg;

ESi*j*=max{Eij+dij|(i,j)∈Pi*j*};

For?k∈Kp∧rpi*j*k>0

Endfor

For?k∈Kr∧ri*j*k>0

Endfor

Sg+1=Sg∪{(i*,j*)},g=g+1;

End

2.3適應度分配與選擇算子

采用基于排序的適應度分配法,以避免適應度函數選取不當而降低求解的魯棒性。對于規模為Np的種群,按照個體最大保障完成時間Cmax進行排序,即Cmax越小排序越高,設選擇壓力Π(Π∈[1,2]),表示最佳個體被選中的概率與平均選中概率的比值,pi種群中個體i的位序,則基于線性排序的適應度計算方法可表示為

(12)

根據式(12)所得適應度分配,按照輪盤賭策略選擇個體進行種群更新。

2.4交叉算子

2.5基于子拓撲工序網的自適應變異策略

變異策略是增加種群多樣性,避免陷入局部最優的重要手段,常規的基于Insertion或Inerchange的變異策略僅能產生較小的鄰域變換范圍,對于較大規模的調度問題則難以跳出局部最優。為此,本文針對大規模的RCMPSP問題特性,設計一種新的鄰域結構如下:

(1) 針對染色體個體X根據概率Pm選擇艦載機i,并從X中提取其工序排列πi;

(4) 將重排的序列隨機插入至原染色體X的[dx1,dx2]位置區間,得到新的染色體Y。

該鄰域結構一方面通過基于子拓撲工序網的重排實現艦載機內的工序排序的變動,另一方面通過重插入實現艦載機之間的工序變換,從未增大了搜索空間。此外,為了進一步增強變異策略在進化后期避免陷入局部極值的能力,對變異概率采用自適應變化策略

(13)

(14)

2.6基于模擬退火機制的局部搜索策略

通過引入局部搜索策略可進一步引導算法在多局部極值解空間中進行高效地深度搜索,增強算法的全局尋優能力。在執行了交叉和變異的全局搜索后,選取種群中100p%的最優個體,并采用基于Inerchange的鄰域結構和模擬退火選擇機制進行局部搜索:

步驟 1對選取的個體Spbest,令k=1。

步驟 2按概率Pl選取基因位xk=(i,j),找到其緊前工序集所在Spbest中的最大基因位xk′=(i,h),h∈Pij。

步驟 5令k=k+1,若k

基于上述各部分算法描述,求解艦載機一站式保障調度問題的Memetic算法基本流程圖如圖2所示。

圖2　Memetic算法流程圖Fig.2　Flow diagram of Memetic algorithm

3　仿真分析

以庫茲涅佐夫號航母為實例分析對象,如圖1所示，某出動任務想定需要對8架艦載機進行出動前的保障作業。任一艦載機i的單機保障工序流程如圖3所示,其中除編號1和編號19為單機虛擬開始/結束工序,其余編號工序右上角括號內分別表示需要的保障人員專業類型和設備類型,且需求量均為1,虛線連接的工序表示因站位空間的限制而不能同時進行。通過添加整體保障任務的虛擬開始/結束節點可將各艦載機保障工序流程合并為多機保障網絡流程。

圖3　艦載機單機保障工序流程圖Fig.3　Support process flow chart of single aircraft

各艦載機工序保障的時間參數和設備對艦載機的保障覆蓋情況分別如表1和表2所示。

表1 保障工序時間參數表

表2中單元格的數字集合表示該列設備類型可覆蓋到該行的艦載機的設備集合。此外,參與保障的5類專業保障人員的數量分別為|Lp1|=4,|Lp2|=4,|Lp3|=6,|Lp4|=4,|Lp5|=4;5類設備資源分別對應5類可消耗性資源,例如工序Oij需要Kr1類設備保障的同時也需要Kw1類消耗性資源供給,且各類消耗性資源的供給限制可表示[Nw1,Nw2,…,Nw5]=[6,5,2,4,2],其中Nwk表示第k(k∈Kw)類消耗性資源能同時供給Nwk架艦載機進行保障作業。

表2　設備對艦載機保障覆蓋關系

將GA、IGA和Memetic算法分別求得的最優解進化曲線進行對比,如圖4所示,并結合表3的對比分析可以看出,本文所提出的Memetic算法不僅具有較強的全局搜索能力和收斂速度,且算法更穩定,魯棒性更強;而通過比較基于本文所設計變異策略的IGA和標準GA算法,驗證了

表3　算法性能對比

圖4　最優解收斂對比曲線Fig.4　Comparison diagram of optimal convergence

圖5　最優調度甘特圖Fig.5　Gantt chart of optimal scheduling

為了檢驗Memetic算法求解中、大規模調度問題的優越性,另外分別在相同保障條件下進行4機和12機出動的仿真對比,算法設置相同,得到出動保障效率參數如表4所示。通過仿真可以看出,在保障規模較小的情況下,3種算法基本上均能以較大概率收斂至最優解或次優解,而隨著艦載機規模的增加,3種算法的求解性能差距拉大,GA和IGA算法往往收斂不到最優解,而Memetic算法依然保持較好的收斂性和魯棒性。

表4　不同出動規模下算法性能對比

4　結　論

本文針對艦載機艦面一站式保障調度問題,通過系統分析艦載機保障的流程約束和各類資源約束,以優化保障時間和可更新資源利用率方差為目標,建立了問題的數學模型。在此基礎上,設計了一種基于子拓撲結構的變異策略和基于模擬退火機制局部搜索的Memetic算法求解該模型。通過以庫茲涅佐夫號航母為背景的仿真實例驗證了模型的可行性,以及算法對于中、大規模保障調度問題求解的有效性。在今后研究中,將著力研究算法在實際調度中的時效性問題。

[1]HanW,WangQG. Conspectus of aircraft carrier and carrier plane[M].Yantai:NavalAeronauticalandAstronauticalUniversityPress, 2009: 37-41. (韓維, 王慶官. 航母與艦載機概論[M].煙臺: 海軍航空工程學院出版社, 2009: 37-41.)

[2]WuY,QuXJ.Pathplanningfortaxiofcarrieraircraftlaunching[J].Science China Technological Sciences, 2013, 56(6): 1561-1570.

[3]HanW,SiWC,DingDC,etal.Multi-routesdynamicplanningondeckofcarrierplanebasedonclusteringPSO[J].Journal of Beijing University of Aeronautics and Astronautics, 2013, 39(5): 610-614. (韓維, 司維超, 丁大春, 等. 基于聚類PSO算法的艦載機艦面多路徑動態規劃[J].北京航空航天大學學報, 2013, 39(5): 610-614.)

[4]RyanJC,CummingsML,RoyN,etal.Designinganinteractivelocalandglobaldecisionsupportsystemforaircraftcarrierdeckscheduling[C]∥Proc.of the AIAA Infotech@ Aerospace Conference, 2011.

[5]RyanJC,BanerjeeAG,CummingsML,etal.Comparingtheperformanceofexpertuserheuristicsandanintegerlinearprograminaircraftcarrierdeckoperations[J].IEEE Trans. on Cybernetics, 2014, 44(6): 761-773.

[6]MichiniB,JonathanP.Ahuman-interactivecourseofactionplannerforaircraftcarrierdeckoperations[C]∥Proc.of the AIAA Infotech @ Aerospace Conference, 2011.

[7]DastidarRG,FrazzoliE.Aqueueingnetworkbasedapproachtodistributedaircraftcarrierdeckscheduling[C]∥Proc.of the AIAA Infotech @ Aerospace Conference, 2011.

[8]FengQ,ZengSK,KangR.AMAS-basedmodelfordynamicschedulingofcarrieraircraft[J].Acta Aeronautica et Astronautica Sinica,2009,30(11):2119-2125.(馮強,曾聲奎,康銳.基于MAS的艦載機動態調度模型[J].航空學報,2009,30(11):2119-2125.)

[9]HanW,SuXC,ChenJF.Integratedmaintenancesupportschedulingmethodofmulti-carrieraircrafts[J].Systems Engineering and Electronics,2015,37(4):809-816.(韓維,蘇析超,陳俊鋒.艦載機多機一體化機務保障調度方法[J].系統工程與電子技術,2015,37(4): 809-816.)

[10]LiuXC.Technicalfeaturesandcriticaltechnologiesforthe“pit-stop”aircraftservicingadoptedbyfordclassaircraftcarriers[J].Chinese Journal of Ship Research, 2013, 8(6): 1-5. (劉相春. 美國“福特”級航母“一站式保障”技術特征和關鍵技術分析[J].中國艦船研究, 2013, 8(6): 1-5.)

[11]HartmannS,BriskornD.Asurveyofvariantsandextensionsoftheresource-constrainedprojectschedulingproblem[J].European Journal of Operational Research, 2014, 207(1): 1-14.

[12]WangL,FangC.Ahybridestimationofdistributionalgorithmforsolvingtheresource-constrainedprojectschedulingproblem[J].Expert Systems with Application, 2012, 39(3): 2451-2460.

[13]NeriF,CottaC.MemeticalgorithmandMemeticcomputingoptimization:aliteraturereview[J].Swarm and Evolutionary Computation, 2012(2): 1-14

[14]GaoL,ZhangGH,ZhangLP,etal.AnefficientMemeticalgorithmforsolvingthejobshopschedulingproblem[J].Computers & Industrial Engineering, 2011, 60(4): 699-705.

[15]ChiangTC,ChengHC,FuLC.NNMA:aneffectiveMemeticalgorithmforsolvingmultiobjectivepermutationflowshopschedulingproblems[J].Expert Systems with Application, 2011, 38(5): 5986-5999.

[16]ShouYY. Resource-constrained multi-project scheduling models and methods[M].Hangzhou:ZhejiangUniversityPress, 2010: 74-80. (壽涌毅. 資源受限多項目調度的模型與方法[M].杭州:浙江大學出版社, 2010: 74-80.)

Pit-stop support scheduling on deck of carrier plane based on Memetic algorithm

SU Xi-chao1, HAN Wei1, XIAO Wei2, JIANG Ting-ting3

(1. Department of Airborne Vehicle Engineering, Naval Aeronautical and Astronautical University, Yantai 264001, China;2. System Engineering Research Institute, China State Shipbuilding Corporation, Beijing 100094, China;3. Graduate Student’s Brigade, Naval Aeronautical and Astronautical University, Yantai 264001, China)

Forimprovingtheeffectivenessindexessuchassupportefficiencyandresourcesavailabilityondeckofcarrierplaneseffectively,thepit-stopsupportroutingconstraintsandresourcesconstraintsareanalyzedsystematically,andanoptimizedpit-stopsupportschedulingmathematicmodelondeckofcarrierplanesisestablished.Tosolvelarge-scaleschedulingproblemswhicharedifficultfortraditionaloptimizationmethods,aMemeticalgorithmisproposed.First,tomaketheloadofrenewableresourcesequalized,aserialschedulegenerationschemeembeddedbyresourcesallocationstrategiesisadopted.Second,anewadaptivemutationstrategybasedonthesub-topologystructureisdesignedtoimproveexplorationabilityofthealgorithm,andalocalsearchmethodbasedonsimulatedannealingisintroduced.Finally,thesimulationresultsshowthefeasibilityofthemodelandtheeffectivenessofthealgorithmunderdifferentdispatchscales.

carrierplane;pit-stopsupportschedulingondeck;Memeticalgorithm;optimization

2016-02-29；

2016-04-05；網絡優先出版日期：2016-06-29。

國家自然科學基金(51375490)；航空科學基金(20145784010)資助課題

V271.4+92

ADOI:10.3969/j.issn.1001-506X.2016.10.12

蘇析超(1989-),男,博士研究生,主要研究方向為艦載機技術研究及應用。

E-mail:suiting1012@163.com

韓維(1970-),男,通信作者,教授,博士研究生導師,博士，主要研究方向為航空保障工程和飛行動力學。

E-mail:Luckydevilhan@163.com

蕭衛(1966-),男,研究員,碩士,主要研究方向為航空系統工程、流程優化。

E-mail:18911990663@189.cn

蔣婷婷(1995-),女,碩士研究生,主要研究方向為艦載機技術研究及應用。

E-mail:suiting1012@163.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160629.1132.002.html