基于遺傳算法的機艙管路自動布置研究

高躍峰+張均東

摘 要 船舶機艙管路分布密集、且走向復雜，目前在生產(chǎn)設(shè)計中仍然主要依靠經(jīng)驗豐富的專業(yè)人員來完成管路的布局。為實現(xiàn)船舶機艙管路的自動布置，基于遺傳算法設(shè)計了一種自動尋找最優(yōu)路徑的算法。算法通過將機艙空間分割為三維網(wǎng)格節(jié)點，將各個坐標點編碼，產(chǎn)生初始種群，建立個體適應(yīng)度函數(shù)，根據(jù)路徑總長、路徑彎頭數(shù)、路徑能量值來評價個體的適應(yīng)度，從而評價路徑的優(yōu)劣，從中選擇適應(yīng)度高的個體作為父代進行交叉變異，經(jīng)過一定代數(shù)的遺傳進化可使種群收斂到全局最優(yōu)解，得到最優(yōu)路徑。仿真實驗證明該算法在尋找最優(yōu)路徑方面可行、有效，并將其應(yīng)用于虛擬船舶機艙視景仿真的管路布置設(shè)計中，對船舶生產(chǎn)設(shè)計中的管路布置有一定參考價值。

【關(guān)鍵詞】船舶制造 機艙管路 自動布置 遺傳算法

0 引言

船舶機艙是典型的復雜室內(nèi)場景，艙內(nèi)管路縱橫交錯，設(shè)備繁多，高效地管路布置是實現(xiàn)船舶設(shè)計制造和虛擬船舶機艙視景仿真的關(guān)鍵環(huán)節(jié)。機艙管路的布置是船舶制作設(shè)計中的重要一環(huán)，但由于機艙管路較為復雜，目前還主要依靠管路設(shè)計經(jīng)驗豐富的專業(yè)人員來完成，自動化程度較低，并且使船舶整體的設(shè)計周期延長。因此，在整個機艙管路設(shè)計中，自動化技術(shù)的運用對于提高船舶設(shè)計效率、降低設(shè)計成本具有重要的意義。

在實船中，對管路的布置和敷設(shè)必須要滿足很多約束條件。在本研究中，認為對以下的幾個條件是必不可少的：

（1）空間方面：所布置管路要能夠自動避開機艙設(shè)備、管路及艙壁等。

（2）成本方面：所設(shè)計出的管路要求在經(jīng)濟方面達到最優(yōu)，即在管路能夠避開機艙設(shè)備的前提下，其總長度最短（耗費材料最少），管路的彎折次數(shù)即法蘭數(shù)量最少。

（3）安裝方面：管路應(yīng)盡量貼艙壁或艙頂布置，不能離艙壁太遠，同時應(yīng)不出現(xiàn)斜管。

大部分文獻在判斷障礙物時采用在目標函數(shù)中加入罰函數(shù)法，這種一貫的做法表面上看能夠剔除種群中適應(yīng)度值較低的個體，但實際上在初始化種群時產(chǎn)生了很多非法個體；文獻[3]的選擇算子在利用最優(yōu)保存策略時替換個體數(shù)量略少，算法參數(shù)選取所得結(jié)果并非最優(yōu)。據(jù)此本文提出一種遺傳算法，在初始化種群時采用逐點判斷的方法來減少非法個體的產(chǎn)生，并且增加最優(yōu)個體保存數(shù)量，將其用于船舶虛擬機艙的管路自動敷設(shè)，仿真實驗證明該方法可行、有效。

1 遺傳算法概述

遺傳算法（Genetic Algorithm）是借鑒達爾文生物進化論中自然選擇和遺傳學原理來模擬優(yōu)化計算的模型算法，通過不斷進化逐漸搜索出過程最優(yōu)解。遺傳算法種群中的每一個體代表一個可行解，通過這些個體模擬自然界中生物染色體的交叉變異過程，產(chǎn)生新的種群，使個體的適應(yīng)度值（優(yōu)秀程度）越來越大，當進化到一定代數(shù)時，最佳個體被保留，即得到解決問題的最優(yōu)解。

2 算法設(shè)計

2.1 管路編碼設(shè)計

編碼操作是運用遺傳算法解決實際問題的重要一環(huán)，整個算法是否能夠成功在很大程度上取決于編碼操作。在本例中，用長方體空間來簡化模擬實船機艙，并將其均勻切割為A×B×C個坐標的節(jié)點，每個節(jié)點的坐標即固定為（a，b，c），例如一個長、寬、高分別為1、2、3的長方體型三維空間，其總的節(jié)點數(shù)為24（2×3×4）個，節(jié)點采用十進制方式進行編碼。在三維空間中，若給定起點和終點，那么能夠連接這兩個點的任意一條管路就是一個染色體，也就是一個個體，這個個體的基因即為其上的每個坐標點，在上例中管路{（0，0，0），（1，0，0），（1，0，1），（1，0，2），（1，0，3），（1，1，3），（1，2，3）}就是滿足條件的種群中的一個個體（染色體），路徑上的坐標點即為其基因。由于管路可能存在反復、回折等現(xiàn)象，因此對于符合條件的管路其長度是不確定的，這就導致每條染色體上的編碼長度不一定，因此必須采用變長度的編碼方式進行編碼。在實際編碼中，管路節(jié)點從起始點出發(fā)，每次前進一個節(jié)點，直至到達終點，為了避免產(chǎn)生斜線，下一個節(jié)點的坐標只能與上一個坐標在某一個坐標軸上相差1，比如前一個節(jié)點坐標為（i，j，k），那么后一個節(jié)點坐標就必須為（i+1，j，k），（i-1，j，k），（i，j+1，k），（i，j-1，k），（i，j，k+1）和（i，j，k-1）中的一個，使用這種策略得出的管路可使其路徑任意一段始終平行于長方體空間的棱。

2.2 種群的初始化

所布置管路構(gòu)成的種群初始化就是指在整個算法的起始隨機生成多條滿足條件的路徑，這些路徑都能夠從起始點到達終止點。但如果缺乏導向，管路在機艙三維空間的移動就具有相當大的隨機性，這會導致管路在空間中出現(xiàn)折返、交叉等現(xiàn)象，與實際不相符合，為避免這種情況發(fā)生，在使用算法搜索路徑時，若管路是向終點方向移動，那么規(guī)定此時向這個方向移動的概率將大大超過向其他方向移動的概率，使用這種方式可使種群中優(yōu)良個體的比例大大提升。

管路按照概率大小由起始點向終止點移動，每相鄰兩個節(jié)點的距離為1，此時初始化生成的種群中一定有許多管路穿越障礙物，不滿足要求。文獻[3]在解決此問題時采用了罰函數(shù)的辦法，當生成的管路穿越障礙物時，立即將此管路的適應(yīng)度值將至最低，而此個體由于適應(yīng)度較低無法進入下一代，這種辦法有效但帶來的后果是使種群中生成的有用個體減少，并且使整個算法的計算效率下降。所以本文在初始化種群個體過程中，管路在由上一個節(jié)點向下一個節(jié)點移動時，則判斷下一個節(jié)點是否在障礙物中，若在則直接將此點剔除，重新向其他方向移動，而這點是一定存在的，若這點不在障礙物中則繼續(xù)向下一點搜尋，直至完成管路的初始化，使用這種辦法得到的個體一定是已經(jīng)避開障礙物的管路。

另外，在初始化過程為避免管路折返，特采用截斷機制，如初始化可能生成回路如（0，0，0），（0，0，1），（0，0，2），（0，1，2），（0，1，1），（0，0，1），（0，1，1），采用截斷機制后直接簡化為（0，0，0），（0，0，1）， （0，1，1）。

2.3 目標函數(shù)和適應(yīng)度函數(shù)的設(shè)計

在設(shè)計初期，需要對障礙物模型進行簡化，將機艙簡化為立方體空間，設(shè)備、已有的管路等障礙物簡化為長方體空間。引言中的（1）條件已經(jīng)在種群的初始化中實現(xiàn)，對于條件（2）可以通過編程時計算和比對坐標實現(xiàn)管路總長度和彎頭數(shù)的統(tǒng)計；對于條件（3），本文引入能量值的概念，也就是將空間各個節(jié)點賦予一定的能量值，搜索管路的過程也就是將所經(jīng)過的節(jié)點能量值累加的過程。規(guī)定距離艙壁近的坐標點能量值低，而距離艙壁較遠的坐標點則能量值較高，規(guī)定能量較低的個體適應(yīng)度高，這樣即可使所產(chǎn)生的管路個體大部分為貼艙壁布置。在圖1中（b）節(jié)點較（a）節(jié)點離艙壁更近，故其能量值較低，經(jīng)過該節(jié)點的個體由于適應(yīng)度值較高而易于保留并進入下一代種群。本文使用E（r）表示管路總的能量值，在不斷的進化過程中使E（r）值最低，從而使管路盡量貼艙壁布置。

綜上所述本文中遺傳算法的目標函數(shù)取為式（1），適應(yīng)度函數(shù)可取為式（2）或式（3）。

表示一條管路的總長度，l（nodei，nodei+1）表示管路路徑中相鄰兩個節(jié)點之間的距離，在本文中都為常數(shù)1；B（r）表示管路路徑總彎頭數(shù)；E（r）為所得管路的能量值；其中，A為適當大的正常數(shù)，需保證F（r）的取值為非負數(shù)；a，b，c均為正常數(shù)系數(shù)。

2.4 選擇算子的設(shè)計和改進

本文結(jié)合排序選擇思想和最優(yōu)保存策略思想，在進化過程中首先將種群的所有個體按照適應(yīng)度的大小由高到低依次排列，然后將適應(yīng)度最高的3個個體替換適應(yīng)度最低的3個個體，種群中其他個體保持不變，這樣一方面可以保留比較優(yōu)秀的個體，另外也不會使部分個體在早期就占據(jù)全部種群空間，從而保持了種群多樣性，避免了遺傳算法中“早熟”的現(xiàn)象發(fā)生。算法的整個選擇過程如圖2所示。

2.5 交叉與變異算子的設(shè)計

在本算法中，染色體為所生成的管路，基因則為管路上的各個坐標點，個體的雜交就是各自染色體的配對和交叉，本算法采用基本的隨機組合雜交策略，也就是將初始化產(chǎn)生的全部個體兩兩配對，經(jīng)過交叉遺傳產(chǎn)生2個新個體。本算法由于其特殊性必須采用十進制進行編碼，因而交叉操作也基于十進制完成，經(jīng)過試驗，算法運用交叉點雜交結(jié)合隨機點雜交來完成染色體的配對。雜交原理如圖3和圖4所示。

文獻[3]采用交叉點雜交和隨機點雜交結(jié)合的辦法，但并未詳細說明種群何時以及如何采用交叉點雜交，文獻[4]只探討了隨機點雜交，這樣在一定程度上降低了種群的多樣性。本文基于文獻[3]和文獻[4]設(shè)計出改進的雜交算子，將兩種雜交方式相結(jié)合，在開始進行交叉操作時就將每條管路上的坐標點（基因）進行一一比對，如果有相同坐標，則采用交叉點雜交辦法進行雜交，如果有多個相同的坐標點，就多次運用交叉點雜交操作，生成一對新的個體，運用這種辦法可能在一定程度上降低了程序的運行效率，但可使種群的多樣性大大增加，對最終產(chǎn)生符合條件的個體非常有利。另外，產(chǎn)生的子代個體中還有可能出現(xiàn)管路坐標點相同的情況，此時依然采用截斷策略來對個體進行保留。

為了盡量減少遺傳算法的局部收斂現(xiàn)象，本文采用如圖5的貼墻壁操作和去彎頭操作來實現(xiàn)變異操作，從而對個體的基因進行局部改造。

圖6為運用遺傳算法解決管路自動布置問題完整的流程圖。

3 仿真實驗

本文在Windows7環(huán)境下，用MATLAB R2013a軟件實現(xiàn)遺傳算法應(yīng)用與船舶管路布置的仿真實驗，并分析其結(jié)果。本文使用相對頂點坐標為（0，0，0）和（30，30，30）的立方體來模擬船舶的機艙三維空間，在其中設(shè)置3個長方體障礙物用來模擬機艙中的設(shè)備或管路，使用相對頂點坐標為（0，15，0）和（5，25，25）的長方體來模擬第一障礙物，用相對頂點坐標為（25，0，0）和（30，5，30）的長方體空間來模擬第二障礙物，使用相對頂點坐標為（10，25，25）和（20，30，30）的長方體來模擬第三障礙物。為了簡化，規(guī)定機艙空間的相對頂點為所布置管路的路徑起始點和終止點，即（0，0，0）為管路布置的起點，（30，30，30）為管路布置的終點，整個模型空間如圖7所示。

在遺傳算法解決實際問題的過程中，參數(shù)的設(shè)定會對算法的性能產(chǎn)生較大的影響，這些參數(shù)包括種群大小、進化代數(shù)、交叉概率和變異概率等。但到目前為止還沒有定論能夠指導如何選擇合適的參數(shù)能夠使算法最優(yōu)，在解決實際問題中基本還依賴前人的經(jīng)驗和大量的重復試驗。

本文在已有文獻基礎(chǔ)上進行了大量的試驗，確定了能夠使結(jié)果達到最優(yōu)的參數(shù)，規(guī)定初始化產(chǎn)生種群中的個體數(shù)量為300個，使其進化完成交叉變異過程120代，即種群進行120次的交叉變異操作，交叉的概率經(jīng)過試驗0.7為最優(yōu)，變異操作由于視情況不同故不設(shè)定變異概率；另外設(shè)定其他參數(shù)A=1000，a=0.004，b=0.005，c=0.003。

通過計算機仿真實驗計算100次后，產(chǎn)生的種群中個體大部分管路總長度為90左右，總的彎折數(shù)（即法蘭數(shù)）在10個上下，從中選出一條各方面均較為滿意的管路為{（0，0，0），（0，2，0），（0，2，30），（0，3，30），（7，3，30），（7，15，30），（16，15，30），（16，23，30），（28，23，30），（28，30，30）， （30，30，30）}。該管路的總長度為90，總彎頭數(shù)為9。圖8展示了該管路路徑的三維空間走向。從圖中可以看出，該管路基本滿足了我們的各項需求，總長度最短，彎頭數(shù)最少，并且能夠避開空間內(nèi)的多個障礙物，也基本能夠貼艙壁布置。但經(jīng)觀察后發(fā)現(xiàn)，管路在幾個位置存在連續(xù)彎折兩次的問題，這是遺傳算法的特性使然，此時需要對所得管路進行適當?shù)奈⒄{(diào)，使其更加符合要求，將其調(diào)整為如圖9的{（0，0，0），（0，2，0），（0，2，30），（7，2，30），（7，23，30），（28，23，30）， （28，30，30），（30，30，30）}，這條管路的總長度仍然沒有變化，但管路總的彎折數(shù)（法蘭數(shù)）減少至6個，經(jīng)濟性更加良好，也使管路的走向更加美觀。在解決實際問題時，自動化的算法設(shè)計出的管路能夠為我們在機艙管路布置中提供一定的導向作用，但由于算法本身存在一定隨機性，導致生成的管路難免會有不合理或不經(jīng)濟的情況，那么這時候船廠的技術(shù)人員可適當對生成的管路進行微調(diào)，使其更加滿足需求。

算法運行結(jié)束后，運用MATLAB分析整個算法的進化過程，圖10為最終生成的所有管路的適應(yīng)度值，其按照由高到低排列，可以看出在最終產(chǎn)生的種群中大部分個體的適應(yīng)度值都能接近最大值，其中最高的適應(yīng)度值為999.7。

圖11與圖12為運用該算法時個體適應(yīng)度值隨遺傳進化代數(shù)變化的趨勢圖，從圖中可以看出，該算法在進化到約80代左右時實現(xiàn)收斂，收斂時的迭代時間大約8分鐘左右。

將該算法應(yīng)用于虛擬船舶機艙視景仿真中，同時對多條管路進行布置，實際證明取得了良好的效果，能夠避開障礙物，并且使管路長度較短，同時也節(jié)約了管路布置的時間，圖13為該算法應(yīng)用于30萬噸VLCC虛擬船舶機艙管路布置的實際效果圖。

4 結(jié)論

本文著重研究了一種基于遺傳算法的船舶管路自動布置方法，在一定的立體空間內(nèi)，將染色體的編碼、選擇、交叉和變異操作應(yīng)用于船舶管路的節(jié)點連接，自動尋找出一條能夠避開障礙物，不走斜線，盡量貼近墻壁，且管路總長度和彎頭數(shù)最少的路徑。

經(jīng)過仿真實驗表明：算法切實有效可行，能夠在初始化時即排除進入障礙物的個體，最終基本生成符合條件的管路路徑，操作簡單方便，外加對管路適當?shù)匚⒄{(diào)，能夠使管路的路徑完全符合實際的要求。這種方法再經(jīng)更深入的研究和推廣后，能夠應(yīng)用于船廠的管路布局設(shè)計環(huán)節(jié)，從而提高船舶的設(shè)計效率。

參考文獻

[1]曾鴻，任光，蘇玉龍.虛擬船舶機艙場景中的快速自動漫游算法研究[J].大連海事大學學報：自然科學版，2012，38（04）：39-42.

[2]鄒玉堂，任光，路慧彪.船舶管路布置仿真模型簡化[J].上海海事大學學報，2010，31（01）：72-76.

[3]白明.船舶管系路徑優(yōu)化算法研究[D]. 哈爾濱：哈爾濱工程大學，2010，45-65.

[4]劉少卿.基于維修性的船舶管路布局優(yōu)化研究[D].武漢：武漢理工大學，2010：20-52.

[5]姜銀煥.基于遺傳算法的液壓支架管路優(yōu)化布置[J].煤礦機械，2013，34（11）：24-25.

[6]沈龍澤，劉衍聰，王文超，等.海洋石油平臺自動化管路布局優(yōu)化算法設(shè)計[J]. 石油機械，2014，42（02）：34-39.

[7]盧永進，華志剛.基于FORAN的船舶管路三維設(shè)計研究[J].船海工程，2012，41（05）：77-80.

[8]賈金，宋永莊， 張闖，等.船舶管路綜合布局優(yōu)化[J].科技資訊，2013（23）：90-90.

[9]閆興亞，吳加賀，石云平.基于遺傳算法的虛擬校園漫游路徑規(guī)劃[J].西安郵電大學學報，2013，18（06）：80-84.

[10]趙柏萱，寧汝新，劉檢華.虛擬環(huán)境下的管路布局與裝配仿真系統(tǒng)關(guān)鍵技術(shù)[J].北京理工大學學報，2010，30（08）：895-900.

[11]范小寧.船舶管路布局優(yōu)化方法及應(yīng)用研究[D].大連理工大學，2006.

[12]Wang Y，Wang C，Peng F，et al. Intelligent layout design of ship pipes based on genetic algorithm with hu-man-computer cooperation[J].Ship Building of China，2015，56（01）：196-202.

[13]Ito T.Genetic algorithm approach to piping route path planning[J]. Journal of Intelligent Manufacturing， 1999，10（01）：103-114.

作者簡介

高躍峰（1989-），男，山西省忻州市人。碩士學位?，F(xiàn)為大連海事大學輪機工程學院實驗教師，助理實驗室。主要研究方向為輪機工程。

張均東（1967-），男，浙江省金華市人。博士學位?，F(xiàn)為大連海事大學輪機工程學院教師，教授。主要研究方向為輪機自動化與智能化。

作者單位

大連海事大學輪機工程學院 遼寧省大連市 116026