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

高躍峰+張均東

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

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

0 引言

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

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

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

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

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

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

1 遺傳算法概述

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

2 算法設計

2.1 管路編碼設計

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

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

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

另外，在初始化過程為避免管路折返，特采用截斷機制，如初始化可能生成回路如（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 目標函數和適應度函數的設計

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

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

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

2.4 選擇算子的設計和改進

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

2.5 交叉與變異算子的設計

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

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

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

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

3 仿真實驗

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

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

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

通過計算機仿真實驗計算100次后，產生的種群中個體大部分管路總長度為90左右，總的彎折數（即法蘭數）在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，總彎頭數為9。圖8展示了該管路路徑的三維空間走向。從圖中可以看出，該管路基本滿足了我們的各項需求，總長度最短，彎頭數最少，并且能夠避開空間內的多個障礙物，也基本能夠貼艙壁布置。但經觀察后發現，管路在幾個位置存在連續彎折兩次的問題，這是遺傳算法的特性使然，此時需要對所得管路進行適當的微調，使其更加符合要求，將其調整為如圖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）}，這條管路的總長度仍然沒有變化，但管路總的彎折數（法蘭數）減少至6個，經濟性更加良好，也使管路的走向更加美觀。在解決實際問題時，自動化的算法設計出的管路能夠為我們在機艙管路布置中提供一定的導向作用，但由于算法本身存在一定隨機性，導致生成的管路難免會有不合理或不經濟的情況，那么這時候船廠的技術人員可適當對生成的管路進行微調，使其更加滿足需求。

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

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

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

4 結論

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

經過仿真實驗表明：算法切實有效可行，能夠在初始化時即排除進入障礙物的個體，最終基本生成符合條件的管路路徑，操作簡單方便，外加對管路適當地微調，能夠使管路的路徑完全符合實際的要求。這種方法再經更深入的研究和推廣后，能夠應用于船廠的管路布局設計環節，從而提高船舶的設計效率。

參考文獻

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

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

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

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

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

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

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

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

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

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

[11]范小寧.船舶管路布局優化方法及應用研究[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為大連海事大學輪機工程學院實驗教師，助理實驗室。主要研究方向為輪機工程。

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

作者單位

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