郭學(xué)鵬，朱永國+，王發(fā)麟，宋利康，陳大偉

(1.南昌航空大學(xué) 航空制造工程學(xué)院，江西 南昌 330063； 2.江西洪都航空工業(yè)集團有限責任公司 經(jīng)理部，江西 南昌 330024； 3.遼陽海關(guān)，遼寧 遼陽 111000)

0 引言

線纜作為傳輸電流和信號的介質(zhì)，廣泛使用在汽車、飛機、武器裝備、雷達、衛(wèi)星等各類復(fù)雜機電產(chǎn)品中[1]。在復(fù)雜機電產(chǎn)品的布線工藝規(guī)劃過程中，由于線纜的種類和數(shù)量眾多，產(chǎn)品內(nèi)部工件復(fù)雜，導(dǎo)致線纜布線繁瑣、易反復(fù)，因此產(chǎn)品中線纜的布線順序已成為影響產(chǎn)品裝配的一個重要因素。在線纜布線順序規(guī)劃方面，尚無一套可供操作，完善且科學(xué)的研究方法。傳統(tǒng)的線纜布線方法是在實物樣機的基礎(chǔ)上，依據(jù)工人經(jīng)驗、參考設(shè)計接線表來完成線纜布線。布線開敞性不足，工人布線經(jīng)驗要求高等不利因素導(dǎo)致線纜布線順序不合理，降低了布線質(zhì)量，增加了制造成本，延長了研制周期。因此，研究一種有效的線纜布線順序規(guī)劃方法，對提高線纜布線質(zhì)量和優(yōu)化產(chǎn)品裝配工藝具有重要的意義[2]。

Conru等[3-4]提出一種并行工程的方法來進行線纜布線設(shè)計，并采用遺傳算法來求解線纜布線的全局最優(yōu)位置;Hermansson等[5]針對線纜布線路徑規(guī)劃中易變形等問題，提出一種低維線纜布線路徑規(guī)劃算法，用于自動規(guī)劃和尋找線束安裝中的連接器的平滑且無碰撞的安裝;王金芳等[6]基于Pro/E平臺，開發(fā)了線纜裝配工藝規(guī)劃原型系統(tǒng)，研究了線纜分支裝配順序和線纜分支路徑規(guī)劃;王發(fā)麟等[7]針對電磁場會干擾線纜敷設(shè)順序的現(xiàn)象，提出一種多尺度混沌變異粒子群算法的線纜敷設(shè)路徑求解方法;劉瀟等[8]提出基于擴展碰撞信息的路徑優(yōu)化方法，對線纜初始布線路徑進行優(yōu)化。張丹等[9]針對航天產(chǎn)品裝配序列規(guī)劃的多目標和非線性的特點，將粒子群算法和遺傳算法進行結(jié)合;居露等[10]利用線束裝配工藝信息建立線束裝配空間約束矩陣，并結(jié)合改進遺傳算法進行線束裝配序列規(guī)劃。上述研究為線纜布線順序規(guī)劃提供了一定的技術(shù)基礎(chǔ)，但線纜布線順序規(guī)劃作為非確定性多項式(Nondeterministic Polynomial，NP)難題[11]，已有研究還存在以下2點不足：①只針對線纜敷設(shè)路徑或線纜干涉等進行研究，未見線纜布線順序規(guī)劃方面的研究;②只研究了純剛性結(jié)構(gòu)件的裝配序列規(guī)劃問題，未涉及到復(fù)雜結(jié)構(gòu)產(chǎn)品線纜的布線順序規(guī)劃。

近年來虛擬裝配技術(shù)的出現(xiàn)為解決線纜裝配工藝規(guī)劃問題提供了方便。虛擬裝配技術(shù)可在無實物樣機的情況下對產(chǎn)品裝配工藝規(guī)劃進行分析、預(yù)測和規(guī)劃，并實現(xiàn)對裝配工藝的仿真與優(yōu)化[12]。Caudell是第一個提出將虛擬裝配和線纜布線相結(jié)合的學(xué)者，其利用增強現(xiàn)實技術(shù)對線纜布線進行仿真[13];Ng等[14]針對一般CAD系統(tǒng)使用人工智能進行線纜自動化或者半自動化布線效率低等問題，在虛擬環(huán)境中開發(fā)了一套沉浸式的人機交互布線系統(tǒng)，并檢驗了其布線效率;Robinson等[15]開發(fā)了一套沉浸式線纜布線設(shè)計系統(tǒng)Co-Star，并進行了一系列的前期測試和驗證，提高了線纜設(shè)計的精確度和效率;高紀開達等[16]認為線纜是空間中一系列截面中心點相連而成的連續(xù)折線段，并利用虛擬裝配的特點，提出了基于離散控制點的線纜建模技術(shù);王志斌等[17]在考慮柔性線纜的物理特性、靜態(tài)位姿、彎曲變形等特點的基礎(chǔ)上，在虛擬環(huán)境下進行了電纜布局設(shè)計。

綜合以上分析，為克服傳統(tǒng)線纜布線方法效率低、易反復(fù)的不足，本文在基于虛擬裝配技術(shù)的線纜布線研究的基礎(chǔ)上，提出一種基于個體擾動變異粒子群優(yōu)化(Individual Disturbance Mutation Particle Swarm Optimization，IDMPSO)算法的線纜布線順序規(guī)劃方法，開發(fā)了線纜布線順序規(guī)劃原型系統(tǒng)，并通過標準測試函數(shù)和實例對算法進行了測試和驗證。

1 線纜布線順序數(shù)學(xué)模型構(gòu)建

1.1 線纜虛擬裝配

線纜虛擬裝配是在虛擬環(huán)境下以柔性線纜為基礎(chǔ)，利用虛擬現(xiàn)實技術(shù)、人工智能、可視化技術(shù)、決策理論和仿真等技術(shù)，通過人機交互的方式在計算機上對線纜布線進行分析與仿真的全過程。線纜虛擬裝配技術(shù)不僅能夠檢驗、評價和預(yù)測線纜的可布線性和整體布線性能，還能對線纜的布線順序、布線路徑和布線方法等問題進行分析和決策。線纜虛擬裝配技術(shù)對提高線纜設(shè)計質(zhì)量，縮短產(chǎn)品設(shè)計和制造周期具有重大意義[18]。線纜虛擬裝配的主要內(nèi)容如圖1所示。

1.2 線纜布線順序可行性數(shù)學(xué)模型構(gòu)建

線纜布線順序可行性評價數(shù)學(xué)模型包括線纜干涉數(shù)學(xué)模型和線纜布線過程流暢性數(shù)學(xué)模型2個模型

(1)線纜干涉數(shù)學(xué)模型構(gòu)建

產(chǎn)品裝配序列規(guī)劃中，碰撞干涉分析是一個無法避免的關(guān)鍵問題，如何有效地避免零部件之間的碰撞干涉是獲得產(chǎn)品合理裝配序列的前提和基礎(chǔ)。線纜作為柔性零件，在受到外力作用時容易發(fā)生變形和接觸不良等問題，因此，在布線時更需要考慮空間干涉問題。本文從兩個方面來分析線纜布線順序的空間干涉問題：①線纜碰撞干涉分析；②線纜與電連接器之間固定方式所采用工具的可操作性。

1)線纜碰撞干涉分析Ni。

線纜碰撞干涉主要包括線纜與線纜之間的碰撞干涉、線纜與剛性結(jié)構(gòu)件的碰撞干涉。其中，線纜與剛性結(jié)構(gòu)件的碰撞干涉在線纜布線路徑設(shè)計中已經(jīng)考慮，故本文的線纜布線順序規(guī)劃中只考慮線纜與線纜之間的碰撞干涉。依據(jù)線纜裝配工程實際，將線纜進行分組。定義各線纜組之間的干涉矩陣如下：

p1p2p3…pn

(1)

其中：pi為第i組線纜，n為線纜組數(shù)量，i、j≤n；aij為線纜組pi與線纜組pj之間的干涉情況，當aij=aji=0時，表示線纜組pi與線纜組pj之間不存在干涉，且規(guī)定i=j時，aij=0；當aij=aji=1時，表示線纜組pi與線纜組pj之間存在碰撞干涉。設(shè)線纜組pi為未裝線纜，i>1,則線纜組pi對于已裝線纜序列P*={p1,p2,…,pk,…,pi-1}的干涉情況為：

(2)

式中Pi為線纜組pi對于已裝線纜序列P*={p1,p2,…,pk,…,pi-1}的干涉情況。當Pi=0時，表示線纜組pi對于已裝線纜序列P*={p1,p2,…,pk,…,pi-1}沒有干涉；當Pi=1時，表示線纜組pi對于已裝線纜序列P*={p1,p2,…,pk,…,pi-1}存在干涉。

將任意產(chǎn)品線纜布線順序記為P={p1,p2,…,pi,…,pn}，n為線纜組號，建立其線纜與線纜之間的干涉數(shù)學(xué)模型：

(3)

式中Nnci為線纜布線序列P的干涉次數(shù)。Nnci越大，表示干涉次數(shù)越多，線纜布線序列P不合理；反之，表示干涉次數(shù)越少，線纜布線序列P越合理。

2)線纜與電連接器之間固定方式所采用工具的可操作性。

(4)

式中：Ti為第i組線纜與電連接器的連接中采用固定工具的操作空間情況；Nfto為在線纜布線順序P中，固定工具操作空間不足的次數(shù)。

結(jié)合以上分析，對于任意線纜布線序列P，建立線纜干涉數(shù)學(xué)模型如下：

fitf=Nnci+Nfto。

(5)

式中fitf表示P對于Nnci與Nfto的干涉情況。Nnci或者Nfto越大，fitf也越大，線纜布線序列P的干涉次數(shù)越多，說明布線序列有待改進；Nnci與Nfto越小，線纜布線序列P的干涉次數(shù)越少，說明規(guī)劃的布線序列比較合理。

(2)線纜布線過程流暢性數(shù)學(xué)模型構(gòu)建

1)線纜布線長度模型Nccl：

(6)

式中：Nccl為線纜布線長度分析模型，在線纜布線順序P中，應(yīng)該遵循先布短線，后布長線的原則來進行布線；Li為在線纜布線順序P中，pi與pi+1之間的長度比較，若li>li+1，則Li=1，表示P存在一次不合理的線纜布線，通過對P的求和計算，即可求得P中存在不合理的線纜布線次數(shù)。Nccl越大，線纜布線序列P的不合理次數(shù)越多，說明布線序列有待改進；Nccl越小，線纜布線序列的不合理次數(shù)越少，說明規(guī)劃的布線序列比較合理。

2)線纜布線空間整體位置模型：

(7)

綜合以上分析，對于任意線纜布線順序，建立線纜布線過程流暢性數(shù)學(xué)模型如下：

fflu=Nccl+Nsdr。

(8)

式中fflu為線纜布線順序的流暢程度。fflu越大，線纜布線序列P的流暢度越差，說明布線序列有待改進；fflu越小，線纜布線序列的流暢度越好，說明規(guī)劃的布線序列比較合理。

2 基于IDMPSO算法的線纜布線順序規(guī)劃

2.1 粒子群算法在線纜布線順序中的離散化

粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法是一種群體智能優(yōu)化算法，能夠很好地解決線纜布線順序規(guī)劃這種NP難題[20-21]?；綪SO算法在迭代過程中，其速度和位置更新公式為：

(9)

(10)

線纜布線順序規(guī)劃是一種整數(shù)離散化問題，而基本粒子群算法的位置與速度是實值計算，不適合線纜布線順序規(guī)劃。為此，本文對基本粒子群算法進行離散化，重新定義粒子的位置、速度以及粒子之間的更新操作和運算。

定義1粒子位置。粒子的位置表示線纜各組號之間的排列，第i個粒子的位置為Xi=(xi1,xi2,…,xid,…,xin)，其中xid∈{1,2,…,n}為線纜組的編號。

定義2粒子速度。線纜各組號之間的排列通過粒子速度來更新。種群中第i個粒子的速度矢量為Vi=(vi1,vi2,…,vid,…,vin)，其中vid∈{1,2,…,n}，為粒子i速度矢量的第d維元素，表示粒子i中xid對應(yīng)的速度，當vid≠0時，表示線纜xid在Xi中的排列位置需要發(fā)生改變。

定義4粒子相互位置的減法。兩個粒子位置相減產(chǎn)生一個新速度，設(shè)X1=(x11,x12,…,x1d,…,x1n)，X2=(x21,x22,…,x2d,…,x2n)，則定義Vi=X2ΘX1，其中Vi為一個新速度，Vi的求解方法為：若x1d=x2d，則vid=0；若x1d≠x2d，則vid=x2d。

定義5粒子速度的加法。重新定義粒子速度的加法Vk=Vi⊕Vj，其中，Vk的求解方式如下：

(11)

式中r為分布于[0,1]區(qū)間的隨機數(shù)。

定義6粒子速度的乘法。重新定義粒子速度的乘法Vj=c?Vi，c∈[0 1]，Vj表達式的值為：

(12)

式中r為分布于[0,1]區(qū)間的隨機數(shù)。

定義7粒子位置和速度更新。重新定義粒子位置和速度更新：

(13)

(14)

式中c1、c2、r1、r2為分布于[0,1]區(qū)間的隨機數(shù)。

2.2 IDMPSO算法目標函數(shù)

以線纜干涉、線纜布線過程流暢性為約束，設(shè)計IDMPSO算法目標函數(shù)。層次分析法(Analytic Hierarchy Process, AHP)[22]是決策者對復(fù)雜、模糊問題做出決策并確定復(fù)雜、模糊問題中各影響因素權(quán)重的一種方法，為此本文采用AHP法對3個影響因素進行權(quán)重的確定。通過層次分析法對線纜布線順序可行性因素集的決策，求解出IDMPSO算法的目標函數(shù)：

F=0.473 4×fitf+0.526 6×fflu

=0.473 4×(0.5×Nnci+0.5×Nfto)+

0.526 6×(0.5×Nccl+0.5×Nsdr)。

(15)

式中：fitf、fflu分別表示線纜布線干涉模型、線纜布線過程流暢性模型；0.473 4表示線纜布線干涉因素對線纜布線順序的影響程度；0.526 6表示布線過程的流暢程度對線纜布線順序的影響程度。系數(shù)越接近1，說明該約束對線纜布線順序的影響程度越大；反之，則該約束對線纜布線順序的應(yīng)先程度越小。

2.3 基于個體擾動變異的粒子群算法

PSO算法在迭代尋優(yōu)過程中，粒子群中其他粒子會向某一個找到當前最優(yōu)位置的粒子靠攏，當該粒子發(fā)現(xiàn)當前最優(yōu)位置不是全局最優(yōu)位置，即局部最優(yōu)解時，粒子群會因為“惰性”不會繼續(xù)在解空間內(nèi)搜索，因而使算法陷入局部最優(yōu)并出現(xiàn)早熟現(xiàn)象。針對這一不足，本文在基本粒子群算法的基礎(chǔ)上，在算法中對粒子進行干擾和變異，以提高粒子的尋優(yōu)能力，避免算法發(fā)生早熟現(xiàn)象。首先，利用混沌搜索機制生成不同的混沌變量對微粒進行干擾，生成新的微粒，以提高算法的搜索精度；然后，利用變異機制以一定的概率對新微粒進行變異操作，避免算法過早陷入局部最優(yōu)。

(1)基于混沌搜索機制的微粒干擾

粒子的混沌搜索具有極度敏感性、遍歷性、規(guī)律性等特點，能夠使部分微粒跳出局部最優(yōu)并保持種群的多樣性。產(chǎn)生混沌變量的模型有Lozi映射、Logistic映射、Ushiki映射和Sinusoidal映射。Logistic映射具有計算復(fù)雜度低,實現(xiàn)簡單等優(yōu)點，適合于對IDMPSO算法微粒進行干擾，采用Logistic映射來產(chǎn)生混沌變量，混沌每次迭代都能產(chǎn)生不同的新解，且產(chǎn)生的混沌變量遍布于整個解空間，具有很大的隨機性。Logistic映射函數(shù)定義如下：

(16)

(2)微粒變異

通過計算種群適應(yīng)度方差σ2能夠較好的判斷算法是否發(fā)生早熟現(xiàn)象。對于種群容量為M的種群，定義該種群適應(yīng)度方差

(17)

式中：fi為第i粒子的適應(yīng)度值;favg為當前種群平均適應(yīng)度值。

種群適應(yīng)度方差σ2能夠反映種群的聚集程度和種群多樣性，σ2越大，種群多樣性越大，σ2越小，種群多樣性越小。當σ2=0，表示種群多樣性消失，種群陷入局部最優(yōu)或者找到全局最優(yōu)解;當σ2

2.4 IDMPSO算法流程

通過對標準粒子群算法的整數(shù)離散化，結(jié)合個體擾動變異思想，得到IDMPSO算法的詳細步驟(如圖2)：

步驟1初始化。設(shè)置算法參數(shù)ωmax、ωmin、c1、c2、最大迭代次數(shù)Tmax、混沌迭代次數(shù)Gcmax、種群容量M和理論閾值gm。

步驟2初始化種群速度V，種群位置P，初始化種群迭代次數(shù)T1=1。

步驟3計算種群中各粒子適應(yīng)度值fi、種群平均適應(yīng)度值favg和種群適應(yīng)度方差σ2。

步驟4判斷適應(yīng)度方差σ2與理論閾值gm的大小，若σ2

步驟5在初始化的種群中選擇0.2×M個適應(yīng)度值較差的粒子作為混沌變異的新種群N，初始化混沌迭代次數(shù)g=1。

步驟10令g=g+1，判斷g與Gcmax的大小。若g

步驟11找到種群中個體最優(yōu)值Pbest和全局最優(yōu)值Gbest。

步驟12計算新種群最小適應(yīng)度值fmin、最大適應(yīng)度值fmax和平均適應(yīng)度值favg，并根據(jù)公式對慣性權(quán)重ω進行更新。

步驟13根據(jù)式(13)和式(14)更新粒子(布線順序)位置和速度。

步驟14種群迭代次數(shù)T1=T1+1，并判斷T1與Tmax的大小，若T1

步驟15輸出最佳布線順序和最佳適應(yīng)度值，算法結(jié)束。

3 實例驗證

為驗證IDMPSO算法的效果，以某型相控陣雷達為研究對象，對雷達內(nèi)部空間中的線纜進行布線順序規(guī)劃。如圖3所示，在相控陣雷達模型中，共有17組柔性線纜，每一組線纜數(shù)量各不相同，且線纜交錯排布于各剛性結(jié)構(gòu)件之間。相控陣雷達由于內(nèi)部空間復(fù)雜，包含各種電子部件、元器件和柔性線纜，且線纜與電子部件、元器件緊密的連接在一起，造成雷達內(nèi)部空間十分狹小，使得線纜在布線時操作困難。因此，為解決上述線纜布線的難點問題，需要一個合理的線纜布線順序來指導(dǎo)布線工人對雷達內(nèi)部線纜進行布線。

依據(jù)構(gòu)建的線纜布線順序數(shù)學(xué)模型和IDMPSO算法，對CREO 2.0平臺進行二次開發(fā)，開發(fā)出線纜布線順序規(guī)劃功能模塊。該功能模塊主要由對話框資源文件和相應(yīng)的控制程序兩大部分構(gòu)成。對話框資源文件的內(nèi)容定義了對話框的組成、外觀和屬性。控制程序由Microsoft Visual Studio 2010通過C++編程實現(xiàn)，用來在CREO/TOOLKIT環(huán)境嵌入對話框資源、顯示對話框、設(shè)置動作和退出對話框等。如圖4所示為IDMPSO算法開發(fā)的線纜布線順序規(guī)劃功能界面。

在運用算法進行線纜布線順序求解之前，需要利用開發(fā)的線纜布線順序規(guī)劃功能模塊自動獲取線纜信息系和電連接器信息，然后對模型線纜信息進行分組處理，如圖5所示。在實例計算中，設(shè)置如下算法參數(shù)：ω采用非線性的動態(tài)慣性權(quán)重系數(shù)，ωmax=0.9，ωmin=0.4；學(xué)習因子c1、c2取值均為2；種群規(guī)模N=40；算法最大迭代次數(shù)Tmax=1 000，混沌迭代次數(shù)Gcmax=20；理論閾值gm=0.8；統(tǒng)計50次試驗運行結(jié)果。算法運行結(jié)果如圖6和圖7所示，從圖7中可以看到，算法最佳適應(yīng)度值在第600代左右收斂于最優(yōu)解17.167，并一直穩(wěn)定在該值。從圖6中可得，算法在收斂后，求出的最佳布線順序為P={15-14-16-17-10-1-2-8-9-3-4-13-5-6-7-11-12}。

為進一步驗證本文IDMPSO算法在求解線纜布線順序的可行性與優(yōu)越性，在保證布線模型、目標函數(shù)以及算法相關(guān)參數(shù)不變的情況下，將IDMPSO算法與基本PSO算法進行比較，分析兩種算法在運行50次試驗時求解線纜布線順序時得到的最優(yōu)布線順序次數(shù)、算法平均尋優(yōu)時間、以及最優(yōu)適應(yīng)度值之間的關(guān)系，如表1所示。從表1中可以得出，隨著種群容量的增加，兩種算法能夠求得的可行布線序列也隨著增加，但是無論種群容量為40、60還是100，本文IDMPSO算法得到的可行布線序列總是比基本PSO算法得到的多，說明本文改進的IDMPSO算法的尋優(yōu)能力比基本PSO算法強；其次，算法的平均運行時間隨著種群容量的增加而增加，但總體而言，IDMPSO算法由于引入的個體擾動變異思想，其平均運行時間比基本PSO算法稍長，但其運算時間均在可接受范圍之內(nèi)；最后，本文IDMPSO算法得到的最佳適應(yīng)度值均比基本PSO算法小，說明在求解線纜布線順序時，本文IDMPSO算法求解的線纜布線順序更合理、可行。綜上所述，本文所提方法和算法能求解出一套較為合理的線纜布線順序，對相控陣雷達這種內(nèi)部空間緊密、操作不便的機電產(chǎn)品的線纜布線過程中，有很好的指導(dǎo)作用。

表1 兩種算法實驗結(jié)果對比

4 結(jié)束語

利用線纜虛擬裝配技術(shù)，在虛擬環(huán)境下構(gòu)建線纜布線順序可行性數(shù)學(xué)模型，確定影響線纜布線順序的因素，為求解算法適應(yīng)度函數(shù)打下基礎(chǔ)。針對基本粒子群算法實值運算，且容易陷入局部最優(yōu)解和早熟收斂等缺點，在基本粒子群算法的基礎(chǔ)上對算法進行整數(shù)離散化，同時引入個體擾動變異搜索機制對算法進行改進，提高了算法的全局搜索能力和局部尋優(yōu)能力。以某型相控陣雷達為例，將本文所提算法應(yīng)用于線纜布線順序規(guī)劃過程中，證明了本文所提個體擾動變異粒子群算法的優(yōu)越性。對于復(fù)雜機電產(chǎn)品的線纜敷設(shè)順序規(guī)劃，由于產(chǎn)品內(nèi)部結(jié)構(gòu)的復(fù)雜性以及線纜敷設(shè)順序需遵循的規(guī)則較多，為提高產(chǎn)品線纜敷設(shè)效率，在后續(xù)研究中需要考慮更多的敷設(shè)順序約束條件和敷設(shè)規(guī)則，以適用于多約束、多規(guī)則產(chǎn)品的線纜敷設(shè)順序規(guī)劃。