基于遺傳算法的編隊(duì)條件下艦船修理周期結(jié)構(gòu)優(yōu)化

朱曉軍 張 濤 彭 飛 李 鋼

1 海軍工程大學(xué) 船舶與動(dòng)力學(xué)院，湖北 武漢 430033 2 中國(guó)人民解放軍92956部隊(duì)，遼寧 大連 116041

1 引 言

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

2 修理周期結(jié)構(gòu)的數(shù)學(xué)描述

在文獻(xiàn)建立的修理周期結(jié)構(gòu)的數(shù)學(xué)描述基礎(chǔ)上，構(gòu)建修理周期結(jié)構(gòu)矩陣，如式（1）所示。基地級(jí)計(jì)劃修理的本質(zhì)是一種定時(shí)修理，雖然在實(shí)施基地級(jí)計(jì)劃修理時(shí)，根據(jù)艦船裝備的實(shí)際狀態(tài)，需要結(jié)合必要的視情和事后修理項(xiàng)目，但從確定艦船修理結(jié)構(gòu)的角度，關(guān)鍵是要明確艦船在規(guī)定的服役期內(nèi)基地級(jí)計(jì)劃修理的類別、修理時(shí)間和間隔周期這三個(gè)要素及其組合。因此，可以用矩陣MC表達(dá)修理周期結(jié)構(gòu)如下：

式中，ci＝［siti］；ti為 各個(gè) 狀態(tài) 的持 續(xù)時(shí)間，以“月”計(jì)；si為狀態(tài)變量，表示艦船在服役期內(nèi)所處于幾種狀態(tài)，si∈U，

以某型艦艇為例，其修理間隔期和在修時(shí)間如表1所示，組合形式如圖1所示，則其修理周期結(jié)構(gòu)矩陣可表示為：

在明確單艦修理結(jié)構(gòu)模型的基礎(chǔ)上，就可以進(jìn)行編隊(duì)內(nèi)艦艇的修理周期的組合優(yōu)化研究。

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

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

3 編隊(duì)條件下的修理調(diào)度模型

3.1 編隊(duì)修理周期結(jié)構(gòu)矩陣

借鑒文獻(xiàn)［1］建立編隊(duì)修理結(jié)構(gòu)矩陣的方法，假設(shè)一個(gè)典型編隊(duì)［5］中的作戰(zhàn)艦艇組成為指揮艦1艘，驅(qū)逐艦Dt艘，護(hù)衛(wèi)艦Ft艘，核潛艇St艘。編隊(duì)里每一艘艦艇的修理周期結(jié)構(gòu)都可以用修理周期結(jié)構(gòu)矩陣表示。若舍棄結(jié)構(gòu)矩陣中的狀態(tài)向量，并把編隊(duì)中各個(gè)艦艇的修理結(jié)構(gòu)矩陣組合起來(lái)，便產(chǎn)生了編隊(duì)修理周期結(jié)構(gòu)矩陣F＿M(jìn)C：

其中：

1）txyi表示編隊(duì)中艦艇的某種狀態(tài)的持續(xù)時(shí)間。 x 表示艦型，x＝c，d，f，s；y 表示一種艦型的某艘艦艇，y＝1，2，… Nx；i表示某艘艦艇修理周期結(jié)構(gòu)矩陣（MC）的狀態(tài)序號(hào)。例如，td22表示編隊(duì)中驅(qū)逐艦（用d表示）的第2艘艦艇處于修理周期結(jié)構(gòu)的第2個(gè)狀態(tài)。

2）此處規(guī)定艦艇均以可部署狀態(tài)進(jìn)入編隊(duì)，即在各艦艇修理周期結(jié)構(gòu)矩陣?yán)?，txy1對(duì)應(yīng)的sxy1＝0；x＝c，d，f，s；y＝1，2，… Nx。

3）y是對(duì)同種艦型中某艘艦艇的標(biāo)識(shí)，同艦型的各個(gè)艦艇進(jìn)入編隊(duì)的部署時(shí)間可以不同，即x相同、y不同時(shí)，txy1可以不相等。

4）編隊(duì)內(nèi)艦船的數(shù)目與矩陣的列數(shù)目對(duì)應(yīng)，即矩陣的列數(shù)等于1＋Dt＋Ft＋St。

5）調(diào)度矩陣的行數(shù)由編隊(duì)內(nèi)服役周期最長(zhǎng)的艦艇決定，修理周期結(jié)構(gòu)較短的艦船在矩陣?yán)飳?duì)應(yīng)的空缺位置用“0”補(bǔ)齊。一般情況下，指揮艦的服役周期最長(zhǎng)，故矩陣的行數(shù)等于m。

3.2 修理調(diào)度模型

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

為簡(jiǎn)化模型，認(rèn)為修理周期結(jié)構(gòu)的各個(gè)修理間隔期長(zhǎng)度是相同的，決策變量V＝［v1，v2，…，vn］，其中vj表示第j艘艦船的修理周期結(jié)構(gòu)中修理間隔期的變化。

優(yōu)化目標(biāo)函數(shù)為：

目標(biāo)函數(shù)中F（S）不是一個(gè)顯函數(shù)，它表示對(duì)調(diào)度矩陣的操作，其值表示編隊(duì)的部署時(shí)間。

當(dāng)編隊(duì)修理結(jié)構(gòu)矩陣中任意一列全為0，即有一艘艦艇到達(dá)其壽命終點(diǎn)要退出編隊(duì)時(shí)，便認(rèn)為整個(gè)編隊(duì)的服役期結(jié)束。

4 調(diào)度模型的求解與優(yōu)化

4.1 目標(biāo)函數(shù)的求解

修理調(diào)度模型中目標(biāo)函數(shù)F（S）根據(jù)編隊(duì)中各個(gè)艦艇服役的時(shí)間序列在編隊(duì)使用時(shí)間上的重合度進(jìn)行編寫。算法實(shí)現(xiàn)的功能為，給出一組決策變量即可求出相應(yīng)的編隊(duì)部署時(shí)間。其流程如圖2所示。

圖2 目標(biāo)函數(shù)的算法流程Fig.2 The flow chart of the object function

4.2 優(yōu)化—遺傳算法

在修理調(diào)度模型中根據(jù)決策變量的不同，可以組合出多種編隊(duì)的修理周期結(jié)構(gòu)。假設(shè)編隊(duì)由10艘艦艇組成，決策變量變化范圍vj∈［-2，8］。都取整數(shù)后每一個(gè)決策變量有10種取值，則有1010種組合方案，因而不宜采用一般的窮舉法尋找最優(yōu)解，必須采用一種簡(jiǎn)便的優(yōu)化工具來(lái)尋找，即尋找編隊(duì)的最大部署時(shí)間。

遺傳算法（Genetic Algorithm，GA）是借鑒生物界自然選擇和群體優(yōu)化的進(jìn)化機(jī)制而形成的一種全局尋優(yōu)算法，與傳統(tǒng)的優(yōu)化算法相比，遺傳算法具有以下優(yōu)點(diǎn)［8］：

1）不是從單個(gè)點(diǎn)，而是從多個(gè)點(diǎn)構(gòu)成的群體開始搜索。

2）在搜索最優(yōu)解的過(guò)程中，只需要由目標(biāo)函數(shù)值轉(zhuǎn)換得來(lái)的適應(yīng)值信息，而不需要導(dǎo)數(shù)等其他輔助信息，這對(duì)于目標(biāo)函數(shù)不是顯函數(shù)尤為適用。

3）搜索過(guò)程不易陷入局部最優(yōu)點(diǎn)。

所以本文選用遺傳算法并加以改進(jìn)后對(duì)模型進(jìn)行了優(yōu)化求解，遺傳算法的關(guān)鍵步驟如下：

1）染色體編碼與解碼

遺傳算法不對(duì)優(yōu)化問(wèn)題的實(shí)際決策變量進(jìn)行操作，所以應(yīng)用遺傳算法的首要問(wèn)題是通過(guò)編碼將決策變量表示成串結(jié)構(gòu)數(shù)據(jù)［9］。本文采用最常用的二進(jìn)制編碼方案，即用二進(jìn)制數(shù)據(jù)構(gòu)成的符號(hào)來(lái)表示一個(gè)種群個(gè)體。首先根據(jù)各決策變量的上下界及其搜索精度來(lái)確定各變量的二進(jìn)制串的長(zhǎng)度，然后用均勻分布的隨機(jī)數(shù)來(lái)生成初始種群的各個(gè)個(gè)體。

編碼后的個(gè)體構(gòu)成的種群必須經(jīng)過(guò)解碼，轉(zhuǎn)換成原問(wèn)題空間的決策變量實(shí)值，方能計(jì)算相應(yīng)的適應(yīng)值。假設(shè)某一變量的取值范圍為［U1，U2］，對(duì)應(yīng)的編碼公式為［10］：

2）選擇算子

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

3）交叉和變異

采用單點(diǎn)交叉的方法實(shí)現(xiàn)交叉算子，即按選擇概率Pc在兩兩配對(duì)的個(gè)體編碼串隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分基因，從而形成兩個(gè)新的個(gè)體。

對(duì)于二進(jìn)制的基因碼組成的個(gè)體種群，以變異概率Pm隨機(jī)選擇變異點(diǎn)并翻轉(zhuǎn)該點(diǎn)，即0變成1，1變成0，從而產(chǎn)生新的基因個(gè)體。

5 算法實(shí)例與討論

本文計(jì)算的編隊(duì)由1艘指揮艦、2艘驅(qū)逐艦、2艘潛艇和2艘護(hù)衛(wèi)艦共7艘艦艇組成。由各艦艇的修理結(jié)構(gòu)得到編隊(duì)修理周期結(jié)構(gòu)矩陣F＿M(jìn)C，其數(shù)據(jù)如表2所示（單位為月）。

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

表2 編隊(duì)的修理周期數(shù)據(jù)Tab.2 The maintenance period data of the fleet

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

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

使用組合臺(tái)式機(jī)進(jìn)行計(jì)算，機(jī)器配置有1.80 GHz的 Intel（R）Pentium（R）Dual E2160處理器，2.00 GB內(nèi)存。計(jì)算結(jié)果如表4所示。

表4 優(yōu)化計(jì)算結(jié)果Tab.4 The optimization results

由計(jì)算結(jié)果可知：

1）由圖3、圖4可以看出，算法遺傳100代后最佳個(gè)體及適應(yīng)值都能穩(wěn)定收斂，說(shuō)明用本算法優(yōu)化計(jì)算出的結(jié)果是可靠的。

2）編隊(duì)中各艦艇的部署時(shí)間依次加上約0.5，8，-2，4.2，6.3，-0.8，-0.8 個(gè)月后，編隊(duì)的部署時(shí)間可達(dá)近110個(gè)月，相對(duì)于沒有優(yōu)化前提高了50個(gè)月，該結(jié)果非?？捎^。

3）調(diào)整后，編隊(duì)內(nèi)3艘艦艇的修理間隔期均被延長(zhǎng)，最多的延長(zhǎng)了8個(gè)月。對(duì)于一艘新服役的艦艇，其壽命周期將延長(zhǎng)7年左右。

4）本算法遺傳進(jìn)化200代需要72.52 s，在實(shí)際應(yīng)用中比較高效。

6 結(jié) 論

本文在編隊(duì)的修理周期結(jié)構(gòu)模型的基礎(chǔ)上，建立了編隊(duì)修理調(diào)度模型，為定量分析編隊(duì)的部署能力奠定了基礎(chǔ)。模型利用改進(jìn)的遺傳算法對(duì)編隊(duì)的部署時(shí)間進(jìn)行了優(yōu)化，并取得了顯著的效果，但將一艘艦艇的服役期延長(zhǎng)7年左右，在實(shí)踐中是否可行還需進(jìn)一步的論證研究。

雖然本文提出了定量分析編隊(duì)條件下的艦船修理周期結(jié)構(gòu)，并運(yùn)用實(shí)例證明編隊(duì)的部署能力經(jīng)過(guò)優(yōu)化后可以大幅提高，但模型中沒有考慮編隊(duì)內(nèi)同一種艦型的多艘艦艇可以相互頂替使用等情況，這也將是下一步的研究重點(diǎn)。

［1］張濤，朱曉軍，彭飛.編隊(duì)作戰(zhàn)需求下艦船修理周期結(jié)構(gòu)的優(yōu)化［J］.中國(guó)修船，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］劉國(guó)華，包宏，李文超.用MATLAB實(shí)現(xiàn)遺傳算法程序［J］.計(jì)算機(jī)應(yīng)用研究，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］雷英杰，張善文，李續(xù)武，等.MATLAB遺傳算法工具箱及應(yīng)用［M］.西安電子科技大學(xué)出版社，2005.

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