薄志斌，胡 義

(武漢理工大學(xué) 能源與動(dòng)力工程學(xué)院，湖北 武漢 430063)

0 引言

傳統(tǒng)的配載方案一般是由大副或港口工人通過經(jīng)驗(yàn)憑借手工方式完成，這樣的配載方案一方面耗時(shí)耗力，另一方面由于人工的疏忽會(huì)出現(xiàn)計(jì)算偏差。船舶貨運(yùn)量的大幅增加和航次路線的越來越復(fù)雜，使得傳統(tǒng)方案越來越不適合當(dāng)今的發(fā)展趨勢(shì)[1]。

國(guó)外，早在20世紀(jì)90年代中期就開始研究散貨船的配載并在計(jì)算機(jī)上開發(fā)相關(guān)的配載軟件,其中:德國(guó)的SCHIFFKO公司開發(fā)了基于DOS環(huán)境的船舶計(jì)算軟件；挪威的Autoship Systems Corporation公司開發(fā)出一款名稱為Autoload的船用裝載儀[2]。國(guó)內(nèi)，大連海事大學(xué)史國(guó)友教授分析了貨物在散貨船的實(shí)際裝載情況，建立約束條件，然后用靜水力數(shù)據(jù)開發(fā)出散貨船配載儀。另外，還有福海船舶配載儀，這是一款涵蓋了谷物穩(wěn)性計(jì)算和破艙穩(wěn)性計(jì)算等很多實(shí)用功能的裝載軟件。

為此，從20世紀(jì)90年代起，散貨船的配載優(yōu)化和自動(dòng)化配載就已經(jīng)成為了相關(guān)領(lǐng)域內(nèi)的研究熱點(diǎn)。隨著計(jì)算機(jī)的廣泛應(yīng)用，關(guān)于船舶配載的軟件也慢慢開始出現(xiàn)，可以通過手動(dòng)輸入船舶的一些參數(shù)來完成配載的計(jì)算，但是這種配載方案仍然需要人工的干預(yù)調(diào)整，才能計(jì)算出最優(yōu)的結(jié)果。近幾年來隨著人工智能的不斷發(fā)展，該技術(shù)也逐漸在航海領(lǐng)域得到了廣泛的應(yīng)用，散貨船的智能配載研究就是人工智能在航運(yùn)業(yè)上的一種重要應(yīng)用。智能化的配載方案不僅可以提高船舶在航行過程中的穩(wěn)性和強(qiáng)度等，有利于船舶的運(yùn)輸安全，并且還會(huì)提高配載效率，降低船舶的運(yùn)營(yíng)成本[2]。本文從當(dāng)前的配載軟件市場(chǎng)出發(fā)，引進(jìn)遺傳算法對(duì)散貨船配載進(jìn)行研究，主要對(duì)配載系統(tǒng)中的約束條件從適應(yīng)度縮放、模擬退火拉伸、加入精英保留法三個(gè)方面對(duì)配載系統(tǒng)進(jìn)行研究。

1 散貨船的遺傳算法優(yōu)化

1.1 遺傳算法的主要操作

遺傳算法的基本操作步驟：選擇(Selection)、交叉(Crossover)和變異(Mutation)。遺傳算法的執(zhí)行中有編碼操作和譯碼操作，其中編碼操作就是將表現(xiàn)型轉(zhuǎn)換到基因型，從基因型轉(zhuǎn)換到表現(xiàn)型被稱為譯碼操作。遺傳算法在進(jìn)行分析的時(shí)候只是將一個(gè)種群看作是一個(gè)對(duì)象來對(duì)其進(jìn)行分析，然后進(jìn)行編碼、計(jì)算適應(yīng)值、遺傳操作和篩選等步驟，這幾個(gè)方式都賦予了遺傳算法一定的優(yōu)勢(shì)[3]。遺傳算法實(shí)現(xiàn)的基本流程見圖1。

1.2 程序設(shè)計(jì)流程

遺傳優(yōu)化程序的基本流程見圖2。從圖2可知，通過船舶基本參數(shù)來確定散貨船的浮態(tài)和強(qiáng)度。為了滿足散貨船的約束條件，保證船舶在運(yùn)營(yíng)中的安全性，要對(duì)遺傳算法的參數(shù)進(jìn)行限制。

1.3 遺傳編碼的確定

編碼是設(shè)計(jì)遺傳算法的一個(gè)關(guān)鍵步驟，編碼的好壞將直接影響到遺傳算法后面的選擇、交叉、變異等操作步驟。遺傳算法的一大難點(diǎn)就是選擇一個(gè)合適的編碼方案，針對(duì)一個(gè)具體的應(yīng)用問題時(shí)，首要目標(biāo)就是找到其編碼方案[4-5]。

圖1 遺傳算法基本流程

Gen—遺傳的代次。

本文研究的76 000 t遠(yuǎn)洋散貨船共有7個(gè)貨艙，本次遺傳算法優(yōu)化采用兩輪裝貨的編碼方案。

隨機(jī)產(chǎn)生的初始解有可能出現(xiàn)強(qiáng)度或者穩(wěn)性不合格的情況，為此對(duì)遺傳算法的初始解進(jìn)行改進(jìn)，可以采用第一輪裝入貨艙預(yù)計(jì)裝載量的1/2。

2 散貨船配載系統(tǒng)對(duì)約束條件的處理

基于遺傳算法的配載系統(tǒng)約束條件主要包括以下4點(diǎn)：

(1)艏艉吃水在散貨船裝貨過程中的任意狀態(tài)下都不允許超過裝貨港的限制。

(2)船舶吃水差在散貨船裝貨過程中的任意狀態(tài)下都要在限定范圍之內(nèi)。

(3)各個(gè)校核點(diǎn)的剪力占該處剪力許用值的百分比不超許用值，且盡量小。

(4)初穩(wěn)性滿足規(guī)范要求。

對(duì)于不滿足上述4個(gè)約束條件中任何一個(gè)條件的個(gè)體，裝載儀軟件中的約束條件函數(shù)會(huì)自動(dòng)將其剔除出當(dāng)前種群。

具體的操作步驟是：散貨船配載對(duì)種群進(jìn)行適應(yīng)度計(jì)算時(shí)，對(duì)上面的4個(gè)約束條件依次進(jìn)行初始判斷，不符合的個(gè)體直接淘汰，并將其適應(yīng)度f強(qiáng)制清零。符合的個(gè)體才依次進(jìn)行其他操作，所以這些不能滿足約束條件要求的個(gè)體將無法被遺傳到下一代[6]。

2.1 適應(yīng)度的縮放

遺傳算法中適應(yīng)度對(duì)最終的優(yōu)化結(jié)果有直接的影響，所以對(duì)適應(yīng)度的選擇是極其重要的。一般遺傳算法的適應(yīng)度是固定不變的，但是這樣存在著一些缺點(diǎn)。固定的適應(yīng)度可能使早期種群中優(yōu)秀的個(gè)體大部分都可以進(jìn)入下一代，不僅會(huì)帶來早熟的現(xiàn)象，而且會(huì)使種群的多樣性受到影響，不能將早期較差個(gè)體中含有的部分優(yōu)秀基因展示出來。這時(shí)，就需要采用適應(yīng)度的縮放。早期適應(yīng)度較低，能充分發(fā)揮每個(gè)個(gè)體中的基因作用；后期將適應(yīng)度放大，擴(kuò)大優(yōu)秀個(gè)體之間的差異，從而能更好地得出最優(yōu)解。

f′=af+b

(1)

式中：f′為縮放后的適應(yīng)度;f為原來的適應(yīng)度;a、b為系數(shù)。

2.2 模擬退火拉伸

Pau1 L.Stoffa提出了模擬退火拉伸?？梢詫⒋藨?yīng)用于遺傳算法當(dāng)中，使遺傳算法具有適度的拉伸作用。

(2)

式中：fi為第i個(gè)的個(gè)體適應(yīng)度；n為種群個(gè)數(shù)總數(shù)；g為遺傳代數(shù)序號(hào)；T為溫度；T0為初始溫度。

采用模擬退火拉伸，目的在于使早期的個(gè)體在溫度高時(shí)產(chǎn)生后代的概率相差不大，充分保障了種群的多樣性。當(dāng)遺傳后期溫度下降后，拉伸作用將越來越明顯，使優(yōu)秀的個(gè)體同普通個(gè)體拉開差距，從而獲得遺傳算法的優(yōu)秀解[7]。

2.3 加入精英保留法

Grefenstette提出了精英保留策略。由于遺傳算法的包容性，可以在本次配載當(dāng)中加入精英保留策略。遺傳算法中使用精英保留策略的主要目的就是為了使群體當(dāng)中最優(yōu)的個(gè)體不至于被淘汰，雖然最優(yōu)的個(gè)體進(jìn)化到下一種群的概率是很高的，但是以防萬一，最保險(xiǎn)的就是將其直接復(fù)制到下一個(gè)種群當(dāng)中，百分百概率保留，并將新種群當(dāng)中隨機(jī)的一個(gè)種群個(gè)體或者最差的一個(gè)種群個(gè)體淘汰。這樣進(jìn)行操作可以幫助遺傳算法優(yōu)化的速度加快，并且保障了最優(yōu)解的存在[8]。

3 軟件開發(fā)

結(jié)合上面理論知識(shí)，用C++語言在Windows環(huán)境下完成裝載儀在遺傳算法下進(jìn)行貨物配載的開發(fā)工作。裝載儀編碼程序中構(gòu)建遺傳算法的個(gè)體和種群兩個(gè)類，其中個(gè)體對(duì)應(yīng)Individual，Generation對(duì)應(yīng)種群。

(1)定義Individual類包括的成員變量和成員函數(shù)

設(shè)置個(gè)體染色體字符串、個(gè)體適應(yīng)度和各艙第一輪的裝貨量的代碼和相應(yīng)操作的代碼。

成員變量：Bool m_chrom[]

//個(gè)體染色體字符串

Float m_fitness

//個(gè)體適應(yīng)度

Int m_xl～m_x7

//1～7輪的裝貨量

成員函數(shù)：Void Initial()

//初始化

Void GetX()

//解碼

Float Getiftness (int x1,int x2,int x3,int x4,

int x5,int x6,int x7)

//返回個(gè)體適應(yīng)度

Void Update()

//更新

(2)定義Generation類包括的成員變量和成員函數(shù)

設(shè)置遺傳算法中父代種群、子代種群、種群中最優(yōu)個(gè)體、最優(yōu)個(gè)體的適應(yīng)度、最優(yōu)裝貨順序的代碼和相應(yīng)操作的代碼。

成員變量：Individual m_oldpop[]

//父代種群

Individual m_newpop[]

//子代種群

Individual m_bestone

//最優(yōu)個(gè)體

Float m_bestiftenss

//最優(yōu)個(gè)體適應(yīng)度

Floatm_bestsequenee[]

//最優(yōu)裝貨順序

成員函數(shù)：VoidGeneration()

//構(gòu)造函數(shù)

Int select

//選擇

Void Crossover(int ml,int m2)

//變異

Void Mutation(bool child[])

//遺傳

Void Generaiton()

//遺傳操作函數(shù)

散貨船配載軟件的系統(tǒng)流程圖見圖3。

圖3 軟件流程圖

3.1 產(chǎn)生初始種群

利用計(jì)算機(jī)的隨機(jī)生成功能，連續(xù)隨機(jī)產(chǎn)生28位二進(jìn)制數(shù)據(jù)，這個(gè)二進(jìn)制數(shù)即是散貨船的一個(gè)初始個(gè)體。這個(gè)28位的二進(jìn)制字符串對(duì)應(yīng)個(gè)體的染色體，其中：1～4位對(duì)應(yīng)的散貨船1號(hào)艙經(jīng)過第一輪裝貨后的艙內(nèi)貨物量，5～8位是對(duì)應(yīng)散貨船2號(hào)艙經(jīng)過第一輪裝貨后的艙內(nèi)貨物量，以此類推。

初始種群是由初始個(gè)體組合而成的，可以用圖4來表示初始種群的生成過程。圖中:M為種群規(guī)模，字符串b=1000100010001000100010001000。

圖4 初始種群產(chǎn)生流程圖

本課題研究的是“76 000 t散貨船”，將散貨船的基本數(shù)據(jù)輸入裝載儀中，對(duì)遺傳算法的初始解進(jìn)行改進(jìn)，可以將總載貨量均勻分配作為初始解。1～7艙的裝貨量均為7 974.516,輸入裝載儀的貨艙裝載框中，見表1。表中：ρ為密度，Per為貨物所占艙室的體積比，W為貨物重量，H為貨物高度，LCG為重心縱向坐標(biāo)。

裝載儀根據(jù)貨艙輸入框中的數(shù)據(jù)生成初始配載圖，具體內(nèi)容見圖5，其中：X1～X7分別代表1～7艙的裝貨量。

計(jì)算散貨船在初始配載狀況下的船舶強(qiáng)度和穩(wěn)性是否滿足要求。通過裝載儀算出“76 000 t散貨船”在改進(jìn)初始配載下的強(qiáng)度和穩(wěn)性。散貨船強(qiáng)度計(jì)算結(jié)果見圖6，穩(wěn)性計(jì)算結(jié)果見圖7。

表1 初始解的貨艙輸入

圖5 初始配載圖

圖6 初始解強(qiáng)度計(jì)算結(jié)果

圖7 初始解穩(wěn)性計(jì)算結(jié)果

3.2 遺傳算法的變異實(shí)現(xiàn)

經(jīng)過初始裝配后，用代碼實(shí)現(xiàn)對(duì)個(gè)體的某些位置進(jìn)行改變，將某些部位的二進(jìn)制碼從1變成0或者從0變成1，形成新的種群個(gè)體。將船舶的初始配載量進(jìn)行變異操作，得到變異后的1～7艙的裝貨量為7 216.393、8 610.586、7 310.325、8 010.546、7 410.546、6 408.331、7 644.128，然后將變異后的裝貨量輸入裝載儀中。裝載儀根據(jù)貨艙輸入框中的數(shù)據(jù)生成變異配載圖，見圖8，其中：X1～X7分別代表1～7艙的裝貨量。

計(jì)算散貨船在初始配載狀況下的船舶強(qiáng)度和穩(wěn)性是否滿足要求。通過裝載儀算出“76 000 t散貨船”在變異配載下的強(qiáng)度和穩(wěn)性。散貨船強(qiáng)度的計(jì)算結(jié)果見圖9，穩(wěn)性計(jì)算結(jié)果見圖10。

圖8 變異配載圖

圖9 變異強(qiáng)度計(jì)算結(jié)果

圖10 變異穩(wěn)性計(jì)算結(jié)果

3.3 散貨船的最終配載完成

散貨船配載經(jīng)過上面的變異操作后，接下來需要進(jìn)行交叉算法實(shí)現(xiàn)。交叉算法的主要步驟是：

(1)找到散貨船配載交叉算法的起始點(diǎn)。

(2)對(duì)散貨船配載進(jìn)行交叉操作。

(3)去除交叉之后的雷同信息。

經(jīng)過初始裝配和變異裝配后，進(jìn)行最后的交叉操作。通過計(jì)算機(jī)運(yùn)算得到1～7艙的最優(yōu)裝貨量，其裝貨量分別為8 040.393、7 500.558、7 927.325、8 710.546、7 422.546、6 906.331、8 244.128，將最優(yōu)解裝貨量輸入裝載儀中。裝載儀根據(jù)貨艙輸入框中的數(shù)據(jù)生成變異配載圖，見圖11，其中：X1～X7分別代表1～7艙的裝貨量。

圖11 最優(yōu)解配載圖

計(jì)算散貨船在初始配載狀況下的強(qiáng)度和穩(wěn)性是否滿足要求。通過裝載儀算出“76 000 t散貨船”在最優(yōu)解配載下的強(qiáng)度和穩(wěn)性。散貨船強(qiáng)度計(jì)算結(jié)果見圖12，穩(wěn)性計(jì)算結(jié)果見圖13。

圖12 最優(yōu)解強(qiáng)度計(jì)算結(jié)果

圖13 最優(yōu)解穩(wěn)性計(jì)算結(jié)果

從圖6、圖9、圖12中找出初始解、變異解、最優(yōu)解的剪力許用值比例的最大值和彎矩許用值比例的最大值，其結(jié)果見表2。

表2 強(qiáng)度計(jì)算結(jié)果對(duì)比

從表2看出，最優(yōu)解下的剪力和彎矩許用值比例最大值表現(xiàn)最好，穩(wěn)性沒有明顯的區(qū)別。經(jīng)過遺傳算法優(yōu)化后的船舶配載方案表現(xiàn)更好，所以此算法有得到滿意解的能力。

4 結(jié)語

散貨船優(yōu)化配載問題是一個(gè)多目標(biāo)組合優(yōu)化問題，本文采用遺傳算法求解該問題。基于遺傳算法，嘗試求解在保證船舶安全航行的前提下，滿足船舶的強(qiáng)度和穩(wěn)性的最佳方案，但是限于問題的復(fù)雜性，研究過程做了大量的假設(shè)，在實(shí)際應(yīng)用中有一定的局限性。

如今，我國(guó)大多數(shù)散貨船碼頭仍然處于人工作業(yè)的狀態(tài)，需要配載人員做出大量的工作。因此，對(duì)散貨船配載的研究不管在理論還是實(shí)際上，都有著重要意義。