基于改進NSGA Ⅱ算法的艦載機保障作業調度

張 勇

(1.海軍航空大學 航空作戰勤務學院， 山東 煙臺 264001; 2.清華大學 精密儀器系， 北京 100084)

1 引言

航空保障調度系統正常運行是實現艦載機出動回收的基礎，提高艦載機保障作業調度能力對于提升航母編隊整體作戰效能具有重要意義[1]。

近年來，艦載機保障作業調度處于由智能優化調度向人機交互智能決策調度的過渡階段。Dastidar等[2]提出了基于排隊網的艦載機保障作業調度方法，各保障站位視為網絡中的節點，將調度問題被轉化為訪問節點的決策問題。Yu等[3]基于柔性作業車間調度模型，提出了艦載機保障作業調度問題的混合整數規劃模型。Su等[4]研究了不確定工時保障作業魯棒調度問題，并提出了魯棒調度機制，設計了魯棒調度算法。李經等[5]以尼米茲航母多站式保障為背景，研究了艦載機多站式保障調度問題，并利用遺傳算法求解問題，但沒有給出具體人員和設備的調度方案。韓維等[6]詳細描述了單機保障作業流程，分析了保障作業約束，建立了基于計劃評審技術的多機一體化機務保障作業調度模型。蔣婷婷等[7]針對艦載機集中式保障模式，綜合考慮保障中的工序邏輯約束和資源約束，建立了艦載機集中式保障調度動態分層目標優化模型。蘇析超等[8]研究了不同人機匹配模式下的艦載機機務勤務保障調度問題，通過仿真試驗表明，一體化保障模式具有更高的保障效率和人員負載均衡性。

隨著艦載機“綜合保障”概念的提出與實踐，機務保障人員“一專多能”已成為發展趨勢。在一體化保障模式下，艦載機艦面保障作業需要機務保障人員可以完成跨專業、多工種的保障工作，因此機務保障人員專業合并是艦載機艦面保障作業需要研究的問題。本文首先建立了保障作業與資源配置聯合優化(joint optimization for flight deck operations and resource allocation,JOFDORA)模型。然后，設計了改進的NSGA Ⅱ算法(improved nondominated sorting genetic algorithm Ⅱ,iNSGA Ⅱ)用于模型求解。在個體選擇階段，采用k-means聚類方法將種群個體分組，在不同分組中分別選取個體用于種群進化。在進化階段，采用正態分布取樣變異算子控制基因變異范圍。種群合并后，采用刪減策略去除聯合種群重復個體。最后基于案例仿真，驗證了模型和算法的有效性，研究了保障人員專業合并對于艦載機保障作業調度效能的影響。

2 數學模型

艦載機在出動之前需要進行加油、掛彈、充氧、通電等保障作業，以維持其良好的作戰性能。艦載機進入保障停機位之后，各專業機務保障人員按照既定的工序執行順序，進行艦載機的保障作業，作業過程中，各類固定保障設備為各項工序作業提供油、液、氣、電等供給類資源。為提高保障效率，甲板上還配置一定數量的移動保障設備。受供給能力的制約，各供給類資源僅可同時為一定數量的保障設備提供服務。各工序存在多種執行模式，不同執行模式需要的保障人員數量不同，但需要的保障設備數量相同。保障人員在執行工序時，需要占據一定的工位空間。艦載機艦面作業調度問題可視為滿足工序邏輯約束和資源約束條件下的資源受限項目調度問題。JOFDORA模型中涉及的符號描述如表1所示。

表1 JOFDORA模型符號表

續表(表1)

建立的JOFDORA模型如下：

(1)

Si1≥Exi, ?i∈I

(2)

Sij≥Eih, ?(i,h)∈Pij, ?(i,j)∈J

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

其中：式(1)表示模型的目標函數為最小化保障完工時間和最小化保障人員、移動保障設備配置數量；式(2)表示艦載機各保障工序最早開始時間為其進入保障停機位的時間；式(3)為工序邏輯約束，只有當某工序的所有緊前工序完成后，該工序才可以開始；式(4)為工序的執行模式約束；式(5)表示工序的開始與結束時間決策變量的關系；式(6)表示保障人員轉移時序約束，只有當保障人員從前一個保障工位轉移至待調度工序工位后，待調度工序才可以開始執行；式(7)表示保障設備只能對其覆蓋范圍內的艦載機提供資源服務；式(8)表示保障設備的轉移時序約束；式(9)表示工位空間最大容納人員量約束；式(10)表示供給類資源最大供給量約束；式(11)和(12)表示調度方案中的人員及設備的分配量與需求量關系；式(13)、(14)表示決策變量關系約束。

3 iNSGA Ⅱ算法

JOFDORA問題屬于大規模多目標組合優化問題，以群智能優化算法等為代表的元啟發式算法在此類問題中應用效果較好[9-12]。NSGA Ⅱ算法[13]作為經典的多目標進化算法，在多目標優化領域具有廣泛的應用，但NSGA Ⅱ算法存在非支配個體多樣性低，個體在目標函數空間分布性差等缺點，本文在NSGA Ⅱ算法基礎上，采用k-means聚類方法將種群分組[14]，并在種群合并后采用刪減策略去除聯合種群重復個體，提出了iNSGA Ⅱ算法，用于JOFDORA模型的求解。

3.1 算法整體流程

iNSGA Ⅱ算法流程如圖1所示，N為種群個體數量。在個體選擇階段，采用k-means聚類方法將種群個體分為k組，然后隨機選擇兩組，分別在兩組中采用二元錦標賽方式選擇一個個體，2個個體經過交叉、變異后產生子代。父代種群與子代種群合并后，采用刪減策略去除聯合種群中重復個體，然后進行重組裁剪，產生新的父代種群。重復以上過程，直至達到最大評價次數，輸出父代種群個體及個體對應的調度方案，算法終止。

3.2 編碼與解碼

采用四段編碼方案，第一段編碼用于表示工序調度的優先級[15]。第二段編碼用于表示機務保障人員配置數量，記人員資源強度為RS，第k(k∈Kp)類專業人員配置數量|Lpk|由式(15)計算得到：

(15)

目標函數f2、f3可將個體編碼中第二、三段編碼對應的數值分別相加計算得到。對于目標函數f1，采用串行調度生成機制將工序調度優先級轉換為可行調度方案，進而得到保障完工時間[16]。

圖1 iNSGA Ⅱ算法流程框圖

3.3 k-means聚類算法

經過重組裁剪得到新的父代種群后，需要從中選擇個體執行交叉、變異操作，以實現種群的進化。若直接從父代種群中選取個體，容易導致進行交叉操作的個體相似度過高，進而導致子代個體與父代個體差異性小，降低種群個體多樣性，最終得到的Pareto最優解集分布性變差。本文采用k-means聚類算法將父代個體分為k組，然后從不同組中分別選取個體，提高了選擇個體的差異性，提高算法的搜索能力。k-means聚類算法的偽代碼如下:

Algorithm：k-means algorithm

Input：k, parents populationPpop

Randomly selectkindividuals fromPpopas cluster centers

Repeat

Foreach individualpinPpop

Calculate the Euclidean distance betweenpand each cluster center in the objective space

Reassignpto the cluster with the minimum Euclidean distance

Update the cluster center as the mean value of members in the objective space for each cluster

Untilclusters do not change

Output:kclusters

首先隨機選取父代種群中的k個個體作為各組聚類中心，然后計算父代種群中各個體到這k個聚類中心的歐式距離(目標函數空間)，將其歸入歐式距離最小的組，全部個體分組完畢后，計算各組目標函數均值作為新的聚類中心。重復以上過程，直至聚類結果不發生改變。

3.4 選擇、交叉與變異

在交叉階段，對選擇的子代個體的每一段編碼實行單點交叉操作。對于完成交叉操作的2個子代個體編碼進行變異操作，其中對于第一、二、四段編碼采用均勻變異方式。為了能夠使算法在相同或相近的人員配置數量下通過迭代進一步壓縮算法得到的機群保障完工時間，對于第三段編碼采用正態分布取樣變異方式，對子代個體的第三段編碼中的人員配置數量|Lpk|，用均值為|Lpk|，方差為1的正態分布隨機數替代，即

|Lpk|←?norm(|Lpk|,1)」

(16)

若隨機數為負數，則重新生成隨機數。各段編碼的變異率分別是pmut1，pmut2，pmut3，pmut4。

算法中共涉及兩次個體選擇。首先在種群聚類操作后，從k組父代種群中隨機選取兩組，在每組種群中選擇2個父代個體，比較2個父代個體的適應度函數值，選取適應度好的個體作為子代。其次是在重組裁剪時，依次按照適應度高、非支配排序序值低、擁擠度小的原則，從聯合種群中擇優選擇N個個體作為新的父代種群，用以執行下一次的種群進化。

3.5 刪減策略

聯合種群經過非支配快速排序后，按照個體序值從大到小的順序，依次判斷目標函數空間內有無重復個體，若有，則將重復個體刪除。經過個體刪減后，聯合種群中的每個個體在目標函數空間中都有唯一的位置，避免重復個體進入下一次的種群進化階段，提高種群個體的多樣性，提高進化效率。需要注意的是，經過個體刪減后，聯合種群中應至少保留N個個體，否則無法完成后續種群的重組裁剪操作。

4 仿真試驗及分析

4.1 案例描述

航母甲板共有16個保障停機位，仿真試驗中共設計了任務1～任務3三類保障任務。機務保障人員共有4個專業類型，勤務保障設備共有5種類型，供給類資源共有5種類型，每類勤務保障設備均需要消耗對應的供給類資源，僅考慮座艙一種類型的工位空間，可同時容納的保障人員數量為1。人員資源強度上下限分別為RSU=3.9和RSL=2.0。各類型移動類保障設備配置數量上下限分別取NeU=3,NeL=0。受篇幅限制，文中沒有給出各工序工期、執行模式及其所需的資源類型，保障人員和保障設備在工位之間的轉移時間，以及勤務保障設備的覆蓋范圍。

考慮到特設和航電2個專業的保障內容、維護設備具有一定的相似性，因此本文將2個專業合并為綜合航電專業。

4.2 仿真結果分析

iNSGAⅡ算法參數設置為種群數量N=100，各段編碼的變異率分別是pmut1=0.05，pmut2=0.2，pmut3=0.2，pmut4=0.2，k-means聚類數量k=10。算法的終止條件為評價次數達到5 000次，算法獨立重復運行10次，將10次仿真得到的Pareto最優解集合并，作為最終的仿真結果。

為了更加清楚地反映保障人員專業合并之后對調度方案的影響，將任務1～任務3的專業合并前、后移動保障設備配置數量分別為3、4時的Pareto最優解單獨提取出來，結果如圖2—圖4所示。

圖2 專業合并前、后任務1的Pareto最優解曲線

圖3 專業合并前、后任務2的Pareto最優解曲線

圖4 專業合并前、后任務3的Pareto最優解曲線

由圖2—圖4可以發現，在相同的機務保障人員和移動保障設備配置數量下，專業合并之后同一保障任務的保障完工時間普遍小于專業合并之前。隨著保障任務規模的擴大，專業合并對于保障效率的提升效果越來越顯著。在移動保障設備配置數量相同的情況下，隨著機務保障人員配置數量的增加，專業合并前后保障完工時間差值逐漸減小，這是由于機務保障人員配置數量增加后，其對于保障完工時間的約束性減小，保障完工時間主要受移動保障設備和甲板消耗性資源的限制，專業合并對于保障效率提升的效果不再顯著。因此，在機務保障人員配置數量受限的情況下，專業合并會顯著提升給機務勤務保障效率，縮短保障完工時間。

5 結論

構建了JOFDORA模型，在NSGA Ⅱ算法基礎上，采用k-means聚類方法將種群分組，并增加了刪減策略，提出了iNSGA Ⅱ算法用于模型的求解。在試驗仿真部分，討論了航電和特設專業的機務保障人員合并對于保障效率的影響。結果表明，在機務保障人員配置數量受限的情況下，專業合并會顯著提升艦載機保障效率，縮短保障完工時間。