基于VPS-PSO算法的裝配序列規(guī)劃方法

劉 冬，張 衛(wèi)，陸寶春

(南京理工大學 機械工程學院，南京 210094)

基于VPS-PSO算法的裝配序列規(guī)劃方法

劉 冬，張 衛(wèi)，陸寶春

(南京理工大學 機械工程學院，南京 210094)

針對裝配序列規(guī)劃問題的特點，提出一種求解裝配序列規(guī)劃問題的變種群策略-粒子群優(yōu)化(Various Population Strategy- Particle Swarm Optimization，VPS-PSO)算法。針對粒子群算法容易陷入局部最優(yōu)的缺點，采用變種群策略，縮短進化停滯時間，提高粒子群算法進化效率，增強算法的尋優(yōu)能力。并結(jié)合裝配幾何可行性、裝配過程連續(xù)性、裝配工具改變次數(shù)3個評價指標構(gòu)建適應度函數(shù)，實現(xiàn)多目標優(yōu)化。以經(jīng)編機成圈傳動機構(gòu)裝配序列規(guī)劃實例驗證VPS-PSO算法比較PSO算法具有更好的全局搜索能力。

裝配序列規(guī)劃；粒子群算法；變種群策略；多目標優(yōu)化

0 引言

產(chǎn)品的裝配序列規(guī)劃(Assembly Sequence Planning，ASP)是裝配過程中的重要環(huán)節(jié)，是在給定產(chǎn)品設計的前提下，基于裝配體中各個零部件之間的幾何和約束關(guān)系，尋找合理的裝配序列，指導實際的產(chǎn)品裝配。裝配序列規(guī)劃是裝配工藝規(guī)劃的核心，然而裝配序列規(guī)劃問題實質(zhì)上是一個NP(Non-deterministic Polynomial，即非確定性多項式)的組合優(yōu)化問題。為此，國內(nèi)外學者對ASP 問題進行了大量的研究，研究方法主要分為兩大類：精確計算方法和啟發(fā)式方法。精確計算方法如樹搜索和圖搜索方法[1-2]，運用割集算法，對零件數(shù)目較少的產(chǎn)品能夠確保得到全局最優(yōu)解；對零件數(shù)目較多的產(chǎn)品，裝配序列數(shù)量與零部件數(shù)量呈現(xiàn)指數(shù)增長，將會出現(xiàn)裝配序列的組合爆炸問題，運用精確計算方法難以解決。將智能啟發(fā)式算法運用到ASP問題中，這類方法主要有遺傳算法[3]、模擬退火算法[4]、神經(jīng)網(wǎng)絡方法[5]和蟻群算法[6]，能夠有效地解決較復雜產(chǎn)品的ASP問題。

粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法[7]也是一種群體智能的優(yōu)化算法，通過對鳥類捕食行為的研究，鳥群通過集體協(xié)作進行尋優(yōu)的啟發(fā)，提出的一種全局優(yōu)化進化算法。最初粒子群算法用于解決連續(xù)優(yōu)化問題，近年來，粒子群算法也被成功地應用到離散性組合優(yōu)化ASP問題中。王敏[8]等將粒子群算法運用到ASP研究中；王豐產(chǎn)[9]等將粒子群算法應用于多工位多目標ASP的求解；于宏[10]等在基本粒子群算法中增加新的學習機制，增強了算法裝配序列的尋優(yōu)能力；劉海江[11]等在基本粒子群算法基礎上將速度進行兩步更新，并驗證方法的可行性。但是由于基本粒子群算法存在早熟收斂的不足，目前運用到ASP研究中的粒子群算法對算法不足改進不多。為克服算法本身易陷入局部收斂的缺陷，引入變種群策略[12](Various Population Strategy，VSP)提出變種群策略-粒子群優(yōu)化(VSP-PSO)算法，豐富種群多樣性，縮短進化停滯狀態(tài)，避免算法陷入局部最優(yōu)，提高搜索效率，改善全局最優(yōu)解的質(zhì)量。通過實例對方法進行驗證，試驗結(jié)果表明該方法能有效提高ASP的全局搜索能力。

1 裝配關(guān)系模型及適應度構(gòu)建

1.1 裝配干涉矩陣

裝配干涉矩陣用于記錄零件之間在裝配路徑上的干涉關(guān)系。干涉信息用于檢查零件之間的干涉情況，也用來檢查裝配方向的變更情況。裝配干涉矩陣MAIM(Assembly Interference Matrix)模型如下：

(1)

式中，MAIM是裝配干涉矩陣；ci，cj是零件i和零件j，n為裝配體零件數(shù)；k是直角坐標系三方向{x,y,z}；ikij是零件ci和零件cj之間的干涉關(guān)系，零件ci和零件cj之間沒有發(fā)生干涉時ikij=0，發(fā)生干涉時ikij=1。設m為一個裝配序列中不能被裝配的零件的數(shù)目，m越小，裝配序列的幾何可行性越好，f1=m。

1.2 裝配連接關(guān)系矩陣

在機械產(chǎn)品的裝配過程中，零件之間的裝配連接關(guān)系是根據(jù)零件在裝配過程中存在的幾何約束和物理約束關(guān)系得到的。裝配連接關(guān)系矩陣MACM(AssemblyConnectionMatrix)模型如下：

(2)

1.3 零件裝配工具集合

在裝配過程中各個零件所需的裝配工具也不盡相同，因此頻繁地更換裝配工具會影響裝配效率。考慮零件裝配工具集合，零件的裝配工具是根據(jù)零件在裝配過程中的實際操作得到的。裝配工具矩陣MATM(Assembly Tool Matrix)模型如下：

cj=1cj=2…cj=n

(3)

式中，MATM是裝配連接關(guān)系矩陣；ci是裝配工具i，cj是零件j，t為工具數(shù)；rij是裝配工具ci和零件cj的使用關(guān)系，當裝配工具ci和零件cj之間沒有使用關(guān)系時，rij=0，否則rij=1。設t為一組裝配序列中裝配工具變化的數(shù)目，t越小，即裝配工具變化的次數(shù)越小，建立裝配工具變化次數(shù)適應度函數(shù)f3=t。

1.4 適應度函數(shù)的構(gòu)建

裝配序列規(guī)劃的評價方法所述包括裝配幾何可行性、裝配過程連續(xù)性、裝配工具改變次數(shù)等多個評價指標,屬于多目標優(yōu)化問題,適應度函數(shù)采用選用權(quán)重系數(shù)法求解確定。

裝配序列規(guī)劃問題的適應度函數(shù)表示為:

F=ω1f1+ω2f2+ω3f3

(4)

式中，f1、f2、f3分別是考慮裝配幾何可行性、裝配過程穩(wěn)定性、裝配工具變化次數(shù)時的目標函數(shù)，ω1、ω2、ω3為權(quán)重系數(shù)。在確定目標函數(shù)各權(quán)重系數(shù)的情況下，針對實例進行序列規(guī)劃得到優(yōu)化后的裝配序列。

2 基于VSP-PSO算法的裝配序列規(guī)劃

2.1 粒子群算法

粒子群算法中每個粒子在D維搜索空間中都有一個位置和速度。每個粒子都會記憶個體的當前和歷史最佳位置，并且粒子i在t時刻的當前最優(yōu)位置用Pi=(Pi1,Pi2,…,Pid,…,PiD)表示，其中d∈{1,2,…,D}，每個粒子都會記憶全局中的最佳位置，在時刻t全局粒子中的歷史最佳位置表示為Pg=(Pg1,Pg2,…,Pgd,…,PgD)。在搜索過程中，每個粒子i根據(jù)速度更新方程和位置更新方程來調(diào)整自己的速度和位置。粒子i的速度更新方程：

(5)

粒子i的位置更新方程：

(6)

2.2 粒子群算法的改進

由于每個粒子在多維度空間里根據(jù)其個體最優(yōu)和群體全局最優(yōu)更新其速度和位置。從表面上看,這種方式對于快速搜尋最優(yōu)解很有幫助,經(jīng)過多次實驗發(fā)現(xiàn),算法在進化初期很快收斂到一個全局最優(yōu)值。然而隨著進化代數(shù)的增加，種群中各粒子趨于相同，幾乎沒有進化。如果此時的全局最優(yōu)是一個局部極值，則整個粒子群便陷入局部最優(yōu)，進化一直處于停滯狀態(tài)，進化效率大幅下降，很難跳出這個暫時的全局最優(yōu)去發(fā)現(xiàn)實際的全局最優(yōu)解。這是由兩個因素引起的：①當其本身的適應度值已經(jīng)很優(yōu)時，比其適應度值更優(yōu)的個體在搜索空間分布較少，所以難以搜索到適應度更優(yōu)的個體；②PSO算法在進化過程中種群各粒子趨于相同，種群中的粒子多樣性減弱，搜索效率降低。

因素①是由搜索空間的特性決定的。對于因素②，通過采用變種群策略，替換現(xiàn)有的部分個體來提高種群的多樣性，從而縮短PSO算法的進化停滯時間，提高尋優(yōu)效率。

為了解決跳出局部最優(yōu)的缺陷，避免陷入早熟狀態(tài)的可能性，縮短進行停滯狀態(tài)，得到更好的全局最優(yōu)解。因此，引入變種群策略VPS(VariousPopulationStrategy)，提出了一種可以使進化跳出局部最優(yōu)的VSP-PSO算法。當進化多代后群體進化緩慢乃至停滯時，在當前群體中加入一定數(shù)量的隨機個體替換部分個體，可以增強群體的多樣性。盡管注入的個體適應度可能較低,多數(shù)會在進化過程中被淘汰,但是通過進化,替換的新個體和原群體中的優(yōu)勢個體進行組合,會提高生成更優(yōu)個體的概率。

2.3 算法的實現(xiàn)步驟

(1)設定參數(shù)

設定的種群規(guī)模P，迭代的最大次數(shù)T，最大進化停滯次數(shù)G，矩陣MAIM，MACM，MATM，慣性權(quán)重ω，學習因子c1和c2，VSP的因子ν，權(quán)重系數(shù)w1，w2，w3，進化更新停滯代數(shù)g=0，初始迭代次數(shù)t=1。

(2)初始化粒子種群

初始化t=t+1時刻粒子種群在D維空間的隨機位置Xi和速度Vi。

(3)計算適應度函數(shù)值

評估t時刻每個粒子的適應度值Fi(t)，找到粒子群中適應度函數(shù)F的最小值，并找到在t時刻的Pi和Pg。

(4)通過公式(5)更新每個粒子的速度Vi(t+1)。

(5)通過公式(6)更新每個粒子的位置Xi(t+1),完成粒子群更新。

(6)檢查進化相鄰兩代適應度值是否一致。如果minF(t+1)=minF(t)，則轉(zhuǎn)向步驟(7)；否則轉(zhuǎn)向步驟(8)。

(7)計算進化更新停滯代數(shù)g=g+1。

(8) 進化更新停滯代數(shù)置零g=0。

(9)檢查進化更新停滯代數(shù)。如果g≥G，則轉(zhuǎn)向步驟(10)；否則轉(zhuǎn)向步驟(12)。

(10)進行變種群策略操作，產(chǎn)生新的種群ν·N個隨機粒子。

(11)替換現(xiàn)有種群中ν·N個粒子。

(12)檢查進化終止條件。如果t

(13)輸出最優(yōu)序列并對方案進行解釋。

變種群策略粒子群優(yōu)化(VSP-PSO)算法流程圖見圖1所示。

圖1 VPS-PSO算法流程圖

3 實例應用及分析

為了驗證方法的有效性，本文采用Matlab2011a軟件編程實現(xiàn)基本PSO算法和VSP-PSO算法，并以典型經(jīng)編機成圈傳動機構(gòu)為實例進行測試和驗證。以經(jīng)編機成圈傳動機構(gòu)為例，成圈傳動機構(gòu)由三拐曲軸驅(qū)動，選取一組曲軸連桿作為研究對象進行分析。成圈傳動機構(gòu)主要由15個零件組成，如圖2所示。

(a)裝配圖 (b)爆炸圖圖2 經(jīng)編機成圈傳動機構(gòu)

設置種群規(guī)模為P=50，迭代次數(shù)T=1000，最大進化停滯次數(shù)G=50，矩陣MAIM，MACM，MATM，VSP的因子ν=0.2，設定慣性權(quán)重ω=0.3，定義權(quán)重系數(shù)w1=0.4，w2=0.3，w3=0.3，學習因子c1=1，c2=3。利用計算機分別對基本PSO算法和VSP-PSO算法進行測試，得到算法的最優(yōu)裝配序列及其適應度函數(shù)值。PSO算法和VSP-PSO算法求解裝配序列結(jié)果圖3、圖4所示。

圖3 PSO算法平均適應度值和各代最優(yōu)解

圖4 VSP-PSO算法平均適應度值和各代最優(yōu)解

表1給出了兩者進行10次仿真運算求解的結(jié)果對比?？梢钥闯?，與PSO算法相比，采用VSP-PSO算法對裝配序列進行求解，適應度函數(shù)值減少了5.2%，裝配幾何可行性、過程連續(xù)性、工具變化次數(shù)都有所降低，在尋優(yōu)能力上有了較大的改善。相比PSO方法而言，VSP-PSO算法基于PSO算法搜索的最優(yōu)解的基礎上還能夠繼續(xù)進行全局最優(yōu)搜索，得到比PSO算法更優(yōu)的解，且得到的解在各目標函數(shù)指標更優(yōu)，更符合實際裝配工藝的要求。經(jīng)過10次計算仿真的結(jié)果中，采用VSP-PSO算法得到最優(yōu)的適應度函數(shù)值為23.4，經(jīng)過裝配序列優(yōu)化后的該部件的最優(yōu)裝配序列如下:3-2-4-6-5-10-9-11-12-14-1-7-13-8-15，符合實際裝配要求。

表1 PSO算法和VSP-PSO算法優(yōu)化結(jié)果對比

4 結(jié)論

本文根據(jù)裝配序列規(guī)劃問題的特點，在粒子群算法的基礎上，引入變種群策略，提出了一種VSP-PSO算法的裝配序列規(guī)劃求解方法。由于該算法既保留了PSO算法的搜索操作，又具有跳出局部最優(yōu)的能力，使其可以在進化停滯狀態(tài)時及時增加種群多樣性，避免了算法陷入局部最優(yōu)，有效地提高了尋優(yōu)能力。實踐

證明，該方法相比于PSO算法能更有效快速地搜索到全局最優(yōu)的裝配序列，是一種有效的解決復雜產(chǎn)品裝配序列規(guī)劃方法。

[1] De Mello L S H，Sanderson A C. A correct and complete algorithm for the generation of mechanical assembly sequences [J]. IEEE Transaction on Robot Automation， 1991，7(2):228-240.

[2] Chen R S，Lu K Y， Tai P H. Optimization of assembly plan through a three-stage integrated approach[J]. International Journal of Computer Applications in Technology， 2004，19(1):28-38.

[3] Marian R M， Lee HS， Abhary K. Agenetic algorithm for the optimization of assembly sequences [J]. Computers & Industrial Engineering， 2006，50(4):503-527.

[4] ANWAR S M. Multi criteria assembly sequencing[J]. Computers & Industrial Engineering，1997，32(4)：743-751.

[5] Chen WC，Tai PH， Deng WJ， et al. A three-stage integrated approach for assembly sequence planning using neural networks. Expert Syst Appl， 2008， 34:1777-1786.

[6] Wang J F， Liu J H， Zhong Y F. A novel ant colony algorithm for assembly sequence planning [J].Advanced Manufacturing Technology， 2005，25(11):1137-1143.

[7] Kennedy J， Eberhart R C. Particle swarm optimization[C] Proceedings of IEEE International Conference on Neural Networks. Perth: IEEE， 1995:1942-1948.

[8] 王敏，葉碧蓮. 基于粒子群算法的裝配規(guī)劃研究[J].軍民兩用技術(shù)與產(chǎn)品， 2008(1):44-45.

[9] 王豐產(chǎn)，孫有朝，李娜. 多工位裝配序列粒子群優(yōu)化算法[J].機械工程學報，2012，48(9) : 155-162.

[10] 于宏，王成恩，于嘉鵬，等.基于粒子群算法的復雜產(chǎn)品裝配序列規(guī)劃[J]. 東北大學學報(自然科學版) ，2010,31(2):261-264.

[11] 劉海江，李玲玉，張含葉.基于改進粒子群算法的鋰電池模塊裝配序列規(guī)劃[J].中國工程機械學報，2014,12(4):306-312,376.

[12] 胡建軍，唐常杰，彭京，等. 快速跳出局部最優(yōu)的VPS-GEP算法[J]. 四川大學學報(工程科學版) ，2007,39(1):128-133.

(編輯 李秀敏)

Assembly Sequence Planning Based on Various Population Strategy-Particle Swarm Optimization Algorithm

LIU Dong，ZHANG Wei，LU Bao-chun

(School of Mechanical Engineering, Nanjing University of Science and Technology, Nanjing 210094, China)

Aiming at the problem of assembly sequence planning, the Various Population Strategy- Particle Swarm Optimization (VSP-PSO) algorithm which is applied to solve the problem of the assembly sequence planning. To rise above the deficiency that PSO algorithm is easy to fall into local optimization, using the various population strategy, which is taken up to improve the optimizability of PSO algorithm to shorten the stagnancy of time in evolution, and enhance the ability of the algorithm optimization. Realizing the multi-objective optimization by designing the objective function based on the geometrical feasibility, the process continuity and assembly tools change times. An exemplification as the loop-forming transmission mechanism assembly application of the warp knitting machine demonstrates that global searching ability of VSP-PSO algorithm is more efficient compared with PSO algorithm.

assembly sequence planning; particles swarm optimization; various population strategy; multi-objective optimization

1001-2265(2017)02-0030-04

10.13462/j.cnki.mmtamt.2017.02.008

2016-04-21；

2016-05-18

劉冬(1992—)，男，吉林長嶺人，南京理工大學碩士研究生，研究方向為CAD/CAE，(E-mail)andylau_dong@126.com。

TH162;TG506

A