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

高躍峰+張均東

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

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

0 引言

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

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

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

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

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

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

1 遺傳算法概述

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

2 算法設(shè)計

2.1 管路編碼設(shè)計

編碼操作是運(yùn)用遺傳算法解決實(shí)際問題的重要一環(huán)，整個算法是否能夠成功在很大程度上取決于編碼操作。在本例中，用長方體空間來簡化模擬實(shí)船機(jī)艙，并將其均勻切割為A×B×C個坐標(biāo)的節(jié)點(diǎn)，每個節(jié)點(diǎn)的坐標(biāo)即固定為（a，b，c），例如一個長、寬、高分別為1、2、3的長方體型三維空間，其總的節(jié)點(diǎn)數(shù)為24（2×3×4）個，節(jié)點(diǎn)采用十進(jìn)制方式進(jìn)行編碼。在三維空間中，若給定起點(diǎn)和終點(diǎn)，那么能夠連接這兩個點(diǎn)的任意一條管路就是一個染色體，也就是一個個體，這個個體的基因即為其上的每個坐標(biāo)點(diǎn)，在上例中管路{（0，0，0），（1，0，0），（1，0，1），（1，0，2），（1，0，3），（1，1，3），（1，2，3）}就是滿足條件的種群中的一個個體（染色體），路徑上的坐標(biāo)點(diǎn)即為其基因。由于管路可能存在反復(fù)、回折等現(xiàn)象，因此對于符合條件的管路其長度是不確定的，這就導(dǎo)致每條染色體上的編碼長度不一定，因此必須采用變長度的編碼方式進(jìn)行編碼。在實(shí)際編碼中，管路節(jié)點(diǎn)從起始點(diǎn)出發(fā)，每次前進(jìn)一個節(jié)點(diǎn)，直至到達(dá)終點(diǎn)，為了避免產(chǎn)生斜線，下一個節(jié)點(diǎn)的坐標(biāo)只能與上一個坐標(biāo)在某一個坐標(biāo)軸上相差1，比如前一個節(jié)點(diǎn)坐標(biāo)為（i，j，k），那么后一個節(jié)點(diǎn)坐標(biāo)就必須為（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)成的種群初始化就是指在整個算法的起始隨機(jī)生成多條滿足條件的路徑，這些路徑都能夠從起始點(diǎn)到達(dá)終止點(diǎn)。但如果缺乏導(dǎo)向，管路在機(jī)艙三維空間的移動就具有相當(dāng)大的隨機(jī)性，這會導(dǎo)致管路在空間中出現(xiàn)折返、交叉等現(xiàn)象，與實(shí)際不相符合，為避免這種情況發(fā)生，在使用算法搜索路徑時，若管路是向終點(diǎn)方向移動，那么規(guī)定此時向這個方向移動的概率將大大超過向其他方向移動的概率，使用這種方式可使種群中優(yōu)良個體的比例大大提升。

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗

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

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

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

通過計算機(jī)仿真實(shí)驗計算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ù)彎折兩次的問題，這是遺傳算法的特性使然，此時需要對所得管路進(jìn)行適當(dāng)?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)濟(jì)性更加良好，也使管路的走向更加美觀。在解決實(shí)際問題時，自動化的算法設(shè)計出的管路能夠為我們在機(jī)艙管路布置中提供一定的導(dǎo)向作用，但由于算法本身存在一定隨機(jī)性，導(dǎo)致生成的管路難免會有不合理或不經(jīng)濟(jì)的情況，那么這時候船廠的技術(shù)人員可適當(dāng)對生成的管路進(jìn)行微調(diào)，使其更加滿足需求。

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

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

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

4 結(jié)論

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

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

[11]范小寧.船舶管路布局優(yōu)化方法及應(yīng)用研究[D].大連理工大學(xué)，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-），男，山西省忻州市人。碩士學(xué)位?，F(xiàn)為大連海事大學(xué)輪機(jī)工程學(xué)院實(shí)驗教師，助理實(shí)驗室。主要研究方向為輪機(jī)工程。

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

作者單位

大連海事大學(xué)輪機(jī)工程學(xué)院 遼寧省大連市 116026