基于改進差分進化算法的艦面保障作業(yè)優(yōu)化

劉小路，楊春輝，崔榮偉，崔海波，劉子玄

（1.海軍工程大學，湖北武漢 430014；2. 92785部隊，遼寧葫蘆島 125000；3. 92823部隊，海南三亞 572000；4.海軍航空大學，山東煙臺 264001）

艦載機著艦后，需要在完成掛彈、加油、通電檢查等一系列艦面保障作業(yè)之后才能再次出動。由于艦面環(huán)境狹小且復雜多變，艦面保障作業(yè)周期較長且呈現(xiàn)高度動態(tài)不確定性，因此，艦載機艦面保障作業(yè)調(diào)度效能是制約艦載機出動率和航母編隊綜合作戰(zhàn)能力的重要因素。相關資料顯示，美軍最新一代“福特”級航母采用先進的“一站式”艦面保障技術和智能調(diào)度技術，使得艦載機出動能力相對于“尼米茲”級航母提升了33%，極大地增強了美軍航母編隊的威懾力和打擊能力。我國對于航母的研究工作起步較晚，目前大多采用基于人工經(jīng)驗的作業(yè)調(diào)度模式，不僅調(diào)度效率低下，而且易發(fā)生危險，因此，亟須發(fā)展基于數(shù)學模型和先進決策優(yōu)化算法的艦面保障作業(yè)智能調(diào)度技術。

國內(nèi)外學者的相關研究為艦面保障作業(yè)優(yōu)化提供了較多可借鑒的經(jīng)驗。韓維等分析了艦載機艦面作業(yè)的流程約束和資源約束，設計了雙種群模糊引力搜索算法，用于作業(yè)流程的優(yōu)化求解；Cui 等在給出艦面保障作業(yè)優(yōu)化模型的基礎上，設計了雙種群多算子遺傳算法用于模型求解。文獻[2]和[3]均在算法中引入雙種群結構以提高求解能力，并通過仿真驗證了算法的優(yōu)越性。蘇析超等研究了一體化模式、大機組模式和單機機組模式下的甲板機務勤務作業(yè)調(diào)度問題，為保障作業(yè)人機匹配模式的選取提供了理論參考。文獻[5-7]研究了艦面保障作業(yè)調(diào)度和資源配置聯(lián)合優(yōu)化問題，并提出了高效的優(yōu)化求解算法框架。其中：文獻[6]給出了求解該類問題的通用超啟發(fā)式算法框架，降低了后續(xù)算法設計的復雜度；文獻[7]分別以邊際算法和人工蜂群算法為外、內(nèi)層框架，研究了人員配置數(shù)量對保障效率的影響；文獻[8-10]研究了不確定環(huán)境下的艦面保障作業(yè)魯棒調(diào)度問題，在算法中嵌入了有效的預約束調(diào)度策略和資源魯棒分配策略，給出了合理的魯棒調(diào)度求解方法。

本文首先分析了艦面保障作業(yè)流程，建立了多機艦面保障作業(yè)調(diào)度（multi-aircraft flight deck operation scheduling，MAFDOS）優(yōu)化模型；然后，設計了改進差分進化算法（modified differential evolution algorithm，MDE）用于模型求解，該算法采用基于作業(yè)開始時間改進的隨機鍵編碼方式和并行變異算子結構，提高了算法搜索效率；最后，設計了仿真試驗，給出了典型保障任務的調(diào)度方案，并研究了變異算子類型對于算法性能的影響。

1 MAFDOS模型建立

艦載機艦面保障作業(yè)調(diào)度問題是一類高度復雜的資源受限項目調(diào)度問題（resource-constrained project scheduling problem，RCPSP），作業(yè)過程中既有考慮作業(yè)工序的流程邏輯約束，也有保障人員、設備等的資源約束。此外，由于調(diào)度方案需要下達至單個作業(yè)單元（人員以及設備），因此，還需要考慮資源分配規(guī)則。

2 MDE算法描述

基于RCPSP 建立的MAFDOS 模型是一類具有NP-hard性質的復雜組合優(yōu)化難題，常規(guī)的分支定界等精確算法難以在有限時間內(nèi)求解。近年來，研究人員將重點多放在啟發(fā)式算法的設計與求解上。DE 是經(jīng)典的群智能進化算法，由Storn 等提出，目前，在優(yōu)化領域被廣泛應用。本文在傳統(tǒng)DE算法的基礎上，根據(jù)MAFDOS 問題的特點，采用基于作業(yè)開始時間改進的隨機鍵編碼方式和并行變異算子結構，以增強算法的搜索效率，提出了MDE 算法用于MAFDOS模型的求解。

2.1 MDE算法流程

MDE 算法偽代碼，如表1 所示。種群大小為。首先，初始化種群個體后，依次選擇當前種群個體作為目標向量（target vector）；其次，針對該目標向量，采用并行變異算子結構生成多個變異向量（mutation vector）；再次，針對各變異向量，采用交叉算子產(chǎn)生其跟蹤向量（trail vector）；最后，從跟蹤向量和目標向量中選擇最優(yōu)個體遺傳至下一代，達到算法停止準則之后，算法結束，輸出種群最優(yōu)個體。

表1 MDE算法偽代碼Tab.1 Pseudo code of MDE algorithm

續(xù)表

2.2 編碼

Debels 等指出，隨機鍵編碼和活動列表編碼是求解RCPSP 問題常用的編碼方式。任務列表編碼的缺陷是個體經(jīng)過交叉、變異等操作后，容易產(chǎn)生不滿足工序流程邏輯約束的非法編碼，若再采用修正機制修正非法編碼，則會顯著增加計算量。隨機鍵編碼則彌補了這一缺陷，其采用隨機鍵表示工序調(diào)度的優(yōu)先級（隨機鍵越小，調(diào)度優(yōu)先級越高）。1 種調(diào)度方案通?？梢詫鄠€隨機鍵編碼，這無疑增大了算法的搜索空間。為了進一步提升搜索效率，本文提出的MDE算法在隨機鍵編碼的基礎上，采用基于作業(yè)開始時間改進的隨機鍵編碼方式，如圖1 所示。個體解碼評價適應度后，以個體對應的調(diào)度方案中各工序的開始時間S代替?zhèn)€體編碼。采用這種編碼方式，可以確保個體編碼和調(diào)度方案的一一對應，在減小算法搜索空間的同時不丟失可行解。

圖1 基于作業(yè)開始時間修正的隨機鍵編碼Fig.1 Random key coding modified by the start time of the operation

2.3 解碼

解碼操作是指利用調(diào)度生成機制實現(xiàn)個體編碼向調(diào)度方案映射，是評價個體適應度的關鍵階段。RCPSP 問題的調(diào)度生成機制主要有串行調(diào)度生成機制和并行調(diào)度生成機制2類。并行調(diào)度生成機制解碼的搜索空間是解空間的1個子集，當問題規(guī)模較大時，不能保證會搜索到最優(yōu)解，因此，本文采用串行調(diào)度生成機制解碼，采用該機制實現(xiàn)個體解碼流程，如圖2所示。

圖2 串行調(diào)度生成機制流程圖Fig.2 Flow chart of the serial scheduling generation scheme

2.4 并行變異算子結構

變異算子用于產(chǎn)生變異向量，從而引導算法能夠持續(xù)探索解空間，避免算法陷入局部最優(yōu)。在DE 算法中，主要采用以下5類變異算子。

1）DE/rand/1變異

式（9）～（13）中：V表示第個變異向量的第次迭代編碼；X表示當前第個目標向量的第次迭代編碼；X～X表示隨機選取的5 個互不相同的個體；表示當前最優(yōu)個體；是變異率。

通常，采用單一變異策略雖會使DE 算法迅速收斂，但無法保證解的全局最優(yōu)性，因此，本文采用并行變異算子結構。針對同一目標向量X，同時采用多個變異算子分別生成變異向量，經(jīng)過交叉操作產(chǎn)生跟蹤向量后，從跟蹤向量和目標向量中選擇適應度最好的個體遺傳至下一代。

2.5 交叉操作

3 仿真試驗

本節(jié)通過構建案例進行仿真試驗，驗證模型和算法的有效性。假設某型航母甲板共有12 個保障停機位，可為艦載機提供燃油、電源、氧氣、氮氣和液壓油等5類消耗性資源。單機保障共有19道工序，各工序的“前驅—后繼”約束關系，如圖3 所示。工序1 和19分別是虛擬開始、結束工序，受文章篇幅限制，各工序工期及保障所需的資源未在文中列出。

圖3 單機保障工序流程圖Fig.3 Flow chart of operation scheduling of single aircraft

共設計3 組出動仿真任務，各任務艦載機保障所在停機位及入場時間情況，如表2所示，其中“—”表示該停機位無待保障艦載機。保障過程中共涉及航電、特設、機械和軍械4類保障人員，保障人員配置數(shù)量與任務規(guī)模相關：任務1中，各類人員配置數(shù)量分別為3、3、5、6；任務2中，各類人員配置數(shù)量分別為4、4、6、8；任務3中，各類人員配置數(shù)量分別為5、5、8、10。

表2 各出動仿真任務艦載機在不同停機位入場時間Tab.2 Parking spot of the aircraft and its released time 單位：min

MDE算法參數(shù)設置情況為：種群規(guī)模=50，交叉率=0.3，變異率=0.7，算法終止準則為評價次數(shù)達到5 000 次。采用DE/rand/1 和DE/best/1 變異算子組成并行變異算子結構，對3 組出動任務進行試驗仿真。為了驗證算法改進效果，采用DE 算法同步進行仿真試驗，DE 算法參數(shù)設置情況與MDE 算法相同。各任務保障完工時間收斂情況，如圖4所示。

圖4 保障完工時間收斂情況Fig.4 Convergence curve of the makespan

從圖4 可以看出，隨著保障規(guī)模的增大，MDE 算法所得最優(yōu)保障完工時間增大，且各仿真任務中MDE算法收斂性優(yōu)于DE 算法。任務1 的保障人員分配方案甘特圖，如圖5所示，其中，符號Lp表示第類第個保障人員，I-表示艦載機的第道工序。經(jīng)過檢驗，分配方案滿足各項約束，驗證了模型和算法的有效性。

圖5 任務1保障人員分配方案甘特圖Fig.5 Gantt chart of the personnel allocation plan in mission 1

進一步地進行仿真試驗，研究不同種類變異算子組成的并行變異算子結構對于MDE算法的影響。對第2.4節(jié)所示的5種類型的變異算子進行兩兩組合，共可產(chǎn)生10 種類型的并行變異算子結構，以數(shù)組[]表示并行變異算子結構中兩變異算子類型，和的取值均為1～5。針對3 組仿真任務，算法獨立運行10次，算法終止準則為評價次數(shù)達到5 000次，以10次獨立運行所得保障完工時間的平均值（Ave.）、最優(yōu)值（Bes.）作為性能指標，結果如表3所示。

表3 并行變異算子結構對MDE算法性能影響情況Tab.3 Influence of the parallel mutation operator structure on the algorithm performance單位：min

從表3 可以看出，由DE/best/1 和DE/rand/2 變異算子組成的并行算子結構在各組仿真任務中表現(xiàn)均優(yōu)于另一組合，因此，在后續(xù)使用中，可采用DE/best/1和DE/rand/2 構成的并行變異算子結構，以期獲得更優(yōu)的調(diào)度方案。

4 結論

本文研究了艦載機艦面保障作業(yè)優(yōu)化問題。在分析艦面保障作業(yè)流程約束的基礎上，以最小化艦面保障作業(yè)完工時間為目標函數(shù)，建立了MAFDOS 模型，設計了MDE算法用于模型求解。案例仿真表明，采用MDE算法生成的調(diào)度方案可以滿足MAFDOS模型的各項約束，可用于艦面保障作業(yè)調(diào)度方案的制定，MDE 算法收斂性優(yōu)于傳統(tǒng)DE 算法，由DE/best/1和DE/rand/2 變異算子組成的并行算子結構可以有效提高MDE算法的尋優(yōu)能力。