基于協同進化算法的分支線纜自動布局設計方法

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

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

基于協同進化算法的分支線纜自動布局設計方法

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

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

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

分支線纜；自動布局設計；協同進化；快速擴展隨機樹

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

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

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

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

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

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

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

1　分支線纜自動布局設計問題描述

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

圖1　分支線纜自動布局設計技術總體思路

工程實踐中，產品內部結構復雜，線纜布局空間極不規則，導致可供線纜布局的空間十分狹小。為了確保線纜工作的可靠性，本文所考慮的線纜布局約束主要包括：

(1) 合理的分支結構，并確保電路連通關系。復雜機電產品中線纜數量多，合理的分支結構不僅能確保連通關系，更能簡化布局；

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

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

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

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

2　分支線纜線束模型

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

圖2　線纜零件示意

圖3　線束示意

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

圖4　線纜線束模型

3　基于協同進化算法的分支線纜自動布局設計

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

分支線纜布局設計是具有多個接插端的線纜布局問題，其形式很復雜。若能夠將分支線纜進行合理巧妙的分解，形成多個種群，其能夠完全表達分支線纜的布局問題，且這些種群之間并不是全無關系，而是相互關聯、相互影響的，那么就可以利用協同進化算法來解決分支線纜布局優化問題。

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

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

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

圖5　分支線纜分解示意

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

3.2.1基本RRT算法

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

基本RRT算法的執行流程如下：

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

步驟2. 創建搜索樹T，該樹初始時為空。先將起點xinit放入T中，在預先設定好的循環數范圍內執行步驟3～7循環，對RRT進行擴展，如圖6所示；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3基于協同進化算法的分支點尋優

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

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

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

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

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

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

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

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

圖9　基于協同進化算法的分支線纜自動布局設計流程

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

圖10　分支線纜種群間的協作原理

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

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

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

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

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

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

圖11　協同進化得到的布局設計結果

4　實例驗證

為了驗證算法的可行性與布局質量，開發出了虛擬環境下的線纜自動布局設計原型系統，系統的開發與運行環境如表1所示。

表1　系統的開發與運行環境

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

圖12　關鍵點擬合線纜測試效果

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

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

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

5　結　論

(1) 針對分支線纜的自動布局設計問題，提出了分支線纜的線束模型，準確表達分支線纜的結構以及內部連通信息；在此基礎上提出了基于協同進化算法的分支線纜自動布局設計方法；開發了線纜自動布局設計原型系統，并進行了實例驗證，證明了算法的可行性。

(2) 該方法考慮了部分工程約束，能夠對分支點的位置進行尋優，得到較優的分支線纜的布局方案。

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

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

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

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

[3] 王志斌, 劉檢華, 劉佳順, 等. 電纜虛擬布線中的物理特性分析與布局設計技術[J]. 計算機輔助設計與圖形學學報, 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] 吳銀鋒, 吳兆華, 李春泉. 電子整機三維自動布線技術研究[J]. 電訊技術, 2005, 45(2): 76-81.

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

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

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

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

[10] 王發麟, 廖文和, 郭宇，等. 復雜機電產品線纜信息本體表達與存儲分析[J]. 圖學學報, 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] 樊江, 馬枚, 楊曉光. 航空發動機外部管路自動敷設研究[J]. 機械設計, 2003, 20(7): 21-23.

[14] 封海波. 機械設備管路自動敷設設計方法的研究[D].哈爾濱: 哈爾濱工業大學, 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] 劉靜, 鐘偉才, 劉芳, 等. 組織協同進化分類算法[J]. 計算機學報, 2003, 26(4): 446-453.

[18] 鄭皎凌, 唐常杰, 徐開闊, 等. 基于協同進化的異構種群挖掘混沌迭代函數[J]. 計算機學報, 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] 尚煒. 復雜產品線纜數字化布局設計與裝配仿真技術[D]. 北京: 北京理工大學, 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

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

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

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