基于協(xié)同進(jìn)化和并行計(jì)算的船舶管路布置方法

董 宗 然，　林 　 焰

( 1.大連理工大學(xué) 電子信息與電氣工程學(xué)部, 遼寧 大連　116024；2.大連理工大學(xué) 運(yùn)載工程與力學(xué)學(xué)部, 遼寧 大連　116024 )

?

基于協(xié)同進(jìn)化和并行計(jì)算的船舶管路布置方法

董 宗 然1，林 焰*2

( 1.大連理工大學(xué) 電子信息與電氣工程學(xué)部, 遼寧 大連116024；2.大連理工大學(xué) 運(yùn)載工程與力學(xué)學(xué)部, 遼寧 大連116024 )

摘要：為解決船舶管路協(xié)同布置問(wèn)題，提出一種適合求解多管路或分支管路協(xié)同布置的算法框架．通過(guò)為每條管路或分支生成對(duì)應(yīng)的進(jìn)化種群，將管路間的協(xié)同布置轉(zhuǎn)換為種群間的協(xié)同進(jìn)化．基于提出的路徑連接點(diǎn)概念，生成管路接口間的候選路徑種群，并對(duì)種群進(jìn)行交叉、變異操作．使用A*算法作為尋路算子，提高了生成路徑的質(zhì)量，同時(shí)保證了路徑的有效性．為了提高運(yùn)算效率，引入并行計(jì)算策略對(duì)算法框架和A*算法進(jìn)行改進(jìn)．最后，兩個(gè)仿真實(shí)例驗(yàn)證了所提出方法的可行性和有效性．

關(guān)鍵詞：船舶管路；A*算法；協(xié)同進(jìn)化；并行計(jì)算

0引言

船舶管路設(shè)計(jì)是船舶詳細(xì)設(shè)計(jì)階段中最繁雜的工作之一．現(xiàn)代船舶需要大量的管路以完成油、氣、水、電等的輸送．管路需要連接指定的設(shè)備接口，同時(shí)需要滿足諸多約束條件，包括管路長(zhǎng)度、彎頭數(shù)目等經(jīng)濟(jì)性約束，還包括易安裝性、易維護(hù)性、美觀性、安全性等高級(jí)需求．船舶設(shè)計(jì)具有非批量的特點(diǎn)，除了少量姐妹船以外，每條船都有各自的設(shè)計(jì)需求．因此，船舶管路設(shè)計(jì)的工作量巨大，難度較高．當(dāng)前船舶管路設(shè)計(jì)主要由管路設(shè)計(jì)師完成，除了要考慮管路的連接性和相關(guān)約束外，當(dāng)布置多條管路和帶分支管路時(shí)，還要考慮管路間的協(xié)同，以使管路整體布置最優(yōu)．研究船舶管路自動(dòng)布置方法，可以減輕管路設(shè)計(jì)人員的工作量，實(shí)現(xiàn)管路設(shè)計(jì)方案的標(biāo)準(zhǔn)化，縮短船舶生產(chǎn)的交付周期．

近年來(lái)管路布置問(wèn)題逐漸得到研究者的關(guān)注，出現(xiàn)在工業(yè)設(shè)計(jì)的不同領(lǐng)域，包括船舶管路設(shè)計(jì)、機(jī)械管路設(shè)計(jì)、航天器管路設(shè)計(jì)等．在使用的優(yōu)化技術(shù)方面，可以分為確定性算法和非確定性算法．確定性算法在初始狀態(tài)相同的情況下具有結(jié)果的可重復(fù)性和運(yùn)算時(shí)間的確定性．基于Dijkstra[1]、最短路徑快速算法[2]、A*算法[3]、直線探索法[4]的管路布置研究均歸屬于確定性算法．非確定性算法依賴控制參數(shù)設(shè)置，尋優(yōu)過(guò)程依賴隨機(jī)策略，結(jié)果不具有可重復(fù)性，而且算法收斂時(shí)間也不確定．采用群進(jìn)化技術(shù)的管路布置方法可歸屬于非確定性算法[5-12]．其中，Jiang等[9]將遺傳算法的交叉和變異操作嵌入蟻群算法的運(yùn)算流程以提高布管算法性能；在文獻(xiàn)[10]中又提出將機(jī)艙設(shè)備布置與船舶管路布置相結(jié)合的優(yōu)化思路，并使用粒子群算法和蟻群算法分別求解設(shè)備布置和管路布置．王運(yùn)龍等[11-12]將爬山算法引入遺傳算法的迭代過(guò)程，用以改進(jìn)算法的收斂性，并基于人機(jī)結(jié)合思想設(shè)計(jì)布管算法，通過(guò)在算法不同階段加入人工個(gè)體提高布置效果．以上方法都使用了不止一種優(yōu)化策略，但仍然屬于非確定性方法．確定性算法和非確定性算法各具優(yōu)勢(shì)，將兩者有機(jī)結(jié)合可以發(fā)揮確定性算法的高效率和非確定性算法的全局尋優(yōu)能力，Asmara等在文獻(xiàn)[13]中提出利用確定性的Dijkstra算法完成管路生成，利用非確定性的粒子群算法優(yōu)化布管序列，該方法從整體上考慮管路布置順序?qū)Y(jié)果的影響，但其順序優(yōu)化和管路布置分別由不同模塊實(shí)現(xiàn)，不滿足管路間的協(xié)同設(shè)計(jì)要求．范小寧等在先期工作中將每條管路的布置對(duì)應(yīng)一個(gè)螞蟻種群的路徑尋優(yōu)，利用多蟻群間的協(xié)作來(lái)實(shí)現(xiàn)管路間的協(xié)同敷設(shè)，該方法的主要不足是蟻群算法存在局部搜索能力較弱和收斂速度較慢等問(wèn)題，且求得的路徑存在較多折彎[5-6]．本文對(duì)范小寧工作做出幾點(diǎn)重要改進(jìn)，包括提出路徑中間連接點(diǎn)概念，并基于確定性A*算法生成候選路徑，設(shè)計(jì)協(xié)同布置算法框架統(tǒng)一處理多管路和帶分支管路的布置，以及對(duì)算法和框架做并行化改進(jìn)以提升布管效率等．

1空間模型及布管約束

布管問(wèn)題本質(zhì)上類似于靜態(tài)環(huán)境中的路徑尋優(yōu)，首先要對(duì)布置空間做預(yù)處理，采用的經(jīng)典方法是網(wǎng)格分解法[1-3,5-8,11-13]．網(wǎng)格分解法先將布置空間分解成網(wǎng)格集合，將設(shè)備、過(guò)道、維修空間等占據(jù)的網(wǎng)格標(biāo)記為障礙網(wǎng)格，障礙網(wǎng)格禁止管路通過(guò)；將布管需要滿足的幾何約束轉(zhuǎn)化為網(wǎng)格能量值，即將期望管路經(jīng)過(guò)區(qū)域(艙壁附近、可依附設(shè)備周圍、希望成束敷設(shè)的管路周圍)的網(wǎng)格設(shè)置為低能量值，將希望管路遠(yuǎn)離布置區(qū)域(如鍋爐周圍、配電設(shè)備上方)的網(wǎng)格設(shè)置為高能量值，進(jìn)而管路對(duì)應(yīng)的能量值可描述其對(duì)布置空間幾何約束的適應(yīng)情況．網(wǎng)格分解法的優(yōu)勢(shì)在于方便尋路算法的實(shí)現(xiàn)和布置約束的表達(dá)；劣勢(shì)在于網(wǎng)格數(shù)目隨著布置空間增大而增多，需占用大量?jī)?nèi)存，同時(shí)因?yàn)樗阉骺臻g變大，導(dǎo)致尋路算法性能下降．船舶管路的布置空間往往很大，如果不對(duì)空間做預(yù)處理和選擇高效算法，網(wǎng)格分解法難以應(yīng)用于實(shí)船管路布置．空間預(yù)處理先根據(jù)船舶結(jié)構(gòu)將艙內(nèi)空間分成不同工作區(qū)(各工作區(qū)內(nèi)的布管任務(wù)相對(duì)獨(dú)立)，再對(duì)獨(dú)立工作區(qū)空間進(jìn)行網(wǎng)格分解完成自動(dòng)布管，為了提高布管效率，還需要設(shè)計(jì)高效的網(wǎng)格尋路算法．

實(shí)船設(shè)計(jì)中不同管路系統(tǒng)的布置要求往往不同，本文主要討論船舶管路布置的共性需求，包括：①管路與管路之間或是管路與設(shè)備之間不發(fā)生干涉；②管路能夠連接到指定的設(shè)備接口點(diǎn)；③管路走勢(shì)盡量與鋼結(jié)構(gòu)件平行；④管路長(zhǎng)度盡可能短；⑤管路彎頭數(shù)目盡可能少；⑥最小管段長(zhǎng)度盡量滿足加工限制以降低生產(chǎn)成本；⑦管路滿足便于安裝和維護(hù)的幾何約束．其中①～③作為必須滿足的需求可以由布管算法和網(wǎng)格分解模型保證，④～⑦作為期望滿足的目標(biāo)可以通過(guò)評(píng)價(jià)機(jī)制從眾多可行解中選擇優(yōu)解滿足．

本文采用尋路算法中最為高效的A*算法進(jìn)行布管，所得路徑可避開設(shè)備和已敷設(shè)管路，因此評(píng)價(jià)管路時(shí)不必再考慮管路穿過(guò)障礙物的懲罰值．基于以上模型和布管約束，管路敷設(shè)質(zhì)量的評(píng)價(jià)函數(shù)(F)需包括管路長(zhǎng)度(Pl)，它是在管徑確定時(shí)，影響管路用料成本的主要因素；管路折彎數(shù)目(Pb)，它表示布管過(guò)程中使用的彎頭個(gè)數(shù)和對(duì)管路進(jìn)行彎曲加工的次數(shù)；管路對(duì)應(yīng)的能量值(Ppo)，它量化了對(duì)管路安裝位置優(yōu)劣的評(píng)價(jià)；管路不滿足最小管段長(zhǎng)度約束的懲罰值(Ppu)，它代表管路布置中違反管路加工工藝限制的程度．評(píng)價(jià)函數(shù)的形式化描述如下式：

minF(x)=a×Pl+b×Pb+c×Ppo+d×Ppu

(1)

式中：x代表一條管路，a、b、c、d為各代價(jià)的權(quán)重系數(shù)．以上目標(biāo)函數(shù)的設(shè)計(jì)源自實(shí)際工程需求，主要考慮布管的經(jīng)濟(jì)成本，屬于可量化、非硬性的優(yōu)化目標(biāo)．在無(wú)法滿足全部約束和目標(biāo)時(shí)，可適當(dāng)犧牲經(jīng)濟(jì)性目標(biāo)(例如增加管路長(zhǎng)度和彎頭數(shù)目或改進(jìn)加工工藝等)以求找到可行布管方案．

目標(biāo)函數(shù)權(quán)重系數(shù)選擇具有一定的隨機(jī)性和經(jīng)驗(yàn)性，不同的系數(shù)設(shè)置方案會(huì)產(chǎn)生不同的優(yōu)化結(jié)果．因此選擇權(quán)重系數(shù)時(shí)可遵循以下方法，包括：①結(jié)合船型特點(diǎn)分析管路布置需求，根據(jù)各目標(biāo)的重要程度設(shè)置初始權(quán)重系數(shù)；②估算各優(yōu)化目標(biāo)的數(shù)值范圍，進(jìn)一步調(diào)整權(quán)重系數(shù)，使經(jīng)過(guò)權(quán)重系數(shù)調(diào)整后的各目標(biāo)值處在可比較的數(shù)量級(jí)；③根據(jù)仿真結(jié)果的反饋，微調(diào)權(quán)重系數(shù)；④將有效的系數(shù)設(shè)置方案存入系統(tǒng)，積累經(jīng)驗(yàn)數(shù)據(jù)，為將來(lái)的權(quán)重系數(shù)選擇提供參考．

2船舶管路協(xié)同布置方法

協(xié)同進(jìn)化由Potter在1994年提出，它是自然界物種進(jìn)化的一種現(xiàn)象．生物進(jìn)化往往不是單一生物種群的進(jìn)化過(guò)程，而是要受到同一生態(tài)環(huán)境中其他種群的影響．根據(jù)其他種群對(duì)當(dāng)前進(jìn)化種群影響的不同，協(xié)同進(jìn)化可分為協(xié)作式協(xié)同進(jìn)化和競(jìng)爭(zhēng)式協(xié)同進(jìn)化兩種類型．協(xié)作式是指各種群會(huì)從其他種群的進(jìn)化中受益，種群的進(jìn)化促使與其他種群配合較好的個(gè)體有更大的生存機(jī)會(huì)；競(jìng)爭(zhēng)式是指其他種群的進(jìn)化會(huì)抑制當(dāng)前種群的進(jìn)化，當(dāng)前種群必須做出相應(yīng)的反應(yīng)以便獲得生存[14]．船舶管路設(shè)計(jì)規(guī)范要求按照管子尺寸，由粗到細(xì)依次布管，但仍然存在一些管徑相同或接近的管路，此時(shí)布管順序會(huì)影響布局結(jié)果，需要協(xié)同布置．管路設(shè)計(jì)的目標(biāo)是使整個(gè)管路系統(tǒng)布局最優(yōu)，各管路更多是一種合作關(guān)系，因此本文采用協(xié)作式進(jìn)化算法框架解決此類管路的協(xié)同布置問(wèn)題．

2.1管路協(xié)同布置算法框架

在布置實(shí)船管路時(shí)，對(duì)于接口點(diǎn)位置靠近、管路性質(zhì)相似的多條管路，往往期望能夠?qū)⑵涑墒笤O(shè)，以方便管路的支撐和維護(hù)，且符合布置的整齊性[5]；對(duì)于一類等徑帶分支管路，其布置要使各分支接口點(diǎn)連接到指定設(shè)備，同時(shí)各分支管路的總長(zhǎng)度最短，彎頭數(shù)目最少，可以將此類管路的布置看作同時(shí)布置幾條具有相同終止接口點(diǎn)的單管路，要求這些單管路間能夠有盡可能多的重疊部分[6]．文獻(xiàn)[5]和[6]使用多蟻群協(xié)同進(jìn)化算法求解多條管路和帶分支管路的布置，驗(yàn)證了協(xié)同布置的有效性，主要不足是蟻群算法作為布管算法收斂速度較慢，得到管路折彎較多，且算法效果依賴較多的控制參數(shù)．分析兩類問(wèn)題的區(qū)別和共性，提出一種求解兩類問(wèn)題的協(xié)作式進(jìn)化算法框架，并將管路布置封裝成可替換的模塊，使其不再局限于特定算法．同時(shí)，因?yàn)槎嗪诵奶幚砥饕呀?jīng)廣泛應(yīng)用，提出對(duì)算法做并行化改進(jìn)以提升求解效率．算法框架如圖1所示．

以上框架統(tǒng)一了多管路和分支管路的算法布置流程，主要區(qū)別在于設(shè)置協(xié)同布置環(huán)境Wi時(shí)，需要根據(jù)管路類型采取不同策略．對(duì)于多管路布置，為了引導(dǎo)管路并行成束敷設(shè)，需將其他種群的管路代表所在網(wǎng)格設(shè)置為障礙區(qū)，管路代表周圍的網(wǎng)格設(shè)為低能量區(qū)；對(duì)于分支管路布置，為了能讓管路分支間有更多的重合以使管路最短，需將其他種群的分支管路代表所在網(wǎng)格設(shè)置為低能區(qū)．此外，在計(jì)算迭代解Scurrent的評(píng)價(jià)值時(shí)，多管路的長(zhǎng)度計(jì)算包括各代表管路的長(zhǎng)度總和，而分支管路的長(zhǎng)度計(jì)算對(duì)分支間的重疊部分只統(tǒng)計(jì)一次．

2.2管路種群的生成及進(jìn)化

在兩個(gè)連接點(diǎn)之間生成多條候選路徑(即路徑種群)是管路協(xié)同布置框架對(duì)管路生成算法的功能需求．范小寧等[5]使用蟻群算法在構(gòu)建路徑時(shí)根據(jù)轉(zhuǎn)移規(guī)則隨機(jī)選擇周圍網(wǎng)格，因此每次找到的路徑都會(huì)不同．但A*算法屬于確定性算法，當(dāng)搜索方式確定之后，每次運(yùn)行找到的兩個(gè)連接點(diǎn)間的路徑都相同．因此提出路徑中間連接點(diǎn)概念，將路徑分成子段，把隨機(jī)性引入路徑生成過(guò)程，方法如下．

設(shè)S和G為某管路的兩端網(wǎng)格連接點(diǎn)，假設(shè)在S、G之間生成的管路需要經(jīng)過(guò)T個(gè)中間連接點(diǎn)，記為V1，V2，…，VT-1，VT．則S到G的路徑由S-V1，V1-V2，…，VT-1-VT，VT-G構(gòu)成的各子路徑段組成．如果中間連接點(diǎn)位置按啟發(fā)式規(guī)則隨機(jī)生成，連接點(diǎn)間的路徑用A*算法生成，則可按需要生成S和G之間的多條候選路徑．

圖1　協(xié)同布管算法框架

基于上述方法可生成各管路所對(duì)應(yīng)的初始進(jìn)化種群(步驟2)，并在后續(xù)迭代進(jìn)化過(guò)程中(步驟7c)對(duì)種群做進(jìn)化操作，包括交叉和變異．交叉操作從種群中隨機(jī)選擇兩條路徑作為父代個(gè)體，隨機(jī)產(chǎn)生一個(gè)1到T之間的序號(hào)，根據(jù)此序號(hào)交叉父代個(gè)體的中間連接點(diǎn)以形成兩個(gè)新的子代個(gè)體．變異操作從種群中隨機(jī)選擇一條路徑作為父代個(gè)體，隨機(jī)產(chǎn)生一個(gè)1到T之間的序號(hào)，重新生成此序號(hào)位置上的連接點(diǎn)以形成一個(gè)新的子代個(gè)體．進(jìn)行交叉和變異操作的個(gè)體是從父代中選出的，生成的子代個(gè)體將替換對(duì)應(yīng)父代個(gè)體進(jìn)入下一代進(jìn)化，以此保證進(jìn)化種群的穩(wěn)定性和多樣性．交叉和變異操作的示意如圖2．子代路徑中虛線表示的子段路徑要用A*算法重新生成．

圖2　交叉和變異

按啟發(fā)式規(guī)則生成路徑中間連接點(diǎn)可以提高初始路徑種群的質(zhì)量．提出如下啟發(fā)規(guī)則：①連接點(diǎn)不能位于障礙物之內(nèi)，以免產(chǎn)生非法路徑；②在期望空間(包含路徑兩端連接點(diǎn)的外包絡(luò)矩形空間)內(nèi)產(chǎn)生連接點(diǎn)，避免路徑向外過(guò)度延展；③協(xié)同布置多條管路時(shí)，按概率(Rcontrol)在已布置管路周圍生成連接點(diǎn)，以引導(dǎo)管路成束布置；④協(xié)同布置分支管路時(shí)，按概率(Rcontrol)在已布置分支管路上生成連接點(diǎn)，以引導(dǎo)各分支路徑更多重合．

2.3種群進(jìn)化的并行處理

從算法框架看出，步驟7c的任務(wù)是對(duì)種群做進(jìn)化操作，這是計(jì)算代價(jià)最高的子任務(wù)．該任務(wù)需要在每代進(jìn)化中為每一進(jìn)化種群生成連接點(diǎn)間的候選網(wǎng)格路徑，并按照評(píng)價(jià)函數(shù)計(jì)算每條路徑的適應(yīng)值．對(duì)該過(guò)程做并行化改進(jìn)，可以提高算法效率．該策略簡(jiǎn)述為將總?cè)蝿?wù)按CPU邏輯內(nèi)核數(shù)目分解，使每個(gè)CPU內(nèi)核都運(yùn)轉(zhuǎn)起來(lái)，完成部分計(jì)算任務(wù)，所有內(nèi)核的計(jì)算任務(wù)完成對(duì)應(yīng)總?cè)蝿?wù)的完成．使用該并行策略的前提是子任務(wù)間不存在依賴關(guān)系，步驟7c中生成的嘗試路徑雖然有多條，但生成每條路徑時(shí)基于的布置環(huán)境相同，生成各嘗試路徑的過(guò)程也不會(huì)改變布置環(huán)境，滿足任務(wù)分解的前提條件．

當(dāng)前主流CPU均為多核架構(gòu)，要使各個(gè)邏輯內(nèi)核并行工作，在實(shí)現(xiàn)上需借助多線程技術(shù)，例如，總的計(jì)算任務(wù)為生成兩個(gè)管路連接點(diǎn)之間的M條候選路徑，當(dāng)前CPU邏輯內(nèi)核數(shù)目為N，如果不使用多線程，那么所有計(jì)算將在1個(gè)內(nèi)核上完成，而其他N-1個(gè)內(nèi)核處在閑置狀態(tài)，若將總?cè)蝿?wù)分成N份，每份子任務(wù)為生成M/N條候選路徑，創(chuàng)建N個(gè)計(jì)算線程對(duì)應(yīng)N份任務(wù)，并分配到不同內(nèi)核執(zhí)行，則全部?jī)?nèi)核并行工作，完成總?cè)蝿?wù)的時(shí)間會(huì)大為減少．隨著多核并行編程技術(shù)的發(fā)展，可以借助OpenMp技術(shù)，它提供了對(duì)并行算法的高層抽象，通過(guò)在代碼中加入pragma指明并行意圖，編譯器可以自動(dòng)將程序并行化．借助OpenMp技術(shù)不需要人為創(chuàng)建線程、分配計(jì)算任務(wù)，優(yōu)化了程序結(jié)構(gòu)，基于OpenMp技術(shù)的候選路徑生成及評(píng)價(jià)方法如下．

方法名：GenerateAndEvaluatePath_OMP

{

1.#pragma omp parallel for

2.for (i=0;i

{

3.t=∶∶omp_get_thread_num( );

4.GeneratePath(i,t);

5.EvaluatePath(i);

}

}

此方法根據(jù)當(dāng)前CPU負(fù)載情況自動(dòng)為每條路徑的計(jì)算分配合適的內(nèi)核資源．第1行為OpenMp指令，用于定義以下for循環(huán)為多線程并行處理代碼塊；第2行中Psize為要生成的候選路徑條數(shù)，i為循環(huán)控制變量；第3行為OpenMp方法，從可用計(jì)算線程組中返回一個(gè)分配給此次計(jì)算任務(wù)的線程編號(hào)，如4核CPU，則t在0，1，2，3中取值，由系統(tǒng)根據(jù)各核計(jì)算負(fù)載狀態(tài)分配；第4行為生成第i條路徑的方法，該任務(wù)在第t號(hào)線程上執(zhí)行，因?yàn)槁窂缴伤惴ㄐ枰薷木W(wǎng)格單元狀態(tài)，而網(wǎng)格單元為線程間的共享資源，為了避免訪問(wèn)沖突，對(duì)算法用到的網(wǎng)格狀態(tài)值按內(nèi)核數(shù)目生成副本，每個(gè)線程在自己對(duì)應(yīng)的副本狀態(tài)上做修改，進(jìn)而提高了計(jì)算并行度，將線程號(hào)t傳入方法，以決定路徑生成時(shí)使用哪個(gè)副本；第5行為評(píng)價(jià)第i條路徑的方法，該任務(wù)在第t號(hào)線程上執(zhí)行．

2.4基于A*算法的子段路徑生成

框架圖中的特定算法(Algorithm)用于生成管路接口間的候選路徑，2.2節(jié)方法通過(guò)引入中間連接點(diǎn)把原始路徑生成分解成各子段路徑的生成，所以生成子段路徑的過(guò)程會(huì)被反復(fù)調(diào)用，生成子段路徑的效率和質(zhì)量對(duì)布管結(jié)果影響很大，本文選擇A*算法實(shí)現(xiàn)子段路徑生成．

2.4.1A*算法原理及復(fù)雜度A*算法最早由Hart等提出，其不是單純的深度優(yōu)先或廣度優(yōu)先搜索，而是基于最優(yōu)優(yōu)先策略的搜索[3]．A*算法在每一步迭代搜索過(guò)程中會(huì)從當(dāng)前頂點(diǎn)的鄰接候選頂點(diǎn)中選擇評(píng)價(jià)函數(shù)值最小的頂點(diǎn)n，評(píng)價(jià)函數(shù)表示為f(n)=g(n)+h(n)，其中g(shù)(n)代表從路徑起始頂點(diǎn)到任意一個(gè)頂點(diǎn)n的實(shí)際代價(jià)，h(n) 代表從任意一個(gè)頂點(diǎn)n到達(dá)目標(biāo)頂點(diǎn)的估計(jì)代價(jià)．A*在搜索過(guò)程中不斷更新g(n)和h(n)，因此每個(gè)網(wǎng)格路徑點(diǎn)的選擇考慮了已形成路徑代價(jià)和剩余路徑代價(jià)，使搜索更具目的性．

A*算法與Dijkstra算法都是尋找最短路徑的經(jīng)典方法，復(fù)雜度同為O(|V|2)，V為頂點(diǎn)數(shù)，因?yàn)樵谧顗那闆r下A*仍然需要訪問(wèn)所有頂點(diǎn)，但啟發(fā)函數(shù)h(n)會(huì)引導(dǎo)搜索向目標(biāo)頂點(diǎn)有效進(jìn)行，使實(shí)際搜索的頂點(diǎn)數(shù)比Dijkstra算法少很多．當(dāng)使用Fibonacci 堆作為算法優(yōu)先隊(duì)列時(shí)，A*算法復(fù)雜度可降低到O(VlogV)，這是目前求解有向圖單源最短路徑的最好算法．

2.4.2基于A*算法的子段網(wǎng)格路徑生成結(jié)合三維網(wǎng)格空間的數(shù)據(jù)結(jié)構(gòu)和布管約束，將使用A*算法生成兩點(diǎn)間網(wǎng)格路徑的過(guò)程說(shuō)明如下．

(1)數(shù)據(jù)結(jié)構(gòu)

空間網(wǎng)格的數(shù)據(jù)結(jié)構(gòu)包括當(dāng)前網(wǎng)格點(diǎn)標(biāo)號(hào)Cid，前繼網(wǎng)格點(diǎn)標(biāo)號(hào)Pid，網(wǎng)格中心點(diǎn)坐標(biāo)(x,y,z)，網(wǎng)格邊長(zhǎng)L，網(wǎng)格所在行號(hào)r、列號(hào)c、層號(hào)l，網(wǎng)格所在位置的勢(shì)能E，A*算法記錄網(wǎng)格點(diǎn)路徑代價(jià)的變量f、g、h．

兩個(gè)表結(jié)構(gòu)：Open表和Close表，Open表用于保存有待考察的網(wǎng)格點(diǎn)(即可能構(gòu)成路徑的網(wǎng)格點(diǎn))；Close表用于記錄所有已訪問(wèn)過(guò)的網(wǎng)格點(diǎn)．

(2)算法流程圖

A*算法生成管路子段的流程如圖3所示．

圖3　基于A*算法的子段路徑生成

算法中的Open表為基于Fibonacci堆的優(yōu)先隊(duì)列．其中，當(dāng)前網(wǎng)格點(diǎn)n到n0之間的已生成路徑代價(jià)g不單純表示管路長(zhǎng)度，而是按路徑評(píng)價(jià)函數(shù)(參見式(1))計(jì)算出的綜合代價(jià)，它考慮了n到n0間的管路長(zhǎng)度、彎頭數(shù)目、管路對(duì)應(yīng)的能量值和管路不滿足最小管段長(zhǎng)度約束的懲罰值；同理，m和n之間的“距離”也代表了m與n之間的綜合代價(jià)；m和目標(biāo)網(wǎng)格點(diǎn)(記為t)之間的“估計(jì)距離”定義為網(wǎng)格點(diǎn)之間的Manhattan距離，該距離與從m到t需要沿行、列、層經(jīng)過(guò)的網(wǎng)格數(shù)相關(guān)(只考慮水平或豎直方向，且忽略障礙物影響)，m和t之間的Manhattan距離計(jì)算如下式：

FManhattan(m,t)=(abs(t.r-m.r)+

abs(t.c-m.c)+

abs(t.l-m.l))×L

(2)

式中：abs()為絕對(duì)值計(jì)算函數(shù),L為網(wǎng)格邊長(zhǎng)．

(3)算法并行化修改

2.3節(jié)提到種群進(jìn)化過(guò)程中路徑生成需要支持并行計(jì)算，其實(shí)質(zhì)就是指此處的A*算法在同一時(shí)刻會(huì)運(yùn)行在N(N為內(nèi)核數(shù))個(gè)線程上，網(wǎng)格作為線程間的共享資源，需要支持多線程并發(fā)訪問(wèn)，因此對(duì)算法中用到的網(wǎng)格狀態(tài)值需按內(nèi)核數(shù)目生成副本，使各線程在自己對(duì)應(yīng)的副本狀態(tài)上做修改，以提高運(yùn)算并行度．從流程圖3看出，網(wǎng)格狀態(tài)中的Pid、f、g、h需要支持并發(fā)修改，當(dāng)算法支持多線程并發(fā)計(jì)算時(shí)，需對(duì)以上狀態(tài)生成副本，使用Pid[t]、f[t]、g[t]、h[t](0≤t

2.5算法成本分析

2.5.1空間成本算法內(nèi)存需求主要包括：①存儲(chǔ)布置空間的網(wǎng)格狀態(tài)，A*算法的尋路及路徑評(píng)價(jià)需要在網(wǎng)格空間進(jìn)行；②存儲(chǔ)表示管路的各種群內(nèi)個(gè)體，協(xié)同算法需要基于種群個(gè)體進(jìn)行迭代．因?yàn)榫W(wǎng)格空間劃分及種群個(gè)體生成均在算法初始化階段完成，所以算法運(yùn)行時(shí)內(nèi)存(Mcost)隨時(shí)間變化波動(dòng)不大，可基于下式估算：

Mcost=O(Sgrid×Ngrid+Spath×Psize×Npipe)

(3)

式中：Sgrid為網(wǎng)格結(jié)構(gòu)大小，Ngrid為網(wǎng)格數(shù)目，Spath為路徑個(gè)體結(jié)構(gòu)大小，Psize為一個(gè)種群內(nèi)的個(gè)體數(shù)目，Npipe為管路或分支對(duì)應(yīng)的種群數(shù)目．

2.5.2時(shí)間成本群進(jìn)化算法的時(shí)間復(fù)雜度可通過(guò)對(duì)種群的更新和評(píng)價(jià)次數(shù)來(lái)估計(jì)，因此本文算法的時(shí)間復(fù)雜度(Tcost)可以用下式估算：

Tcost=O((Cevolve+Cevaluate)×Psize×Npipe×Niter)

(4)

式中：Cevolve為對(duì)路徑個(gè)體執(zhí)行進(jìn)化操作的代價(jià)，Cevaluate為對(duì)協(xié)同解方案的評(píng)價(jià)代價(jià)，Niter為迭代次數(shù)．

3仿真實(shí)驗(yàn)

通過(guò)兩個(gè)實(shí)例驗(yàn)證提出方法的有效性．實(shí)驗(yàn)機(jī)器配置：操作系統(tǒng)為Windows 7 32位，內(nèi)存為2 GB，CPU為Intel(R) Core(TM) i3 M390 2.67 GHz、支持雙核4線程．算法參數(shù)設(shè)置：最大迭代次數(shù)Gmax=200，種群規(guī)模Psize=80，種群進(jìn)化的交叉概率Rc=0.7，變異概率Rm=0.3，連接點(diǎn)控制概率Rcontrol=0.5，連接點(diǎn)個(gè)數(shù)N=3，管路評(píng)價(jià)函數(shù)調(diào)節(jié)系數(shù)a=10，b=10，c=20，d=100，最小管段長(zhǎng)度為2倍網(wǎng)格邊長(zhǎng)．

3.1多管路協(xié)同布置

3.1.1模型空間模型空間為一立方體，其中包括設(shè)備M1～M4、虛擬障礙R1～R5(R1用來(lái)控制管路避開工作空間中心位置，R2、R3為設(shè)備M3提供維修空間，R4為防止管路從M4上方通過(guò)，R5為一禁止區(qū))．待布置管路有3條，管路1、2連接設(shè)備M2和M3，管路3連接設(shè)備M1和M3．關(guān)于設(shè)備、障礙物、管路的更多信息參見文獻(xiàn)[5]．

3.1.2布置結(jié)果圖4為本文方法迭代15次得到的一個(gè)布置結(jié)果．協(xié)同算法使3條管路更好地成束敷設(shè)，且路徑不與障礙物相交，管路之間不干涉，在滿足管路安裝約束和管段最小折彎長(zhǎng)度約束的情況下，使管路長(zhǎng)度盡可能短，折彎數(shù)目盡可能少．未采用并行算法時(shí)，全部計(jì)算任務(wù)在一個(gè)內(nèi)核上進(jìn)行，進(jìn)程的CPU利用率僅為25%；采用并行算法時(shí)，線程在不同邏輯內(nèi)核同時(shí)工作，進(jìn)程的CPU利用率約為75%．統(tǒng)計(jì)10次獨(dú)立計(jì)算結(jié)果，非并行算法平均耗時(shí)315 s，并行算法平均耗時(shí)156 s，采用并行布管算法可使效率提升約50.5%，10次計(jì)算中有5次收斂到實(shí)驗(yàn)最優(yōu)解(實(shí)驗(yàn)最優(yōu)解指實(shí)驗(yàn)過(guò)程中獲得的滿足布管約束的最好解)．

圖4　多管路協(xié)同布置

3.2分支管路協(xié)同布置

3.2.1模型空間模型空間為一立方體，在其內(nèi)部有7個(gè)立方體障礙物，關(guān)于布置空間和障礙物的詳細(xì)信息請(qǐng)參見文獻(xiàn)[6]，要求敷設(shè)一條具有4個(gè)連接點(diǎn)的分支管路，分支管路起點(diǎn)坐標(biāo)為(4,10,10)，終點(diǎn)坐標(biāo)為(15,30,20)，(32,38,15)，(45,30,30)．

3.2.2布置結(jié)果本文方法迭代15次時(shí)的一個(gè)優(yōu)化結(jié)果如圖5所示．由結(jié)果可以看出分支管路在繞開障礙物，彎頭盡可能少的情況下，可以與其他分支管路重合敷設(shè)，使分支管路的總路徑較短，且分支管路能較多地沿物體表面敷設(shè)．統(tǒng)計(jì)10次獨(dú)立計(jì)算結(jié)果，非并行算法平均耗時(shí)214 s，并行算法平均耗時(shí)97 s，效率提升約54.7%，10次計(jì)算中有6次收斂到實(shí)驗(yàn)最優(yōu)解．

圖5　分支管路協(xié)同布置

按分支路徑重合思想敷設(shè)多分支管路，雖然不必在敷設(shè)前確定分支點(diǎn)的位置，但該方法可能形成實(shí)際布管中不允許出現(xiàn)的分支點(diǎn)形狀，如圖6(a)所示，實(shí)際布管中要求使用T型分支點(diǎn)，如圖6(b)所示．因此在評(píng)價(jià)帶分支管路質(zhì)量時(shí)，對(duì)存在不可行分支點(diǎn)的布置方案要加以懲罰(在式(1)中引入懲罰項(xiàng))，使其不被選入迭代優(yōu)解．

圖6　分支點(diǎn)

從實(shí)驗(yàn)結(jié)果看出，應(yīng)用本文方法可以得到滿足協(xié)同布置多管路或分支管路需求的布管方案．統(tǒng)計(jì)多次實(shí)驗(yàn)，算法收斂到實(shí)驗(yàn)最優(yōu)解的概率較高，使用并行策略改進(jìn)算法能有效縮短布管時(shí)間．驗(yàn)證了提出方法的可行性和有效性．

4結(jié)語(yǔ)

本文提出一種適合求解管路協(xié)同布置的算法框架，統(tǒng)一解決了多管路和帶分支管路的協(xié)同敷設(shè)問(wèn)題．使用確定性A*算法生成管路路徑，相比之前采用非確定性蟻群算法生成管路，布管質(zhì)量更好，且算法參數(shù)更易配置．結(jié)合協(xié)同布管問(wèn)題特性，提出使用并行計(jì)算技術(shù)對(duì)協(xié)同進(jìn)化過(guò)程和路徑生成算法做并行化改進(jìn)，使求解效率提升50%以上，說(shuō)明將并行計(jì)算引入布管系統(tǒng)具有實(shí)用性．仿真實(shí)例驗(yàn)證了應(yīng)用本文方法可生成更為合理的管路協(xié)同布置方案．

后續(xù)研究包括：(1)將更高級(jí)的專家經(jīng)驗(yàn)形成布管規(guī)則，引入自動(dòng)化布管算法；(2)研究協(xié)同進(jìn)化算法的調(diào)優(yōu)理論，為改進(jìn)算法框架和設(shè)置算法參數(shù)提供指導(dǎo)；(3)探索基于多主機(jī)網(wǎng)格系統(tǒng)的復(fù)雜管路并行優(yōu)化．

參考文獻(xiàn)：

[1] Ando Y, Kimura H. An automatic piping algorithm including elbows and bends [C] // Proceedings of the 15th International Conference on Computer Applications in Shipbuilding. Trieste:RINA, 2011:153-158.

[2]董宗然,林 焰. 基于最短路徑快速算法的船舶管路自動(dòng)敷設(shè)方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2014, 20(12):2962-2972.

DONG Zong-ran, LIN Yan. Automatic ship pipe routing method based on shortest path faster algorithm [J]. Computer Integrated Manufacturing Systems, 2014, 20(12):2962-2972. (in Chinese)

[3]李純軍. 基于A*算法的多管線通道化自動(dòng)敷設(shè)方法研究[D]. 武漢:華中科技大學(xué), 2011.

LI Chun-jun. Study on the channelized auto-routing method of multi-pipeline based on A*algorithm [D]. Wuhan:Huazhong University of Science and Technology, 2011. (in Chinese)

[4]Kim S H, Ruy W S, 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.

[5]范小寧,林 焰,紀(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 coevolution for optimization of ship multi pipe parallel routing [J]. Journal of Shanghai Jiaotong University, 2009, 43(2):193-197. (in Chinese)

[6]鄔 君,林 焰,紀(jì)卓尚,等. 基于協(xié)同進(jìn)化的艦船分支管路系統(tǒng)路徑優(yōu)化研究[J]. 船海工程, 2008, 37(4):135-138.

WU Jun, LIN Yan, JI Zhuo-shang,etal. Optimal approach of ship branch pipe routing optimization based on co-evolutionary algorithm [J]. Ship & Ocean Engineering, 2008, 37(4):135-138. (in Chinese)

[7]LIU Qiang, WANG Cheng-en. Pipe-assembly approach for aero-engines by modified particle swarm optimization [J]. Assembly Automation, 2010, 30(4):365-377.

[8]Kimura H. Automatic designing system for piping and instruments arrangement including branches of pipes [C] // Proceedings of the 15th International Conference on Computer Applications in Shipbuilding. Trieste:RINA, 2011:93-99.

[9]JIANG Wen-ying, LIN Yan, CHEN Ming,etal. An ant colony optimization-genetic algorithm approach for ship pipe route design [J]. International Shipbuilding Progress, 2014, 61(3-4):163-183.

[10]姜文英,林 焰,陳 明,等. 基于粒子群和蟻群算法的船舶機(jī)艙規(guī)劃方法[J]. 上海交通大學(xué)學(xué)報(bào), 2014, 48(4):502-507.

JIANG Wen-ying, LIN Yan, CHEN Ming,etal. An optimization approach based on particle swarm optimization and ant colony optimization for arrangement of marine engine room [J]. Journal of Shanghai Jiaotong University, 2014, 48(4):502-507. (in Chinese)

[11]王運(yùn)龍,王 晨,韓 洋,等. 船舶管路智能布局優(yōu)化設(shè)計(jì)[J]. 上海交通大學(xué)學(xué)報(bào), 2015, 49(4):513-518.

WANG Yun-long, WAN Chen, HAN Yang,etal. Intelligent layout optimization design of ship pipe[J]. Journal of Shanghai Jiaotong University, 2015, 49(4):513-518. (in Chinese)

[12]王運(yùn)龍,王 晨,彭 飛,等. 基于人機(jī)結(jié)合遺傳算法的船舶管路布局優(yōu)化設(shè)計(jì)[J]. 中國(guó)造船, 2015, 56(1):196-202.

WANG Yun-long, WANG Chen, PENG Fei,etal. Intelligent layout design of ship pipes based on genetic algorithm with human-computer cooperation[J]. Shipbuilding of China, 2015, 56(1):196-202. (in Chinese)

[13]Asmara A, Nienhuis U. Automatic piping system in ship [C] // Proceedings of the 5th International Conference on Computer and IT Application. Delft:COMPIT, 2006:269-279.

[14]Nielsen S S, Dorronsoro B, Danoy G,etal. Novel efficient asynchronous cooperative co-evolutionary multi-objective algorithms [C] // 2012 IEEE Congress on Evolutionary Computation. Brisbane:IEEE Press, 2012:1-7.

文章編號(hào)：1000-8608(2016)04-0367-08

收稿日期：2015-11-30；修回日期: 2016-01-30.

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(51209034)；國(guó)家公益性行業(yè)科研專項(xiàng)(201003024)；遼寧省教育廳科研項(xiàng)目(L2012018).

作者簡(jiǎn)介:董宗然(1981-)，男，博士生，E-mail:dongzongran@163.com；林 焰*(1963-)，男，教授，博士生導(dǎo)師，E-mail:linyanly@dlut.edu.cn.

中圖分類號(hào)：U662.9

文獻(xiàn)標(biāo)識(shí)碼：A

doi:10.7511/dllgxb201604007

Method of ship pipe routing based on co-evolution and parallel computing

DONGZong-ran1,LINYan*2

( 1.Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China；2.Faculty of Vehicle Engineering and Mechanics, Dalian University of Technology, Dalian 116024, China )

Abstract：In order to solve the problem of cooperative pipe optimization in ship, an algorithm framework which is suitable for multiple pipes routing or branch pipe routing is presented. In this framework, evolutionary populations are created for the corresponding pipes or branches. Therefore, the cooperative arrangement of pipes or branches is transformed to the co-evolution of these populations. Based on the concept of connection points, the populations that represent the candidate paths between interface points are generated and gradually evolved through the operations like crossover and mutation. A* algorithm is used as the path finding operator, and the quality and validity of the paths are assured. To speed up the pipe routing, parallel computing technology is adopted to improve the proposed framework and A* algorithm. In the end, the feasibility and effectiveness of the proposed approach are verified by two simulation cases.

Key words：ship pipe; A* algorithm; co-evolution; parallel computing