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

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

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

1 引言

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

2 問(wèn)題描述

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

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

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

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

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

改造任務(wù)從系統(tǒng)工程的角度出發(fā)，工序存在排序問(wèn)題。由于不同工序間相互關(guān)聯(lián)，改造先后順序直接影響改造流程的正常運(yùn)行，例如在加裝新設(shè)備之前應(yīng)先拆除原軍用設(shè)備、重設(shè)電氣系統(tǒng)等。從系統(tǒng)化、層次化的角度出發(fā)，運(yùn)用定性與定量相結(jié)合的方法——層次分析法［1］確定合理的工序優(yōu)先級(jí)可以較好體現(xiàn)項(xiàng)目管理的系統(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個(gè)船塢，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）改造艦艇的時(shí)間矩陣T，tij∈T，表示第i艘艦艇pi改造第j道工序的時(shí)間。

6）Aij為第 i艘艦艇開(kāi)始第 j道工序的時(shí)刻，Eij為第i艘艦艇完成第j道工序的時(shí)刻。

7）工序間等待時(shí)間之和為λ。

4.2 優(yōu)化模型

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

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

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

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

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

5.1 算法流程

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

5.2 算法實(shí)現(xiàn)

1）個(gè)體編碼

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

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

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

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

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

3）選擇操作

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

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

4）交叉操作

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

5）變異操作

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

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

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

首先確定工序的優(yōu)先級(jí)。“拆除軍用武器設(shè)備”作為固定的第一道工序，其優(yōu)先級(jí)最大，故只需要比較剩余五道工序。比較是兩兩工序之間進(jìn)行的比較，根據(jù)比較尺度表（見(jiàn)表1）請(qǐng)專(zhuān)家對(duì)兩兩工序的重要程度打分。用aij表示第i道工序相對(duì)于第j道工序的比較結(jié)果，得到比較矩陣A=（aij）。

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

故A通過(guò)一致性檢驗(yàn)。按優(yōu)先級(jí)由大至小的順序分別命名工序?yàn)楣ば?至工序6。

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

表2 工序可選船塢表

表3 工序改造時(shí)間

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

7 結(jié)語(yǔ)

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

圖1 算法過(guò)程

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