基于遺傳算法的編隊條件下艦船修理周期結構優化

朱曉軍 張 濤 彭 飛 李 鋼

1 海軍工程大學 船舶與動力學院，湖北 武漢 430033 2 中國人民解放軍92956部隊，遼寧 大連 116041

1 引 言

艦船修理周期結構指的是艦船在全壽命周期內所進行的基地級計劃修理類別、修理時間和間隔周期的組合，是艦船裝備技術保障實施科學管理的基本依據，直接關系到實施修理的有效性和經濟性、保障資源建設的科學性以及艦船的戰備完好性。對于單艦來說，它需要一個與自身型號及使用情況相適應的修理周期結構來指導其修理保障工作。編隊同樣也需要一套修理周期結構來保障編隊整體的使用和維修，這一套修理周期結構并不是編隊內所有艦艇作為單艦的修理結構的簡單疊加，而是經過組合優化形成的一套整體相互匹配的修理周期結構，所以合適的艦船修理結構是充分發揮編隊戰斗力的重要保證，也是提高整體作戰能力的基礎。我國艦船修理周期結構的研究以往多是從單艦客觀的維修需求和保障資源出發進行的優化，沒有考慮到編隊的整體使用需求。文獻［1］建立了編隊修理結構模型，從減少編隊修理時間的角度對編隊內各個艦艇的修理周期結構做出了優化。外國海軍的編隊使用較早，文獻［2-4］依據美海軍編隊的特點對編隊的修理周期結構進行了深入研究。本文將在已有艦船修理結構定量描述模型的基礎上建立編隊條件下的修理調度模型，分析編隊條件下單艦的修理周期結構優化問題，并采用改進的遺傳算法進行優化計算。

2 修理周期結構的數學描述

在文獻建立的修理周期結構的數學描述基礎上，構建修理周期結構矩陣，如式（1）所示。基地級計劃修理的本質是一種定時修理，雖然在實施基地級計劃修理時，根據艦船裝備的實際狀態，需要結合必要的視情和事后修理項目，但從確定艦船修理結構的角度，關鍵是要明確艦船在規定的服役期內基地級計劃修理的類別、修理時間和間隔周期這三個要素及其組合。因此，可以用矩陣MC表達修理周期結構如下：

式中，ci＝［siti］；ti為 各個 狀態 的持 續時間，以“月”計；si為狀態變量，表示艦船在服役期內所處于幾種狀態，si∈U，

以某型艦艇為例，其修理間隔期和在修時間如表1所示，組合形式如圖1所示，則其修理周期結構矩陣可表示為：

在明確單艦修理結構模型的基礎上，就可以進行編隊內艦艇的修理周期的組合優化研究。

表1 某型艦艇的修理周期數據Tab.1 The maintenance period data of a ship

圖1 某型艦艇的修理周期的組合形式Fig.1 The combination of a ship maintenance period

3 編隊條件下的修理調度模型

3.1 編隊修理周期結構矩陣

借鑒文獻［1］建立編隊修理結構矩陣的方法，假設一個典型編隊［5］中的作戰艦艇組成為指揮艦1艘，驅逐艦Dt艘，護衛艦Ft艘，核潛艇St艘。編隊里每一艘艦艇的修理周期結構都可以用修理周期結構矩陣表示。若舍棄結構矩陣中的狀態向量，并把編隊中各個艦艇的修理結構矩陣組合起來，便產生了編隊修理周期結構矩陣F＿MC：

其中：

1）txyi表示編隊中艦艇的某種狀態的持續時間。 x 表示艦型，x＝c，d，f，s；y 表示一種艦型的某艘艦艇，y＝1，2，… Nx；i表示某艘艦艇修理周期結構矩陣（MC）的狀態序號。例如，td22表示編隊中驅逐艦（用d表示）的第2艘艦艇處于修理周期結構的第2個狀態。

2）此處規定艦艇均以可部署狀態進入編隊，即在各艦艇修理周期結構矩陣里，txy1對應的sxy1＝0；x＝c，d，f，s；y＝1，2，… Nx。

3）y是對同種艦型中某艘艦艇的標識，同艦型的各個艦艇進入編隊的部署時間可以不同，即x相同、y不同時，txy1可以不相等。

4）編隊內艦船的數目與矩陣的列數目對應，即矩陣的列數等于1＋Dt＋Ft＋St。

5）調度矩陣的行數由編隊內服役周期最長的艦艇決定，修理周期結構較短的艦船在矩陣里對應的空缺位置用“0”補齊。一般情況下，指揮艦的服役周期最長，故矩陣的行數等于m。

3.2 修理調度模型

一般艦艇在服役期內進行的各基地級修理（塢修、小修、中修）都有規定的需要完成的維修項目，所以在修理周期結構矩陣MC中，基地級修理時間的可變化范圍很小，這里認為各基地級修理時間在 MC 中為常量，即 si＞2 時，txyi＝consti。 但艦船的修理間隔在不超過艦上重要裝備要求的最大修理間隔情況下，可調整的范圍比較大，如美軍艦艇在其國家戰略需求的牽引下，不斷延長修理間隔以達到更高的部署能力。自2003年美軍提出艦隊反應計劃后，其大型水面編隊的維修周期從24個月依次延長到27個月、32個月以及將來的42個月［6-7］。本文中的維修周期是指從一次基地級修理結束時刻至下一次基地級修理開始之間的時間。

為簡化模型，認為修理周期結構的各個修理間隔期長度是相同的，決策變量V＝［v1，v2，…，vn］，其中vj表示第j艘艦船的修理周期結構中修理間隔期的變化。

優化目標函數為：

目標函數中F（S）不是一個顯函數，它表示對調度矩陣的操作，其值表示編隊的部署時間。

當編隊修理結構矩陣中任意一列全為0，即有一艘艦艇到達其壽命終點要退出編隊時，便認為整個編隊的服役期結束。

4 調度模型的求解與優化

4.1 目標函數的求解

修理調度模型中目標函數F（S）根據編隊中各個艦艇服役的時間序列在編隊使用時間上的重合度進行編寫。算法實現的功能為，給出一組決策變量即可求出相應的編隊部署時間。其流程如圖2所示。

圖2 目標函數的算法流程Fig.2 The flow chart of the object function

4.2 優化—遺傳算法

在修理調度模型中根據決策變量的不同，可以組合出多種編隊的修理周期結構。假設編隊由10艘艦艇組成，決策變量變化范圍vj∈［-2，8］。都取整數后每一個決策變量有10種取值，則有1010種組合方案，因而不宜采用一般的窮舉法尋找最優解，必須采用一種簡便的優化工具來尋找，即尋找編隊的最大部署時間。

遺傳算法（Genetic Algorithm，GA）是借鑒生物界自然選擇和群體優化的進化機制而形成的一種全局尋優算法，與傳統的優化算法相比，遺傳算法具有以下優點［8］：

1）不是從單個點，而是從多個點構成的群體開始搜索。

2）在搜索最優解的過程中，只需要由目標函數值轉換得來的適應值信息，而不需要導數等其他輔助信息，這對于目標函數不是顯函數尤為適用。

3）搜索過程不易陷入局部最優點。

所以本文選用遺傳算法并加以改進后對模型進行了優化求解，遺傳算法的關鍵步驟如下：

1）染色體編碼與解碼

遺傳算法不對優化問題的實際決策變量進行操作，所以應用遺傳算法的首要問題是通過編碼將決策變量表示成串結構數據［9］。本文采用最常用的二進制編碼方案，即用二進制數據構成的符號來表示一個種群個體。首先根據各決策變量的上下界及其搜索精度來確定各變量的二進制串的長度，然后用均勻分布的隨機數來生成初始種群的各個個體。

編碼后的個體構成的種群必須經過解碼，轉換成原問題空間的決策變量實值，方能計算相應的適應值。假設某一變量的取值范圍為［U1，U2］，對應的編碼公式為［10］：

2）選擇算子

以模型的目標函數作為遺傳算法的適應度函數并以此計算各個個體的適應值。標準遺傳算法按與個體適應值成正比的概率來決定當前群體中各個個體遺傳到下一代群體中的機會的多少。在本算子中，采用了精英保留策略與賭輪算法相結合的思路。首先找出當前群體中適應值最高和最低的個體，將最佳個體保留并用其替換掉最差個體，直接進入下一代，這種劣種淘汰的方法提高了整個種群的競爭力［11］，然后將剩下的個體按賭輪算法進行操作。將這兩種方法相結合的目的是，在遺傳操作中，不僅能不斷提高群體的平均適應值，而且還能保證最佳個體不被交叉、變異等操作所破壞，可有效防止“早熟收斂”。

3）交叉和變異

采用單點交叉的方法實現交叉算子，即按選擇概率Pc在兩兩配對的個體編碼串隨機設置一個交叉點，然后在該點相互交換兩個配對個體的部分基因，從而形成兩個新的個體。

對于二進制的基因碼組成的個體種群，以變異概率Pm隨機選擇變異點并翻轉該點，即0變成1，1變成0，從而產生新的基因個體。

5 算法實例與討論

本文計算的編隊由1艘指揮艦、2艘驅逐艦、2艘潛艇和2艘護衛艦共7艘艦艇組成。由各艦艇的修理結構得到編隊修理周期結構矩陣F＿MC，其數據如表2所示（單位為月）。

將表2的編隊部署數據輸入到模型算法中，令 X＝［x1，x2…x7］＝［0，0…0］，則由目標函數 FDeployTime＝F（S）計算得出編隊整體的部署時間a＝60（月）。然后依照遺傳算法參數設置的一般原則（表3），并通過反復調試。

表2 編隊的修理周期數據Tab.2 The maintenance period data of the fleet

表3 遺傳算法的參數設置Tab.3 The setting of the genetic algorithm parameter

為提高艦艇的在航率，通用的做法是延長修理周期，但考慮到編隊內各艘艦艇的相互配合，也可適當縮短。因此，變量的范圍設定為xi∈［-2，8］，i＝1，2…7，可以根據需要進行調整。

使用組合臺式機進行計算，機器配置有1.80 GHz的 Intel（R）Pentium（R）Dual E2160處理器，2.00 GB內存。計算結果如表4所示。

表4 優化計算結果Tab.4 The optimization results

由計算結果可知：

1）由圖3、圖4可以看出，算法遺傳100代后最佳個體及適應值都能穩定收斂，說明用本算法優化計算出的結果是可靠的。

2）編隊中各艦艇的部署時間依次加上約0.5，8，-2，4.2，6.3，-0.8，-0.8 個月后，編隊的部署時間可達近110個月，相對于沒有優化前提高了50個月，該結果非常可觀。

3）調整后，編隊內3艘艦艇的修理間隔期均被延長，最多的延長了8個月。對于一艘新服役的艦艇，其壽命周期將延長7年左右。

4）本算法遺傳進化200代需要72.52 s，在實際應用中比較高效。

6 結 論

本文在編隊的修理周期結構模型的基礎上，建立了編隊修理調度模型，為定量分析編隊的部署能力奠定了基礎。模型利用改進的遺傳算法對編隊的部署時間進行了優化，并取得了顯著的效果，但將一艘艦艇的服役期延長7年左右，在實踐中是否可行還需進一步的論證研究。

雖然本文提出了定量分析編隊條件下的艦船修理周期結構，并運用實例證明編隊的部署能力經過優化后可以大幅提高，但模型中沒有考慮編隊內同一種艦型的多艘艦艇可以相互頂替使用等情況，這也將是下一步的研究重點。

［1］張濤，朱曉軍，彭飛.編隊作戰需求下艦船修理周期結構的優化［J］.中國修船，2011，21（4）：51-55.

［2］Chief of Naval Operation.Representative intervals，durations，maintenance cycles，and repair mandays for depot level maintenance availabilities of U.S.navy ships ［R］.OPNAV Notice 4700，June 13，2005.

［3］JACOBS K S，ROBERT L C.The maintenance requirements system：risk-based resource planning comes of ages［C］／／American Society of Naval Engineers Conference，2001.

［4］ROLAND J Y，JAMES G K，JOHN F S，et.al.Increasing aircraft carrier forward presence：changing the length of the maintenance cycle［R］.RAND，2008.

［5］MATTHEW H H，MATTHEW W C.The impact of longteam aircraft carrier maintenance scheduling on the fleet readiness plan［D］.Naval Postgraduate school，Monterey，California，2004，9.

［6］ROLAND J Y，JOHN F S，JAMES G K.Aircraft carrier maintenance cycles and their effects［R］.RAND，2008.

［7］ROLANDLY J Y，RAJ R，JESSIE R.Impacts of the fleet response plan on surface combatant maintenance ［R］.RAND，2006.

［8］劉國華，包宏，李文超.用MATLAB實現遺傳算法程序［J］.計算機應用研究，2001，18（8）：80-82.

［9］ROLAND J Y，JOHN F S，JAMES G K.A methodology for estimating the effect of carrier operational cycles on the maintenance industrial base［R］.RAND，2007.

［10］雷英杰，張善文，李續武，等.MATLAB遺傳算法工具箱及應用［M］.西安電子科技大學出版社，2005.

［11］夏華波，紀卓尚，張明霞.改進遺傳算法在駁船配載中的應用［J］.中國艦船研究，2010，5（6）：51-55.