基于改進遺傳算法的艦船物資轉(zhuǎn)運方案研究＊

2013-08-29 09:34:56趙彥森

艦船電子工程 2013年6期

王凱趙彥森

（海軍駐鄭州地區(qū)軍事代表室鄭州 450015）

1 引言

現(xiàn)代大中型水面艦船在執(zhí)行作戰(zhàn)任務(wù)以及進行海上補給的時候，需要在甲板和貯存艙室之間轉(zhuǎn)運大量的武器彈藥、零部件和生活物品等物資。為了滿足作戰(zhàn)需求并避免諸如彈藥等具有較高危險性的物資長時間暴露于甲板，需要安全高效地進行物資轉(zhuǎn)運［1～3］。因此，如何通過采用先進的技術(shù)手段和措施，獲得最優(yōu)的物資轉(zhuǎn)運方案，對于提高轉(zhuǎn)運效率和載艦安全性具有重要的意義。

本文建立了艦船物資轉(zhuǎn)運方案決策模型，并采用遺傳算法對模型進行了求解運算，有效解決了車輛配置和轉(zhuǎn)運路徑的優(yōu)化問題。

2 模型建立

2.1 問題描述

艦船物資通常由專用的轉(zhuǎn)運車進行轉(zhuǎn)運，其轉(zhuǎn)運可簡單描述為：假設(shè)在一次物資轉(zhuǎn)運任務(wù)中要將物資由中轉(zhuǎn)站轉(zhuǎn)運到n個貯存艙室，有m輛轉(zhuǎn)運車可供使用，要運往每個貯存艙室的物資量為wi（i＝1，2，…，n），每輛轉(zhuǎn)運車的最大裝載量為q，要合理安排車輛和轉(zhuǎn)運路徑，以使總路徑最短。

2.2 模型建立

令物資中轉(zhuǎn)站編號為0，各貯存艙室的編號為1，2，…，n，轉(zhuǎn)運車輛的編號為1，2，…，k，每個路徑（i，j）對應(yīng)的長度為lij，將該問題簡化為最短路徑問題，則目標函數(shù)為

并滿足以下約束條件：

其中：

式（2）表示在轉(zhuǎn)運過程中轉(zhuǎn)運車輛的載貨量不能超過其最大裝載量。

3 遺傳算法設(shè)計

3.1 編碼方案

由于遺傳算法不能直接處理解空間數(shù)據(jù)，因此必須將問題編碼，轉(zhuǎn)換成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)［4～5］。編碼的好壞直接影響選擇、交叉、變異等遺傳運算，是設(shè)計遺傳算法的關(guān)鍵和應(yīng)用難點之一。在這里，針對要解決的車輛配置和轉(zhuǎn)運路徑優(yōu)化問題，采用自然數(shù)編碼方法。圖1為染色體結(jié)構(gòu)圖，C1～Cn表示貯存艙室，其值為貯存艙室編號，長度由貯存艙室的數(shù)量決定。V1～Vm表示車輛分配，其值為該車輛所要保障的貯存艙室個數(shù)，長度由需要的車輛數(shù)決定。需要說明的是，實際上只有染色體的前半部分參與遺傳運算。

圖1 染色體結(jié)構(gòu)圖

如染色體［3 1 4 2 5∣2 3］表示用兩輛車從中轉(zhuǎn)站前往五個儲存艙室運送物資，第一輛車負責兩個貯存艙室的物資轉(zhuǎn)運，第二輛車負責三個貯存艙室的物資轉(zhuǎn)運，車輛分配和轉(zhuǎn)運方案為：

第一輛車：從物資中轉(zhuǎn)站出發(fā)，依次運送物資到3號貯存艙室和1號貯存艙室，返回中轉(zhuǎn)站。

第二輛車：從物資中轉(zhuǎn)站出發(fā)，依次運送物資到4號貯存艙室、2號貯存艙室和1號貯存艙室，返回中轉(zhuǎn)站。

3.2 種群的初始化

設(shè)定種群規(guī)模N，步驟如下：

1）對n個艙室隨機進行排序，得到染色體前n位C1～Cn；

2）按步驟1得到染色體的前n位從左到右進行計算，若前i個艙室要轉(zhuǎn)運的物資量小于或等于車輛的載重量q，并且前（i＋1）個艙室要轉(zhuǎn)運的物資量大于車輛的載重量q，則令染色體的V1為i，即該輛車負責前i個艙室的物資轉(zhuǎn)運；

3）從染色體的第（i＋1）位開始，按照步驟2對剩下的（n－i）個艙室從左到右進行計算，得到V2。如此反復(fù)，直到所有的艙室都被安排完畢，得到一個染色體。

4）重復(fù)前三步，直到得到N個染色體。

3.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是根據(jù)目標函數(shù)確定的用于區(qū)分群體中個體好壞的標準，是遺傳算法設(shè)計的一個重要方面，如果設(shè)計不當，可能造成某個局部最優(yōu)解，影響算法的全局優(yōu)化性能。針對本文要解決的問題，設(shè)計適應(yīng)度函數(shù)如下：

式中Lmax為一個適當?shù)南鄬Ρ容^大的數(shù)。

3.4 選擇算子

選擇算子對群體中的個體根據(jù)適應(yīng)度值大小進行優(yōu)勝劣汰操作，適應(yīng)度高的個體被遺傳到下一代群體中的概率較大。本文選用隨機遍歷抽樣，該算法使用N個相等距離的指針從隨機排列的種群中來選擇個體，每個個體被選擇的概率為

3.5 交叉算子

交叉運算產(chǎn)生的新個體具有父代的一部分遺傳物質(zhì)，交叉算子的設(shè)計和實現(xiàn)與具體問題密切相關(guān)，并要和編碼設(shè)計一同考慮。由于本文采用自然數(shù)編碼方式，進行交叉運算會產(chǎn)生大量不可行解，因此這里不進行交叉運算。

3.6 變異算子

變異操作模仿生物遺傳和進化過程中的基因突變現(xiàn)象，將個體染色體編碼串中的某些基因座上的基因值用其他等位基因來替換，從而形成一個新的個體。變異算子能夠改善遺傳算法的局部搜索能力，維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。遺傳算法中通常的變異算子不適用于本文的車輛配置和轉(zhuǎn)運路徑優(yōu)化問題，這里構(gòu)造了一種特殊的變異算子，即設(shè)定變異概率后，對每個要變異的個體隨機確定兩個基因位，將其基因值進行互換。

3.7 進化終止條件

當進化達到最大進化代數(shù)或連續(xù)幾代的適應(yīng)度值沒有明顯變化時，則停止進化得到最優(yōu)解。

4 算法驗證

為驗證本文所提算法的有效性，運用Matlab語言編程實現(xiàn)該算法，并針對國內(nèi)外常用的測試實例進行仿真計算。

4.1 小規(guī)模測試實例

為了便于比較，對參考文獻［8～12］都采用的實例進行計算。設(shè)定初始種群為60，最大進化代數(shù)為50，隨機進行20次計算，平均值為67.85，獲得最優(yōu)解67.5的百分率為80%，對應(yīng)的車輛分配和轉(zhuǎn)運方案為：［4 7 6 2 8 5 3 1∣3 5］。幾種算法結(jié)果對比見表1，可以看出本文算法的計算結(jié)果要優(yōu)于文獻［7，9～10］的結(jié)果，圖2為經(jīng)過50次迭代后最優(yōu)解的變化和種群均值的變化曲線。

表1 幾種算法20次計算結(jié)果的統(tǒng)計表

圖2 初始種群60迭代次數(shù)50

4.2 中等規(guī)模測試實例

為了驗證本文算法對于更大規(guī)模測試實例的有效性，從網(wǎng)址http：／／branchandcut.org／下載測試實例E－n22－k4進行計算。為了與文獻［12］進行對比分析，設(shè)定初始種群為60，最大進化代數(shù)為50，隨機進行10次運算，計算結(jié)果見表2，可見本文算法結(jié)果明顯優(yōu)于文獻［12］。圖3為經(jīng)過50次迭代后最優(yōu)解的變化和種群均值的變化曲線，獲得局部最優(yōu)解為431，對應(yīng)的車輛分配和轉(zhuǎn)運方案為：［19 21 20 17 10 2 1 6 8 11 13 16 18 15 12 14 3 4 7 5 9∣4 7 5 5］。