蘆 欣，周曉卉

（1.撫順職業(yè)技術(shù)學(xué)院 信息工程系，遼寧 撫順 113122;2.遼寧石油化工大學(xué) 信息與控制工程學(xué)院，遼寧 撫順 113001）

一種管線布局智能優(yōu)化方法

蘆 欣1，周曉卉2

（1.撫順職業(yè)技術(shù)學(xué)院 信息工程系，遼寧 撫順 113122;2.遼寧石油化工大學(xué) 信息與控制工程學(xué)院，遼寧 撫順 113001）

為了實(shí)現(xiàn)復(fù)雜機(jī)電裝備管線布局優(yōu)化設(shè)計(jì)，提出了一種基于新的編碼方式的管線布局智能優(yōu)化方法。首先，設(shè)計(jì)了一種具有更好通用性的新的粒子編碼方法，給出了管路路徑映射規(guī)則。其次，給出了基于該編碼方式的目標(biāo)函數(shù)計(jì)算方法。再次，結(jié)合管路布局領(lǐng)域的相關(guān)技術(shù)，采用粒子群算法對(duì)管路避障路徑進(jìn)行尋優(yōu)。最后應(yīng)用MATLAB軟件進(jìn)行管路布局優(yōu)化仿真計(jì)算，驗(yàn)證了該方法的有效性。

管路；布局；編碼；優(yōu)化

管路布局規(guī)劃的數(shù)學(xué)核心為直角避路徑規(guī)劃，其可以描述為在含有障礙的空間內(nèi)尋找一條連接始末點(diǎn)的、符合一定工程規(guī)則的避障最優(yōu)路徑問(wèn)題，其布局目標(biāo)通常包括長(zhǎng)度最小化、彎頭數(shù)最小化以及安裝位置最優(yōu)化（盡量沿著障礙敷設(shè)以便于固定），同時(shí)還要考慮避障、電氣區(qū)域等工程約束[1,5-6]，因此該問(wèn)題在理論上與工程上均十分復(fù)雜。雖然一些商用CAD軟件提供了管路布局模塊，但由于管路布局的復(fù)雜性，目前仍然以技術(shù)人員通過(guò)手工操作為主，需要經(jīng)過(guò)反復(fù)試驗(yàn)與修改，設(shè)計(jì)效率較低，且難以實(shí)現(xiàn)最優(yōu)化與自動(dòng)化。

隨著優(yōu)化理論與工程實(shí)踐的發(fā)展，近年來(lái)，以實(shí)現(xiàn)管路布局最優(yōu)化與自動(dòng)化為目標(biāo)的布管優(yōu)化算法被廣泛提出來(lái)解決這一問(wèn)題。典型的管路布局算法有迷宮法[2]、Zhu算法[3]，啟發(fā)式搜索算法[4]以及遺傳算法[5]、蟻群算法[1]、粒子群算法[6]等智能優(yōu)化方法。這些方法可以解決一定的實(shí)際問(wèn)題，但由于管路布局問(wèn)題的復(fù)雜性，高效的管路布局優(yōu)化算法仍有待遇于進(jìn)一步開(kāi)發(fā)設(shè)計(jì)。近年來(lái)，智能優(yōu)化方法如遺傳算法、蟻群算法、粒子群算法等由于其不依賴于數(shù)學(xué)模型并具有并行性，已經(jīng)成為管路布局問(wèn)題的一個(gè)研究熱點(diǎn)，但已有方法中的個(gè)體編碼方法大多依賴于柵格建模，因此通用性與計(jì)算效率受到一定限制。

應(yīng)用智能優(yōu)化算法解決工程優(yōu)化問(wèn)題的兩個(gè)關(guān)鍵環(huán)節(jié)是建立個(gè)體編碼方法與評(píng)價(jià)函數(shù)。本文設(shè)計(jì)了一種不依賴于柵格的編碼方法，考慮管線布局領(lǐng)域常用的優(yōu)化目標(biāo)，給出了基于該編碼方法的評(píng)價(jià)函數(shù)計(jì)算方法。結(jié)合管路布局領(lǐng)域的相關(guān)技術(shù)，采用粒子群算法對(duì)管路避障路徑進(jìn)行尋優(yōu)，最后進(jìn)行了計(jì)算與仿真，驗(yàn)證了所提方法的有效性。

1 粒子群優(yōu)化算法

其中j=1,2,…N；ω 為慣性權(quán)重，代表粒子保持自己速度的權(quán)值,通常取值為1；c1與c2為學(xué)習(xí)因子，分別表示粒子向自己的最優(yōu)經(jīng)驗(yàn)以及群體中的最優(yōu)經(jīng)驗(yàn)學(xué)習(xí)的權(quán)值，通常取值為2；R1、R2為介于[0,1]之間的隨機(jī)數(shù),相互獨(dú)立。

圖1 粒子群算法基本流程Fig. 1 Basic flow chart of PSO

2 管路布局的粒子群優(yōu)化

2.1 粒子編碼

設(shè)計(jì)粒子編碼與評(píng)價(jià)方法是應(yīng)用粒子群優(yōu)化算法解決實(shí)際工程優(yōu)化問(wèn)題的兩個(gè)關(guān)鍵環(huán)節(jié)，文中提出了一種新的用于管路布局的編碼方法。如圖2所示，給定規(guī)劃空間及管路始末點(diǎn)s、t，首先對(duì)規(guī)劃空間進(jìn)行預(yù)處理：在s、t之間按豎直方向均勻生成一系列豎直線[8]，設(shè)數(shù)量為n，在各條豎直線上各生成一點(diǎn)，其坐標(biāo)依次為 （x1，y1）,(x2,y2), …(xn,yn)，由于橫坐標(biāo)已定，所以，這些點(diǎn)的縱坐標(biāo)[y1,y2, …,yn]便構(gòu)成了一個(gè)粒子編碼。下面以編碼子段 [y1，y2] 為例，介紹編碼與管路路徑的映射規(guī)則。

圖2 規(guī)劃空間預(yù)處理Fig. 2 Pre-processing of routing space

對(duì)于編碼子段 [y1，y2]，該編碼子段多代表的路徑表示如下：點(diǎn)（x1，y1） → 點(diǎn) ((x1+x2)/2，y1) → 點(diǎn) ((x1+x2)/2，y2)→ 點(diǎn)(x2，y2)。其涉及到的3種情況分別如圖3(a)、(b)、(c)所示。

圖3 粒子編碼方法Fig. 3 Particle encoding

按照上述編碼方法，粒子編碼[y1，y2，y3，y4]對(duì)應(yīng)的整條管路路徑如圖4所示。由該編碼方法可知，該方法可以適用于柵格建模情況，但卻不局限于不依賴于柵格，因此具有更好的通用性。

圖4 編碼[y1,y2,y3,y4]對(duì)應(yīng)的整條路徑Fig. 4 Encoding[y1,y2,y3,y4] and its pipe path

2.2 粒子評(píng)價(jià)

一般而言，管路布局的優(yōu)化目標(biāo)[1,5-6]為：1）管路長(zhǎng)度盡量短; 2）管路彎頭最盡量少; 3）盡量沿著墻壁或某些設(shè)備敷管以便于固定。而管路布局的約束條件為：管路應(yīng)該避過(guò)某些區(qū)域，如設(shè)備、已敷設(shè)管路、電氣區(qū)域以及維修區(qū)域等限制區(qū)域。

設(shè)粒子編碼為 [y1, y2,… yn]，根據(jù)本文提出的粒子編碼方法，可建立管路路徑的長(zhǎng)度l、彎頭數(shù)b的計(jì)算方法為如式(3)、(4)所示。

對(duì)于“盡量沿著設(shè)備敷設(shè)”這一優(yōu)化目標(biāo)，借鑒已有相關(guān)技術(shù)，可通過(guò)“能量值”[5]的概念來(lái)解決，即對(duì)那些距離障礙的路徑點(diǎn)賦予較低的“能量值”。對(duì)于約束條件，可通過(guò)管路布局領(lǐng)域常用的罰函數(shù)法[5]來(lái)解決，即對(duì)于與障礙碰撞的個(gè)體路徑，賦予其較差的評(píng)價(jià)函數(shù)。

經(jīng)過(guò)上述處理，即可采用線性加權(quán)法，將上述優(yōu)化目標(biāo)及約束函數(shù)歸一化處理為單目標(biāo)優(yōu)化問(wèn)題。

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

仿真計(jì)算基于個(gè)人PC電腦，采用MATLAB軟件的M函數(shù)編程實(shí)現(xiàn)管路布局優(yōu)化算法，并在UG系統(tǒng)中對(duì)管路布局結(jié)果可視化。管路端點(diǎn)坐標(biāo)分別為(0，0.5)與 ( 20 , 19.5)。粒子群規(guī)模M為60,算法運(yùn)行10次，代表性布局結(jié)果如圖5所示，最優(yōu)粒子收斂曲線如圖6所示。

圖5 管路布局結(jié)果Fig. 5 Pipe layout results

圖6 粒子收斂曲線Fig. 6 Convergence curve of particles

由布局結(jié)果可知，所得管路路徑不僅避過(guò)了設(shè)備以及維修區(qū)域等限制區(qū)域，沿著部分障礙敷設(shè)便于管路固定，而且獲得了較短的管路長(zhǎng)度與較少的彎頭數(shù)，符合工程約束且實(shí)現(xiàn)了優(yōu)化目標(biāo)，驗(yàn)證了方法的有效性。

4 結(jié)束語(yǔ)

針對(duì)管路布局優(yōu)化問(wèn)題，文中設(shè)計(jì)了一種新的用于管路布局的粒子編碼方法，該方法不依賴于柵格建模，因此具有更好的通用性。基于該編碼方法，給出了管路布局優(yōu)化目標(biāo)函數(shù)的計(jì)算方法。集成若干管路布局領(lǐng)域相關(guān)技術(shù)與概念，應(yīng)用粒子群算法對(duì)管路布局路徑進(jìn)行尋優(yōu)。最后通過(guò)仿真算例驗(yàn)證了該方法的有效性。進(jìn)一步的工作將集中在如何將所提管路布局算法推廣到復(fù)雜三維空間中去。

[1] 范小寧. 船舶管路布局優(yōu)化方法及應(yīng)用研究[D].大連:大連理工大學(xué), 2006.

[2] Lee C Y. An algorithm for path connections and its application [J].IRE Transactions on Electronic Computer,1961,EC-10(3):346-364.

[3] Zhu D, Latombe J. Pipe routing=path planning (with many constraints)[C]//Proceedings of the 1991 IEEE International Conference on Robotics and Automation, Sacramento, California,1991:1940-1947.

[4] 柳強(qiáng),王成恩, 白曉蘭. 基于工程規(guī)則的航空發(fā)動(dòng)機(jī)管路敷設(shè)算法[J]. 機(jī)械工程學(xué)報(bào),2011,47(5):163-169.

LIU Qiang, WANG Cheng-en, BAI Xiao-lan. Engineering rules-based pipe routing algorithm for aero-engines[J].Journal of Mechanical Engineering. 2011, 47(5): 163-169.

[5] Ito T. A genetic algorithm approach to pipe route path planning [J].Journal of Intelligent Manufacturing, 1999,10(1): 103-114.

[6] 柳強(qiáng),王成恩,任濤,等. 基于粒子群算法的航空發(fā)動(dòng)機(jī)管路布局方法[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版,2009, 30(7):940-943.

LIU Qiang, WANG Cheng-en, REN Tao, et al. PSO-based pipe routing approach for aircraft engine [J]. Journal of Northeastern University, 2009, 30(7): 940-943.

[7] Kennedy J,Eberhart RC. Particle swarm optimization[C] //Proc of IEEE Int Conf on Neural Networks. Piscataway: IEEE Press,1995:1942-1948.

[8] 趙先章,常紅星,曾雋芳,等. 一種基于粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃方法[J]. 計(jì)算機(jī)應(yīng)用研究,2007,24(3):181-186.

ZHAO Xian-zhang , CHANG Hong-xing , ZENG Jun-fang, et al.Path planning method for mobile robot based on particle swarm algorithm [J].Application Research of Computers,2007,24(3):181-186.

An intelligent optimization method for pipe layout design

LU Xin1, ZHOU Xiao-hui2
（ 1. Department of Information Engineering, Fushun Vocational Technical Institute, Fushun 113112, China;2. School of Information and Control Engineering, Liaoning Shihua University, Fushun 113001, China）

In order to implement optimization design for pipe and cable layout for complex electromechanical equipment, this paper presents a new encoding based pipe layout intelligent optimization algorithm. First, this paper designs a new particle encoding method with better generality and gives a method to map it into a pipe path. Then, this paper gives the computation method for particle evaluation. Further, by integrating several existing techniques in pipe routing areas, the paper applies the particle swarm optimization algorithm to plan the shortest collision-free pipe paths.Finally, pipe layout computations are performed in MATLAB system, which demonstrates the effectiveness of proposed method.

pipe; layout; encoding; optimization

TN702

A

1674-6236(2014)03-0034-03

2013–06–18 稿件編號(hào)：201306110

蘆 欣(1966—)，女，河北滄州人，副教授。研究方向：控制理論與應(yīng)用，電路分析與設(shè)計(jì)。