夏華波 紀卓尚 張明霞

大連理工大學船舶工程學院，遼寧大連 116024

改進遺傳算法在駁船配載中的應用

夏華波 紀卓尚 張明霞

大連理工大學船舶工程學院，遼寧大連 116024

駁船是大型海洋結構物下水作業(yè)的一種常用運輸工具。駁船的配載主要是依據(jù)靜力學平衡原理和船舶基本知識對船舶浮態(tài)的調(diào)節(jié)。為了在較短時間內(nèi)完成配載作業(yè)，對遺傳算法進行了改進，提出種群全部交叉和分布式動態(tài)懲罰函數(shù)法等改進機制，對駁船配載中的調(diào)載水量分布進行優(yōu)化。計算結果表明，改進遺傳算法的配載方案比基本配載方案時間更短、效率更高。運用本改進遺傳算法對駁船配載進行方案優(yōu)化，能夠滿足工程要求，縮短上駁作業(yè)時間。

駁船；遺傳算法；適應值；懲罰函數(shù)；配載

1 引言

海洋結構物下水上駁船過程中壓載水的調(diào)載作業(yè)一般都是操作人員利用以往的經(jīng)驗完成，但是，這種方式對操作人員的依賴性很大，作業(yè)過程效率不高，精確程度不夠。

近年來大型海洋結構物不斷增加，為了更好地控制產(chǎn)品上駁過程，一些基于駁船的智能配載方式便相應誕生。目前在國外，如挪威、美國、墨西哥等國家在駁船配載方面主要是通過不斷地調(diào)節(jié)駁船的壓載水來實現(xiàn)海洋結構物的下水安裝作業(yè)［1-3］。但是，這些方法都沒有進行方案優(yōu)化，本文便是在此工程背景下，利用改進的遺傳算法優(yōu)化配載結果，使結構物上駁作業(yè)安全穩(wěn)定、快捷高效。

2 遺傳算法及其改進

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局優(yōu)化概率搜索算法。本文通過對遺傳算法進行改進，采用種群全部交叉、1＋n連續(xù)位擾動機制、劣種淘汰、分布式動態(tài)懲罰函數(shù)等多項比較靈活的處理種群基因的方式，使每一代種群既有良好的適應值又兼多樣性。同時為了增加子種群之間的交流，在一定代數(shù)的子種群計算后，把子種群融合為一個種群進行大范圍交流，限制子種群的非理想局部收斂。

本文中以一個大種群為例（多子群類似）把過程分為以下幾個方面：

1） 計算染色體串長［4］

如果要求計算的精度達到小數(shù)點后K位，同時為了讓參與遺傳運算的每個變量為非負數(shù)，則二進制串長度及其解碼方法可分別用式（1）和式（2）計算：

其中，LLi、ULi分別為自變量的下限和上限；decimal（substringi）代表變量 xi的十進位值。

2） 確定初始種群［5］

（1）每個變量在區(qū)間內(nèi)進行離散，自變量的上下限要包括進來，即分別為首尾兩個點。

（2）依次在每個變量內(nèi)取一個劃分的離散點xi，組成目標函數(shù)的可行解點列X ＝ （x1，x2，…，xn），計算每個可行解的染色體適應值（不是目標函數(shù)值）。

（3）按照適應值的高低進行排序，從前到后取Popsize個染色體形成初始種群。

這種初始種群使自變量在可行解范圍內(nèi)均勻分布且適應值相對較高，利于后續(xù)的進化計算。而隨機形成的初始種群很難在可行解范圍內(nèi)均勻離散分布，不利于全局收斂。

3）選擇運算

本文選擇操作的基本思想［5］是：

（1）計算群體中各個個體在下一代群體中的數(shù)目indivnumi

（2） 用整數(shù) Int（indivnumi）確定各個對應個體在下一代群體中的生存數(shù)目。

（3）按照（2）中的方法一直取到第popsize－1個個體在下一代種群中的數(shù)目，剩余的種群基因數(shù)即為當代適應值最大的個體在下一代種群中的數(shù)目。

另外，本文的選擇算子采用了“劣種變異”原則。其指導思想是：對每一代適應值比較靠后的個體（20%）用上一代保留的優(yōu)秀個體進行變異若干次，取與劣種數(shù)量相同的適應值較大的變異個體作為劣種的替換。這種劣種淘汰方法提高了整個種群的競爭力。

4）適應度評價

種群適應值的計算是整個遺傳算法的關鍵，關系著算法能否快速有效的收斂到全局極值。適應值的評價重在約束處理，對于約束的處理方法，常用的有算子修正法、可行解搜索法以及懲罰函數(shù)法［6］，本文以分布式動態(tài)參數(shù)懲罰函數(shù)法對約束進行處理，具體適應度函數(shù)評價如（4）所示：

式中，f（X）為個體函數(shù)值；λ為固定罰因子，本文經(jīng)過函數(shù)試驗取為0.2；β為分段罰因子，即根據(jù)個體滿足等式約束的程度而定；為自適應懲罰比例因子，其中，favg為當代所有個體目標函數(shù)值的平均值，ε為能夠允許的超出約束的值，即約束允許誤差；Rf（X）為實際滿足約束的程度，在文中指超出約束的實際值，即

需要說明的是，在式（4）中分段罰因子β的確定尤為關鍵，本為是通過多個有代表性的函數(shù)試驗進行確定的。為了說明β的分段劃分情況僅以等式約束為例：針對不同的問題首先要確定一個等式約束允許的誤差范圍ε，根據(jù)種群不滿足等式約束的值確定分段罰因子β。如果值越大，則β越大，反之則β越小。但β的分段值也不宜劃分過細，過細容易把較好的個體淘汰掉，要針對具體問題具體分析，經(jīng)過本文的函數(shù)試驗其范圍為0.8～1.5。

5）交叉操作

為了交叉后種群的多樣性，本文令每一代種群全部參與交叉運算，其中每兩個選中要交叉的父個體需要在不同交叉點進行很多次交叉運算，最后把交叉得到的所有新個體和父個體合在一起選擇適應值最高的兩個個體取代父個體進入后續(xù)的計算。該方法既增加了新個體的種類，也使得新個體適應值是不斷增大的，具有良好的效果。

6）變異操作

參與變異運算的個體經(jīng)過變異算子作用后，產(chǎn)生的新個體直接取代了原有個體，然而，新個體適應值是否有所提高，基本的變異算子是無法確定的。為了取得良好的變異效果，使得變異操作以后的新個體能夠有一個較高的適應值，本文采用1＋n連續(xù)位擾動機制進行變異，即讓每個參與變異的父代在每個自變量所在的二進制代碼中隨機選取幾個連續(xù)變異點。每個自變量需變異的位數(shù)視具體情況而定，文中是選擇每個自變量二進制長度的10%的整數(shù)（至少為1位）。其中，每個個體進行mutanum（mutanum≥1）次變異，最后把變異產(chǎn)生的大量個體與父代一起進行比較，選擇適應值最大的個體作為下一代的初始種群。

3 駁船配載優(yōu)化

3.1 駁船配載原理及模型

對于不同的碼頭潮水漲退情況，駁船配載操作需要重點考慮的問題不一樣。有些碼頭潮水漲退維持的時間比較短，駁船配載作業(yè)必須在較短的時間內(nèi)完成，因而對駁船配載方案進行優(yōu)化非常重要。本文以各待調(diào)節(jié)水艙調(diào)節(jié)前后的壓載水的變化量為設計對象；以駁船的中縱剖面與基平面的交線為x軸，方向沿船首為正；駁船中橫剖面與基平面的交線為y軸，方向沿右舷為正。設駁船壓載艙共有N列，每一列有S個艙，從1到N列艙沿船尾到船首分布，第i列各艙從右至左舷的編號分別為：1，2，…，S。 值得注意的是，駁船橫向一列艙一般是由一個泵控制，一列艙的排注水情況是相同的，雖然一列中各艙有單獨的閥門控制，但是控制一列艙的泵的功率是不變的，從而決定配載操作時間的是一列艙的總流量，而不是一列中某個艙的流量，因此，在本文中以橫向每一列為基本單位選擇調(diào)節(jié)水艙。一般來說，選擇其中的2列艙參與配載就可以滿足工程要求，所以本文每次方案配載時選擇其中的2列艙作為調(diào)節(jié)水艙。

配載操作中各調(diào)節(jié)水艙的水位確定主要與駁船的要求吃水（假設要保持滑道平齊）、上駁分段的實時重量和重心位置、各調(diào)節(jié)水艙的艙容要素、調(diào)節(jié)前各水艙的原有水位以及漲落潮實時水位等有關［7-8］，其計算的理論基礎是“雙零原則”。 以駁船為研究對象，如圖1所示，即駁船所受到的合力與合力矩為零。對于最后選定的最佳配載方案，需要校核最大剪力彎矩，如果該方案的最大剪力彎矩都滿足要求，則最終確定該方案為本輪配載方案，否則，對次優(yōu)方案驗證，直至找到合適的方案。

圖 1 中符號意義如下：Fb和（xb，yb）分別為駁船浮力及浮心坐標；GP和（LP，yP）分別為上駁分段壓力及其作用點；GS和（LS，yS）分別為駁船本身的重力及其作用點；GW和（LW，yW）分別為駁船調(diào)載水重力及其作用點；G0W和（L0W，y0W）分別為駁船調(diào)載前壓載水重力及其作用點。

在合力的作用下，駁船最終處于平衡狀態(tài)，其衡方程可以式（6）表達為：

其中，ρ為水密度；V0Wi、VWi分別為第i個艙調(diào)載前水的體積和調(diào)載變化的水體積；h1（V）、h2（V）、h3（V）分別為力平衡方程、縱向力矩以及橫向力矩平衡方程；Vimin、Vimax分別為第i個艙調(diào)節(jié)水體積的下限和上限，其余參數(shù)與圖1中意義相同。

方案優(yōu)化首先要選定兩列調(diào)節(jié)水艙。為了方便遺傳算法對數(shù)值的處理，首先必須對選定的兩列艙進行排注水判斷，即兩列2S個艙最多只有兩個符號。由于駁船橫向一列艙的形狀大致相同，所以其縱向型心基本相同，從而把一列艙作為一個整體考慮用于判斷進出水符號是完全可以的。其具體判斷方法可由式（7）～式（9）表達：

設被選擇配載的兩列艙其調(diào)載量分別為V1、V2，縱向力臂分別為 ML1、ML2，駁船達到預定浮態(tài)需要調(diào)節(jié)的水量和縱向力矩分別為ΔG和ΔMx，根據(jù)靜力學的“雙零原則”，則有：

本文中，縱向力臂為一列艙經(jīng)過疊加得到的合力臂，其計算公式為式（8）。

其中，MLji為某一列各艙的縱向力臂。

綜上可知，利用簡化處理方法可以得到兩列艙的整體調(diào)水量由式（9）表示為：

如果兩列艙整體調(diào)水量V1、V2都在允許調(diào)節(jié)范圍內(nèi)，則該方案繼續(xù)進行，否則認為該方案不可行，直接進行下一個方案的計算。確定了進水或排水符號后，需要把兩列艙中的2S個艙全部單獨看做一個變量，其對應的配載優(yōu)化模型可以寫成（10）～式（12）所示的形式。

其中，ai和bi分別為調(diào)節(jié)水量的下限和上限；V0i和Vi分別為調(diào)載前的水量以及調(diào)載水量；LxS、Lxi、Lx0i、Lxp分別為駁船、調(diào)節(jié)水、原有壓載水、上駁 分段 各重 心的 縱坐 標；LyS、Lyi、Ly0i、Lyp分 別 為駁船、調(diào)節(jié)水、原有壓載水、上駁分段各重心的橫坐標，其余符號意義與圖1中相同。

鑒于基本遺傳算法計算結果隨機性比較大，即結果不穩(wěn)定，本文以上文中提及的改進遺傳算法為配載優(yōu)化方法。其優(yōu)化目標可描述為式（10）所示：設A代表所選擇的兩列艙 （如第1和第3列）優(yōu)化的結果，即此時該兩列的所有可行方案中調(diào)水量最大列比較的結果是A方案中調(diào)水最大列的調(diào)水最少，也就是操作時間最短，B代表所有A方案中（共個計算方案）調(diào)水量最大列結果最小的那個方案，則B即為目標函數(shù)所求解的最終方案。

3.2 駁船配載實例

上駁初始數(shù)據(jù)的選定直接影響大型結構物的滑移裝船是否能夠順利完成，是產(chǎn)生預配方案的關鍵，同樣也是指導實時配載的依據(jù)［9］。本文中以2列艙為研究對象，即上式中M＝2。下面以某實際駁船數(shù)據(jù)為例，任意給定一個狀態(tài)進行配載分析。其中，駁船有8列艙，每列4艙，左右對稱。表1和2為產(chǎn)品和駁船的一些參數(shù)。

表1 上駁產(chǎn)品參數(shù)

表2 駁船參數(shù)

為方便敘述，規(guī)定文中符號如下：ΔG和ΔG’分別為需要調(diào)節(jié)的壓載水量和實際調(diào)節(jié)水量；ΔMx和ΔMx’分別為需要調(diào)節(jié)的水量和實際調(diào)水量產(chǎn)生的縱向力矩；ΔMy和ΔMy’分別為需要調(diào)節(jié)的水量和實際調(diào)水量產(chǎn)生的橫向力矩；［N］為配載過程允許出現(xiàn)的最大的剪力，本實例中［N］＝1.87 × 103（tf）；［M］為配載過程允許出現(xiàn)的最大彎矩，本實例中［M］＝6.18×104（t·m）；ε 為本次配載允許的超出3個等式方程約束的值，本實例中ε＝10。 其約束如式（13）：

本次配載為整個駁船配載方案中的一步調(diào)載情況，即由目前的駁船狀態(tài)預配一段時間后（下一步配載）駁船對應的狀態(tài)，本次方案如表3所示。對整個上駁過程的每一步調(diào)載按照本改進遺傳算法和基本配載法［10］進行計算即可得到整個駁船配載的所有方案情況。

表3中的“基本”和“改進”分別為基本配載和運用改進遺傳算法的配載方案結果，其中，基本配載方法為孫承猛［10］發(fā)表的博士論文中提出的“配對法”，其方法中利用了駁船的特殊結構，在壓載艙橫向和縱向配載的處理上對調(diào)節(jié)水艙的型心分別采用了類似文中式（7）～式（9）的簡化處理。由于基本配載法為解平衡方程組法，所以結果無誤差，而改進遺傳算法的優(yōu)化方法有一定的誤差，其具體分析結果如表5所示。其中，實際誤差為實際自變量滿足合力與合力矩3個平衡方程的約束程度，其表達式為：

從表3和表4中的數(shù)據(jù)分析可以看出，相同方案時，基本配載法的單列最大調(diào)節(jié)水量更大，上駁作業(yè)時間更長。而改進遺傳算法調(diào)節(jié)的最終結果顯示，本次駁船配載的所有可行方案中的4個最優(yōu)秀的方案都能滿足工程上的要求，且都比相應的基本配載方案單列最大調(diào)節(jié)水量更少，即上駁作業(yè)時間更短，這4個優(yōu)化方案的單列調(diào)節(jié)水量最大排列順序為：354.75 t＜ 373.16 t＜401.07 t＜412.4 t，可見方案一中單列最大調(diào)載量最小，故方案一配載作業(yè)時間最少。同時方案一的最大剪力 Nmax＝ 1.14 × 103（tf） ＜ ［N］ ＝ 1.87 × 103（tf），對應產(chǎn)生的彎矩 Mmax＝2.76×104（t·m）＜［M］＝6.18×104（t·m），實際誤差 δ＝6.47＜ 允許誤差 ε ＝10，均滿足給定要求，此即為本次配載最終方案?？梢?，應用本改進遺傳算法對駁船配載模型的方案優(yōu)化能夠達到理想的效果。

表3 配載方案

表4 方案分析

4 結論

駁船配載問題與浮船塢的浮態(tài)調(diào)節(jié)類似，其實質(zhì)可歸結為求解一個約束優(yōu)化問題［11］，工程處理上一般會簡化處理，不需要用很多列來調(diào)節(jié)，一般2列壓載艙完全可以滿足駁船配載的要求。本文從配載方案優(yōu)化的角度出發(fā)，以2列壓載艙的調(diào)水量變化為設計變量（N為艙列數(shù)，則有C種配載方案），應用基于分布式動態(tài)懲罰函數(shù)的改進遺傳算法對配載作業(yè)時間進行了優(yōu)化，使得配載作業(yè)在時間限制比較大 （較短時間內(nèi)完成結構物上駁作業(yè)）的情況下可以很好地完成任務。此算法優(yōu)化過程中應用了小生境遺傳算法中的多個子群體并行運算模式，對函數(shù)多峰值情況處理有很好的效果。經(jīng)過計算驗證，該算法穩(wěn)定，計算效率較高，對駁船配載實際工程的應用有一定的指導意義。本論文設計中有以下創(chuàng)新點：

1）首次在駁船配載模型中應用了遺傳算法。

2）遺傳算法的改進中，提出了種群全部交叉、1＋n連續(xù)位擾動變異機制以及分布式動態(tài)懲罰函數(shù)法，使得遺傳算法每一代能夠得到最優(yōu)秀的個體，利于種群穩(wěn)定、快速地進化。

［1］COLE L G.The treatment of ship bi1ge， ballast and dock rain－water run－off by an electrox process［J］.Ocean Engineering，1996，19 （8）：72－74.

［2］HUA H，LEE P，WANG W.Analytical solution on the surge motion of tension－leg twin platform structural systems ［J］.Ocean Engineering， 2000，27：393－415.

［3］ARUP O.Solution for the shallows［J］.Offshore Engineering，1998（1）：42－43.

［4］雷英杰，張善文，等.MATLAB遺傳算法工具箱及應用［M］.西安：西安電子科技大學出版社，2005.

［5］周明，孫樹棟.遺傳算法原理及應用［M］.北京：國防工業(yè)出版社，1999.

［6］敖友云.基于遺傳算法的連續(xù)函數(shù)優(yōu)化技術研究［D］.上海：上海師范大學，2006.

［7］楊星，季永青.集裝箱船配載優(yōu)化方法研究［J］.武漢理工大學學報（交通科學與工程版），2002，26（2）：223－226.

［8］王鴻鵬.一種優(yōu)化編制船舶裝載計劃的新方法［J］.集美大學學報（自然科學版），2002，7（1）：38－44.

［9］楊曉寧.下水駁船自動配載研究［D］.大連：大連理工大學，2008.

［10］孫承猛.下水駁船實時配載關鍵技術研究［D］.大連：大連理工大學，2008.

［11］孫承猛，劉寅東.浮船塢實時配載模型及算法［J］.大連：大連理工大學學報，2006，46（6）：857－861.

Application of Improved Genetic Algorithm in Barge Stowage Planning Analysis

Xia Hua-bo Ji Zhuo-shang Zhang Ming-xia
School of Naval Architecture and Ocean Engineering，Dalian University of Technology，Dalian 116024，China

The barge is a common transportation widely adopted for launching large marine structures in the ship industry.Barge＇s stowage planning is conducted mainly depending on the adjustment of floating conditions in accordance with the hydrostatic balance principium and basic knowledge of ships.In order to complete stowage process in a short time，this paper applies an improved Genetic Algorithm （GA）to optimize ballast water＇s distribution， which propose improved approaches such as all－cross and distributed dynamic penalty function.The results show that stowage planning using improved GA is better than the basic planning in terms of time and efficiency.Improved GA to optimize barge＇s stowage can meet the engineering requirements and is time－saving for loading onboard the barge.

barge； GA； adaptive value； penalty function； stowage planning

U674.18

A

1673－3185（2010）06－51－05

10.3969/j.issn.1673-3185.2010.06.010

2009-12-18

夏華波（1984－），男，碩士研究生。研究方向：船舶結構物設計制造。E-mail：xiahuabo0303＠126.com

紀卓尚（1938－ ），男，教授，博士生導師。 研究方向：船舶結構物設計制造。E-mail：jizshang＠ dlut.edu.cn

張明霞（1969 － ） ，女，副教授。 研究方向：船舶結構物設計制造。 E-mail：mxzhang＠ dlut.edu.cn