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

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

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

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

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

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

分支線纜；自動(dòng)布局設(shè)計(jì)；協(xié)同進(jìn)化；快速擴(kuò)展隨機(jī)樹

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

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

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

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

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

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

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

1　分支線纜自動(dòng)布局設(shè)計(jì)問題描述

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

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

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

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

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

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

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

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

2　分支線纜線束模型

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

圖2　線纜零件示意

圖3　線束示意

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

圖4　線纜線束模型

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

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

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

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

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

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

圖5　分支線纜分解示意

3.2基于改進(jìn)RRT算法的單根線纜路徑求解

3.2.1基本RRT算法

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

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

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

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

步驟3. 通過隨機(jī)采樣得到一個(gè)隨機(jī)點(diǎn)xrand；

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

步驟5. 沿xnear到xrand方向，通過給定步長s獲取新的擴(kuò)展點(diǎn)xnew；

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

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

圖6　快速擴(kuò)展隨機(jī)樹算法擴(kuò)展示意

3.2.2基于改進(jìn)RRT算法的線纜路徑求解

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

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

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

圖7　基于障礙物碰撞信息擴(kuò)展示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4　實(shí)例驗(yàn)證

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

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

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

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

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

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

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

5　結(jié)　論

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

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

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

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

[1] 魏發(fā)遠(yuǎn), 陳新發(fā), 王峰軍. 電纜虛擬布線及其逆運(yùn)動(dòng)學(xué)仿真[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006, 18(10): 1623-1627.

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

[3] 王志斌, 劉檢華, 劉佳順, 等. 電纜虛擬布線中的物理特性分析與布局設(shè)計(jì)技術(shù)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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ī)三維自動(dòng)布線技術(shù)研究[J]. 電訊技術(shù), 2005, 45(2): 76-81.

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

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

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

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

[10] 王發(fā)麟, 廖文和, 郭宇，等. 復(fù)雜機(jī)電產(chǎn)品線纜信息本體表達(dá)與存儲(chǔ)分析[J]. 圖學(xué)學(xué)報(bào), 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ā)動(dòng)機(jī)外部管路自動(dòng)敷設(shè)研究[J]. 機(jī)械設(shè)計(jì), 2003, 20(7): 21-23.

[14] 封海波. 機(jī)械設(shè)備管路自動(dòng)敷設(shè)設(shè)計(jì)方法的研究[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ìn)化分類算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2003, 26(4): 446-453.

[18] 鄭皎凌, 唐常杰, 徐開闊, 等. 基于協(xié)同進(jìn)化的異構(gòu)種群挖掘混沌迭代函數(shù)[J]. 計(jì)算機(jī)學(xué)報(bào), 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è)計(jì)與裝配仿真技術(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é)基金項(xiàng)目(51275047)；國防基礎(chǔ)科研項(xiàng)目(A2220110008)；總裝預(yù)先研究項(xiàng)目(51318010102)

徐金寶(1989–)，男，安徽安慶人，碩士研究生。主要研究方向?yàn)榉种Ь€纜自動(dòng)布局設(shè)計(jì)技術(shù)。E-mail：xujb_1989@163.com

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