基于協(xié)同進化算法的分支線纜自動布局設(shè)計方法

徐金寶， 劉檢華， 劉佳順， 劉　瀟

(北京理工大學(xué)機械與車輛學(xué)院，北京 100081)

基于協(xié)同進化算法的分支線纜自動布局設(shè)計方法

徐金寶， 劉檢華， 劉佳順， 劉瀟

(北京理工大學(xué)機械與車輛學(xué)院，北京 100081)

針對分支線纜布局設(shè)計中分支點難以確定的問題，提出基于協(xié)同進化算法的分支線纜自動布局設(shè)計方法。首先建立分支線纜的線束模型，基于線纜的線束模型信息將分支線纜分解為多個一對一的單根線纜，每個單獨的線纜代表一個種群；在此基礎(chǔ)上采用改進的快速擴展隨機樹算法求解單根線纜的路徑，然后基于協(xié)同進化的思想對分支線纜的分支點進行尋優(yōu)，通過種群間相互影響適應(yīng)度的評價使得分支線纜的布局結(jié)果達到最優(yōu)；最后對最終優(yōu)化得到的路徑點進行擬合，從而獲得線纜作為布局設(shè)計結(jié)果并輸出。設(shè)計并開發(fā)了線纜自動布局設(shè)計軟件原型系統(tǒng)，進行算例測試與實例應(yīng)用，驗證方法的可行性。

分支線纜；自動布局設(shè)計；協(xié)同進化；快速擴展隨機樹

線纜是航空、航天和船舶等行業(yè)的復(fù)雜機電產(chǎn)品的重要組成部分，作為傳遞能量和信號的介質(zhì)，線纜布局設(shè)計質(zhì)量直接影響著機電產(chǎn)品的性能與可靠性。傳統(tǒng)的線纜布局設(shè)計通常通過物理樣機來實現(xiàn)，隨著CAD技術(shù)的出現(xiàn)和發(fā)展，線纜數(shù)字化布局設(shè)計技術(shù)獲得越來越廣泛地應(yīng)用，并有效提高了線纜布局設(shè)計效率和質(zhì)量。目前，線纜數(shù)字化布局設(shè)計主要包括人機交互式布局設(shè)計和自動布局設(shè)計兩種方法，而自動布局設(shè)計技術(shù)由于具有更高的布線效率，已逐漸成為國內(nèi)外研究熱點。

線纜可以分為單根線纜和分支線纜。工程中的線纜零件往往是包含多個接插端子的分支線纜。與單根線纜相比，分支線纜的布局設(shè)計更為復(fù)雜，分支線纜在進行布局設(shè)計時不僅需考慮分支點位置的合理性，還需考慮線纜整體的布局特性以及滿足單根線纜所需滿足的布局約束條件。由于線纜分支點位置的不同，線束的成束拓撲會有相應(yīng)的變化，進而線纜的長度、布局、捆扎位置也都有所不同。

在線纜人機交互式布局與裝配仿真方面，中國工程物理研究院的魏發(fā)遠等[1]提出了一種基于虛擬樣機的交互式電纜布線方法以及在此基礎(chǔ)上基于逆運動學(xué)的安裝仿真方法。北京理工大學(xué)的尚煒等[2]針對復(fù)雜機電產(chǎn)品中柔性線纜結(jié)構(gòu)復(fù)雜且在裝配操作中發(fā)生變形而導(dǎo)致的裝配過程仿真難的問題，系統(tǒng)提出了柔性線纜裝配過程仿真的解決方案及其關(guān)鍵技術(shù)的實現(xiàn)方法。北京理工大學(xué)的王志斌等[3]針對機電產(chǎn)品中電纜布局設(shè)計中沒有考慮物理特性導(dǎo)致電纜取樣長度不準(zhǔn)確的問題，提出了虛擬環(huán)境中基于物理特性的電纜布局設(shè)計方法。

目前國內(nèi)外有關(guān)分支線纜自動布局設(shè)計的成果較少。Conru[4]采用遺傳算法對分支線纜布局問題進行求解，首先確定分支點的位置，然后進行路徑的求解，考慮了多種約束的路徑成本，但并未考慮線纜的柔性。桂林電子工業(yè)學(xué)院的吳銀鋒等[5]采用最小斯坦納樹生成法求解一對多的線路問題，以自行開發(fā)的電子整機三圍布線系統(tǒng)(3D routing system，3DRS)驗證了該算法的可行性。北京航空航天大學(xué)的郭偉等[6]提出了一種在骨架模型中進行快速自動布線的方法，根據(jù)電連接器節(jié)點數(shù)據(jù)表與三維模型的連接關(guān)系，能夠自動完成三維布線，生成線纜分支圖以及各種線纜的信息報表。合肥工業(yè)大學(xué)的徐本柱等[7]將無向圖布局理論中的力導(dǎo)向不算模型和算法引入到汽車線束連接圖的布局中，實現(xiàn)了連接圖主干的自動搜索和線束分支的約束對稱布局，進而完成了汽車線束連接圖的自動布局。此外，合肥工業(yè)大學(xué)的劉曉平等[8]提出基于工程語義約束的線束預(yù)裝配自動規(guī)劃方法，朱吉滿等[9]提出了一種汽車線束工藝工序及工序關(guān)系自動生成方法。南京航空航天大學(xué)的王發(fā)麟等[10]針對復(fù)雜機電產(chǎn)品中線纜工程語義信息統(tǒng)一表達難、線纜復(fù)雜拓撲結(jié)構(gòu)難以表示和存儲的問題，提出基于本體和無向圖的復(fù)雜線纜信息表達與存儲分析方法。

與分支線纜布局技術(shù)研究成果的匱乏相比，分支管路布局設(shè)計的國內(nèi)外研究成果相對多一些。華盛頓大學(xué)的 Park[11]提出了管路布局的單元生成法，將分支管路簡化為端點分支和中點分支兩種簡單形式的混合，但是該方法難以確定分支點的位置。荷蘭代爾夫特理工大學(xué)的 Asmara和Nienhuis[12]應(yīng)用粒子群算法和Djikstra算法對分支管路布局問題進行了研究，首先用粒子群算法確定端點的連接順序，然后依次用Djikstra算法搜索每次所選定的兩個端點間的最短管路。北京航空航天大學(xué)的樊江等[13]應(yīng)用改進的 Lee算法以及最小斯坦納生成樹法對分支管路端點進行串行連接，該方法首先選定兩個端點并應(yīng)用改進的 Lee算法進行連接，然后依次連通其余端點。哈爾濱工業(yè)大學(xué)的封海波[14]應(yīng)用混沌算法和粒子群算法對分支管路敷設(shè)問題進行了研究，該方法需要事先確定主管路，然后在連通其余端點。東北大學(xué)的Liu和Wang[15]采用粒子群算法以及最小斯坦納生成樹法求解航空器表面的分支管路布局問題，并采用測地線的原理保證管路的最短路徑。

綜上所述，雖然國內(nèi)外目前研究成果中針對分支管線布局有不同的優(yōu)化方法，但都需要事先確定連通順序或假定分支點的位置，然后以分支點為起點和其他終點相連尋找路徑。由于分支管線敷設(shè)順序和分支點位置的不確定性，使得已有的方法計算效率低，難以在工程中得到應(yīng)用。

近年來，協(xié)同進化算法成為計算智能研究的熱點。該算法擴展了傳統(tǒng)進化算法的應(yīng)用范圍，具有較高的自適應(yīng)能力，能有效地解決一些傳統(tǒng)進化算法難以解決的復(fù)雜問題。協(xié)同進化最早由Ehrlich和 Raven[16]在討論植物和植食昆蟲(蝴蝶)相互之間的進化影響時提出的。協(xié)同優(yōu)化算法在解決復(fù)雜問題時具有明顯的優(yōu)勢，并在各學(xué)科領(lǐng)域得到了應(yīng)用[17-18]。分支線纜由于結(jié)構(gòu)的復(fù)雜性，導(dǎo)致其布局設(shè)計十分繁瑣。本文基于協(xié)同進化算法求解復(fù)雜問題的優(yōu)越性以及分支線纜的結(jié)構(gòu)特點，將其分解為多個形式相對簡單的單根線纜，采用協(xié)同進化算法優(yōu)化分支點的位置，在此基礎(chǔ)上開發(fā)了線纜自動布局設(shè)計原型系統(tǒng)，并通過實例對算法進行了測試與驗證。

1　分支線纜自動布局設(shè)計問題描述

基于協(xié)同進化算法的分支線纜自動布局設(shè)計技術(shù)的總體思路如圖 1所示。求解的具體流程為：①通過CAD數(shù)據(jù)接口，將不同類型的產(chǎn)品設(shè)計CAD模型轉(zhuǎn)換為三維線纜布局設(shè)計環(huán)境中的模型，并構(gòu)建產(chǎn)品的結(jié)構(gòu)件虛擬數(shù)字樣機，作為線纜布局設(shè)計的模型準(zhǔn)備；②對線纜布局設(shè)計過程中的約束信息進行分析，并轉(zhuǎn)化為線纜路徑規(guī)劃的約束，例如線纜貼壁的約束、彎曲半徑的約束等；③導(dǎo)入電器原理設(shè)計階段的連接關(guān)系文件，如接線圖和接線表等，從而得到分支線纜的基本連通信息和部分幾何信息，但此時分支線纜的分支點的位置和布局路徑還未確定；④基于改進RRT算法進行線纜布局初始路徑求解，并利用協(xié)同進化算法進行布局優(yōu)化與分支點尋優(yōu)，從而得到可行的線纜布局結(jié)果，最后結(jié)合工程需求完成線纜布局設(shè)計結(jié)果的輸出。

圖1　分支線纜自動布局設(shè)計技術(shù)總體思路

工程實踐中，產(chǎn)品內(nèi)部結(jié)構(gòu)復(fù)雜，線纜布局空間極不規(guī)則，導(dǎo)致可供線纜布局的空間十分狹小。為了確保線纜工作的可靠性，本文所考慮的線纜布局約束主要包括：

(1) 合理的分支結(jié)構(gòu)，并確保電路連通關(guān)系。復(fù)雜機電產(chǎn)品中線纜數(shù)量多，合理的分支結(jié)構(gòu)不僅能確保連通關(guān)系，更能簡化布局；

(2) 合理的分支點位置可保證線纜盡量短；

(3) 避障，不與環(huán)境中裝配體、組件及已布局的線纜等發(fā)生干涉；

(4) 盡量沿著障礙物表面布局；

(5) 滿足線纜最小彎曲半徑，避免過彎而損壞線纜。

2　分支線纜線束模型

在復(fù)雜機電產(chǎn)品中，線纜數(shù)量龐大，連接關(guān)系較復(fù)雜，并存在大量分支線纜(如圖2所示)。采用合理的模型不僅能準(zhǔn)確表達分支線纜及信息，更能為分支線纜自動布局設(shè)計提供數(shù)據(jù)支持，簡化分支線纜的自動布局設(shè)計問題。為了縮短走線路徑、節(jié)省走線空間、使得線纜布局簡單整潔，實際中有相同電氣連接關(guān)系和共同路徑的多根導(dǎo)線通常會安裝套管等輔助材料形成線束，如圖 3所示。

圖2　線纜零件示意

圖3　線束示意

為了建立線纜的線束模型，將線纜抽象為 3個基本元素：線纜零件、線束、線纜段。線纜零件是指工程中將導(dǎo)線、電纜經(jīng)過捆扎、分支、包扎、安裝電器連接后，具有一定拓撲連接結(jié)構(gòu)和外形的柔性零件。線纜段表達線纜零件中不存在分支的部分，如圖4(a)中的AE、EF、FD等。線束是線纜零件中兩個接插端子間具有電器連接關(guān)系的導(dǎo)線束。如圖4(a)所示，接頭A至接頭C包含一個連通的線束。圖4(b)采用了鄰接表的形式存儲并表示了此線纜零件中的線纜段與線束的關(guān)系。

圖4　線纜線束模型

3　基于協(xié)同進化算法的分支線纜自動布局設(shè)計

協(xié)同進化是提高進化算法性能的一個新方法，其使用分解協(xié)調(diào)的思想將復(fù)雜系統(tǒng)的優(yōu)化問題分解為一系列子系統(tǒng)優(yōu)化問題，各子系統(tǒng)可以分別進行優(yōu)化，再從整體上進行協(xié)調(diào)。算法充分體現(xiàn)了“協(xié)作”的思想，個體適應(yīng)度評價就是要考察個體與其他群體個體協(xié)作解決問題的能力。而且，各個群體也是在每一代中相互協(xié)調(diào)、同步向上進化的，具有較高的并行性和魯棒性。

分支線纜布局設(shè)計是具有多個接插端的線纜布局問題，其形式很復(fù)雜。若能夠?qū)⒎种Ь€纜進行合理巧妙的分解，形成多個種群，其能夠完全表達分支線纜的布局問題，且這些種群之間并不是全無關(guān)系，而是相互關(guān)聯(lián)、相互影響的，那么就可以利用協(xié)同進化算法來解決分支線纜布局優(yōu)化問題。

3.1基于線束模型信息的分支線纜分解

分支線纜有多個接插端，即多個出發(fā)端點，布局十分復(fù)雜，是一對多的布局問題。本文提出將結(jié)構(gòu)復(fù)雜的分支線纜分成多個一對一的單根線纜，然后分別采用改進的RRT算法進行單根線纜路徑求解，以此降低問題的復(fù)雜度。線纜線束模型充分考慮了線纜的連接關(guān)系信息，表達其內(nèi)部的連通關(guān)系。因此，可以基于線纜的線束模型信息，將復(fù)雜的線纜拆分成多個單根線纜。

線束模型詳細表達了復(fù)雜線纜的電器連通關(guān)系以及接插端子信息。圖 2所示的分支線纜，包含線束AC、AD、BD，其中線束模型接頭A與C相連，接頭A與D相連，接頭B與D相連。將分支線纜分解為3個單根線纜AC、AD、BD，如圖5所示。分解后的單根線纜既相互獨立，又彼此關(guān)聯(lián)。復(fù)雜的分支線纜分解為由單根線纜 AC、AD、BD組成的一個系統(tǒng)。針對分解后的單根線纜，就可以采用改進的RRT算法進行路徑求解。

圖5　分支線纜分解示意

3.2基于改進RRT算法的單根線纜路徑求解

3.2.1基本RRT算法

RRT算法是一種基于采樣的路徑搜索算法，由美國伊利諾伊大學(xué)的 LaValle和 Kuffner[19]提出。其設(shè)計用來解決高維非凸空間中物體的運動規(guī)劃問題，特點是無需對空間中的障礙物進行顯式表達，通常也不需要對空間進行預(yù)處理。

基本RRT算法的執(zhí)行流程如下：

步驟1. 初始化路徑搜索的起點xinit、終點位置xgoal，搜索步長s、終止循環(huán)數(shù)N等；

步驟2. 創(chuàng)建搜索樹T，該樹初始時為空。先將起點xinit放入T中，在預(yù)先設(shè)定好的循環(huán)數(shù)范圍內(nèi)執(zhí)行步驟3～7循環(huán)，對RRT進行擴展，如圖6所示；

步驟3. 通過隨機采樣得到一個隨機點xrand；

步驟4. 計算并獲取距離該隨機點最近的點xnear(在最初的循環(huán)中，該點即為起點)；

步驟5. 沿xnear到xrand方向，通過給定步長s獲取新的擴展點xnew；

步驟6. 對xnear到xnew部分進行干涉檢查，若干涉，則進入下一次循環(huán)，若不干涉則繼續(xù)該循環(huán)；

步驟7. 將xnew加入T中，并判斷該點是否足夠接近終點，若足夠接近，則直接與終點相連，算法結(jié)束，否則進入下一循環(huán)。

圖6　快速擴展隨機樹算法擴展示意

3.2.2基于改進RRT算法的線纜路徑求解

線纜自動布局設(shè)計的核心問題是三維空間的布局路徑求解問題。三維空間中的線纜的布局路徑求解問題，可看作求解空間中的球形剛體機器人的運動規(guī)劃問題[20]。因此，可以采用RRT算法求解線纜的布局路徑。RRT算法直接用于線纜自動布局，計算效率低，且不能滿足線纜布局的各項約束，因此基于其良好的適應(yīng)性，并對采樣或擴展策略進行改進，以用于線纜路徑搜索。

為了滿足工程中線纜沿著障礙物表面敷設(shè)的約束，采用基于障礙物碰撞信息的擴展策略。如圖7所示，構(gòu)造方向沿xnear到xgoal、起點為xnear、長度為 d的向量 μgoal。若 μgoal與障礙物發(fā)生碰撞，則直接計算出碰撞面片法向量 N(如圖 7(a)所示)；若μgoal不與環(huán)境中障礙物發(fā)生碰撞(如圖7(b)所示)，則產(chǎn)生與μgoal垂直且長度為d的向量μ，直到 μ與障礙物發(fā)生碰撞。計算得到當(dāng)前碰撞面片的法向量N，即N垂直于碰撞障礙物表面。定義角度θ為單位向量N與向量μ的夾角：

取與 N垂直的方向為新的擴展方向，μe=μsinθ。構(gòu)造以 xnear的父節(jié)點 xpar為起點、xnear為終點的向量 μp，分別計算 μe與 μp的夾角α(0°≤α≤180°)，μe與 μgoal的夾角β(0°≤β ≤180°)。若xnear為根節(jié)點，即μp不存在，如果β大于 90°，則使 μe反向，反之 μe不變。若 μp存在，如果α大于90°，則使μe反向，反之μe不變。沿μe方向擴展一個步長s得到xnew，若xnear到xnew方向不發(fā)生碰撞，則擴展成功，本文取步長s=4。

圖7　基于障礙物碰撞信息擴展示意圖

在設(shè)定的求解空間中，根據(jù)設(shè)定的剛體半徑和搜索步長，按照上述改進RRT算法進行計算，可得到分布于求解空間內(nèi)的“樹”以及一條連接起始和終止點的“路”。由于RRT算法是隨機采樣算法，每一次運算所得到的“樹”和“路”并不相同，但所得路徑一定是空間可行的，即球形剛體機器人沿該路徑運動時不與障礙物發(fā)生干涉，可將該路徑中的所有節(jié)點的位置坐標(biāo)取出并保存，以便得到線纜的初始路徑，如圖 8所示。為了得到較短的線纜路徑，采用多次RRT重復(fù)求解，選擇其中的最優(yōu)解。

圖8　利用改進RRT算法得到的沿障礙物表面的路徑圖

經(jīng)過路徑搜索得到一系列離散點，但在實際中需要平滑的線纜布局路徑，因此需剔除冗余點，采用曲線進行擬合得到光順的路徑，對路徑中各點最小彎曲半徑、最小應(yīng)力等進行計算及修正[21]，最后根據(jù)線束屬性生成線纜。

3.3基于協(xié)同進化算法的分支點尋優(yōu)

在采用改進的RRT算法求解單根線纜路徑的基礎(chǔ)上，基于協(xié)同進化算法優(yōu)化得到分支線纜分支點的位置，其分支線纜自動布局設(shè)計方法主要包含以下5部分：

(1) 問題的分解?；诰€纜的線束模型信息將分支線纜分解，分解后的每根線纜對應(yīng)一個種群，整個分支線纜構(gòu)成一個多種群的生態(tài)系統(tǒng)；

(2) 各種群的進化方式。每一個種群采用改進的RRT算法實現(xiàn)各自的進化過程；

(3) 種群的進化次序。在每一代中，單根線纜的生成順序隨機，即每一代中種群的進化次序是隨機的；

(4) 個體適應(yīng)度的評價。采用最優(yōu)個體配合協(xié)同模式，即任一種群中個體的進化環(huán)境由原始環(huán)境和當(dāng)前其他種群中的最優(yōu)個體所形成的小環(huán)境疊加而成，因此不同種群的進化環(huán)境各不相同，同一種群在不同的進化代數(shù)下所處的進化環(huán)境也可能不同，而種群個體適應(yīng)度的評價取決于該個體所處的環(huán)境。其他種群的代表在適應(yīng)值評估過程中只提供一個環(huán)境，其本身并不接受任何的獎賞或懲罰，組合在評估中所獲得結(jié)果不會影響到這些代表自身的適應(yīng)值；

(5) 終止條件。當(dāng)整體最優(yōu)解不再變化時，輸出這個整體最優(yōu)解作為分支線纜系統(tǒng)的全局整體最優(yōu)解，或以某一固定的進化代數(shù)為終止條件。

綜上所述，基于協(xié)同進化算法的分支線纜自動布局設(shè)計方法的流程如圖9所示。

基于協(xié)同進化的思想，將分支線纜分解為單根線纜，每根線纜分別對應(yīng)一個種群，所有種群構(gòu)成了一個生態(tài)系統(tǒng)。分支線纜系統(tǒng)的多種群協(xié)同進化算法的核心思路是：每根線纜對應(yīng)一個種群，在第 gen代進化中，隨機生成種群進化順序，并設(shè)置可以避免由于固定進化順序而產(chǎn)生局部最優(yōu)解，也就是說種群的進化與順序無關(guān)，排除了線纜進化順序的干擾。假設(shè)最先進化的為線纜i(即種群i)，種群i在原始環(huán)境中率先進化，得到線纜i的gen代解Gen-i，并將線纜i的路徑作為整個分支線纜的主干；假設(shè)第 2個進化的種群為j，則種群j的進化環(huán)境是由初始環(huán)境和gen代中已經(jīng)產(chǎn)生的線纜i的解Gen-i組成的新的生態(tài)系統(tǒng) i，種群 j在生態(tài)系統(tǒng) i中產(chǎn)生一個 gen代解Gen-j；假設(shè)第3個進化的種群為k，則種群k的進化環(huán)境是由初始環(huán)境和gen代中已經(jīng)產(chǎn)生的線纜i的解Gen-i、線纜j的解Gen-j組成的新的生態(tài)系統(tǒng)ij，種群k在生態(tài)系統(tǒng)ij中產(chǎn)生一個gen代解Gen-k。以此類推直到規(guī)劃完最后一根線纜，得到整個三維分支線纜系統(tǒng)的 gen代解 Gen-best，將gen代解Gen-best和至今最優(yōu)解Global-best進行比較，如果當(dāng)代解優(yōu)于至今最優(yōu)解，則 Gen-best成為至今最優(yōu)解，否則不變。循環(huán)執(zhí)行上面的過程，直到滿足迭代終止條件，即分支線纜系統(tǒng)的整體最優(yōu)解不再變化或者滿足固定的進化代數(shù)。

圖9　基于協(xié)同進化算法的分支線纜自動布局設(shè)計流程

在協(xié)同進化過程中，任一種群個體的進化環(huán)境都由原始環(huán)境和當(dāng)前其他種群中的最優(yōu)個體代表所形成的小環(huán)境疊加而成，不同種群的進化環(huán)境各不相同，同一種群在不同的進化代數(shù)下所處的進化環(huán)境也可能不同，而種群個體適應(yīng)度的評價會受到該個體所處的環(huán)境的影響，如圖 10所示。同時其他種群的代表在適應(yīng)值評估過程中只提供一個環(huán)境，其本身并不接受任何的獎賞或懲罰，在評估中所獲得結(jié)果并不會影響自身的適應(yīng)值。

圖10　分支線纜種群間的協(xié)作原理

線纜種群間的協(xié)作行為和相互影響主要是使分支線纜的總路徑變得更短。在優(yōu)化單根線纜路徑的前提下，與其重合的單根線纜路徑越長，說明其共用的線束越多，即總路徑越短，經(jīng)濟性越好。由此可以看出，本文方法只需使單根線纜的路徑最優(yōu)且與其他單根線纜路徑盡量重合，就可以得到合理的分支點的位置，使分支線纜的布局設(shè)計達到較優(yōu)。

本文討論的是求分支線纜的最短路徑問題，約束條件是線纜不與障礙物相交，并沿著障礙物表面敷設(shè)，彎曲半徑不易過小，映射到對某一線纜種群個體的評價，就是求其他線纜種群個體與被評價線纜代表重合最多的最短路徑，優(yōu)化目標(biāo)函數(shù)表達如下：

浮籠多是出現(xiàn)在半籠或是鋼筋籠底部配筋相對較少時，混凝土澆筑到上半部分時下部混凝土開始初凝，形成硬殼導(dǎo)致鋼筋籠整體上升。

其中，Pi和 Pc(c≠i)是單個線纜種群的路徑，L表示單個線纜種群的路徑， Pi∩Pc代表兩個線纜種群的共同路徑，優(yōu)化目標(biāo)是使得在單個線纜種群路徑盡量短的情況下，線纜種群之間的共同路徑盡量大。因此，適應(yīng)度函數(shù)定義如下：

其中，Lic是單個線纜種群 Pic的長度，Cic是單個線纜種群 Pic與主干路徑(某一代進化中首次進化的線纜種群的路徑)重合的長度，也就是線纜種群間的共同路徑長度，a和b(a+b=1)是兩個權(quán)值變量。

按照上述的思想，當(dāng)某個線纜種群在某一代中首次進化時，在計算出線纜路徑后，將其作為整個分支線纜的主干路徑。將主干路徑進行分解，并將所有節(jié)點當(dāng)作其他線纜的終點，以便其他線纜更多地通過。這就意味著其他線纜盡量向主干路徑“靠攏”，使其重合的主干路徑最大化，并擁有共同的目標(biāo)點。通過式(3)求得主干路徑上適應(yīng)度函數(shù)最大點Mi，然后利用改進的RRT算法求解Mi與剩余端點間的路徑。在允許的耗費下，使整體的耗費降至最低。如圖11所示，分支線纜是由4個接插端子組成，包含3個線束AC、AD、BD，對應(yīng)3個種群，每個種群獨自進化生成的路徑如圖11(a)所示。假設(shè)線纜種群BD首先進化，并將首次進化的線纜生成的路徑作為主干路徑，算法將已求解路徑的每個節(jié)點當(dāng)作其他路徑的目標(biāo)點。假設(shè)下個進化的線纜種群是AC，按照式(3)計算得到適應(yīng)度函數(shù)最大的節(jié)點M1為終點，利用改進RRT算法分別求解路徑AM1、得到路徑2作為最優(yōu)路徑。同理，AD線纜種群進化得到最優(yōu)路徑 3，最終的布局結(jié)果如圖 11(b)所示。此時3條路徑的組合擁有最大的公共路徑，工藝優(yōu)化，整體的耗費達到最小。圖11(c)、圖11(d)表示的是隨著進化代數(shù)的增加、進化順序的不同，可能得到的布局設(shè)計結(jié)果。

圖11　協(xié)同進化得到的布局設(shè)計結(jié)果

4　實例驗證

為了驗證算法的可行性與布局質(zhì)量，開發(fā)出了虛擬環(huán)境下的線纜自動布局設(shè)計原型系統(tǒng)，系統(tǒng)的開發(fā)與運行環(huán)境如表1所示。

表1　系統(tǒng)的開發(fā)與運行環(huán)境

該系統(tǒng)利用Spatial公司的三維顯示/交互工具包 HOOPS建立三維環(huán)境，采用三維實體造型引擎 ACIS進行模型的讀取與解析。其中結(jié)構(gòu)件模型是在 Pro/E中完成，并通過數(shù)據(jù)轉(zhuǎn)換接口導(dǎo)入到本系統(tǒng)中，而線纜模型則是利用 ACIS進行實體造型，并通過 HOOPS工具包進行顯示或操作。測試模型采用衛(wèi)星結(jié)構(gòu)版模型，其中適應(yīng)函數(shù)的參數(shù) a=0.9，b=0.1，最大進化代數(shù)為 10。部分測試結(jié)果如圖 12所示，其中線纜零件含有AB、AC兩個線束。

圖12　關(guān)鍵點擬合線纜測試效果

本節(jié)討論取不同a、b值對布局設(shè)計結(jié)果的影響。每一組數(shù)據(jù)均通過 5次平均值計算得到，其中AB為主干路徑的數(shù)據(jù)如表2所示，AC為主干路徑的數(shù)據(jù)如表3所示。由表2、3可以看出，當(dāng)主干路徑確定時，隨著a、b取值的變化，可導(dǎo)致分支線纜的公共路徑長度以及總長度發(fā)生變化。分支線纜公共路徑長度增加，會導(dǎo)致整個線纜的總長度增加。因此，a、b的取值需要根據(jù)線纜布局的實際情況而定，如果需要公共路徑長度大，a取值可盡量小；反之，a取值盡量大，本文取值為a=0.9，b=0.1。當(dāng)a、b值確定時，通過協(xié)同進化算法求解的最優(yōu)主干路徑的分支線纜總長度小于其他主干路徑，也證明了此方法的可行性。

表2　AB為主干路徑不同a、b取值對線纜長度的影響

表3　AC為主干路徑不同a、b取值對線纜長度的影響

5　結(jié)　論

(1) 針對分支線纜的自動布局設(shè)計問題，提出了分支線纜的線束模型，準(zhǔn)確表達分支線纜的結(jié)構(gòu)以及內(nèi)部連通信息；在此基礎(chǔ)上提出了基于協(xié)同進化算法的分支線纜自動布局設(shè)計方法；開發(fā)了線纜自動布局設(shè)計原型系統(tǒng)，并進行了實例驗證，證明了算法的可行性。

(2) 該方法考慮了部分工程約束，能夠?qū)Ψ种c的位置進行尋優(yōu)，得到較優(yōu)的分支線纜的布局方案。

圖13　不同情況下的分支線纜自動布局測試結(jié)果

(3) 實際中的線纜布局設(shè)計問題更加復(fù)雜，需要考慮更多的約束；本文方法很難求出布局的全局最優(yōu)解，算法得到的線纜路徑更可能是次優(yōu)解或者是滿意解，如何提高算法的效率并考慮多個復(fù)雜的分支線纜的布局優(yōu)化等內(nèi)容都將在以后的工作中進一步探索。

[1] 魏發(fā)遠, 陳新發(fā), 王峰軍. 電纜虛擬布線及其逆運動學(xué)仿真[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2006, 18(10): 1623-1627.

[2] 尚煒, 寧汝新, 劉檢華, 等. 復(fù)雜機電產(chǎn)品中的柔性線纜裝配過程仿真技術(shù)[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2012, 24(6): 822-831.

[3] 王志斌, 劉檢華, 劉佳順, 等. 電纜虛擬布線中的物理特性分析與布局設(shè)計技術(shù)[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2014, 26(7): 1193-1202.

[4] Conru A B. A genetic approach to the cable harness routing problem [C]//Proceedings of the IEEE Conference on Evolutionary Computation. Orlando, USA, 1994, (1): 200-205.

[5] 吳銀鋒, 吳兆華, 李春泉. 電子整機三維自動布線技術(shù)研究[J]. 電訊技術(shù), 2005, 45(2): 76-81.

[6] 郭偉, 劉艷芳, 趙輝, 等. 基于骨架模型的快速布線方法[J]. 計算機集成制造系統(tǒng), 2012, 18(11): 2391-2397.

[7] 徐本柱, 程光春, 李忠澤, 等．基于力導(dǎo)向算法的線束連接圖自動布局研究[J]. 工程圖學(xué)學(xué)報, 2010, 31(6): 171-177．

[8] 劉曉平, 李忠澤, 徐本柱, 等. 基于工程語義約束的線束預(yù)裝配自動規(guī)劃方法[J]. 圖學(xué)學(xué)報, 2012, 33(5): 44-50.

[9] 朱吉滿, 徐本柱, 凌欣南, 等. 汽車線束工藝工序及工序關(guān)系自動生成[J]. 圖學(xué)學(xué)報, 2013, 34(2): 38-46.

[10] 王發(fā)麟, 廖文和, 郭宇，等. 復(fù)雜機電產(chǎn)品線纜信息本體表達與存儲分析[J]. 圖學(xué)學(xué)報, 2015, 36(3): 376-383.

[11] Park J H. Pipe-routing algorithm development for a ship engine room design [D]. Washington: University of Washington, 2002.

[12] Asmara A, Nienhuis U. Automatic piping system in ship [C]//5th International Conference on Computer and IT Applications in the Maritime Industries, Sieca Repro (TUD), Delft, 2006: 269-280.

[13] 樊江, 馬枚, 楊曉光. 航空發(fā)動機外部管路自動敷設(shè)研究[J]. 機械設(shè)計, 2003, 20(7): 21-23.

[14] 封海波. 機械設(shè)備管路自動敷設(shè)設(shè)計方法的研究[D].哈爾濱: 哈爾濱工業(yè)大學(xué), 2009.

[15] Liu Q, Wang C G. Multi-terminal pipe routing by Steiner minimal tree and particle [J]. Enterprise Information Systems, 2012, 6(3): 315-327.

[16] Ehrlich P R, Raven P H. Butterflies and plants: a study in coevolution [J]. Evolution, 1964, 18: 586-608.

[17] 劉靜, 鐘偉才, 劉芳, 等. 組織協(xié)同進化分類算法[J]. 計算機學(xué)報, 2003, 26(4): 446-453.

[18] 鄭皎凌, 唐常杰, 徐開闊, 等. 基于協(xié)同進化的異構(gòu)種群挖掘混沌迭代函數(shù)[J]. 計算機學(xué)報, 2010, 33(4): 672-686．

[19] LaValle S M, Kuffner J J. Rapidly-exploring random trees: progress and prospects [C]//Algorithmic & Computational Robotics New Directions. Wellesley MA: A K Peters Ltd, 2000: 293-308.

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

[21] 尚煒. 復(fù)雜產(chǎn)品線纜數(shù)字化布局設(shè)計與裝配仿真技術(shù)[D]. 北京: 北京理工大學(xué), 2012.

Branch Cable Automatic Routing Based on Co-evolutionary Algorithm

Xu Jinbao,Liu Jianhua,Liu Jiashun,Liu Xiao

(School of Mechanical Engineering, Beijing Institute of Technology, Beijing 100081, China)

Facing the problem that the middle forked point is difficult to determine which exists in the branch cable routing, a branch cable automatic routing method is proposed based on co-evolutionary algorithm. Firstly, the branch cable harness model is established. The approach divides the whole system of branch cable into a few single cables based on the cable harness model, and every single cable represents a population. Improved RRT (rapidly-exploring random trees, RRT) algorithm is used to obtain initial path of every single cable. Then middle forked points is optimized based on the idea of co-evolution, which is affected by other single cables during its evolution, and the branch cable routing optimized obtained. Finally, the final optimization of path points obtained were fitted to obtain the cable as a result. A 3D automatic routing prototype system is developed and some experiments are applied to verify the efficiency of the method.

branch cable; automatic routing; co-evolutionary algorithm; rapidly-exploring random tree algorithm

TP 391.9

10.11996/JG.j.2095-302X.2016010025

A

2095-302X(2016)01-0025-09

2015-09-24；定稿日期：2015-10-11

國家自然科學(xué)基金項目(51275047)；國防基礎(chǔ)科研項目(A2220110008)；總裝預(yù)先研究項目(51318010102)

徐金寶(1989–)，男，安徽安慶人，碩士研究生。主要研究方向為分支線纜自動布局設(shè)計技術(shù)。E-mail：xujb_1989@163.com

劉檢華(1977–)，男，江西萍鄉(xiāng)人，教授，博士，博士生導(dǎo)師。主要研究方向為數(shù)字化裝配與檢測。E-mail：jeffliu@bit.edu.cn