基于粒子群優(yōu)化算法的裝配序列規(guī)劃研究

陳大亨，張 彪，宮 華

(沈陽理工大學(xué) 理學(xué)院，沈陽 110159)

?

基于粒子群優(yōu)化算法的裝配序列規(guī)劃研究

陳大亨，張 彪，宮 華

(沈陽理工大學(xué) 理學(xué)院，沈陽 110159)

針對裝備制造業(yè)中存在的裝配序列規(guī)劃問題，建立最小化裝配次數(shù)和方向改變次數(shù)之和為目標(biāo)的優(yōu)化模型。針對優(yōu)化模型提出具有隨機性特點的初始種群啟發(fā)式編碼，設(shè)計粒子群算法。為避免粒子陷入局部最優(yōu)，采用不同程度的局部搜索操作方式，達(dá)到增強粒子群算法局部搜索的能力。實例驗證表明，該算法在解決裝配序列規(guī)劃問題上具有優(yōu)勢，求解效果較好。

裝配序列規(guī)劃；粒子群算法；局部搜索

裝配序列規(guī)劃(Assembly Sequence Planning,ASP)問題是裝備制造企業(yè)的一個重要研究課題，是整個產(chǎn)品周期的一個重要的基礎(chǔ)環(huán)節(jié)。產(chǎn)品的裝配過程占產(chǎn)品全部生產(chǎn)環(huán)節(jié)的20%～70%的時間和費用。合理的裝配序列能夠減少產(chǎn)品的裝配時間，降低產(chǎn)品整體的生產(chǎn)費用，提高企業(yè)競爭力。在一些裝備制造企業(yè)，特別是軍工等特殊行業(yè)的制造企業(yè)，裝配序列的產(chǎn)生很大程度上還是依賴人工經(jīng)驗，由于人工經(jīng)驗的有限，得出的裝配序列并非最優(yōu)序列，因此利用先進(jìn)的智能計算方法產(chǎn)生優(yōu)化的裝配序列將會為這些企業(yè)的生產(chǎn)節(jié)省成本。

裝配序列指產(chǎn)品各零件的裝配順序和裝配方向的排序，是典型的難解組合優(yōu)化問題。一方面大量學(xué)者基于幾何約束分析解決裝配序列產(chǎn)品規(guī)劃問題。Su[1]系統(tǒng)地提出一種幾何約束分析方法用于產(chǎn)生最優(yōu)的裝配序列。Mello 等[2]提出一種幾何約束割集算法產(chǎn)生待裝配產(chǎn)品的所有裝配序列。Hsu 等[3]基于知識分析設(shè)計近優(yōu)的啟發(fā)式裝配序列。另一方面基于智能優(yōu)化算法解決裝配序列規(guī)劃問題得到廣泛的關(guān)注。Tseng 等[4]提出遺傳算法(GA)解決裝配序列規(guī)劃問題。王珍等[5]研究了基于蟻群算法的引信產(chǎn)品的裝配序列規(guī)劃問題。Sinanoglu[6]利用人工神經(jīng)網(wǎng)絡(luò)開發(fā)出機械零件裝配序列規(guī)劃系統(tǒng)。Lv 等[7]使用離散粒子群算法解決ASP問題。Zhang等[8]將免疫算法和粒子群算法進(jìn)行結(jié)合解決ASP問題。Somayé等[9]基于近優(yōu)解在解空間呈現(xiàn)近似的均勻分布的性質(zhì)，設(shè)計跳出局部搜索(BLS)算法，該算法具有很強的鄰域搜索能力。

結(jié)合文獻(xiàn)[9]的工作，本文以產(chǎn)品各零件之間的干涉關(guān)系作為幾何約束，以最大化滿足幾何約束次數(shù)和最小化裝配方向改變次數(shù)為目標(biāo)，建立產(chǎn)品裝配序列規(guī)劃模型。提出帶有隨機性的啟發(fā)式算法產(chǎn)生初始種群，設(shè)計粒子群算法，采用局部搜索操作提高算法跳出局部最優(yōu)的能力。本文所提出的算法不僅具有較高收斂速度，同時避免陷入局部最優(yōu)。通過實例驗證，并與現(xiàn)有算法進(jìn)行比較，驗證了該算法的有效性。

1 問題描述

ASP問題假設(shè)如下：裝配體的各零件均為不可形變零件，即不可通過形變改變幾何約束；結(jié)合實際裝配操作，將裝配方向設(shè)定為±X,±Y,±Z；各零件不可重復(fù)裝配，一次操作只能裝配一個零件。

1.1 符號說明

N：組成一個機械產(chǎn)品的零件個數(shù)；pi：產(chǎn)品的第i個零件，i=1,2,…,N；di：第i個零件的裝配方向，di∈{±x,±y,±z},i=1,2,…,N。為描述裝配序列，采用一種典型的編碼方式予以表示：Xi為第i個裝配序列，Xi=[xi1,xi2,…,xij,…,xiN]，其中xij=(pij,dij)，pij代表第i個裝配序列的第j個零件，dij代表這個零件的裝配方向，dij∈{±x,y,z}。

1.2 幾何約束

采用干涉矩陣表示描述產(chǎn)品在所有裝配方向上的幾何約束，即第i個零件pi在任意裝配方向上對其他零件是否存在干涉。干涉矩陣通常根據(jù)±X、±Y、±Z方向建立，假設(shè)共有N個零件，則干涉矩陣可表示如下：

式中k表示裝配方向，k∈{±x,y,z}。

需要注意的是，Iiik=0，因為零件對自身不造成干涉。

為得到第i個裝配的零件及其裝配方向，假設(shè)已得到有m個零件的子裝配體Xsub=[p1,p2,…,pm],第i個零件pi能否順利裝配取決于Iik的值，k∈±x,y,z。Iik定義如下：

Iik的值由如下公式計算：

Iik=Ii1k∨Ii2k∨…∨Iimk，其中∨為布爾操作“或”。

1.3 目標(biāo)函數(shù)

2 算法描述

2.1 基本粒子群算法

(1)

(2)

式中：w為慣性權(quán)重；c1和c2為學(xué)習(xí)因子；r1和r2為[0,1]之間均勻分布的隨機數(shù)。根據(jù)迭代次數(shù)線性變化的慣性權(quán)重為

w=wmax-(t×(wmax-wmin))/Dmax

(3)

式中：ωmax為慣性權(quán)重最大值0.9；ωmin為慣性權(quán)重最小值0.1；Dmax表示PSO算法的最大迭代次數(shù)。

2.2 初始化粒子種群

本文提出一種兼具啟發(fā)性和隨機性的產(chǎn)生初始解方法，以減少無效搜索的可能。該方法細(xì)致描述如下所示：

步驟1：輸入各裝配方向的干涉矩陣IMk，通過對各矩陣求和得到干涉矩陣DIM；

步驟2：隨機選擇第一個零件的裝配方向d1，之后選擇在該方向具有與其他零件最少干涉次數(shù)的零件作為第一個零件p1；

步驟3：產(chǎn)生1-N的隨機整數(shù)(代表零件編號)，依次作為裝配序列的第2-N個零件，當(dāng)產(chǎn)生和p1相等的編號，順延一位；

步驟4：隨機產(chǎn)生第2-N個零件的裝配方向d2至dn；

步驟5：重復(fù)步驟1～4，直到為初始種群中所有粒子賦值。

2.3 局部搜索策略

基本粒子群算法容易陷入局部最優(yōu)，影響算法尋找全局最優(yōu)解的能力。對于ASP問題，Somayé和Ellips研究成果表明，多個局部最優(yōu)解近似均勻的分布在解空間中。利用粒子群算法的快速尋優(yōu)能力，增強其局部搜索能力，將會是一種行之有效的求解ASP 問題的方法。本文根據(jù)該問題解的形式，設(shè)計出四種可增強局部搜索能力的操作：(1)在當(dāng)前裝配序列中隨機選擇一個零件

并隨機改變其裝配方向；(2)在當(dāng)前裝配序列中隨機選擇兩個零件，并交換其裝配次序和方向，并將這兩個零件之間的所有其他零件顛倒次序；(3)在當(dāng)前裝配序列中隨機選擇一個零件，隨機將其插入序列其他位置，后續(xù)零件依次后移一位。

在算法搜索過程中，規(guī)定當(dāng)某一粒子的函數(shù)值連續(xù)Imax代沒有更新，即認(rèn)為該粒子陷入局部最優(yōu)。將從上述(1)～(3)局部搜索操作中選擇，若粒子陷入局部最優(yōu)的代數(shù)越大，需選擇強度更大的操作進(jìn)行影響。該算法流程如圖1所示。

圖1 帶有深度鄰域搜索策略的粒子群算法流程圖

3 實例驗證

通過實例驗證本文所提出的算法。圖2是一個典型的機械產(chǎn)品的零件框圖。

圖2 產(chǎn)品結(jié)構(gòu)方框圖

本文所提出的算法參數(shù)如下：學(xué)習(xí)因子c1=c2=2。粒子種群規(guī)模K=40，最大迭代次數(shù)Dmax=200。采用C語言編程，以2.0GRAM，2.20GHzCPU的計算機為平臺進(jìn)行實驗。將求解結(jié)果與其他算法求得結(jié)果進(jìn)行比較，如表1所示。

表1 本文算法與其他算法結(jié)果對比

求解過程收斂圖如圖3所示。

圖3 本文算法求解過程收斂圖

本文提出的粒子群算法在迭代200次的情況下可以得到最優(yōu)解。該序列裝配方向改變次數(shù)為0次，裝配過程滿足幾何約束11次，即每個零件的裝配操作都不對其他零件產(chǎn)生干涉。運行30次，除有1次得到函數(shù)值為109的序列外，其余都可產(chǎn)生函數(shù)值為110的序列，表明該算法的穩(wěn)定性較好。與其他算法比較可以看出，該算法與Somayé 等提出的BLS算法在迭代100次的情況下具有相同的實驗效果，好于遺傳算法(GA)的求解結(jié)果。本文算法在84代已經(jīng)產(chǎn)生最優(yōu)解，具有較快收斂速率，程序運行時間為1.2s。粒子群算法本身具有的編碼簡單，易于操作等特點，使得所提出的算法在解決ASP問題上仍具有很大的優(yōu)勢。

4 結(jié)束語

裝配序列規(guī)劃問題對于裝備制造行業(yè)提高產(chǎn)品的裝配質(zhì)量和裝配效率具有重要意義，通過優(yōu)化裝配序列達(dá)到減少產(chǎn)品裝配時間和費用，進(jìn)而縮短生產(chǎn)制造周期，提高企業(yè)競爭力。本文以產(chǎn)品各零件之間的干涉關(guān)系作為幾何約束，以最大化滿足幾何約束次數(shù)和最小化裝配方向改變次數(shù)為目標(biāo)，建立產(chǎn)品裝配序列規(guī)劃模型。根據(jù)對現(xiàn)有求解方法的對比，提出具有隨機性要求的初始解隨機產(chǎn)生方法，并提出局部搜索操作方式的粒子群算法，增強算法的局部搜索能力。通過實例驗證，與現(xiàn)有的算法進(jìn)行比較，得到的最優(yōu)裝配序列質(zhì)量較高，算法穩(wěn)定性較好，收斂速度較快。在不同企業(yè)的實際裝配過程中，產(chǎn)品具有很強的多樣性，零件的數(shù)量可能很大，存在可形變的零件等問題也較為常見。對于此類產(chǎn)品的裝配序列規(guī)劃問題是今后的研究方向。

[1]Su Q.Computer aided geometric feasible assembly sequence planning and optimizing[J].International Journal of Advanced Manufacturing Technology,2007,33(1-2):48-58.

[2]Mello H D,Sanderson A C.A correct and complete algorithm for the generation of mechanical assembly sequences[J].IEEE Trans Robot Automation,1991(2):228-240.

[3]Hsu Y Y,Tai P H,Wang M W,et al.A knowledge-based engineering system for assembly sequence planning[J].International Journal of Advanced Manufacturing Technology,2011,55(5-8):763-782.

[4]Tseng H E,Li J D,Chang Y H.Connector-based approach to assembly planning using a genetic algorithm[J].International Journal of Production Research,2004,42(11):2243-2261.

[5]王珍，陳芳，張杰.基于蟻群算法的引信裝配序列優(yōu)化[J].探測與控制學(xué)報,2014,36(3):42-46.

[6]Sinanoglu C.Design of an artificial neural network for assembly sequence planning system[J].International Journal of Industrial Engineering,2008,15(1):92-103.[7]Lv H G,Lu C.An assembly sequence planning approach with a discrete particle swarm optimization algorithm[J].International Journal of Advanced Manufacturing Technology,2010,50(5/8):761-770.

[8]Zhang H Y,Liu H J,Li L Y.Research on a kind of assembly sequence planning based on immune algorithm and particle swarm optimization algorithm[J].The International Journal of Advanced Manufacturing Technology,2014,71(5/8):795-808.

[9]Somayé G,Ellips M.A breakout local search(BLS)method for solving the assembly sequence planning problem[J].Engineering Applications of Artificial Intelligence,2015(39):245-266.

[10]Kennedy J,Eberhart R C.Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks.Perth,Australia,1995:1942-1948.

(責(zé)任編輯：馬金發(fā))

Assembly Sequence Planning Based on a Particle Swarm Optimization Algorithm

CHEN Daheng,ZHANG Biao，GONG Hua

(Shenyang Ligong University,Shenyang 110159,China)

For the assembly sequence planning(ASP)problem in equipment manufacturing industry,an optimization model is established in order to maximize the assembly operation times and minimize the times of changing assembly direction.A particle swarm optimization algorithm is designed to solve ASP problem where the initial swarm is generated by a heuristic method with randomness characteristic.The different methods of local search operations are selected so that the particles cannot fall into local optimization and improve the ability of local search.The experimental results show that the algorithm proposed in this paper is efficient in solving ASP problem,and it has better solving effect.

assembly sequence planning;particle swarm optimization algorithm;local search

2015-07-13

國家自然科學(xué)基金資助項目(71101097)；遼寧省“百千萬人才工程”培養(yǎng)資助項目(2014921043)

陳大亨(1973—)，男，工程師；通訊作者：宮華(1976—)，女，教授，博士，研究方向：組合優(yōu)化、生產(chǎn)調(diào)度。

1003-1251(2016)04-0038-04

O224

A