基于多層編碼遺傳算法的艦艇改造任務(wù)分配方法?

李一夫 宋貴寶 賈汝娜 張文鵬

（1.海軍航空大學(xué) 煙臺 264001）（2.國防大學(xué)聯(lián)合勤務(wù)學(xué)院研究生管理大隊 北京 100039）

1 引言

由于我國海域范圍遼闊且近年來海洋維權(quán)執(zhí)法任務(wù)繁重，提高我國海監(jiān)漁政執(zhí)法力量對有效管理海洋秩序、合理利用海洋資源、堅定維護(hù)海洋權(quán)益等方面具有現(xiàn)實意義。海軍艦艇退役以后，拆卸軍艦的重型武器系統(tǒng)、改裝新設(shè)備并移交海洋執(zhí)法部門一直都是世界各國的慣例。本文將多層編碼的遺傳算法作為工具，尋找最短時間改造退役軍艦的任務(wù)分配方案，可以在兼顧執(zhí)法船只整體噸位、續(xù)航能力、功能等有效執(zhí)法能力的同時，及時緩解執(zhí)行海洋維權(quán)船只不足的問題，最大限度地再利用退役軍艦的剩余價值。

2 問題描述

對退役軍艦的改造問題根本上是根據(jù)任務(wù)要求合理分配改造工序和船塢，從而提高改造作業(yè)過程效率的項目管理問題［1］。從數(shù)學(xué)的角度可以描述為：有n艘待改造的艦艇要在m個性能不同的船塢內(nèi)進(jìn)行改造，每艘艦艇需要經(jīng)歷q道工序，每艘艦艇的各工序可在不同船塢內(nèi)完成改造，最終尋求最短時間內(nèi)全部艦艇完成全部工序改造的優(yōu)化方案。此外，改造過程中還應(yīng)滿足以下假設(shè)：

1）同一時刻每個船塢只能進(jìn)行一艘艦艇一道工序的改造；

2）每道工序只能在同一個船塢內(nèi)完成且中途不可停工；

3）工序存在優(yōu)先級，但待改造艦艇和船塢無優(yōu)先級［2～5］。

3 確定工序優(yōu)先級

改造任務(wù)從系統(tǒng)工程的角度出發(fā)，工序存在排序問題。由于不同工序間相互關(guān)聯(lián)，改造先后順序直接影響改造流程的正常運(yùn)行，例如在加裝新設(shè)備之前應(yīng)先拆除原軍用設(shè)備、重設(shè)電氣系統(tǒng)等。從系統(tǒng)化、層次化的角度出發(fā)，運(yùn)用定性與定量相結(jié)合的方法——層次分析法［1］確定合理的工序優(yōu)先級可以較好體現(xiàn)項目管理的系統(tǒng)屬性。

4 模型建立

4.1 模型參數(shù)

1）待改造艦艇集 P=｛p1，p2，p3，…，pi，…，pn｝，pi表示第i艘待改造艦艇，i=1，2，3，…，n。

2）船塢集 M=｛m1，m2，m3，…，ms，…，mm｝，mj表示第j個船塢，j=1，2，3，…，m。

3）工序序列集 OP=｛op1，op2，op3，…，opq｝。

4）可選船塢 OPM=｛opi1，opi2，opi3，…，opik｝，opij=｛opij1，opij2，opij3，…，opijk｝表示艦艇 pi的工序 j可以選擇的加工機(jī)器。

5）改造艦艇的時間矩陣T，tij∈T，表示第i艘艦艇pi改造第j道工序的時間。

6）Aij為第 i艘艦艇開始第 j道工序的時刻，Eij為第i艘艦艇完成第j道工序的時刻。

7）工序間等待時間之和為λ。

4.2 優(yōu)化模型

工序確定。運(yùn)用層次分析法確定各工序的優(yōu)先級，并按優(yōu)先級由大至小的順序分別對應(yīng)工序集OP中第一至最后一個元素，即op1優(yōu)先級最高，op2次之，opq優(yōu)先級最低。

目標(biāo)函數(shù)。本文目標(biāo)是使加工所有艦艇所有工序的時間與工序間等待時間λ之和最小。

約束條件。同一時刻一艘艦艇只能在一個船塢內(nèi)進(jìn)行改造；同一時刻一個船塢只能改造一艘艦艇；且后一道工序必須在前一道工序完成后才可進(jìn)行。因此得到如下數(shù)學(xué)模型：

其中，nis表示某時刻s船塢內(nèi)第i艘艦艇的數(shù)量；nij表示某時刻i艦艇在第j個船塢內(nèi)的數(shù)量；Eij表示第i艘艦艇完成第 j道工序的結(jié)束時刻；Ai（j+1）表示第 i艘艦艇開始第（j+1）道工序的開始時刻；自變量x為優(yōu)化后的任務(wù)分配方案并最終可形成任務(wù)安排甘特圖，從而方便使用。

5 基于多層編碼遺傳算法求解過程及實現(xiàn)

5.1 算法流程

首先進(jìn)行種群初始化，確定初始解集，按整數(shù)編碼的方式對染色體進(jìn)行多層編碼，；計算適應(yīng)度值；利用輪盤賭方法對個體尋優(yōu)；利用整數(shù)交叉法產(chǎn)生新的個體；利用整數(shù)變異法得到變異后的優(yōu)秀個體；進(jìn)行判別選擇循環(huán)或者結(jié)束［6］。

5.2 算法實現(xiàn)

1）個體編碼

每個染色體按照整數(shù)編碼的方式反映一個可行解的二維特征，即工序和所選機(jī)器型號。待改造的艦艇總數(shù)為n，艦艇ni改造工序為mj時，則每個染色體的長度為

其中染色體的前半部分表示為所有艦艇的改造順序，后半部分表示為艦艇每道工序選擇的船塢序號。例如個體｛16543321//29885321｝“//”前后各有2個數(shù)組，各位置一一對應(yīng)?！?/”前面的數(shù)表示所有艦艇的改造順序，“//”后面的數(shù)表示艦艇的每道工序被處理的船塢序號。第一層編碼描述的改造順序為艦艇1→艦艇6→艦艇5→艦艇4→艦艇3→艦艇3→艦艇2→艦艇1；第二層編碼描述的船塢依次為船塢2→船塢9→船塢8→船塢8→船塢5→船塢3→船塢2→船塢1。

2）計算適應(yīng)度

染色體的適應(yīng)度為全部艦艇改造完成的總時間，公式為

其中time指全部改造任務(wù)完成時間，time越小該染色體越優(yōu)秀［7～8］。

3）選擇操作

采用輪盤賭法選擇適應(yīng)度較好（適應(yīng)度值大）的染色體［4］，個體選擇概率為

其中pi（i）表示染色體i在每次選擇中被選中的概率。

4）交叉操作

交叉操作創(chuàng)造出的新染色體是推動種群進(jìn)化的主要因素。交叉操作首先隨機(jī)選擇兩個染色體，在每個染色體的前位隨機(jī)選擇交叉位置進(jìn)行交叉操作［9～11］。

5）變異操作

變異操作獲得的新的個體是推動種群進(jìn)化另一個因素。首先利用變異算子從種群中隨機(jī)選取變異個體，然后選擇變異位置S1和S2，最后把個體中S1和S2位的工序和對應(yīng)的船塢序號交換位置［12］。

6 算例仿真實現(xiàn)

算例可描述為6艘待改造艦艇，在10個船塢內(nèi)進(jìn)行改造，除必須首先完成的“拆除軍用武器設(shè)備”這一道工序以外，每艘艦艇還需要經(jīng)歷5道工序，即總共6道工序。試尋找在最短時間內(nèi)完成所有艦艇改造的優(yōu)化方案。

首先確定工序的優(yōu)先級?！安鸪娪梦淦髟O(shè)備”作為固定的第一道工序，其優(yōu)先級最大，故只需要比較剩余五道工序。比較是兩兩工序之間進(jìn)行的比較，根據(jù)比較尺度表（見表1）請專家對兩兩工序的重要程度打分。用aij表示第i道工序相對于第j道工序的比較結(jié)果，得到比較矩陣A=（aij）。

該比較矩陣A的最大特征值λ=5.073，歸一化特征向量為Ω=［0.263，0.475，0.055，0.099，0.110］。為了判斷五個工序優(yōu)先級比較結(jié)果是否具有一致性，計算總排序一致性比率進(jìn)行檢驗。

故A通過一致性檢驗。按優(yōu)先級由大至小的順序分別命名工序為工序2至工序6。

然后，利用多層編碼遺傳算法尋找最優(yōu)任務(wù)分配。利用Matlab 2014a環(huán)境中謝菲爾德大學(xué)遺傳算法工具箱，按照上文建立的數(shù)學(xué)模型及多層編碼遺傳算法編程并進(jìn)行模擬仿真實驗，形成優(yōu)化方案。每個工序可選擇的船塢編號如表2所示，每道工序在對應(yīng)船塢內(nèi)的改造時間如表3所示。

表2 工序可選船塢表

表3 工序改造時間

各參數(shù)分別設(shè)為種群數(shù)量為40，最大遺傳代數(shù)為50，交叉率0.8，代溝0.9，變異率0.6。算法搜索得到最優(yōu)方案的完成時間為49，算法過程和反映最優(yōu)優(yōu)化方案的甘特圖分別如圖1和圖2所示。

7 結(jié)語

本文主要討論了退役艦艇改造任務(wù)分配問題。針對工序多、船塢多、艦艇多的任務(wù)特點選擇多層編碼遺傳算法篩選出最優(yōu)方案，算法經(jīng)驗證能得到穩(wěn)定解，效果良好，可以較好應(yīng)用于多維復(fù)雜問題的尋優(yōu)。本文為退役艦艇改造問題提供了解決方案，對實施項目的進(jìn)度管理、迅速生成海上執(zhí)法力量具有一定參考價值。

圖1 算法過程

圖2 最優(yōu)甘特圖