基于迷宮算法和遺傳算法的船舶管路路徑規(guī)劃

隋海騰，牛文鐵

（天津大學(xué)機(jī)構(gòu)理論與裝備設(shè)計(jì)教育部重點(diǎn)實(shí)驗(yàn)室，天津　300072）

基于迷宮算法和遺傳算法的船舶管路路徑規(guī)劃

隋海騰，牛文鐵

（天津大學(xué)機(jī)構(gòu)理論與裝備設(shè)計(jì)教育部重點(diǎn)實(shí)驗(yàn)室，天津300072）

船舶管路的多樣性和布局環(huán)境中約束的復(fù)雜性導(dǎo)致管路設(shè)計(jì)效率低下.為輔助設(shè)計(jì)人員提高管路設(shè)計(jì)效率并減少人為錯(cuò)誤，提出了一種新的管路設(shè)計(jì)方法.首先，基于軸平行包圍盒簡(jiǎn)化管路布局空間，利用柵格法對(duì)其進(jìn)行離散化，并賦予空間網(wǎng)格特定的能量值，構(gòu)建管路布局優(yōu)化問題的數(shù)學(xué)模型.其次，基于遺傳算法的框架，引入改進(jìn)迷宮算法，提出管路路徑規(guī)劃方法，其中：迷宮搜索中引入輔助點(diǎn)的概念，增加了遺傳算法中初始種群的多樣性，有利于提高遺傳算法的全局搜索能力；提出了定長(zhǎng)度的編碼方法，簡(jiǎn)化了管路染色體處理難度，提高了算法性能；基于引入方向優(yōu)先搜索策略的迷宮算法，設(shè)計(jì)定長(zhǎng)度編碼遺傳算子，保證了子代個(gè)體的質(zhì)量，提高算法的收斂速度.最后，基于仿真試驗(yàn)，驗(yàn)證算法的性能.試驗(yàn)結(jié)果表明了該方法的可行性和高效率，以及其對(duì)實(shí)際管路布局工作具有指導(dǎo)意義.

管路布局；迷宮算法；遺傳算法；定長(zhǎng)度編碼

從20世紀(jì)70年代起，管路布局設(shè)計(jì)問題已經(jīng)在諸如航空發(fā)動(dòng)機(jī)、大規(guī)模集成電路及船舶機(jī)艙等工業(yè)領(lǐng)域成為一個(gè)熱門的研究課題.管路設(shè)計(jì)是船舶設(shè)計(jì)過程中至關(guān)重要的部分.由于布局空間結(jié)構(gòu)的復(fù)雜性、管路數(shù)量眾多以及各種設(shè)計(jì)約束等，船舶管路布局工作復(fù)雜而耗時(shí)［1］.因此，需要一種智能優(yōu)化設(shè)計(jì)方法輔助設(shè)計(jì)人員提高設(shè)計(jì)效率，減少設(shè)計(jì)過程中的人為錯(cuò)誤.

在路徑規(guī)劃問題的研究中，傳統(tǒng)的搜索算法包括Dijkstra算法［2］、迷宮算法［3-4］等.其中迷宮算法是經(jīng)典的布線算法，在管路解存在的條件下，迷宮算法一定能找到最優(yōu)解；但當(dāng)搜索空間的范圍增大時(shí)，迷宮算法則需要大量的數(shù)據(jù)存儲(chǔ)空間，其搜索效率降低.對(duì)此，Hightower［5］提出了逃逸算法，有效提高了算法的搜索效率，但是難以保證搜索到最短路徑.近年來，現(xiàn)代優(yōu)化算法［6-16］的發(fā)展推動(dòng)了管路路徑規(guī)劃算法的進(jìn)一步研究，遺傳算法［6-9］是具有代表性的一種算法.Ito［6］應(yīng)用遺傳算法對(duì)二維空間的管路布局問題進(jìn)行了系列的研究，提出變長(zhǎng)度的編碼方法，引入空間能量的概念，取得了較好的仿真驗(yàn)證結(jié)果.范小寧等［8］基于遺傳算法提出了變長(zhǎng)度編碼的交叉變異方法，求解三維空間管路布局問題，其仿真實(shí)例也驗(yàn)證了算法的有效性.但是，變長(zhǎng)度編碼易產(chǎn)生過分冗長(zhǎng)的管路，而這些管路對(duì)更優(yōu)管路的搜索意義不大，造成程序設(shè)計(jì)復(fù)雜，影響算法效率.此外，專家系統(tǒng)法也被廣泛應(yīng)用于管路布局的實(shí)踐中.

針對(duì)上述問題，本文在對(duì)簡(jiǎn)化布局空間進(jìn)行網(wǎng)格劃分并完成網(wǎng)格能量值分布的基礎(chǔ)之上，構(gòu)建了管路布局優(yōu)化問題的數(shù)學(xué)模型.進(jìn)一步將改進(jìn)的迷宮算法與遺傳算法相結(jié)合，提出一種優(yōu)化設(shè)計(jì)方法解決管路路徑規(guī)劃問題.引入輔助點(diǎn)改進(jìn)迷宮算法保證了初始種群的多樣性，保證了管路編碼的連續(xù)并且沒有重復(fù)基因段.在此基礎(chǔ)上，提出了定長(zhǎng)度的管路染色體編碼方法，并結(jié)合基于引入方向優(yōu)先搜索策略的迷宮算法設(shè)計(jì)相應(yīng)的操作算子，提高了遺傳算法的性能.仿真試驗(yàn)驗(yàn)證了算法的有效性和可行性.

1　管路布局問題描述

船舶艙室空間有限，布局環(huán)境復(fù)雜，而且管路系統(tǒng)復(fù)雜，在管路布局過程中需要滿足多種約束.其中主要的約束有障礙躲避、管路長(zhǎng)度最短、管路彎頭數(shù)最少、保證管路間的安全距離及管路支架的公用性等.本文考慮的管路布局的評(píng)價(jià)標(biāo)準(zhǔn)為管路總長(zhǎng)度最短、彎頭數(shù)最少和管路的并行性好；將障礙躲避等作為管路布局優(yōu)化問題的約束條件.針對(duì)以上的評(píng)價(jià)標(biāo)準(zhǔn)與約束條件，首先闡述了布局空間的數(shù)學(xué)描述方法，并在此基礎(chǔ)之上構(gòu)成了管路布局優(yōu)化問題的數(shù)學(xué)模型.

1.1布局空間表達(dá)

船舶管路布局空間的表達(dá)指對(duì)布局環(huán)境中船舶設(shè)備、管路的實(shí)體模型的數(shù)學(xué)描述，其首要任務(wù)是進(jìn)行空間劃分.本文利用軸平行包圍盒對(duì)布局空間進(jìn)行包絡(luò)，并將其分解為m×n×l個(gè)均等的網(wǎng)格細(xì)胞.選定包圍盒某一頂點(diǎn)作為坐標(biāo)原點(diǎn)，并設(shè)定其坐標(biāo)值為（1，1，1），則其他各個(gè)網(wǎng)格細(xì)胞的坐標(biāo)由其與原點(diǎn)網(wǎng)格的相對(duì)位置關(guān)系決定，換句話說，當(dāng)前網(wǎng)格所處的行、列、層即為其坐標(biāo)值.同時(shí)，各個(gè)網(wǎng)格細(xì)胞也被賦予了一個(gè)默認(rèn)的標(biāo)定值“0”，代表了布局環(huán)境中的可行布局空間.工作空間中的船舶設(shè)備、已生成的管路等都是布局過程中的障礙，其所占據(jù)的網(wǎng)格被賦予一個(gè)標(biāo)定值“#”，代表工作環(huán)境中的不可行空間.完整地表達(dá)設(shè)備、管路的模型信息需要大量的存儲(chǔ)空間，影響算法的運(yùn)行效率.據(jù)此，本文利用軸平行包圍盒對(duì)船舶設(shè)備進(jìn)行包絡(luò)，極大地簡(jiǎn)化了模型的表達(dá)；同時(shí)，對(duì)于生成的管路，本文也將其圓形橫截面處理為矩形橫截面.鑒于網(wǎng)格劃分的精度和各障礙在工作空間中的位置差異性，每個(gè)網(wǎng)格細(xì)胞存在3種狀態(tài)：空、完全被占據(jù)和部分被占據(jù).文中將部分被占據(jù)的網(wǎng)格細(xì)胞視為完全占據(jù)，并賦予標(biāo)定值“#”.圖1為一個(gè)簡(jiǎn)化布局空間網(wǎng)格劃分后對(duì)布局障礙和生成管路進(jìn)行表達(dá)的例子.

圖1　布局空間表達(dá)示例Fig.1 An example for representation of layout space

基于上述空間劃分方法，管路路徑即被定義為一條從起始點(diǎn)到終止點(diǎn)、由一系列相互鄰接網(wǎng)格組成的折線段，并假定管路的中軸線穿過各網(wǎng)格點(diǎn)的中心.一條管路路徑的編碼即與其所穿過的網(wǎng)格細(xì)胞相對(duì)應(yīng)的坐標(biāo)值構(gòu)成的序列，其中，路徑的始、末點(diǎn)即為船舶設(shè)備的進(jìn)、出口.但是，采用上述的簡(jiǎn)化方法對(duì)設(shè)備模型進(jìn)行簡(jiǎn)化之后，會(huì)導(dǎo)致設(shè)備進(jìn)、出口被包含在模型內(nèi)，因此，將設(shè)備的原進(jìn)、出口沿中心軸線向外延伸至模型外部的鄰接網(wǎng)格，并以此網(wǎng)格作為新的管路接口點(diǎn).

1.2能量值分布

在管路布局設(shè)計(jì)過程中，2條或者多條管路并行時(shí)，可以共享管路支架，降低管路安裝的費(fèi)用.為了便于對(duì)管路并行性的優(yōu)劣進(jìn)行評(píng)價(jià)，文中對(duì)布局空間中劃分的網(wǎng)格細(xì)胞賦予特定的能量值，表示該網(wǎng)格的優(yōu)先權(quán)值［6］.本文假定，能量值越低，管路穿過該區(qū)域的消耗越小，該網(wǎng)格的優(yōu)先權(quán)值越大.對(duì)于不可行布局空間所包含的網(wǎng)格細(xì)胞，其默認(rèn)能量值為E∞；對(duì)于可行布局空間包含的所有網(wǎng)格細(xì)胞，其能量值的默認(rèn)值為E.當(dāng)布局空間中存在已生成的管路時(shí)，管路本身所穿過的網(wǎng)格細(xì)胞的能量值為“無窮”，但其周圍網(wǎng)格細(xì)胞的能量值根據(jù)距離差異被賦予不同的能量值Ei（Ei＜E）.圖2為一個(gè)對(duì)管路周圍網(wǎng)格細(xì)胞能量值進(jìn)行賦值的例子.

圖2　布局空間網(wǎng)格能量值評(píng)估示例Fig.2 An example for evaluation of energy value of grid cells

1.3優(yōu)化數(shù)學(xué)模型的建立

有以上的介紹可知，船舶管路路徑尋優(yōu)問題是典型的多目標(biāo)優(yōu)化問題，其本質(zhì)是尋找一組滿足約束條件并使評(píng)價(jià)函數(shù)得到最優(yōu)組合的解.本文根據(jù)工程設(shè)計(jì)經(jīng)驗(yàn)，對(duì)各個(gè)評(píng)價(jià)目標(biāo)賦予一個(gè)權(quán)值，將復(fù)雜的多目標(biāo)優(yōu)化問題轉(zhuǎn)換為單目標(biāo)優(yōu)化問題，并將迷宮算法和遺傳算法相結(jié)合對(duì)其進(jìn)行求解.依據(jù)評(píng)價(jià)標(biāo)準(zhǔn)，確定優(yōu)化問題的目標(biāo)函數(shù)Obj（f），見式（1），并將此目標(biāo)函數(shù)直接作為后文優(yōu)化算法中的適應(yīng)度函數(shù).

其中：c1，c2和c3為與各目標(biāo)函數(shù)相關(guān)的權(quán)重值，它們的值取決于優(yōu)化問題中目標(biāo)函數(shù)的重要性，且與設(shè)計(jì)人員對(duì)多個(gè)目標(biāo)函數(shù)的權(quán)衡相關(guān)；Lp為管路路徑的總長(zhǎng)度，Bp為管路路徑的拐彎次數(shù)，Ep為管路路徑所穿過的網(wǎng)格細(xì)胞能量值的總和.

2　管路路徑規(guī)劃方法

為解決方向優(yōu)先搜索策略存在的易產(chǎn)生無效管路而導(dǎo)致需要大量修補(bǔ)工作的問題，本文將迷宮算法和遺傳算法相結(jié)合，提出了一種新的管路路徑規(guī)劃方法.利用改進(jìn)迷宮算法生成少量的初始種群，迷宮算法擴(kuò)展編碼的連續(xù)性有效保證了種群中個(gè)體的有效性；而且，相比單純利用迷宮算法搜索所有可行路徑后比較選出最優(yōu)解的方法，遺傳算法所需的種群規(guī)模非常小，用以生成初始種群的迷宮算法的搜索效率也是可以接受的.在此基礎(chǔ)之上，利用遺傳算法對(duì)初始種群進(jìn)行優(yōu)化，并最終得出綜合最優(yōu)解.圖3為利用優(yōu)化算法進(jìn)行路徑規(guī)劃的流程圖，其中，gen表示遺傳代數(shù)，max gen表示設(shè)定的最大遺傳代數(shù).

圖3　路徑規(guī)劃算法流程圖Fig.3 Flow chart of pipe routing algorithm

2.1迷宮算法的改進(jìn)

2.1.1迷宮算法概述

迷宮算法是經(jīng)典的路徑搜索算法，主要包括擴(kuò)展搜索和回溯兩個(gè)過程.

擴(kuò)展搜索是指從一個(gè)網(wǎng)格細(xì)胞到另一個(gè)相鄰網(wǎng)格細(xì)胞的擴(kuò)張過程，并且對(duì)到達(dá)的網(wǎng)格賦予特定的標(biāo)定值進(jìn)行標(biāo)記.擴(kuò)展搜索持續(xù)進(jìn)行直到找到目標(biāo)網(wǎng)格點(diǎn)，其中擴(kuò)展過程與網(wǎng)格標(biāo)記的規(guī)則如下：

1）初始網(wǎng)格標(biāo)記為1；

2）只有當(dāng)前網(wǎng)格相鄰的可行空間網(wǎng)格可以被標(biāo)記，其標(biāo)定值為當(dāng)前網(wǎng)格標(biāo)定值加1；

3）當(dāng)前搜索到的網(wǎng)格已經(jīng)標(biāo)記，則取較小的值作為其標(biāo)定值.

回溯過程是從目標(biāo)點(diǎn)到起始點(diǎn)的反向搜索過程.回溯的方向取為網(wǎng)格標(biāo)記值減少的方向，每次遍歷1個(gè)網(wǎng)格細(xì)胞，直到找到起始網(wǎng)格點(diǎn).則由起始點(diǎn)到終止點(diǎn)的網(wǎng)格坐標(biāo)編碼構(gòu)成了一條可行并且無重復(fù)路徑段的聯(lián)通路徑.

2.1.2輔助點(diǎn)的引入

由于迷宮算法的編碼特性，直接利用迷宮算法可以對(duì)由以始、末點(diǎn)為對(duì)角頂點(diǎn)構(gòu)成的空間S進(jìn)行全局的搜索，但卻難以到達(dá)除此之外的布局空間.另外，試驗(yàn)發(fā)現(xiàn)，在利用迷宮算法進(jìn)行路徑搜索過程中存在與單純方向優(yōu)先搜索策略相同的問題：可行解多集中于始、末點(diǎn)對(duì)角連接線附近，而無法均勻遍布布局空間［6］.因此，本文在布局空間中引入了輔助點(diǎn)的概念.以圖4為例，空間S分別沿著坐標(biāo)軸的方向進(jìn)行適當(dāng)擴(kuò)充得到S′，為了能夠遍歷S′中所有的區(qū)域，增加管路多樣性，在S′中的可行空間中隨機(jī)產(chǎn)生一個(gè)輔助點(diǎn)P.以原起始點(diǎn)為起點(diǎn)，P點(diǎn)為終點(diǎn)，利用迷宮算法生成一條可行的輔助路徑A-P1；然后以P點(diǎn)為起點(diǎn)，原終止點(diǎn)為終點(diǎn)，產(chǎn)生另一條可行的輔助路徑A-P2；將2條路徑連接，便構(gòu)成了一條新的有效的路徑.輔助點(diǎn)的引入擴(kuò)大了迷宮算法的搜索范圍，增加了可行管路的多樣性，有助于算法搜尋到最優(yōu)的管路段，提高算法的搜索效率.

圖4　輔助點(diǎn)的引入Fig.4 Introduction of auxiliary point

2.2定長(zhǎng)度編碼

在改進(jìn)迷宮算法的基礎(chǔ)之上，結(jié)合迷宮算法自身的特點(diǎn)，本文提出了管路染色體的定長(zhǎng)度編碼策略.一般地，在由始、末點(diǎn)所構(gòu)成的布局空間S中可以搜索到有效的管路路徑，因此本文假定擴(kuò)展的空間即S′-S是無障礙的.由迷宮算法的搜索原理易知，利用其在布局空間S中搜索到的路徑長(zhǎng)度是相同的.但在擴(kuò)展空間中，由于輔助點(diǎn)位置的差異性，管路路徑的長(zhǎng)度也會(huì)有所不同，并且有一個(gè)最大長(zhǎng)度值.為了找到這個(gè)最大的長(zhǎng)度值，分別選取擴(kuò)展空間中的8個(gè)頂點(diǎn)作為輔助點(diǎn)，與原始末點(diǎn)共同構(gòu)造出可行的聯(lián)通路徑，并比較其路徑長(zhǎng)度，得出最大值.此最大值即為遺傳算法過程中染色體編碼的固定長(zhǎng)度值.

本文提出的定長(zhǎng)度編碼方法只需在遺傳操作進(jìn)行之前進(jìn)行1次，不會(huì)顯著增加算法的計(jì)算量，影響算法的運(yùn)行效率.而且，定長(zhǎng)度編碼克服了變長(zhǎng)度編碼在遺傳操作過程中程序設(shè)計(jì)復(fù)雜、運(yùn)行效率低等缺陷，有助于提高算法的收斂效率.

2.3遺傳算子

2.3.1選擇算子

本文采用的選擇方法為隨機(jī)聯(lián)賽選擇機(jī)制，其具體操作過程如下：從種群中隨機(jī)選擇N個(gè)個(gè)體進(jìn)行適應(yīng)度大小比較，將其中適應(yīng)度最高的個(gè)體遺傳到下一代，此處N=2；重復(fù)上述過程n次，便得到了包含n個(gè)個(gè)體的下一代種群.但是，單純采用聯(lián)賽選擇機(jī)制可能會(huì)造成最優(yōu)個(gè)體的丟失，因此，引入最優(yōu)個(gè)體保留策略，不失種群多樣性的同時(shí)保證了最優(yōu)個(gè)體的優(yōu)先權(quán).

2.3.2交叉算子

傳統(tǒng)的單點(diǎn)交叉操作是隨機(jī)選擇一個(gè)染色體串的節(jié)點(diǎn)位置，然后交換2個(gè)父代染色體節(jié)點(diǎn)右端部分來產(chǎn)生2個(gè)子代個(gè)體.在此基礎(chǔ)之上，結(jié)合范小寧等［8］所提出的變長(zhǎng)度編碼交叉方法，本文提出了基于定長(zhǎng)度編碼的交叉策略.此部分以圖5為例來說明定長(zhǎng)度編碼的交叉策略：隨機(jī)選定2個(gè)父代染色體Parent 1和Parent 2；分別在2個(gè)父代染色體上選擇2個(gè)交叉點(diǎn)，本例假設(shè)Parent 1上的交叉點(diǎn)為（1，5，3），Parent 2上的交叉點(diǎn)為（1，2，1）；分別以這2個(gè)交叉點(diǎn)為始、末點(diǎn)，利用改進(jìn)迷宮算法生成一條輔助路徑Mid-path 1，并與父代染色體重新結(jié)合生成2個(gè)子代個(gè)體Child 1和Child 2，結(jié)合方法如圖5所示.本例中，子代染色體Child 1長(zhǎng)度在限定長(zhǎng)度內(nèi)，不足位置由0補(bǔ)充；子代染色體Child 2的長(zhǎng)度超過了限定長(zhǎng)度，直接刪除.

圖5　定長(zhǎng)度編碼交叉方法Fig.5 Crossover based on fixed-length coding method

其中，此處的迷宮算法不同于初始路徑生成時(shí)采用的改進(jìn)迷宮算法，在擴(kuò)展過程結(jié)束后，算法的回溯過程采用方向優(yōu)先的搜索策略：利用2個(gè)點(diǎn)的位置關(guān)系確定優(yōu)選方向的矢量，隨機(jī)選擇初始方向，沿網(wǎng)格值減小的方向搜索，遇到障礙后改變回溯方向，直到找到終止點(diǎn)形成一條有效的聯(lián)通路徑作為子路徑；若多次改變方向仍無法找到有效的聯(lián)通路徑，則重新選擇交叉點(diǎn)，重復(fù)以上操作，直到找到可行的路徑. 2.3.3 變異算子

在基本位變異的思想的基礎(chǔ)上，結(jié)合變長(zhǎng)度編碼變異方法［8］，提出了基于定長(zhǎng)度編碼的變異策略.以圖6為例詳細(xì)敘述該策略的實(shí)現(xiàn)過程：隨機(jī)選定一個(gè)父代染色體Parent 3；在父代染色體上隨機(jī)選擇2個(gè)變異點(diǎn)，本例假設(shè)選定的變異點(diǎn)為（1，3，1）與（1，7，3）；分別以這2個(gè)變異點(diǎn)作為始、末點(diǎn)，利用與交叉操作中相同的迷宮算法構(gòu)造一條輔助路徑Midpath 2，并以該路徑替換父代染色體Parent 3上變異點(diǎn)間的基因段，生成一個(gè)子代染色體Child 3.同樣，若生成的子代個(gè)體長(zhǎng)度超過了定長(zhǎng)度編碼限定的長(zhǎng)度，則直接將其刪除，不計(jì)入子種群當(dāng)中.

圖6　定長(zhǎng)度編碼變異方法Fig.6 Mutation based on fixed-length coding method

3　仿真試驗(yàn)

3.1布局空間建模

在Windows 7的環(huán)境下，利用MATLAB 2011b實(shí)現(xiàn)了上述管路路徑規(guī)劃算法.試驗(yàn)建立了一個(gè)三維模擬空間Space-test，空間對(duì)角坐標(biāo)為（1，1，1）和（50，50，50）.利用布置在模擬空間Spacetest中的長(zhǎng)方體塊模擬布局過程中的障礙，各長(zhǎng)方體塊的對(duì)角坐標(biāo)如表1所示.

表1　障礙對(duì)角坐標(biāo)Table 1 Diagonal coordinates of obstacles

在確定了布局空間后，首先要對(duì)其進(jìn)行網(wǎng)格劃分.本例的模擬空間Space-test被劃分為50×50× 50個(gè)網(wǎng)格細(xì)胞，并賦予默認(rèn)標(biāo)定值和能量值.對(duì)于長(zhǎng)方體障礙空間中的網(wǎng)格，則將其標(biāo)記為“#”，賦予其能量值為“∞”.為充分檢驗(yàn)算法的性能，在模擬空間Space-test加入一條“已生成”直管路G-pipe，假定該管路路徑染色體編碼為：［（25，1，1）；（25，1，2）；（25，1，3）；…；（25，1，50）］，并依據(jù)前文所述能量值賦值方法對(duì)該管路及其周圍的網(wǎng)格細(xì)胞進(jìn)行賦值.其中，默認(rèn)能量值取為10，管路周圍網(wǎng)格能量值的范圍取為（2，6），偶數(shù)遞增.至此，完成了管路布局空間的構(gòu)建.

3.2仿真、結(jié)果與分析

對(duì)模擬空間Space-test進(jìn)行參數(shù)設(shè)置的基礎(chǔ)上，以公式（1）作為評(píng)價(jià)函數(shù)，利用本文提出的組合優(yōu)化算法對(duì)以（1，1，1）和（50，50，50）為始、末點(diǎn)的管路路徑進(jìn)行規(guī)劃求解.本例中各目標(biāo)函數(shù)采用的計(jì)量單位均為1，多次試驗(yàn)發(fā)現(xiàn)，當(dāng)各目標(biāo)函數(shù)的權(quán)值相同時(shí)，由于管路路徑的拐彎次數(shù)的取值相對(duì)于路徑總長(zhǎng)度值和路徑穿過的網(wǎng)格細(xì)胞總能量值較小，其對(duì)總體適應(yīng)度函數(shù)值的影響較小，易導(dǎo)致優(yōu)化算法無法收斂到最優(yōu)解.因此，需適當(dāng)增加目標(biāo)函數(shù)的Bp權(quán)值大小，并減小目標(biāo)函數(shù)Lp和Ep權(quán)值的大小.基于大量的試驗(yàn)總結(jié)，并考慮到各目標(biāo)函數(shù)對(duì)優(yōu)化結(jié)果影響的均衡性，最終將各目標(biāo)函數(shù)的權(quán)值c1，c2，c3依次確定為0.01，0.97，0.02.遺傳算法的參數(shù)如表2所示.

表2　遺傳算法的參數(shù)Table 2 Parameters of the genetic algorithm

算法的進(jìn)化過程如圖7所示，其中，圖示中x，y，z坐標(biāo)軸表示了布局空間中管路的位置坐標(biāo)值.參考圖7（a）可知，輔助點(diǎn)的引入增加了初始種群的多樣性，并使得管路能夠遍布整個(gè)布局空間，為得出最優(yōu)管路奠定了良好的基礎(chǔ).圖7（b）為算法收斂曲線圖，其中橫坐標(biāo)為遺傳代數(shù)，縱坐標(biāo)為適應(yīng)度函數(shù)值.可見，最優(yōu)個(gè)體保留策略保留了當(dāng)代的最優(yōu)個(gè)體，有助于算法向最優(yōu)解收斂；算法在23代左右收斂，證明了算法具有良好的收斂性能.圖7（c）為依據(jù)得到的最優(yōu)路徑編碼繪制的三維路線圖，作為比較，在布局空間Space-test中去除“已生成”管路G-pipe，則利用路徑規(guī)劃算法對(duì)其求解，得出的可能最優(yōu)管路路徑圖如圖7（d）所示.比較發(fā)現(xiàn)，所提出的算法能夠有效地找到一條長(zhǎng)度最短、拐彎次數(shù)最少并且具有良好并行性的綜合最優(yōu)管路.

圖7　優(yōu)化算法路徑規(guī)劃進(jìn)程Fig.7 Optimization procedure of pipe routing algorithm

為進(jìn)一步驗(yàn)證算法的效率，采用文獻(xiàn)［8］中的例子進(jìn)行對(duì)比試驗(yàn)，如圖8所示.測(cè)試結(jié)果顯示，在相同的測(cè)試條件下，本文的規(guī)劃算法平均迭代10次即可收斂，文獻(xiàn)［8］平均迭代60次；得到路徑圖如圖8（a）所示，圖8（b）為某次算法運(yùn)行過程的收斂曲線圖.對(duì)比試驗(yàn)結(jié)果，充分驗(yàn)證了改進(jìn)迷宮算法對(duì)提高算法搜索效率的顯著效果，也證明了所提出的路徑規(guī)劃算法具有較快的收斂速度和較高的搜索效率.

圖8　比較案例優(yōu)化進(jìn)程Fig.8 Optimization procedure of a comparative case

結(jié)合布局空間參數(shù)設(shè)置和優(yōu)化算法得到最優(yōu)管路，其仿真試驗(yàn)三維實(shí)體模型示意圖如圖9所示.應(yīng)當(dāng)注意，試驗(yàn)中的模型是對(duì)實(shí)際布局空間的一種簡(jiǎn)化，因此布局結(jié)果可能與實(shí)際的管路布局存在一定的差距.但試驗(yàn)結(jié)果表明了算法可以獲得一定約束條件下的綜合最優(yōu)解，可以對(duì)設(shè)計(jì)人員的管路布局工作提供有效的參考，提高其工作效率，因此該算法對(duì)實(shí)際布局工作具有一定的指導(dǎo)意義.

以上算法主要是針對(duì)兩點(diǎn)管路進(jìn)行路徑規(guī)劃，在此基礎(chǔ)上，進(jìn)行適當(dāng)擴(kuò)展即可對(duì)分支管路路徑進(jìn)行規(guī)劃.在處理分支管路路徑問題時(shí)，可以將分支管路視為若干個(gè)兩點(diǎn)管路，以最短重合路徑為評(píng)價(jià)標(biāo)準(zhǔn)并設(shè)計(jì)相應(yīng)的遺傳算子，利用優(yōu)化算法進(jìn)行優(yōu)化，從而得出近優(yōu)解.不難看出，本文所提出的算法為分支管路路徑規(guī)劃問題的研究奠定了良好的基礎(chǔ).

圖9　仿真環(huán)境管路布局結(jié)果Fig.9 Pipe layout result of simulation environment

4　結(jié) 論

本文將改進(jìn)的迷宮算法與遺傳算法相結(jié)合，提出了一種新的船舶管路布局方法.迷宮算法的應(yīng)用保證了管路編碼的連續(xù)性和無重復(fù)性，輔助點(diǎn)的引入增加了初始種群的多樣性，有利于算法搜索效率的提升.基于此，提出了定長(zhǎng)度的編碼方法，結(jié)合基于引入方向優(yōu)先搜索策略的迷宮算法，設(shè)計(jì)了相應(yīng)的遺傳操作算子.帶方向優(yōu)先策略的迷宮算法加快了遺傳算法的收斂速度，提高了搜索算法的收斂性能.仿真試驗(yàn)也表明所提出的算法能夠找到長(zhǎng)度最短、拐彎次數(shù)最少及并行性好的綜合最優(yōu)路徑，驗(yàn)證了其可行性和效率，以及對(duì)實(shí)際管路布局工作的指導(dǎo)意義.

［1］PARK J H，STORCH R L.Pipe-routing algorithm development：case study of a ship engine room design［J］. Expert Systems with Applications，2002，23（3）：299-309.

［2］DIJKSTRA E W.A note on two problems in connexion with graphs［J］.Numerische Mathematik，1959，1（1）：269-271.

［3］LEE C Y.An algorithm for path connections and its applications［J］.Ire Transactions on Electronic Computers，1961，10（3）：346-365.

［4］樊江，馬枚，楊曉光.航空發(fā)動(dòng)機(jī)外部管路自動(dòng)敷設(shè)研究［J］.機(jī)械設(shè)計(jì)，2003，20（7）：21-23.

FAN Jiang，MA Mei，YANG Xiao-guang.Research on automatic laying out for external pipeline of aero-engine［J］.Journal of Machine Design，2003，20（7）：21-23.

［5］HIGHTOWER D W.A solution to line routing problems on the continuous plane［C］//Proceedings of 6th Design Automation Workshop.IEEE，1969：1-24.

［6］ITO T.A genetic algorithm approach to piping route path planning［J］.Journal of Intelligent Manufacturing，1999，10（1）：103-114.

［7］ITO T.Developments in applied artificial intelligence［C］.Berlin：Springer，2002：547-556.

［8］范小寧，林焰，紀(jì)卓尚.船舶管路三維布局優(yōu)化的變長(zhǎng)度編碼遺傳算法［J］.中國造船，2007，48（1）：82-90.

FAN Xiao-ning，LIN Yan，JI Zhuo-shang.A variable length coding genetic algorithm to ship pipe path routing optimization in 3Dspace［J］.Shipbuilding of China，2007，48（1）：82-90.

［9］SANDURKAR Sunand，WEI Chen.GAPRUS—genetic algorithms based pipe routing using tessellated objects［J］.Computers in Industry，1999，38（3）：209-223.

［10］REN Tao，ZHU Zhi-liang，DIMIROVSKI G M，et al.A new pipe routing method for aero-engines based on genetic algorithm［J］.Proceedings of the Institution of Mechanical Engineers，Part G：Journal of Aerospace Engineering，2014，228（3）：424-434.

［11］JIANG Wen-ying，LIN Yan，CHEN Ming，et al.An ant colony optimization-genetic algorithm approach for ship pipe route design［J］.International Shipbuilding Progress，2014，61（3）：163-183.

［12］范小寧，林焰，紀(jì)卓尚.多蟻群協(xié)進(jìn)化的船舶多管路并行布局優(yōu)化［J］.上海交通大學(xué)學(xué)報(bào)，2009，43（2）：193-197.

FAN Xiao-ning，LIN Yan，JI Zhuo-shang.Multi ant colony cooperative co-evolution for optimization of ship muti pipe parallel routing［J］.Journal of Shanghai Jiaotong University，2009，43（2）：193-197.

［13］LIU Qiang，WANG Chen-gen.A discrete particle swarm optimization algorithm for rectilinear branch pipe routing［J］.Assembly Automation，2011，31（4）：363-368.

［14］LIU Qiang，WANG Chen-gen.Pipe-assembly approach for aero-engines by modified particle swarm optimization［J］.Assembly Automation，2010，30（4）：365-377.

［15］LIU Qiang，WANG Chen-gen.Multi-terminal pipe routing by Steiner minimal tree and particle swarm optimization［J］.Enterprise Information Systems，2012，6（3）：315-327.

［16］KIM S H，RUY W，JANG B S.The development of a practical pipe auto-routing system in a shipbuilding CAD environment using network optimization［J］.International Journal of Naval Architecture and Ocean Engineering，2013，5（3）：468-477.

Ship pipe route planning method based on maze algorithm and genetic algorithm

SUI Hai-teng，NIU Wen-tie
（Key Laboratory of Mechanism Theory and Equipment Design of Ministry of Education，Tianjin University，Tianjin 300072，China）

The diversity of piping systems and complexity of constrains in layout space lead to the low efficiency of ship pipe design.A new pipe route planning method was proposed to improve the design efficiency and reduce human errors.Based on the simplified layout space，the mathematical model was firstly built by the discretization of the layout space and the specific energy value which was given to the spatial network.Based on the constructed mathematical model，the improved maze algorithm and genetic algorithm were then combined together to conduct pipe route planning.The concept of auxiliary point was introduced to improve the maze searching performance，which guaranteed the diversity of initial population and enhanced the global search ability of genetic algorithm.A fixed-length coding method was also proposed to simplify the difficulty in handling the pipe chromosomes and improve the performance of algorithm.The direction oriented strategy was applied in maze retracing process to design the genetic operators with fixed-length chromosomes，which not only guaranteed the quality of children chromosomes but also improved the convergence speed of the algorithm.The simulation results verify the feasibility and effectiveness of this approach，and prove the guiding significance of the approach to actual ship pipe route planning.

pipe route planning；maze algorithm；genetic algorithm；fixed-length coding method

U 662.9

A

1006-754X（2016）02-0188-07

10.3785/j.issn.1006-754X.2016.02.013

2015-05-08.本刊網(wǎng)址·在線期刊：http：//www.journals.zju.edu.cn/gcsjxb

國家自然科學(xué)基金資助項(xiàng)目（51275340）.

隋海騰（1989—），男，山東煙臺(tái)人，碩士生，從事設(shè)計(jì)理論與方法研究，E-mail：suihaitengtju@tju.edu.cn. http：//orcid.org//0000-0002-3364-1715

牛文鐵（1971—），男，內(nèi)蒙古赤峰人，副教授，博士，從事設(shè)計(jì)理論與方法及數(shù)控機(jī)床數(shù)字化設(shè)計(jì)研究，E-mail：niuwentie@tju.edu.cn.