基于改進(jìn)NSGA-Ⅱ的船舶管路路徑設(shè)計(jì)

董宗然，王法勝，樓偶俊，卞璇屹

(1.大連外國語大學(xué) 軟件學(xué)院，遼寧 大連 116044；2.大連民族大學(xué) 信息與通信工程學(xué)院，遼寧 大連 116600；3.大連理工大學(xué) 船舶工程學(xué)院，遼寧 大連 116024)

0 引言

船舶管路如同人體的血管，負(fù)責(zé)在船舶設(shè)備間傳輸油、氣、水、電等資源，對(duì)船舶功能實(shí)現(xiàn)和性能表現(xiàn)有著重要影響。船舶管路設(shè)計(jì)一般可分為：初步設(shè)計(jì)、功能設(shè)計(jì)、詳細(xì)設(shè)計(jì)、生產(chǎn)設(shè)計(jì)和系統(tǒng)支持信息5個(gè)連續(xù)階段[1]。其中，管路路徑的布局優(yōu)化設(shè)計(jì)屬于詳細(xì)設(shè)計(jì)階段的重要工作。船舶空間常按功能劃分為不同區(qū)域，如機(jī)艙區(qū)、生活區(qū)、甲板區(qū)、特殊功能區(qū)等。機(jī)艙空間相對(duì)狹小，設(shè)備和管路繁多，布局約束復(fù)雜，因此機(jī)艙區(qū)的管路布局優(yōu)化是船舶管路設(shè)計(jì)的難點(diǎn)[2]。船舶管路路徑設(shè)計(jì)本質(zhì)上是在設(shè)備接口間尋找滿足約束條件和優(yōu)化目標(biāo)的連通路徑，目前主要依靠人工在不斷試錯(cuò)中完成，十分低效。因此，研究自動(dòng)化船舶管路路徑設(shè)計(jì)方法具有重要意義。

相關(guān)研究在過去近二十年中發(fā)展迅速，一些代表性研究包括：KANG等[3]提出采用基于知識(shí)規(guī)則的專家系統(tǒng)布置船舶管路，并給出了一個(gè)原型系統(tǒng);PARK等[4]提出一種基于單元生成技術(shù)的管路設(shè)計(jì)方法，但由于單元生成模式有限，不適合復(fù)雜的管路布局;ASMARA[5]提出一個(gè)針對(duì)船舶機(jī)艙管路詳細(xì)設(shè)計(jì)的算法框架，為管路自動(dòng)設(shè)計(jì)系統(tǒng)開發(fā)指明方向;KIM等[6]在CAD環(huán)境下基于網(wǎng)絡(luò)優(yōu)化法開發(fā)了一個(gè)船舶管路設(shè)計(jì)系統(tǒng)，但該方法由于精度較低，只適合為管路初步設(shè)計(jì)提供參考;范小寧[7]提出基于蟻群算法布置船舶管路，JIANG等[8]、WANG等[9]對(duì)其工作進(jìn)行了擴(kuò)展研究。筆者早期工作提出基于最短快速算法[10]和LEE—禁忌搜索算法[11]求解船舶布管，關(guān)注算法效率和復(fù)雜約束處理，近期工作則側(cè)重遺傳算法在船舶管路布局方面的改進(jìn)研究[12-13]，關(guān)注布管質(zhì)量提升。相關(guān)研究從解決小規(guī)模簡(jiǎn)單問題逐漸發(fā)展到解決大規(guī)模實(shí)際問題，但大多停留在實(shí)驗(yàn)室研究階段。此外，以SolidWorks、Catia、UG等為代表的商業(yè)建模軟件目前也提供了自動(dòng)步路模塊，但只能按有限連接模式生成兩點(diǎn)間的簡(jiǎn)單路徑，同時(shí)缺少避障功能，仍然依賴設(shè)計(jì)師手工調(diào)整。出現(xiàn)以上現(xiàn)象的主要原因是船舶管路路徑設(shè)計(jì)是在復(fù)雜約束條件下的多目標(biāo)優(yōu)化問題，而傳統(tǒng)算法將多目標(biāo)優(yōu)化通過線性加權(quán)方式轉(zhuǎn)換為單目標(biāo)優(yōu)化，僅輸出唯一優(yōu)解或類似優(yōu)解(具有相同評(píng)價(jià)值的多個(gè)優(yōu)解)[5,7-9,11-14]。這類算法獲得的優(yōu)解不一定是最優(yōu)解，優(yōu)解集也不是Pareto優(yōu)解集，計(jì)算結(jié)果依賴各目標(biāo)權(quán)重設(shè)置，限制了算法推廣。近年來，多目標(biāo)優(yōu)化問題的研究熱度很高，其中使用多目標(biāo)進(jìn)化算法(Multi-Objective Evolutionary Algorithms, MOEAs)求解的研究最為豐富[15]。KONAK等[16]綜述了基于遺傳算法的多目標(biāo)優(yōu)化算法發(fā)展歷程和設(shè)計(jì)要素，其中最具代表性的研究為NSGA(non-dominated sorting genetic algorithm)[17]及NSGA-Ⅱ[18]。NSGA提出較早，但存在非支配排序計(jì)算復(fù)雜度高，缺少精英解保護(hù)機(jī)制，需要指定共享參數(shù)等不足；NSGA-Ⅱ基于快速非支配排序策略對(duì)NSGA進(jìn)行改進(jìn)，在保證求解質(zhì)量的前提下降低時(shí)間復(fù)雜度并且不需要指定共享參數(shù)，是目前多目標(biāo)優(yōu)化研究的主流算法。在此基礎(chǔ)上，參考Pareto設(shè)計(jì)思路，一些學(xué)者還設(shè)計(jì)出了多目標(biāo)蟻群優(yōu)化(Multi-Objective Ant Colony Optimization, MOACO)[19-20]和多目標(biāo)粒子群優(yōu)化(Multi-Objective Particle Swarm Optimization, MOPSO)[21-22]，但不如NSGA-Ⅱ算法成熟和應(yīng)用廣泛。管路路徑設(shè)計(jì)屬于多目標(biāo)優(yōu)化問題，更適合采用多目標(biāo)優(yōu)化算法求解。AHMED等[23]嘗試使用NSGA-Ⅱ在二維空間求解多目標(biāo)路徑設(shè)計(jì)問題；郭秀[24]以管路長度、彎頭數(shù)、安裝性為優(yōu)化目標(biāo)，探索了應(yīng)用NSGA算法求解直角管路的布局優(yōu)化問題；柳強(qiáng)等[25-26]采用NSGA-Ⅱ求解發(fā)航空發(fā)動(dòng)機(jī)的布管問題；文獻(xiàn)[27-28]初次嘗試應(yīng)用NSGA-Ⅱ布置三維船舶管路。以上研究已證明多目標(biāo)優(yōu)化算法在求解各類管路路徑設(shè)計(jì)問題中前景很好，但由于問題復(fù)雜性和領(lǐng)域局限性，目前相關(guān)研究仍然較少，同時(shí)多目標(biāo)優(yōu)化算法在實(shí)際應(yīng)用中容易出現(xiàn)早熟收斂、尋優(yōu)性能差、解集分布不均等問題。為此，本文針對(duì)船舶管路路徑設(shè)計(jì)提出一種基于NSGA-Ⅱ的改進(jìn)算法，主要研究?jī)?nèi)容包括：

(1)算法優(yōu)化目標(biāo)設(shè)計(jì)。根據(jù)實(shí)際管路布局需求，擴(kuò)展算法所能處理的優(yōu)化目標(biāo)和約束條件，使布局結(jié)果更符合需要。

(2)算法流程改進(jìn)。在NSGA-Ⅱ框架基礎(chǔ)上引入改進(jìn)策略，提升算法尋優(yōu)能力、穩(wěn)定性和收斂性。

(3)算法應(yīng)用擴(kuò)展。為應(yīng)對(duì)工程中的大量復(fù)雜管路，基于改進(jìn)多目標(biāo)算法和人工決策給出布局成束管路和分支管路的流程。

1 問題建模

1.1 布局空間和路徑

布局空間內(nèi)安裝著各類設(shè)備，可用包絡(luò)矩形法近似替代原始設(shè)備外形，既滿足布管精度又便于算法設(shè)計(jì)[2,5,7]。網(wǎng)格分解法是管路設(shè)計(jì)問題中最流行的預(yù)處理方法，將空間網(wǎng)格分解后便可借助網(wǎng)格屬性描述管路路徑、障礙區(qū)域和布局約束等[2,5,7-14,25-28]。網(wǎng)格劃分過程如下：根據(jù)最小管徑尺寸(網(wǎng)格邊長L)將三維布局空間劃分成網(wǎng)格集合，將障礙空間覆蓋的網(wǎng)格標(biāo)記為“禁用”狀態(tài)，將允許管路經(jīng)過的空間網(wǎng)格標(biāo)記為“自由”狀態(tài)，對(duì)于“自由”狀態(tài)網(wǎng)格，通過網(wǎng)格能量值區(qū)分網(wǎng)格所在區(qū)域?qū)苈返慕邮艹潭龋瑢⑵谕苈吠ㄟ^空間網(wǎng)格設(shè)置為低能量，不期望管路通過空間網(wǎng)格設(shè)置為極高能量，其余自由空間網(wǎng)格設(shè)置為常規(guī)能量。

在網(wǎng)格空間中布置管路p時(shí)，若其管徑(Dp)大于網(wǎng)格邊長L，為保證p不與障礙物和已布置管路發(fā)生干涉，可采用膨脹法處理，通過式(1)[12,28]計(jì)算障礙物向外膨脹距離，在布置管路p前先對(duì)障礙物做膨脹處理(膨脹空間網(wǎng)格標(biāo)記為“臨時(shí)禁用”狀態(tài))，然后運(yùn)行尋路算法可保證管路p的中心線路徑擴(kuò)展回原始尺寸后不與障礙物干涉，最后將膨脹空間恢復(fù)成初始狀態(tài)(“臨時(shí)禁用”被重置為“自由”狀態(tài))。采用障礙膨脹法，可以在同一網(wǎng)格空間完成不同管徑管路的布局。

(1)

式中：Np表示障礙物向外膨脹的網(wǎng)格數(shù);Dp表示管路p的最大管徑;L表示網(wǎng)格邊長。

將布局空間劃分網(wǎng)格后，各網(wǎng)格位置可用行、列、層構(gòu)成的網(wǎng)格坐標(biāo)描述，設(shè)布局空間左、下、后頂點(diǎn)網(wǎng)格坐標(biāo)為(0,0,0)，序號(hào)為k的網(wǎng)格坐標(biāo)記為(Rk,Ck,Lk)。令管路起點(diǎn)所在網(wǎng)格序號(hào)為0，終點(diǎn)所在網(wǎng)格序號(hào)為N，則路徑總長度為N個(gè)網(wǎng)格邊長之和，路徑可用網(wǎng)格位置序列表示，如式(2)所示。

p(0→N):(R0,C0,L0)→…→(Rk,Ck,Lk)→

(Rk+1,Ck+1,Lk+1)→…→(RN,CN,LN)。

s.t.

|Rt+1-Rt|+|Ct+1-Ct|+|Lt+1-Lt|=1,

t=0,…,N-1。

(2)

文獻(xiàn)[8]的方法用起點(diǎn)、折彎點(diǎn)、終點(diǎn)位置坐標(biāo)表示管路，但在路徑評(píng)價(jià)中也需轉(zhuǎn)換成上述路徑表示，本質(zhì)上與此相同。

1.2 優(yōu)化目標(biāo)和約束

實(shí)際船舶布管中考慮的優(yōu)化目標(biāo)和約束較多[2]，本文算法處理如下主要優(yōu)化目標(biāo)和約束條件：

(1)優(yōu)化目標(biāo)

Obj.1連接管路接口的管路路徑長度盡可能短；

Obj.2管路路徑的折彎數(shù)目盡可能少；

Obj.3管路盡可能靠近支撐面(艙壁、地板、設(shè)備表面)敷設(shè)，方便安裝固定；

Obj.4管路路徑盡可能避免出現(xiàn)“凹兜”結(jié)構(gòu)(路徑在豎直方向形成的U型管段)，減少傳輸介質(zhì)在“凹兜”處發(fā)生阻滯；

Obj.5管路相鄰折彎間距離盡可能不小于限定長度(L)，減少管路折彎的加工成本；

Obj.6對(duì)管路接口靠近的多條同類管路盡可能成束敷設(shè)，以便共享支架，節(jié)省成本并提高美觀性。

(2)約束條件

Con.1管路路徑能連接管路接口點(diǎn)，而且不與障礙物(艙室結(jié)構(gòu)、設(shè)備、已布置管路、預(yù)留空間等)發(fā)生干涉，可通過路徑生成算法保證該約束；

Con.2管路路徑與船體結(jié)構(gòu)間保持正交布置，即管路布局走勢(shì)與地面或設(shè)備等剛性結(jié)構(gòu)垂直或平行，該約束可通過網(wǎng)格分解模型和布管算法保證，實(shí)際布局中允許某些管路傾斜放置，可由設(shè)計(jì)師手工調(diào)整。

設(shè)p是路徑空間R中長度為N的一條網(wǎng)格路徑，則船舶管路路徑設(shè)計(jì)問題的多目標(biāo)形式如式(3)所示：

minf(p)={Obj.1,Obj.2,Obj.3,Obj.4,

Obj.5,Obj.6}

={flength(p),fbends(p),fpower(p),fpocket_num(p),

fover_limit_num(p),fneighbor_cells_convert(p,q)}。

s.t.

h(p)=0,g(p)=0。

(3)

其中：Obj.1～Obj.6對(duì)應(yīng)優(yōu)化目標(biāo);h(p)、g(p)對(duì)應(yīng)約束條件Con.1和Con.2，h(p)為0表示路徑不與環(huán)境空間發(fā)生干涉，g(p)為0表示路徑與剛性結(jié)構(gòu)正交布置。

fneighbor_cells_convert(p,q)=1.0/(x-(y-z))，表示路徑p與路徑q(已布置管路)并行敷設(shè)程度的度量值。計(jì)算方法如下：先統(tǒng)計(jì)路徑p與路徑q間相鄰網(wǎng)格數(shù)目x、路徑p經(jīng)過的網(wǎng)格數(shù)目y、當(dāng)前最短路徑經(jīng)過的網(wǎng)格數(shù)目z。x-(y-z)表示有效并行網(wǎng)格數(shù)目的估算值，值越大并行效果越好，取其倒數(shù)形式轉(zhuǎn)化成最小值優(yōu)化問題，fneighbor_cells_convert(p,q)∈(0,1]。原理如圖2所示，p路徑中x取值較大，是因?yàn)閜在q附近有迂回路徑導(dǎo)致，迂回路徑的網(wǎng)格數(shù)目被記入到x中，需減掉(估算值為p路徑與當(dāng)前最短路徑網(wǎng)格數(shù)之差)。

2 基于改進(jìn)NSGA-Ⅱ的管路路徑設(shè)計(jì)

船舶管路路徑設(shè)計(jì)是典型的多目標(biāo)優(yōu)化問題。求解多目標(biāo)優(yōu)化問題，早期使用最多的是加權(quán)求和法，將多目標(biāo)優(yōu)化轉(zhuǎn)換為單目標(biāo)優(yōu)化，該方法實(shí)現(xiàn)簡(jiǎn)單，但需要主觀指定目標(biāo)權(quán)重。此外，單目標(biāo)優(yōu)化算法一次運(yùn)行僅能給出唯一優(yōu)解或評(píng)價(jià)值相同的類似優(yōu)解，而基于多目標(biāo)優(yōu)化的NSGA-Ⅱ算法，一次運(yùn)行可給出問題的Pareto優(yōu)解集(每個(gè)優(yōu)解適度滿足各目標(biāo)而又不被其他優(yōu)解支配[16])，為設(shè)計(jì)者提供更多參考方案。

2.1 求解管路布局的改進(jìn)NSGA-Ⅱ框架

根據(jù)NSGA-Ⅱ算法框架，提出改進(jìn)算法求解船舶管路布局設(shè)計(jì)，流程如下。

算法1Dong-MO算法。

步驟1算法預(yù)處理。包括：導(dǎo)入問題模型、網(wǎng)格劃分布局空間、設(shè)置網(wǎng)格狀態(tài)(能量值和障礙標(biāo)記)、選定待布局管路、對(duì)環(huán)境障礙物做膨脹處理等。

步驟2初始化算法參數(shù)。包括：種群規(guī)模pop_size、交叉概率cross_rate、變異概率mutate_rate、進(jìn)化代數(shù)max_num、爬山次數(shù)climb_num、路徑不同個(gè)體占比閾值differ_rate。

步驟3初始化最優(yōu)解集pareto，即pareto=?。

步驟4基于改進(jìn)A*和連接點(diǎn)策略生成初始種群parent[12]，計(jì)算parent中個(gè)體的各目標(biāo)值。

步驟5迭代變量置0，即iter=0。

步驟6復(fù)制種群parent到子代種群child。

步驟7在child種群上執(zhí)行交叉、變異、爬山算子。

步驟8計(jì)算child種群中個(gè)體各目標(biāo)值。

步驟9合并parent和child到新種群combo，即combo=parent∪child。

步驟10對(duì)combo種群個(gè)體進(jìn)行快速非支配排序(fast-non-dominated-sort)和擁擠度距離計(jì)算，將combo種群個(gè)體分類到不同的非支配前沿面集合F1,F2,…,Fk。

步驟11根據(jù)前沿面排序和擁擠度距離，從combo個(gè)體中選出新一代parent種群[18]。

步驟12將最優(yōu)前沿面F1中個(gè)體與pareto解集個(gè)體按2.2.4節(jié)算法(non_dominated_merge)進(jìn)行非支配合并，更新pareto。

步驟13去除pareto中存在的重復(fù)個(gè)體(布局路徑相同個(gè)體保留一個(gè))。

步驟14檢查parent中路徑不同個(gè)體占比是否超過閾值differ_rate，若超過，則去除parent中多余重復(fù)個(gè)體，并生成新個(gè)體補(bǔ)充到parent種群以維持種群規(guī)模不變。

步驟15判斷iter是否小于進(jìn)化代數(shù)max_num，若是，則iter=iter+1，轉(zhuǎn)步驟6，否則轉(zhuǎn)步驟16。

步驟16輸出pareto優(yōu)解集。

影響NSGA-Ⅱ性能的關(guān)鍵因素是快速非支配排序(fast non-dominated sorting)，其時(shí)間和存儲(chǔ)復(fù)雜度分別是O(MN2)和O(N2)，M是目標(biāo)個(gè)數(shù)，N是種群規(guī)模[18]。

相比經(jīng)典的NSGA-Ⅱ[16,18]，新算法改進(jìn)表現(xiàn)為：在步驟7中引入爬山算子；在步驟12中將當(dāng)前迭代優(yōu)解與全局優(yōu)解進(jìn)行非支配合并；為避免種群出現(xiàn)過多同質(zhì)個(gè)體，在步驟14加入種群多樣性保持操作。此外，針對(duì)船舶管路布局問題設(shè)計(jì)了遺傳編碼和進(jìn)化算子。

2.2 算法關(guān)鍵步驟設(shè)計(jì)

2.2.1 路徑編碼和種群生成

遺傳算法的編碼被稱為染色體，由基因片段組成。本文采用可變長編碼，即將連接起點(diǎn)S和終點(diǎn)T的管路路徑編碼成從起點(diǎn)到終點(diǎn)所經(jīng)過的網(wǎng)格序列，同時(shí)要求路徑編碼中的任何網(wǎng)格不經(jīng)過障礙空間。

進(jìn)化種群由一定數(shù)量的編碼個(gè)體組成，初始種群是遺傳進(jìn)化的起點(diǎn)狀態(tài)。由于初始種群質(zhì)量對(duì)算法性能影響較大，采用基于A*算法的隨機(jī)路徑生成算法構(gòu)建高質(zhì)量初始種群個(gè)體[12]。文獻(xiàn)[27-28]基于LEE算法構(gòu)建種群個(gè)體，算法性能和個(gè)體質(zhì)量方面與A*算法相比沒有優(yōu)勢(shì)[12]。A*算法可用于在三維網(wǎng)格空間快速生成兩點(diǎn)間距離短、折彎少、盡量貼壁敷設(shè)的連通路徑。為保證初始種群中的個(gè)體多樣性，引入連接點(diǎn)策略，即先在布局空間的非障礙網(wǎng)格中隨機(jī)選擇網(wǎng)格作為中間連接點(diǎn)，之后用A*算法分別構(gòu)建起點(diǎn)到連接點(diǎn)和連接點(diǎn)到終點(diǎn)的路徑段，再將二者連接形成完整路徑，重復(fù)以上過程，直到個(gè)體數(shù)量滿足種群規(guī)模。為了進(jìn)一步提高解質(zhì)量，可規(guī)定連接點(diǎn)僅從鄰接支撐表面的網(wǎng)格(S1)中選取。高質(zhì)量路徑都是低能量的，路徑勢(shì)必包含很多靠近支撐表面的網(wǎng)格(S2)。因?yàn)镾2?S1，所以從S1中選擇連接點(diǎn)范圍足夠，且能提高優(yōu)解生成概率。采用連接點(diǎn)策略構(gòu)建個(gè)體路徑可能會(huì)生成非法路徑，為方便觀察，以二維圖為例說明(如圖3和圖4)，圖3a兩段路徑在連接點(diǎn)附近發(fā)生重疊，圖4a兩段路徑連接后存在環(huán)路。因此，可采用去重疊和去環(huán)路算法對(duì)生成個(gè)體進(jìn)行后處理，保證個(gè)體路徑的有效性，去除重疊和環(huán)路后的路徑如圖3b和圖4b所示。

2.2.2 遺傳算子

2.2.3 局部爬山算子

在種群進(jìn)化中，交叉和變異操作之后得到的子代路徑可通過嘗試改變折彎模式提升質(zhì)量。本文基于兩種折彎模式修改策略，即rectangle-mode和cuboid-mode。

rectangle-mode中，在待優(yōu)化路徑中隨機(jī)找出相鄰的3個(gè)折彎點(diǎn)(B1-B2-B3)，3個(gè)折彎可處在不同平面，以B1和B3折彎為對(duì)角頂點(diǎn)位置構(gòu)建矩形，嘗試調(diào)整B2位置到對(duì)角位置，可將當(dāng)前連接模式更換成另一種連接模式(XY?YX、XZ?ZX、YZ?ZY)，“?”表示轉(zhuǎn)換，如XY模式表示從B1開始先沿X探索路徑網(wǎng)格，再沿Y探索路徑網(wǎng)格到達(dá)B3，其他情況與此類似，如圖7a所示。

cuboid-mode中，在待優(yōu)化路徑中隨機(jī)找出相鄰的4個(gè)折彎點(diǎn)(B1-B2-B3-B4)，以B1和B4折彎點(diǎn)為對(duì)角頂點(diǎn)構(gòu)建長方體，則兩頂點(diǎn)間的連接模式共有6種(XYZ?XZY?YXZ?YZX?ZXY?ZYX)，調(diào)整B2、B3位置，可將當(dāng)前連接模式變換成其他連接模式之一，如圖7b所示。

爬山操作將得到的新個(gè)體與原個(gè)體進(jìn)行比較，若新個(gè)體好于原個(gè)體，則替換原個(gè)體。本文多目標(biāo)優(yōu)化沒有單目標(biāo)優(yōu)化中的個(gè)體評(píng)價(jià)值，因此提出基于多目標(biāo)的比較算子，若原個(gè)體(pold)通過折彎模式變化得到的新個(gè)體(pnew)滿足讓折彎數(shù)和路徑能量?jī)蓚€(gè)目標(biāo)至少一個(gè)變好，而其他目標(biāo)不下降，則接受當(dāng)前折彎模式修改，條件表達(dá)如式(4)所示：

((fbends(pnew)

fpower(pold)) or (fbends(pnew)≤fbends(pold) and

fpower(pnew)

flength(pold) andfpocket_num(pnew)≤fpocket_num(pold)

andfover_limit_num(pnew)≤fover_limit_num(pold) and

fneighbor_cells_convert(pnew,q)≤fneighbor_cells_convert(pold,q)。

(4)

為了保證爬山效果，每代進(jìn)化建議對(duì)child種群內(nèi)的所有個(gè)體分別執(zhí)行climb_num次rectangle-mode和cuboid-mode爬山操作。

2.2.4 精英保留

每次迭代經(jīng)過快速非支配排序后，迭代最優(yōu)解會(huì)被保存在Pareto前沿面F1中，其中的優(yōu)解個(gè)體可能是進(jìn)化所能找到的最優(yōu)解，也可能是當(dāng)前搜索到的最優(yōu)解。為了不丟失迭代中能發(fā)現(xiàn)的全部精英個(gè)體，設(shè)置一個(gè)Pareto精英解集，用于保存進(jìn)化中發(fā)現(xiàn)的當(dāng)前最優(yōu)解，要求其中的個(gè)體間互不占優(yōu)。因此需要在每次迭代后將F1中個(gè)體與Pareto解集中個(gè)體進(jìn)行非支配合并，合并算法(non-dominated-merge)描述如下。

算法2non-dominated-merge算法。

輸入：F1為當(dāng)前迭代獲得的最優(yōu)前沿面?zhèn)€體集合，pareto為保存當(dāng)前精英個(gè)體的集合;

輸出：pareto，為將F1與原pareto合并更新后的新精英解集合。

for X in F1:

flag=True

for Y in pareto:

flag=False

break

if flag==True:

for Z in pareto:

pareto=pareto-{Z}

pareto=pareto∪{X}

2.2.5 種群更新和多樣性保持

文獻(xiàn)[27-28]的方法先采用模糊集理論對(duì)Pareto解集中個(gè)體的目標(biāo)值進(jìn)行規(guī)范化，使各目標(biāo)取值范圍在[0,1]之間，再基于個(gè)體目標(biāo)值之和與解集個(gè)體的目標(biāo)值之和計(jì)算個(gè)體適應(yīng)值，種群更新的選擇算子使用個(gè)體適應(yīng)值和二分錦標(biāo)賽策略實(shí)現(xiàn)。

本文沒有采用個(gè)體適應(yīng)值進(jìn)行非支配排序和選擇下一代種群，而是基于快速非支配排序得到的個(gè)體前沿面級(jí)別和擁擠度距離作為排序依據(jù)構(gòu)建下一代種群。主要原因是文獻(xiàn)[27-28]的方法中，基于適應(yīng)值進(jìn)行個(gè)體優(yōu)劣比較與單目標(biāo)優(yōu)化類似，雖然一些布局方案的路徑不同，但適應(yīng)值可能相同，而基于多目標(biāo)的非支配排序來比較個(gè)體優(yōu)劣，更符合NSGA-Ⅱ算法，得到的Pareto解種類更豐富，計(jì)算量相對(duì)更小。

由于每次迭代需將父代種群P先復(fù)制一份給子代種群Q，再在子代種群Q上進(jìn)行交叉、變異，該過程可能會(huì)在Q中產(chǎn)生父代種群P中原來就有的個(gè)體。隨著P與Q合并，以及對(duì)合并種群進(jìn)行快速非支配排序和擁擠度計(jì)算，選出新一代種群P，將導(dǎo)致P中出現(xiàn)管路布局相同的個(gè)體。由于重復(fù)的優(yōu)秀個(gè)體彼此不占優(yōu)，隨著進(jìn)化發(fā)展，P中的重復(fù)個(gè)體比例升高，導(dǎo)致早熟收斂。為此提出如下改進(jìn)：在每代種群P選出之后，計(jì)算路徑不同個(gè)體所占的比例(重復(fù)個(gè)體算一個(gè))，當(dāng)比例低于閾值時(shí)，將重復(fù)個(gè)體保留一個(gè)，刪除其他的，再用連接點(diǎn)策略和A*算法生成相同數(shù)目的新個(gè)體補(bǔ)充到P中。改進(jìn)策略使精英個(gè)體得以保留，又提高了種群多樣性。

2.3 成束管路布局設(shè)計(jì)

管路布局設(shè)計(jì)中對(duì)接口靠近、性質(zhì)相同的管路，希望成束布局以共用支架。為實(shí)現(xiàn)基于改進(jìn)NSGA-Ⅱ算法的多管路成束布局，提出以下算法流程。

算法3管路成束布局流程。

步驟1讀取預(yù)定義的布局配置文件，確定各管路敷設(shè)順序和相鄰關(guān)系，設(shè)管路布置順序?yàn)閧p1,p2,…,pN}，相鄰關(guān)系為后一條管路(pk+1)靠近前一條管路(pk)布置。

步驟2按提出算法(Dong-MO)布置管路p1，算法結(jié)束后從p1的Pareto解集中選擇一個(gè)優(yōu)解方案p1(l1)。

步驟3對(duì)p1(l1)路徑經(jīng)過的網(wǎng)格設(shè)置狀態(tài)(管路ID、障礙標(biāo)記)，并將p1(l1)路徑周圍網(wǎng)格能量值設(shè)為0。

步驟4按Dong-MO算法布置下一條管路p2，生成p2種群個(gè)體時(shí)要求連接點(diǎn)在p1(l1)路徑周圍網(wǎng)格中隨機(jī)選取，以提高個(gè)體靠近p1布置概率，中間連接點(diǎn)個(gè)數(shù)從步驟1配置文件讀取并對(duì)連接點(diǎn)做排序[12]。算法結(jié)束后，從p2的Pareto解集中選擇一個(gè)優(yōu)解方案p2(l2)，參照步驟3對(duì)p2(l2)進(jìn)行設(shè)置。

步驟5參照步驟2～步驟4，繼續(xù)完成后續(xù)管路p3,…,pN的布置。

步驟6輸出由{p1(l1),p1(l2),…,pN(lN)}構(gòu)成的多管路成束布局方案。

2.4 分支管路布局設(shè)計(jì)

船舶中存在大量分支管路，分支管路布局需要確定分支管路布置順序和分支點(diǎn)位置。該決策可由人或算法生成。文獻(xiàn)[5,11]先由算法隨機(jī)生成布管次序，再通過比較確定最終順序，分支點(diǎn)位置則按接口到已布完分支的最短路徑方式生成；文獻(xiàn)[28]則基于管路分級(jí)和通過比較接口間的歐氏距離之和來確定接口連接次序。多目標(biāo)優(yōu)化需要從Pareto解中選擇優(yōu)解，因此可由用戶制定分支策略，增加布局靈活性?；诟倪M(jìn)NSGA-Ⅱ算法的分支管路設(shè)計(jì)流程如下。

算法4分支管路布局流程。

步驟1讀取預(yù)定義的分支管路接口連接順序(按接口尺寸降序排列)，記為{b1,b2,b3,…,bN}。

步驟2先按Dong-MO算法布置b2到b1的分支路徑，再從Pareto解集中選擇一個(gè)優(yōu)解方案，記為b2(l1)。

步驟3觀察b2(l1)，若不滿意，則恢復(fù)布管環(huán)境，轉(zhuǎn)步驟2重新設(shè)計(jì)；若滿意，則標(biāo)記b2(l1)分支所經(jīng)過的網(wǎng)格狀態(tài)(管路ID)。

步驟4基于OpenGL拾取技術(shù)在b2(l1)路徑網(wǎng)格中為b3接口選取連接點(diǎn)P(也可按[11]中算法生成)，再用Dong-MO算法設(shè)計(jì)b3到P的分支路徑，從Pareto解集中選擇一個(gè)優(yōu)解方案，記為b3(l2)。

步驟5觀察b3(l2)，若不滿意，則重置布管環(huán)境，轉(zhuǎn)步驟4重選連接點(diǎn)P或保持不變，調(diào)用Dong-MO算法重新設(shè)計(jì)b3到P路徑；若滿意，則標(biāo)記b3(l2)分支所經(jīng)過的網(wǎng)格狀態(tài)。

步驟6參照步驟4～步驟5完成剩余接口{b4,…,bN}到已完成分支的路徑設(shè)計(jì)(P在已布分支網(wǎng)格中選取)。

步驟7輸出由{b2(l1),b3(l2),b4(l3),…,bN(lN-1)}構(gòu)成的分支管路設(shè)計(jì)方案。

3 實(shí)驗(yàn)及結(jié)果分析

為了分析算法表現(xiàn)，分別采用仿真算例和實(shí)際算例進(jìn)行驗(yàn)證。仿真算例考察算法尋優(yōu)能力、收斂性、穩(wěn)定性和時(shí)間代價(jià)；實(shí)際算例考察算法求解復(fù)雜問題時(shí)的表現(xiàn)。

開發(fā)環(huán)境：Microsoft Visual Studio 2019 VC++，編譯器優(yōu)化設(shè)置為最大優(yōu)化(優(yōu)選速度)/O2；OpenGL；SolidWorks；Python。運(yùn)行環(huán)境：Intel(R)Core(TM)i5-8265U CPU，RAM 24.0 GB，Windows 10 x64。

3.1 仿真模型管路設(shè)計(jì)算例

3.1.1 布局空間描述

設(shè)管路布局空間為100×100×100的立方體空間，坐標(biāo)原點(diǎn)位于中心?？紤]機(jī)艙障礙較多，布管空間有限，在空間內(nèi)設(shè)置了13個(gè)長方體障礙物，各障礙物對(duì)角頂點(diǎn)坐標(biāo)如下：{(-45,-50,20)～(-30,20,0);(0,-50,30)～(50,10,10);(0,-50,-10)～(50,50,-30);(-40,-50,50)～(-20,50,30);(-50,-50,-20)～(-20,50,-30);(-20,-10,-40)～(0,0,20);(-50,-50,-20)～(-30,-20,0);(-30,-50,-50)～(10,30,-40);(-20,-50,-40)～(0,-40,20);(-10,0,-10)～(0,50,10);(30,-50,50)～(20,-40,40);(-10,-50,50)～(-20,-10,20);(-14,-10,-16)～(-6,-16,8)}。

3.1.2算法參數(shù)設(shè)置

種群規(guī)模pop_size=40，交叉概率cross_rate=0.85，變異概率mutate_rate=0.05，進(jìn)化代數(shù)max_num=100，連接點(diǎn)個(gè)數(shù)mid_points_num=1(單管路、成束布局時(shí)首條管路)或3(成束布局時(shí)后敷設(shè)管路)，爬山次數(shù)climb_num=20，種群內(nèi)不同個(gè)體占比閾值differ_rate=40%；網(wǎng)格空間靠近內(nèi)側(cè)面和障礙物表面的網(wǎng)格能量值設(shè)為0，連接點(diǎn)從能量值為0的網(wǎng)格中選取，相鄰折彎間管段長度設(shè)為2倍網(wǎng)格邊長。

3.1.3 單管路布局算例

用50×50×50的粒度將布局空間網(wǎng)格化，算例中各管路起點(diǎn)和終點(diǎn)的網(wǎng)格坐標(biāo)為：P1(49,0,49)～(0,23,0)，P2(49,0,49)～(49,23,0)，P3(0,0,49)～(0,23,0)，P4(0,0,49)～(49,23,0)。

為了對(duì)比研究，分別用本文算法Dong-MO、根據(jù)文獻(xiàn)[27-28]算法思想實(shí)現(xiàn)的算法Sui-MO(以LEE算法構(gòu)建路徑，用模糊集理論計(jì)算個(gè)體評(píng)價(jià)值，算法步驟和參數(shù)與Dong-MO相同)和單目標(biāo)遺傳算法Dong-SO[13]對(duì)以上布局問題進(jìn)行求解。因?yàn)樗惴ň哂须S機(jī)性，每種算法均布置管路10次以上。

分析各算法一次運(yùn)行后所求得的最優(yōu)解信息(取Sui-MO算法獲得解個(gè)數(shù)最多的一次)，如表1所示，其中“包含優(yōu)解個(gè)體數(shù)目”表示在個(gè)體路徑的6個(gè)度量目標(biāo)相同時(shí)，路徑布局不同的個(gè)體數(shù)目。與表1對(duì)應(yīng)的Dong-MO和Sui-MO求得路徑布局如圖8、圖9所示(路徑間有重疊，需要時(shí)可逐一觀察單條路徑布局)。Dong-SO方法布局效果可參考文獻(xiàn)[13]，其布局結(jié)果只是Dong-MO和Sui-MO方法結(jié)果之一。

表1 管路布局結(jié)果信息

注：成束度量取值范圍為(0,1]，當(dāng)該值為1時(shí)，表示路徑與成束布置無關(guān);記為“-”時(shí)，表示不適用。

通過對(duì)比可知，各算法求得優(yōu)解均能滿足路徑的能量值最低、不違反折彎長度限制和不帶“凹兜”結(jié)構(gòu)，本算例為單管路布局，不涉及成束敷設(shè)，因此成束度量值列為1，算法差別主要體現(xiàn)在發(fā)現(xiàn)優(yōu)解數(shù)目和布局路徑種類方面。單目標(biāo)優(yōu)化算法Dong-SO每次運(yùn)行只能得到唯一優(yōu)解，Sui-MO每次運(yùn)行能獲得評(píng)價(jià)值相同的部分Pareto優(yōu)解，不能發(fā)現(xiàn)子目標(biāo)不全相同且互不支配的優(yōu)解，Dong-MO算法獲得優(yōu)解數(shù)目最多，可完全包含其他兩種方法的優(yōu)解，布局樣式更豐富。

統(tǒng)計(jì)Dong-MO算法在P1～P4管路上10次運(yùn)行獲得Pareto優(yōu)解個(gè)數(shù)，如表2所示。不同管路間獲得解的個(gè)數(shù)差別較大主要與布局空間形狀有關(guān)，布局空間頂部位置可供P1、P2形成優(yōu)解通路較少，而可供P3、P4形成優(yōu)解通路較多；改進(jìn)算法每次運(yùn)行能找到P1、P2的幾乎全部Pareto優(yōu)解，也能找到P3、P4的絕大部分Pareto優(yōu)解；P1、P2管路解個(gè)數(shù)接近均值，P3、P4管路解個(gè)數(shù)在均值附近波動(dòng)，說明算法尋優(yōu)性能穩(wěn)定。

表2 Dong-MO算法10次運(yùn)行獲得優(yōu)解個(gè)數(shù)

觀察Dong-MO算法在P1～P4管路布局上的一次運(yùn)算，路徑不同個(gè)體隨迭代過程在種群中的比例不斷變化，如圖10所示，可見種群會(huì)隨著進(jìn)化過程出現(xiàn)同質(zhì)化(相同個(gè)體增多)，多樣性保持策略能夠及時(shí)剔除重復(fù)個(gè)體并補(bǔ)充新個(gè)體，使種群多樣性維持在合理水平，促進(jìn)算法發(fā)現(xiàn)更多優(yōu)解。

3.1.4 多管路成束布局算例

對(duì)于多管路成束布局，布管順序不同或?qū)ο炔季止苈返姆桨高x擇不同都會(huì)影響最終布局效果。例如，Case 1按P5、P6、P7順序依次布置，先布置P5，得到的Pareto優(yōu)解集如圖11a所示，從布局結(jié)果中選擇下方一個(gè)長度短的布局結(jié)果，在此基礎(chǔ)上布置后續(xù)管路，得到的一個(gè)布局效果如圖11b，若為P5選擇上方一個(gè)折彎少的布置方案，得到的一個(gè)并行布局效果如圖11c；若按P7、P6、P5順序布置，先布置P7，得到的優(yōu)解集如圖12a，分別以P7下方兩個(gè)不同方案為基礎(chǔ)成束布局，得到的效果如圖12b和12c?？梢?，用多目標(biāo)優(yōu)化算法結(jié)合順序和優(yōu)解選擇可以構(gòu)建多種布局方案，相比單目標(biāo)方法只給出唯一方案，改進(jìn)方法能更好地滿足用戶需求。

本文方法基于多目標(biāo)比較確定個(gè)體間支配關(guān)系，但優(yōu)化目標(biāo)不是硬性約束，選出的優(yōu)解不能保證滿足每個(gè)目標(biāo)的最優(yōu)狀態(tài)。例如，算法獲得的一個(gè)優(yōu)解在P6和P7中存在違反折彎間距離限制的情況(如圖15)，這會(huì)導(dǎo)致折彎加工成本增大。因此，工程師在選擇結(jié)果時(shí)需做核查或借助算法濾掉非法解。

對(duì)比Case 1和Case 2獲得布局效果1時(shí)的一次運(yùn)算中，100次迭代的耗時(shí)統(tǒng)計(jì)如表3所示。由網(wǎng)格劃分粒度可知，Case 2網(wǎng)格數(shù)是Case 1的8倍，去除障礙網(wǎng)格后有效網(wǎng)格數(shù)小于8倍，算法計(jì)算時(shí)間上Case 2接近Case 1的7倍，說明算法耗時(shí)與網(wǎng)格數(shù)目線性相關(guān)，算法計(jì)算性能良好。

表3 不同網(wǎng)格劃分下算法耗時(shí)對(duì)比

3.2實(shí)船機(jī)艙燃油管路設(shè)計(jì)算例

3.2.1 布局問題描述

該實(shí)際算例取自文獻(xiàn)[28]，為某溢油應(yīng)急處置船中機(jī)艙管系的燃油管路，布局空間涉及的主要設(shè)備包括：燃油日用柜2個(gè)、蒸汽鍋爐1個(gè)、熱水鍋爐1個(gè)、柴油發(fā)電機(jī)2臺(tái)、主機(jī)2臺(tái)、燃油輸送泵2臺(tái)。上述設(shè)備簡(jiǎn)化模型主要部件對(duì)角頂點(diǎn)網(wǎng)格位置參見文獻(xiàn)[28]中的表4。布局空間尺寸為5 700 mm×3 360 mm×9 600 mm。鑒于管路最小管徑為22 mm，網(wǎng)格精度取30 mm，布局空間劃分為190×112×320個(gè)立方體網(wǎng)格單元。

管路布局需求為在上述空間中設(shè)計(jì)6條連接相應(yīng)設(shè)備的燃油管路P1～P6。該管路系統(tǒng)原理參見文獻(xiàn)[28]中圖21，各條管路所連接的設(shè)備、接口點(diǎn)網(wǎng)格位置、管徑尺寸等參見文獻(xiàn)[28]中表5，其中管路P1、P2、P6為等管徑分支管路，管路P3、P4、P5為非等管徑分支管路。

3.2.2 算法參數(shù)設(shè)置

由于該算例網(wǎng)格數(shù)目遠(yuǎn)多于上節(jié)算例，約是50×50×50劃分網(wǎng)格數(shù)的54倍，100×100×100劃分網(wǎng)格數(shù)的7倍，為了提升計(jì)算速度，將種群規(guī)模(pop_size)減小為20，其他參數(shù)設(shè)置與前節(jié)算例相同。

實(shí)際管路布局通常對(duì)接口方向有要求，因此計(jì)算前可將接口網(wǎng)格位置向外延伸一段距離，本實(shí)驗(yàn)中默認(rèn)接口延伸距離為4個(gè)網(wǎng)格尺寸?？紤]管路P3、P4、P5在燃油日用柜下方的主分支管路接口位置靠近，且需跨越燃油泵連接兩側(cè)燃油柜，因此采用與文獻(xiàn)[28]類似策略，加大此處接口延伸距離，分別設(shè)置為28、30、32網(wǎng)格距離。文獻(xiàn)[28]中提到將接口位置向外延伸可使布局更加靈活，但沒有給出具體延伸數(shù)值。

按管路P1～P6主分支管徑尺寸由大到小確定布置順序?yàn)椋篜1或P2→P4或P5→P3→P6，實(shí)驗(yàn)中取P1→P2→P4→P5→P3→P6；分支點(diǎn)位置按選定接口點(diǎn)到已布完分支間的最短路徑方式生成，對(duì)于非等徑分支管路，按各接口尺寸降序排列，管路P1～P6接口連接順序分別為：{1,2,3,4}，{1,2,3,4}，{1,2,3,4,5,6}，{1,2,3,4,5,6}，{1,2,3,4}，{1,3,4,2}。

3.2.3 布局結(jié)果及分析

本文算法(Dong-MO)完成布局后可在軟件環(huán)境中實(shí)時(shí)觀察設(shè)計(jì)效果，為方便工程師結(jié)合經(jīng)驗(yàn)交互式修改結(jié)果，軟件實(shí)現(xiàn)了到CAD建模系統(tǒng)的導(dǎo)出接口，在SolidWorks中顯示的機(jī)艙燃油管路布局效果如圖16所示。

用Dong-MO算法獲得的兩個(gè)優(yōu)化布局如圖17所示，與文獻(xiàn)[28]算法(記為Sui-MO*)結(jié)果進(jìn)行對(duì)比分析(如表4)，可得如下結(jié)論：

(1)由于多目標(biāo)優(yōu)化結(jié)果與Pareto解的選取策略有關(guān)，因此Dong-MO在該算例上可產(chǎn)生多種布局方案，表4中列出Dong-MO的兩個(gè)結(jié)果，左側(cè)對(duì)應(yīng)圖17a，右側(cè)對(duì)應(yīng)圖17b，它們?cè)赑3之外的管路上獲得了不同路徑，方案1、2的路徑總長度和總折彎數(shù)分別為(2 773,44)，(2 828,43)，兩者整體優(yōu)化目標(biāo)相差不大，長度上的差別主要由P6路徑不同引起；雖然方案2的路徑長度大于方案1，但其靠近鍋爐設(shè)備的管路更短，減少了為管路做隔熱處理的代價(jià)。

(2)Dong-MO與Sui-MO*在P1、P2、P3布局效果上接近，但在P4、P5、P6布局效果上有差異，Sui-MO*的路徑總長度和總折彎數(shù)為(3 224,42)。對(duì)比發(fā)現(xiàn)Dong-MO和Sui-MO*總折彎數(shù)相近，但Dong-MO的總路徑長度小于Sui-MO*，主要是因?yàn)镈ong-MO可在P5、P6上找到更短路徑。此處長度對(duì)比不是精確比較，原因如下：文獻(xiàn)[28]沒有給出接口延伸距離，且設(shè)備模型僅包含主要部件，數(shù)據(jù)不完整會(huì)影響結(jié)果準(zhǔn)確復(fù)現(xiàn)；路徑長度統(tǒng)計(jì)時(shí)對(duì)分支點(diǎn)網(wǎng)格計(jì)數(shù)規(guī)則可能不同，Dong-MO路徑總長度為各分支長度累加，在分支點(diǎn)處有少量重復(fù)計(jì)數(shù)，文獻(xiàn)[28]對(duì)此未說明；文獻(xiàn)[28]中表5的管路P4、P5接口數(shù)據(jù)與該文獻(xiàn)圖22中P4、P5的接口位置無法對(duì)應(yīng)(在燃油日用柜下方接口交換了位置)，Dong-MO算法以表5數(shù)據(jù)為準(zhǔn)計(jì)算，由此可能導(dǎo)致長度統(tǒng)計(jì)上的差別。此外，文獻(xiàn)[28]中表4發(fā)電機(jī)1的第6個(gè)坐標(biāo)應(yīng)為(146,33,118)，而非(46,33,118)，否則與設(shè)備模型相差較大。

(3)Sui-MO*對(duì)管路P5的布局不如Dong-MO布局合理。因?yàn)镻5在燃油柜下方接口是管徑為42 mm的一級(jí)接口，在蒸汽鍋爐和熱水鍋爐上接口是管徑為34 mm的二級(jí)接口，為提高燃油供應(yīng)效率，應(yīng)讓二級(jí)接口與一級(jí)接口間的主分支管連接。Sui-MO*布局中存在二級(jí)接口間共享部分路徑與主管相連的情況。這與Sui-MO*算法將分支管路間的重疊長度作為子優(yōu)化目標(biāo)有關(guān)。

文獻(xiàn)[28]提到對(duì)Sui-MO*結(jié)果僅作少量修改即可滿足實(shí)際布管需求，實(shí)驗(yàn)表明Dong-MO算法同樣適于該案例設(shè)計(jì)，甚至在路徑長度、布局合理性等方面表現(xiàn)更好，說明了本文算法的有效性和先進(jìn)性。

表4 機(jī)艙燃油管路路徑對(duì)比

續(xù)表4

4 結(jié)束語

本文提出一種基于NGSA-Ⅱ的船舶管路路徑設(shè)計(jì)方法。使用A*算法和連接點(diǎn)策略構(gòu)建種群個(gè)體和遺傳算子；基于個(gè)體多目標(biāo)間的比較關(guān)系定義支配算子，同時(shí)考慮多個(gè)布局優(yōu)化目標(biāo)，增加了Pareto解集的多樣性；通過引入爬山操作、精英保留和種群多樣性保持來改進(jìn)算法框架以提高算法尋優(yōu)能力；在多目標(biāo)單管路算法的基礎(chǔ)上給出了多管路成束布局和帶分支管路布局的求解過程。相比將多目標(biāo)優(yōu)化轉(zhuǎn)化為單目標(biāo)優(yōu)化后再求解的傳統(tǒng)算法，本文所提算法能在一次運(yùn)算中求得高質(zhì)量的Pareto優(yōu)解集，為工程師提供更多參考；與基于文獻(xiàn)[27-28]方法的多目標(biāo)船舶布管算法相比，本文算法求得的Pareto優(yōu)解數(shù)量更多、布局類型更豐富。

未來將基于OpenMP或CUDA技術(shù)對(duì)算法作并行化改進(jìn)，提升算法效率；探索基于機(jī)器學(xué)習(xí)技術(shù)的船舶管路設(shè)計(jì)方法。