基于混沌-粒子群算法的柔性線纜裝配序列規(guī)劃技術(shù)

楊嘯東， 劉檢華， 馬江濤， 趙瑛峰， 呂乃靜

(北京理工大學(xué) 機械與車輛學(xué)院 數(shù)字化制造研究所，北京 100081)

裝配序列規(guī)劃(assembly sequence planning，ASP)是指尋求一組較優(yōu)的序列使得待裝配零部件組裝在一起. ASP是產(chǎn)品裝配工藝規(guī)劃的核心環(huán)節(jié)，在產(chǎn)品質(zhì)量、裝配效率以及產(chǎn)品的全生命周期中起到關(guān)鍵作用，其優(yōu)劣將直接影響到產(chǎn)品的裝配質(zhì)量. 但是，目前復(fù)雜機電產(chǎn)品的裝配工藝規(guī)劃尚存在不足，其裝配序列自動規(guī)劃通常僅考慮剛性結(jié)構(gòu)件，柔性線纜的裝配規(guī)劃仍以模裝法和模板法為主，大量依賴物理樣機和操作工人的經(jīng)驗，線纜的裝配序列規(guī)劃問題已經(jīng)成為復(fù)雜機電產(chǎn)品裝配序列規(guī)劃中的瓶頸難題[1-3].

當(dāng)前常見的裝配序列規(guī)劃方法有人機交互法、幾何可行推理法、基于知識的推理方法和智能優(yōu)化算法[4]. 由于裝配序列規(guī)劃是一個典型的非確定多項式(NP)問題，利用智能優(yōu)化算法通?？梢缘玫竭@類問題的較優(yōu)解. 常見的智能優(yōu)化算法有遺傳算法、蟻群算法、粒子群算法、模擬退火算法、螢火蟲算法等. Murali等[5]通過模擬退火算法來解決減速箱的裝配序列規(guī)劃問題，Wang等[6]基于遺傳-蟻群混合算法對反射板進(jìn)行了裝配序列規(guī)劃，吳宏超等[7]提出了一種基于螢火蟲算法的管路布局序列優(yōu)化方法，相對而言，粒子群算法是一種易于編碼的群智能優(yōu)化算法，其全局搜索能力強，收斂速度快，同時比較容易實現(xiàn)，因此也越來越多地用來求解這類問題，如Wu等[8]通過粒子群算法解決了偏心銑床的裝配序列規(guī)劃問題，與遺傳算法相比，該算法的收斂速度更快，效率更高.

上述研究存在的主要問題在于假設(shè)待裝配的零部件都是剛體，即在裝配過程中不會發(fā)生變形，但復(fù)雜機電產(chǎn)品中柔性線纜的裝配占據(jù)了大量的比重，且線纜不同于剛性零部件，具有布局密集、長徑比大、彎角多、分支結(jié)構(gòu)復(fù)雜等特點，這也為線纜裝配序列規(guī)劃的研究增加了困難. Somayé等[9]通過柔性件的裝配干涉矩陣和裝配應(yīng)力矩陣，從幾何、物理、機械等方面定義了其裝配性能，但并未提出柔性線纜裝配序列規(guī)劃的具體方法. 為解決線纜序列規(guī)劃難題，筆者提出了一種基于改進(jìn)粒子群算法的柔性線纜裝配序列規(guī)劃方法，該方法綜合考慮了線纜上述特點，并通過實例分析和算法對比驗證了所提算法的可行性及效率.

1 線纜裝配序列規(guī)劃數(shù)學(xué)模型

針對柔性線纜裝配序列規(guī)劃問題，需要建立相應(yīng)的數(shù)學(xué)模型. 筆者首先根據(jù)線纜裝配序列規(guī)劃的影響因素確定其約束條件，然后在此基礎(chǔ)上建立該過程的優(yōu)化目標(biāo).

1.1 約束條件的確定

在實際布線過程中，先敷設(shè)的線纜將會直接影響到后續(xù)線纜的敷設(shè)空間，因此整機的線纜裝配順序?qū)Ξa(chǎn)品的布線成功率具有重要影響. 線纜裝配順序一般要服從的約束條件為：①先敷設(shè)布局密集的線纜，后敷設(shè)布局稀疏的線纜；②先敷設(shè)直徑和彎曲半徑大的線纜，后敷設(shè)直徑和彎曲半徑小的線纜；③先敷設(shè)多分支線纜，后敷設(shè)單分支線纜. 其中①為考慮線纜裝配的優(yōu)先級約束，即滿足可裝配性與裝配可達(dá)性的要求，若先敷設(shè)布局稀疏的線纜，則本身布局密集的線纜的裝配空間將會進(jìn)一步受到制約，甚至無法完成裝配；第②③則是考慮線纜敷設(shè)路徑的幾何復(fù)雜性. 線纜裝配序列的優(yōu)化目標(biāo)也將依據(jù)①②③中的約束條件設(shè)計.

1.2 優(yōu)化目標(biāo)的建立

1.2.1適應(yīng)度函數(shù)影響因子的確定

根據(jù)上述的約束條件，確定以線纜裝配優(yōu)先級、線纜長度、直徑、彎曲半徑和線纜分支數(shù)為設(shè)計變量，即目標(biāo)函數(shù)(適應(yīng)度函數(shù))的影響因子. 其中，線纜裝配優(yōu)先等級系數(shù)P由線纜布局密度δ(δ為每平方米的線纜數(shù)目)決定. 線纜布局越密集的區(qū)域，裝配優(yōu)先等級越高，二者的對應(yīng)關(guān)系如表1所示. 數(shù)值越小則對應(yīng)區(qū)域內(nèi)線纜的裝配優(yōu)先等級越高.

表1 線纜布局密度與裝配優(yōu)先等級系數(shù)的對應(yīng)關(guān)系

1.2.2適應(yīng)度函數(shù)的構(gòu)造

適應(yīng)度函數(shù)的構(gòu)造對線纜裝配序列優(yōu)劣的評判具有重要作用，由上述的布線約束條件可知，本文目標(biāo)函數(shù)為最大值問題，即適應(yīng)度值越高，其對應(yīng)的裝配序列性能越好. 根據(jù)1.1節(jié)的影響因素進(jìn)行適應(yīng)度函數(shù)的構(gòu)造，包括線纜裝配優(yōu)先等級系數(shù)P、長度L、直徑D、彎曲半徑R、分支數(shù)S這幾方面，以下將詳細(xì)說明.

① 線纜裝配優(yōu)先等級系數(shù)P.

f1表示線纜裝配優(yōu)先等級系數(shù)P對適應(yīng)度函數(shù)的影響因子. 通常情況下，最優(yōu)裝配序列中最先裝配完成的線纜，其裝配優(yōu)先等級系數(shù)P是最小的(優(yōu)先等級高的線纜要先完成裝配)，即Xi[1].P=1. 且隨著裝配先后次序的遞增，線纜裝配優(yōu)先等級系數(shù)P總體上應(yīng)呈遞增趨勢，即Xi[j].P≤Xi[j+1].P，其中1≤j≤n-1，n為線纜總數(shù)(若某支線纜為跨裝配單元裝配，即線纜不同部位對應(yīng)的裝配優(yōu)先級系數(shù)不同，則該線纜的裝配優(yōu)先級系數(shù)取其中的最小值，但在實際裝配過程中，非跨裝配單元的線纜優(yōu)先于相同優(yōu)先等級系數(shù)跨裝配單元的線纜完成裝配).

綜合上述情況，f1的表達(dá)式為

(1)

② 線纜長度L*線纜直徑D*彎曲半徑R.

f2表示線纜長度L*線纜直徑D*彎曲半徑R對適應(yīng)度函數(shù)的影響因子(同一支線纜中的多個彎曲半徑，取其中最大值). 一般來說，粗長且彎角大的線束的裝配要優(yōu)先于細(xì)短且彎角小的線束.

綜合上述情況，f2的表達(dá)式為

f2=

(2)

③ 線纜分支數(shù)S.

f3表示線纜分支數(shù)S對適應(yīng)度函數(shù)的影響因子. 一般來說，分支數(shù)大的線纜的裝配要優(yōu)先于分支數(shù)小的線纜.

綜合上述情況，f3的表達(dá)式為

(3)

綜合考慮線纜裝配序列的可行性、線纜裝配優(yōu)先等級P,線纜長度L*線纜直徑D*彎曲半徑R、線纜分支數(shù)S，確定適應(yīng)度函數(shù)如下(w1、w2、w3為三個影響因素的權(quán)重系數(shù))：

fitness(n)=

(4)

式中：n為線纜的總數(shù)；f1、f2、f3的初始值均為0；wi(1≤i≤3)為這三個影響因子的權(quán)重系數(shù)，且滿足：

(5)

2 標(biāo)準(zhǔn)粒子群算法原理

2.1 粒子群算法概述

標(biāo)準(zhǔn)PSO算法的速度和位置更新公式為

Vi(t+1)=ωVi(t)+c1rand()×

[Pbesti-Xi(t)]+c2rand()×

[Gbesti-Xi(t)],

(6)

Xi(t+1)=Xi(t)+Vi(t+1),

(7)

式中:Pbesti為當(dāng)前粒子i找到的最優(yōu)解；Gbesti為當(dāng)前在整個種群中找到的全局最優(yōu)解；Vi(t)和Xi(t)分別代表粒子i在第t次迭代中的速度和位置;ω為非負(fù)慣性權(quán)重(慣性因子)，決定了對粒子當(dāng)前速度的繼承比例，其作用是保持粒子群體擴展搜索空間的能力;參數(shù)c1和c2是用以調(diào)整粒子運動過程中的局部搜索能力與全局搜索能力學(xué)習(xí)因子，其中學(xué)習(xí)因子c1反映了個體歷史最優(yōu)位置對更新速度Vi(t+1)的影響，學(xué)習(xí)因子c2反映了全局最優(yōu)位置對更新速度Vi(t+1)的影響.

2.2 線纜裝配序列規(guī)劃與PSO模型的對應(yīng)關(guān)系

對于PSO算法，編碼方式、位置更新與速度更新需要離散化處理，因此線纜裝配序列規(guī)劃問題的模型可通過以下關(guān)系與PSO模型對應(yīng)起來.

① 編碼方式：采用實數(shù)編碼的方式，設(shè)第i支線纜的編號為xi，xi∈[1,n]，則X=[x1x2…xn]為解的一般形式. 序列中的元素與線纜編號一一對應(yīng)，如{2,5,1,7,3,9,10,8,6,4}，其結(jié)構(gòu)示意圖如圖1所示.

② 粒子i的位置：粒子i的位置對應(yīng)于線纜裝配序列的一組有序排列，每個粒子的位置初始化為一個n維矢量，即Xi=[xi1xi2…xij…xin]，其中xij∈{1,2…,n}，n為機電產(chǎn)品中線纜總數(shù).

③ 粒子i的速度：粒子的速度對應(yīng)粒子位置的改變，粒子i位置的改變即線纜裝配序列i排列順序的一種變換序列，裝配序列i的速度矢量表示如下：Vi=[vi1vi2…vij…vin]，其中vij∈{1,2,3,…,n}，vij表示粒子i速度矢量的第j維分量且算法的初始速度隨機生成.

由于慣性權(quán)重ω與學(xué)習(xí)因子c1和c2對PSO算法的性能有很大程度的影響，同時為提高粒子的自我總結(jié)和向群體中精英個體學(xué)習(xí)的能力，需要重新定義上述公式中的ω、c1和c2. 此處的慣性權(quán)重ω與學(xué)習(xí)因子c1和c2均為變量，其定義如下：

(8)

式中：ωmax和ωmin為設(shè)定的慣性權(quán)重的最大值與最小值，其值分別為ωmax=0.9，ωmin=0.3；Gmax為最大迭代次數(shù)；n為已迭代次數(shù)；c1l、c1s、c2l、c2s分別為學(xué)習(xí)因子c1和c2在PSO中的最大值與最小值，其中，c1l=0.8，c1s=0.2，c2l=0.2，c2s=0.8. 式(8)重新定義的優(yōu)點在于算法迭代早期避免了粒子陷入局部最優(yōu)，迭代后期有利于算法的快速收斂.

3 粒子群算法的改進(jìn)

由于標(biāo)準(zhǔn)PSO算法的初始解是隨機生成的，搜索尋優(yōu)的過程也是隨機的，這會浪費粒子群的搜索時間，降低優(yōu)化的效率，同時容易陷入局部最優(yōu)解. 為克服以上缺點，需要對PSO算法的初始化和搜索策略進(jìn)行改進(jìn). 本文提出裝配優(yōu)先關(guān)系矩陣的概念，對裝配序列的初始化進(jìn)行改進(jìn)，同時引入混沌算法來確定線纜的交換位置，改進(jìn)了算法的搜索策略.

3.1 PSO算法的初始化改進(jìn)

3.1.1裝配優(yōu)先關(guān)系矩陣的生成

本文通過引入裝配優(yōu)先關(guān)系矩陣APM(assembly priority matrix，APM)，來改進(jìn)PSO算法的初始化.

裝配優(yōu)先關(guān)系矩陣由一個n維矩陣APM=[aij](1 ≤i,j≤n)表示，其中n為機電產(chǎn)品中線纜的數(shù)量，對APM中的元素aij做如下規(guī)定：

如果aii= 3，則第i支線纜為非跨裝配單元線纜；

如果aii= 2，則第i支線纜為跨裝配單元線纜；

如果aij= 0(i≠j)，則第i支線纜可以優(yōu)先于第j支線纜進(jìn)行裝配；

如果aij= 1(i≠j)，則第i支線纜不可以優(yōu)先于第j支線纜進(jìn)行裝配.

以表2中6支線纜為例，對APM的建立進(jìn)行說明.

表2 線纜裝配優(yōu)先級基本信息

則APM為

3.1.2初始種群生成方法的改進(jìn)

初始種群(即初始的線纜裝配序列)生成方法的改進(jìn)是指根據(jù)上述的APM求解出一些可行的線纜裝配序列作為初始種群，以降低初始化的隨機性與盲目性，提高粒子的搜索效率. 初始種群改進(jìn)算法(IPSO)的流程圖如圖2所示，相應(yīng)步驟如下：

① 遍歷APM，找出符合所有aij=0(i≠j) 的行，加入到集合T1中；

② 遍歷步驟①得到的集合T1，并將集合T1中滿足aii= 3(非跨裝配單元的線纜)的行序號i加入到集合T2中，將滿足aii= 2(跨裝配單元的線纜)的行序號i加入到集合T3中；

③ 若T2非空，則從集合T2中隨機選擇一個元素，例如p，在APM中刪除p行、p列的所有元素，更新APM并將p記錄到線纜裝配序列集合T4中；若T2為空，則從集合T3中隨機選擇一個元素，例如q，在APM中刪除q行、q列的所有元素，更新APM并將q記錄到線纜裝配序列集合T4中；

④ 重復(fù)步驟①到③，直至APM為空；

⑤ 將線纜裝配序列集合T4中元素的順序作為可行的初始化線纜裝配序列.

3.2 PSO算法搜索策略的改進(jìn)

3.2.1混沌算法的引入及作用

PSO算法優(yōu)化成功的關(guān)鍵是具有持續(xù)發(fā)現(xiàn)最優(yōu)解的能力. 標(biāo)準(zhǔn)PSO算法在每一次迭代尋優(yōu)的過程中，粒子通過隨機搜索發(fā)現(xiàn)下一個最優(yōu)解，因此在整個優(yōu)化過程中會產(chǎn)生大量重復(fù)解，浪費了粒子群的搜索時間；如果不能發(fā)現(xiàn)更好的最優(yōu)解，算法就會陷入局部最優(yōu). 為解決粒子搜索過程中的問題，在改進(jìn)PSO算法初始化的基礎(chǔ)上，進(jìn)一步引入混沌算法，以增加粒子個體的多樣性和持續(xù)發(fā)現(xiàn)最優(yōu)解的能力.

3.2.2基于混沌-粒子群算法的線纜裝配序列規(guī)劃

步驟1 確定混沌算法的發(fā)生機制. 選擇下式所示的logistic映射作為混沌發(fā)生機制，其中μ是控制參量，稱為吸引子. 當(dāng)取μ=4且xk?{0,0.25,0.50,0.75,1.00}時，確定性等式表現(xiàn)出混沌動態(tài)性，混沌變量初始值的微小變化會導(dǎo)致長期顯著的變化，混沌變量的軌跡可以遍歷優(yōu)化問題的整個搜索空間.

xk+1=μxk(1-xk),xk∈(0,1).

(9)

步驟3 按照給定的交換概率q交換裝配序列Xi,k中ui,k+1，wi,k+1位置的線纜，得到新的裝配序列Xi,k+1.

4 實例驗證與算法比較

為驗證上述算法的可行性及效率，對算法進(jìn)行了實例測試. 系統(tǒng)的CPU為2.80 GHz Intel Core i5-2300，顯卡為NVIDIA GeForceGT 240，內(nèi)存4 GB，操作系統(tǒng)為Window 7 SP1，利用Matlab與C++的混合編程實現(xiàn)算法集成. 以圖3所示

衛(wèi)星結(jié)構(gòu)板(包含10支多分支線纜，線纜編號如圖所示)為例進(jìn)行計算實例分析，其中結(jié)構(gòu)件與線纜的建模均在CATIA軟件中完成，提取的線纜參數(shù)信息如表3所示.

表3 線纜參數(shù)信息表

由于粒子數(shù)目越多，個體多樣性越明顯且越容易收斂到全局最優(yōu)，為此，分別對PSO、IPSO、C-IPSO算法進(jìn)行不同粒子數(shù)目下的實驗. 算法參數(shù)設(shè)置如下：CNum=10，最大迭代次數(shù)為500，設(shè)定交換概率q=0.8，粒子數(shù)目分別為100，300，500，測試10次取平均值后得到的實驗結(jié)果如表4所示，當(dāng)粒子數(shù)目為500時得到的迭代收斂曲線對比如圖4所示，最終得到的最優(yōu)裝配序列為7-2-10-8-4-3-1-9-5-6，最大適應(yīng)度值為33.6.

表4 實驗結(jié)果對比

從表4的平均值對比中可看出，IPSO和C-IPSO算法的平均值較PSO算法有明顯提升；從收斂速度和搜索到最優(yōu)解的成功率可看出，C-IPSO算法的收斂速度和收斂到全局最優(yōu)的概率明顯優(yōu)于PSO和IPSO算法. 從圖4中可看出，IPSO和C-IPSO算法的初始值明顯高于PSO算法的初始值，且C-IPSO算法的迭代收斂速度要快于IPSO和PSO算法. 因此，C-IPSO算法不僅改進(jìn)了初始化的結(jié)果，同時提升了PSO算法的全局優(yōu)化能力，加快了收斂速度. 從工程應(yīng)用角度來看，C-IPSO算法得到的裝配序列結(jié)果可用于指導(dǎo)并優(yōu)化衛(wèi)星結(jié)構(gòu)板中線纜的裝配工作，具有實際的工程意義.

5 結(jié)束語

針對復(fù)雜機電產(chǎn)品中線纜裝配序列規(guī)劃問題，引入粒子群算法，通過提出APM的概念對標(biāo)準(zhǔn)粒子群算法的初始化加以改進(jìn)，通過引入混沌算法提高算法的搜索效率，并以衛(wèi)星結(jié)構(gòu)板中線纜的敷設(shè)為例進(jìn)行了實例驗證，反映出所提算法的可行性與穩(wěn)定性，為線纜裝配序列的優(yōu)化提供了指導(dǎo). 本文所述研究實現(xiàn)了線纜的裝配序列規(guī)劃，但復(fù)雜機電產(chǎn)品的實際裝配通常是剛性零件與柔性線纜交叉裝配的過程，因此如何確定剛?cè)峄旌系难b配序列將會是后續(xù)研究的重點工作.