散貨船優(yōu)化算法

1、散貨船裝載過程優(yōu)化的研究Study on Optimization of Bulk Carriers Loading Process12本文從散貨船的安全問題出發(fā)，結(jié)合散裝船舶裝卸貨過程中的實際情況，提出了通過優(yōu)化裝載方案來控制船舶裝貨時強度變化的觀點，以使整個裝貨過程中產(chǎn)生的剪力、彎矩對船舶強度的影響盡量最小。初步建立了散貨船裝載優(yōu)化模型，提出了求解該模型的基本思想，并將遺傳算法運用于該優(yōu)化模型的求解。研究了遺傳算法在散貨船裝載過程優(yōu)化上的具體實施方法。采用面向?qū)ο蟮某绦蛟O(shè)計方法，在Windows平臺的Visual C+環(huán)境下開發(fā)了基于遺傳算法的散貨船裝載過程優(yōu)化軟件。本文所開發(fā)的基于遺傳算

2、法的散貨船裝載過程優(yōu)化軟件，可以作為裝載儀中的一個子系統(tǒng)，對各種裝貨過程進行優(yōu)選，最后得到一個近似最優(yōu)的裝貨方案。經(jīng)過優(yōu)化的裝貨方案可以大大減小裝貨過程中所產(chǎn)生的船舶剪力和彎矩最大值。該軟件可以運用于實際生產(chǎn)，通過控制船舶裝貨環(huán)節(jié)的船體強度，提高散貨船的安全性，延長船舶的使用壽命。ABSTRACTThis paper particularly analyzes the characteristic of bulk carrier. Present the attitude that controls the vessels strength in loading by optimizing t

3、he loading scheme. This optimization intends to make the vessels Shear Force (SF) and Bending Moment (BM) in loading process to the lowest extent. An optimization modal for loading of bulk carrier is basically established in this paper. Author creatively uses the Genetic Algorithms to get the soluti

4、on of this optimization modal.The software named “Optimization of Bulk Carriers Loading Procession”, which can be inserted to “Stowage System of Bulk Carrier” as a subsystem. This software chose the best one approximately from every loading scheme. The optimized scheme can reduce the maximum of SF a

5、nd BM in loading at most extend. Using the software to optimize the loading process in practice will improve the security of the bulk carrier, and prolong the life span of the bulk carrier.Key Words: Bulk Carrier, Vessels Strength, Optimization of Loading Process, Genetic Algorithms.1.4 散貨船裝卸操作中的強度控

6、制問題從散貨船的安全現(xiàn)狀可以看出，目前都存在一個共同的問題，即船舶強度問題。如何才能把營運中的風險降至最低，如何才能提高散貨船營運的安全系數(shù)，保證人、船、貨的安全，延長船舶的使用壽命，這有賴于通過適當?shù)难b卸，使裝卸過程中產(chǎn)生的剪力、彎矩對船體的潛在損傷降至最低。這就提出了散貨船在裝卸過程中的強度控制問題。7散貨船在裝卸過程中的強度控制的核心，就是要制定較優(yōu)化的裝卸貨方案，使整個裝卸過程中產(chǎn)生的剪力、彎矩對船舶強度的影響盡量最小?，F(xiàn)有散貨船根據(jù)SOLAS公約第/11條的規(guī)定，均安裝了規(guī)定的裝載儀。船舶駕駛員通過輸入某一狀態(tài)下的裝載貨物情況和油水分布情況，就可以得到該狀態(tài)下的各站號及特殊要求位置的

7、剪力和彎矩值，再將這些數(shù)據(jù)與規(guī)范標準相比較。通常船舶駕駛員是事先制訂一個裝卸貨方案，再用裝載儀去校核，以確定裝卸過程中船舶強度是否滿足規(guī)范要求，如不滿足則對原計劃進行修改，直到滿足規(guī)范要求為止。該裝卸方案雖然滿足規(guī)范要求，但是卻未達到優(yōu)化的程度。如果能夠獲得優(yōu)化方案并以此指導(dǎo)裝卸作業(yè)，那么貨物操作過程中散貨船船體的損傷將會大大降低，從而大大減少船體的疲勞，提高散貨船的使用壽命，保證船舶安全。一般來說，由于散貨船的裝貨速度遠高于卸貨速度，所以裝貨時對船舶強度的控制就顯得比卸貨時更加重要。本文就是從散貨船的裝載角度出發(fā)，在船舶裝載儀的基礎(chǔ)上引入人工智能的思想，運用遺傳算法對船舶的裝貨過程進行優(yōu)化，

8、并可在散貨船的裝載儀中增設(shè)一個子系統(tǒng)，對各種裝貨過程進行優(yōu)選，最后得到一個近似最優(yōu)的裝貨方案，以解決散貨船裝卸過程中的強度控制問題。散貨船裝載過程優(yōu)化模型的建立 在散貨船裝載過程優(yōu)化中需要考慮的主要因素僅是船舶縱向強度和船舶的吃水、吃水差限制。本章首先介紹了靜水中船舶縱向強度和浮態(tài)的計算方法，再進一步建立了散貨船裝載過程的優(yōu)化模型，并初步提出了該模型的求解思路。裝載過程優(yōu)化模型的建立在散貨船的實際裝載過程，可以定義為單艙裝載方式和多艙裝載方式。單艙裝載方式就是裝貨過程中只有一部裝貨設(shè)備，一次只能對一個貨艙進行裝貨操作；多艙裝載方式就是指用兩部或兩部以上的裝貨設(shè)備對不同的貨艙同時進行裝貨操作的裝

9、載方式。與多艙裝載方式相比，采用單艙裝載方式時，裝貨過程中對船舶強度和浮態(tài)的控制是比較困難的。因此對單艙裝載方式的優(yōu)化是非常必要的。本文僅對單艙裝載方式進行了研究，對單艙裝載過程建立了優(yōu)化模型。2.3.1 建立優(yōu)化模型的目的。裝載過程優(yōu)化就是要在已知每個貨艙計劃裝貨量的基礎(chǔ)上，確定一個優(yōu)化的裝貨方案，使得按照這個方案進行裝貨的整個過程中，船舶產(chǎn)生的剪力、彎矩對船舶強度的影響盡量最小，并且在整個過程中船舶的浮態(tài)也能滿足規(guī)定的要求。所以，建立裝載過程優(yōu)化模型的目的就是：在盡量減少裝貨次數(shù)的前提下，確定一個能使整個裝貨過程中船舶的剪力、彎矩盡量小并且使船舶吃水、吃水差始終保持在規(guī)定要求以內(nèi)的裝貨優(yōu)化

10、方案。2.3.2 目標函數(shù)的建立2.3.2.1 確立基本變量每個貨艙最終要裝載的貨物重量是已知的，用表示。船舶總共需要裝貨的貨艙數(shù)，用C表示。則該航次船舶總裝貨量為。將每一次裝貨設(shè)備從一個貨艙口移動至另一貨艙口稱之為一次換裝作業(yè)，而裝貨設(shè)備對全船所有貨艙依次完成了一次裝貨的過程定義為一輪裝貨作業(yè)。完成整個裝貨需要的換裝次數(shù)用J表示，完成整個裝貨需要的輪次數(shù)用R表示。對于有5個貨艙和7個貨艙的散貨船，一般經(jīng)過兩輪裝貨均可滿足優(yōu)化的要求，即可取R=2。而對于9個貨艙以上的大型散貨船，往往需要3輪或以上的裝貨作業(yè)才能滿足優(yōu)化的要求，即R3。我們假定?？梢钥闯鋈我庖环N裝貨方案都是由每輪裝艙的次序S（S

11、equence）和每輪各艙的裝貨數(shù)量Q（Quantity）構(gòu)成。確定了每輪的裝艙次序和每輪的各艙裝貨量，就確定了一種裝貨的方案E，即 （2-3-1）在裝貨中為了保證船舶的縱向強度，一般情況下壓載水排放位置與裝載貨艙的位置趨于一致，因此，壓載水方案B是由裝貨方案所決定的，現(xiàn)定義為 （2-3-2）2.3.2.2 目標函數(shù)的建立在裝貨過程中，每個校核站面的剪力、彎矩都是在不斷變化的，它們變化是個連續(xù)的過程，因而可取每一次換裝作業(yè)時各個校核站面的剪力和彎矩其中，i為校核站面的位置， j為換裝作業(yè)的次數(shù)。設(shè)各個校核站面的剪力許用值為，彎矩許用值為，則可設(shè)定裝貨過程中優(yōu)化模型的目標函數(shù)為： （2-3-3）

12、 （2-3-4）對裝貨方案的優(yōu)化，理論上就是要求得一個解，使得和 為最小值。2.3.3 約束條件的設(shè)立考慮到港口航道或碼頭泊位水深的限制和壓載水排放要求，散貨在裝載過程中必須限定船舶吃水和吃水差。設(shè)每次換裝作業(yè)時船舶的首吃水為(E)，尾吃水為(E)，吃水差為(E)，則裝卸過程中約束條件為： （2-3-5）式中，分別為裝貨過程中最大尾傾吃水差和最大首傾吃水差，其中 為負值，為正值。2.3.4 裝載過程的優(yōu)化模型 建立最優(yōu)化模型，有三個基本要素，即決策變量、目標函數(shù)和約束條件 ，于是可建立如下裝貨過程優(yōu)化模型： min s.t. （2-3-6） 在多目標決策問題中，根據(jù)實際情況確定一個目標為主要目

13、標，而把其余目標作為次要目標，并且根據(jù)決策者的經(jīng)驗，選取一定的界限值。這樣就將原多目標決策問題轉(zhuǎn)化為在一個新的約束條件下，求主要目標的單目標規(guī)劃問題20。 現(xiàn)將每次換裝作業(yè)時船舶各個站點的實際剪力占許用剪力的百分比限定在以內(nèi)作為約束條件，就可以把2-3-6式變?yōu)橄率剑?min s.t. （2-4-1） 其中，可根據(jù)船齡及裝載條件限定在50%70%范圍內(nèi)。 2.4 裝載過程優(yōu)化模型求解的基本思路將2-3-1式代入2-3-3和2-3-4式，我們可以將目標函數(shù)變?yōu)椋?（2-4-2） 求解最優(yōu)解，也就是求解最優(yōu)裝艙順序和每輪各艙最優(yōu)裝貨量。首先選擇出全部可行的裝艙順序N，然后確定出每一種裝艙順序下每一

14、輪各貨艙的最優(yōu)裝貨量，從而可以求出每一裝艙順序下最優(yōu)裝貨方案，t（t= 1N），再將代入目標函數(shù)，選出其中使目標函數(shù)最小者即為最優(yōu)解。在選擇過程中，應(yīng)先將那些不可行的裝艙順序排剔除，僅保留有可能產(chǎn)生最優(yōu)解的裝艙順序。2.4.4 優(yōu)化求解過程1) 隨機產(chǎn)生一個確定的各貨艙每輪裝貨量的組合，即一個確定的；2) 選擇出全部可行裝艙順序；3) 計算每一種裝貨順序下的目標函數(shù)h(E),并對結(jié)果進行比較，選取在約束條件下使h(E)最小的裝貨順序，于是產(chǎn)生了相應(yīng)的裝貨方案。4) 重復(fù)步驟1）3），不斷比較所有產(chǎn)生的裝貨方案，直到能找到一個優(yōu)化方案。我們可以看出，求解裝載過程優(yōu)化模型的過程實際上就是一個典型的

15、數(shù)學(xué)尋優(yōu)過程。由于每輪裝貨量的組合和可行裝貨順序的組合都是非常多的，用一般的枚舉法是很難找出最優(yōu)解的。因此需要一種效率極高的尋優(yōu)方法來解決該優(yōu)化問題。于是作者將遺傳算法應(yīng)用于裝載過程優(yōu)化模型的求解?；谶z傳算法的散貨船裝載過程優(yōu)化運用遺傳算法對具體的散貨船裝載過程進行優(yōu)化的過程也就是用遺傳操作對可能的裝載過程的解空間進行搜索，最終找出一個最優(yōu)解的過程。3.3 遺傳編碼方案的確定在遺傳算法開始時，通過編碼將變量轉(zhuǎn)化為一條字符串，作為每一個個體唯一對應(yīng)的染色體。在遺傳算法結(jié)束時，對選出的最優(yōu)個體的染色體字符串進行解碼，即編碼算法的逆運算，最終得到優(yōu)化變量。根據(jù)2.4節(jié)的基本優(yōu)化過程，本模型需要對各

16、貨艙每輪裝貨信息進行編碼。本文采用Holland的經(jīng)典遺傳算法，應(yīng)用二進制編碼規(guī)則。 對于具有n個貨艙且擬兩輪完成裝貨的船舶，將每個貨艙的最終裝貨數(shù)量分為16等份，則用任意一個4位二進制數(shù)（=, ,）來對應(yīng)各艙的第一輪裝貨量為 （3-3-1）若需進一步提高計算精度，可以將每個艙的裝貨量分為128等份，用8位二進制數(shù)來表示。一般來說，用4位二進制數(shù)來表示的計算結(jié)果即可滿足優(yōu)化要求。對于具有n個貨艙且擬三輪完成裝貨的船舶，用4位二進制數(shù)對應(yīng)各艙的第一輪裝貨量,和4位二進制數(shù)對應(yīng)各艙的第二輪裝貨量為： （3-3-2）將，按順序排列，組成一條二進制字符串，作為個體的染色體。3.4 初始種群的產(chǎn)生根據(jù)編

17、碼方案，由一個隨機布爾值發(fā)生器連續(xù)產(chǎn)生出20個二進制數(shù)，就隨之產(chǎn)生了一個初始個體。個體的染色體就是這個20位二進制字符串，其中14位對應(yīng)第1艙第一輪裝貨信息，58位對應(yīng)第2艙第一輪裝貨信息，以此類推。在最終遺傳優(yōu)化結(jié)束后，解碼器將依該順序?qū)ψ顑?yōu)個體進行解碼，從而獲取優(yōu)化裝載方案。3.5 個體適應(yīng)度的確定確定個體適應(yīng)度的步驟如下：1）隨機產(chǎn)生一串二進制數(shù)，作為一個個體的染色體，其中包含了各貨艙每輪裝貨量的信息。 對該個體進行解碼，得到各貨艙每輪裝貨量組合，再根據(jù)可行裝貨順序的選擇原則，自動產(chǎn)生出對應(yīng)于該個體的全部可行裝貨順序。2） 比較所有可行裝貨順序下的，找出使其值最小的那個裝貨順序，并把該最

18、小值記為，同時把個體對應(yīng)的最優(yōu)裝貨順序保存入個體。則即為該個體對應(yīng)的最優(yōu)裝貨順序下的裝貨過程中船體所受的實際彎矩占許用值百分比的最大值。3）確定個體適應(yīng)度。 （3-5-1） 3.6 遺傳操作的具體實施3.6.1 選擇 選擇是用來確定需要遺傳復(fù)制和交叉的個體，以產(chǎn)生下一代種群的算法。本文選用了輪盤選擇法。3.6.2 交叉在遺傳算法中，交叉是產(chǎn)生新個體的主要手段。它類似于自然界中生物的交配繁衍，使不同個體的基因互相交換，從而產(chǎn)生新個體。本文優(yōu)化程序中選擇均勻交叉法，具體實施步驟如下：（1）當滿足交叉概率時交叉事件發(fā)生，以輪盤法從種群中選擇出兩個需要交叉?zhèn)€體。(2) 由一個產(chǎn)生“1”的概率為0.5的

19、布爾值發(fā)生器生成一條與個體染色體長度相同的二進制字符串A。(3) 對字符串A進行逐位判斷，為“1”時交換相應(yīng)位置的個體染色體，為“0”時不交換。(4) 交換完畢后，將交叉后的個體保存入下一代種群。 3.6.3 變異變異是遺傳算法產(chǎn)生新個體的方法，它對個體的染色體上某個字符進行補運算，將字符1變?yōu)?，或?qū)?變?yōu)?。由于變異產(chǎn)生的新個體，可能會變得更好（適應(yīng)度高），也可能向壞的方向發(fā)展，因此對于個體本身來說，變異的效果是很難預(yù)料的；但對于整個種群來說，變異增加了種群中個體的多樣性，使最終結(jié)果不易于收斂于局部最優(yōu)解,是遺傳進化中不可缺少的一個環(huán)節(jié)。3.7 對約束條件的處理 對于不滿足任一約束條件中的

20、個體，將它排除出種群。具體的方法是：在每一代種群計算個體適應(yīng)度時，用3個約束條件對種群中所有個體依次進行檢驗，將凡是不能完全滿足約束條件要求的個體挑選出來，使其適應(yīng)度強制清零。根據(jù)式3-6-1，由于,該個體在遺傳中被選中的概率，因此這些不能滿足約束條件要求的個體將無法被遺傳到下一代。通過這樣的方法，經(jīng)過若干代遺傳搜索所求出的最優(yōu)裝貨方案將完全滿足3個約束條件的要求。裝載過程遺傳優(yōu)化的計算機實現(xiàn)本程序以散貨船“Sea Brilliance”輪為對象編寫，程序選用是在WINDOWS平臺上的Microsoft Visual C+ 6.0開發(fā)的。4.2.1.1 輸入計算參數(shù)輸入的計算參數(shù)包括：船舶基本

21、參數(shù)：船員行李、食品、船舶常數(shù)、油水重量和裝貨前各壓載水艙內(nèi)壓載水的重量。各艙裝貨參數(shù)：即各貨艙的配貨重量，通常該數(shù)值可由船舶駕駛員或配載軟件計算得出。船舶浮態(tài)的限制：根據(jù)港口的自然條件設(shè)定最大、最小吃水限制，并設(shè)定最大首、尾吃水差。遺傳算法參數(shù)：遺傳代次、交叉概率、變異概率。這些參數(shù)決定了最終優(yōu)化結(jié)果的精確性及計算時間的長短。4.2.1.5 優(yōu)化結(jié)果輸出優(yōu)化結(jié)果包括：整個裝貨過程中的裝艙次序、每次裝貨的數(shù)量和對應(yīng)的壓載水操作。同時顯示每次裝貨結(jié)束即每次換裝作業(yè)時的船舶首尾吃水、吃水差、艙壁處剪力、彎矩值的最大值。這些數(shù)據(jù)可以幫助船舶駕駛員監(jiān)督實際裝貨是否按照優(yōu)化后的裝貨計劃進行。遺傳優(yōu)化程序

22、的基本流程如下：初始種群發(fā)生器船舶基本參數(shù)、油水分布、各艙裝貨量由若干裝貨方案組成的初始種群船舶浮態(tài)限制遺傳算法參數(shù)Gen次遺傳操作優(yōu)化結(jié)果輸出圖41 優(yōu)化程序流程圖4.3計算實例4.3.2 數(shù)據(jù)輸入1) 船舶基本參數(shù)輸入在“數(shù)據(jù)輸入”菜單中選擇“船舶基本參數(shù)”項，或通過點擊工具欄的按鈕B(Basic parameter),打開以下窗口并輸入船舶基本參數(shù)：圖44 船舶基本參數(shù)窗口2) 油水及壓載水數(shù)據(jù)輸入在“數(shù)據(jù)輸入”菜單中選擇“油水及壓載水數(shù)據(jù)”項，或通過點擊工具欄的按鈕O(Oil and ballast water),打開以下窗口并輸入船舶裝貨前的油水及壓載水數(shù)據(jù)。 : 圖45油水及壓載水

23、數(shù)據(jù)窗口3) 各艙裝貨數(shù)量在“數(shù)據(jù)輸入”菜單中選擇“各艙裝貨數(shù)量”項，或通過點擊工具欄的按鈕C 打開以下窗口并將每個貨艙配貨量依次輸入。:圖46 各艙裝貨數(shù)量窗口4) 約束條件限制在“數(shù)據(jù)輸入”菜單中選擇“約束條件限制”項，或通過點擊工具欄的按鈕D(Draft limit) 打開以下窗口并根據(jù)裝貨港的實際情況輸入。圖47約束條件限制窗口 5) 在“參數(shù)設(shè)置”菜單中選擇“遺傳算法基本參數(shù)”項，或通過點擊工具欄的按鈕P(Parameter of GE),在以下窗口中輸入遺傳算法的基本參數(shù)。 圖48 遺傳算法基本參數(shù)界面種群大小一般取在100300之間，太大了會使遺傳算法的效率大大下降。遺傳代次一般設(shè)置在100次以上，遺傳代次越大，計算結(jié)果就會越接近最優(yōu)解，但計算時間會大大延長。交叉率一般設(shè)置在0.20.6之間，變異率一般設(shè)置在0.0050.02之間。4.3.3 優(yōu)化計算過程 我們繼續(xù)將值調(diào)整為50%，計算后可得：圖411 為50%的優(yōu)化結(jié)果輸出界面為了同時控制裝貨過程中的剪力和彎矩最大