改進粒子群算法的裝配序列規(guī)劃方法

于 宏，水 麗

(沈陽理工大學 機械工程學院，遼寧 沈陽 110159)

改進粒子群算法的裝配序列規(guī)劃方法

于 宏，水 麗

(沈陽理工大學 機械工程學院，遼寧 沈陽 110159)

針對裝配序列規(guī)劃問題的特點，重新定義應用于連續(xù)空間優(yōu)化的粒子群算法的各種相關操作，并對粒子群算法的更新公式及粒子優(yōu)化進行改進，提出面向裝配序列規(guī)劃問題的改進型離散粒子群算法。構建鄰接矩陣、干涉矩陣和支撐矩陣，描述零部件之間的裝配關系。建立包括可行性、重定向性、穩(wěn)定性、連續(xù)性和聚合性為評價指標的適應函數(shù)，實現(xiàn)多目標優(yōu)化。以安全閥裝配序列規(guī)劃實例驗證了改進粒子群裝配序列優(yōu)化算法的有效性。

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

裝配是裝備制造業(yè)的重要環(huán)節(jié)，是裝備研制的重要方面，其結果直接關系到產(chǎn)品質量、性能、壽命和可維護性。裝配在復雜產(chǎn)品的制造成本和生產(chǎn)周期中所占的比例日益增大[1]，因此，裝配規(guī)劃在產(chǎn)品設計開發(fā)過程中具有非常重要的地位。裝配序列規(guī)劃是裝配規(guī)劃的核心，裝配序列的優(yōu)劣直接影響裝配資源配置、裝配線設計、裝配成本、裝配質量和裝配效率。

目前，國內外的學者對裝配序列規(guī)劃進行了大量的研究，現(xiàn)有的裝配序列規(guī)劃方法主要分為兩大類：精確計算方法和啟發(fā)式方法。精確計算方法如樹搜索或圖搜索方法[2-3]，通常采用割集算法，能確保全局最優(yōu)解的產(chǎn)生；然而對零件數(shù)目較多的復雜產(chǎn)品，將會出現(xiàn)裝配序列組合爆炸問題，使該方法求解難度增大，很難得到理想結果。近20 年來廣大研究者開始將現(xiàn)代智能優(yōu)化計算方法應用到裝配序列規(guī)劃領域中來，如人工神經(jīng)網(wǎng)絡方法[4]、模擬退火算法[5]、遺傳算法[6]、蟻群算法[7]、和螢火蟲算法[8]等，為復雜產(chǎn)品的裝配序列求解提供了強有力的方法。

與上述智能優(yōu)化算法相類似，粒子群優(yōu)化算法(particle swarm optimization,PSO)也是一種基于群體智能的優(yōu)化算法。該算法是Kennedy等[9]受鳥群捕食行為的啟發(fā)于1995年提出的。最初粒子群算法用于解決連續(xù)優(yōu)化問題，在函數(shù)優(yōu)化和其他連續(xù)性問題中得到廣泛應用。近年來，粒子群算法也被成功地應用到離散性組合優(yōu)化問題中，如旅行商和各種調度問題。但是對裝配序列規(guī)劃問題，PSO算法應用較少[10]，且在算法的實現(xiàn)上，都采用標準的粒子群算法流程。鑒于此，本文針對裝配序列規(guī)劃問題對粒子群算法進行改進，提高搜索效率，避免算法快速收斂局部最優(yōu)，改善最優(yōu)解的質量。

1 裝配關系模型

使用智能優(yōu)化算法求解裝配序列，需采用合適的形式表示裝配模型中各零部件之間的裝配關系，建立裝配關系矩陣是常用的表示方法。本文采用了鄰接矩陣、干涉矩陣和支撐矩陣表達零件之間的約束關系。當需要建立零件與子裝配體的關系矩陣時，可通過矩陣合并操作，生成相應的收縮矩陣。

1.1 鄰接矩陣

設裝配體P由N個零件組成，P={p1,p2,…,pN},零部件之間的鄰接矩陣用CM來表示：CM=[cij]N×N。其中元素cij表示零件pi和零件pj之間的連接關系，為詳細表達連接信息，可將硬連接的不同連接類型定義到表達式中。cij的定義如下：

當cij≥2時為硬連接；cij=為3時，代表螺紋連接；cij=4代表鍵連接；cij=5代表銷連接；cij=6代表鉚接；cij=7代表為焊接。

1.2 干涉矩陣

干涉矩陣描述零件沿某一方向移動到無窮遠的過程中，與其他零件碰撞干涉的情況。零件之間的干涉關系用矩陣IMk=[Ikij]N×N來表示。

其中k為直角坐標系中坐標軸方向，k=+X,+Y,+Z；i,j∈{1，2,…,N}；Ikij表示主動零件pi沿k方向運動時與被動零件pj之間的碰撞干涉情況，Ikij定義如下：

由于零件pi沿正k方向移動與零件pj的碰撞干涉情況和零件pj沿k的負方向移動與零件pi的碰撞干涉情況相同，即Ikij=I-kij，因此只需三個方向的干涉矩陣即可表示坐標系中六個方向的零件間干涉情況。

1.3 支撐矩陣

1.4 收縮矩陣

以上矩陣中的各元素表示的是零件與零件之間的相互關系。而在進行裝配序列規(guī)劃時，為降低計算復雜度，裝配體中的零件通常被組合成若干個子裝配體，每個子裝配體作為一個整體被視為一個零件參與規(guī)劃。這時需要將僅包含零件信息的鄰接、干涉和支撐矩陣轉化成包含零件及子裝配體信息的各相關矩陣。轉化的過程是對原始的鄰接、干涉和支撐矩陣中組成子裝配體的相關零件所對應的行元素和列元素進行抽取、合并，從而形成一個新的矩陣，該矩陣稱為收縮矩陣。

2 改進型離散粒子群算法模型

2.1 適應度函數(shù)的構造

在裝配序列規(guī)劃領域，最優(yōu)的裝配序列應是裝配困難度最低、裝配效率最高、裝配成本最低的可行序列。因此評價一個裝配序列應該從兩個方面入手，即裝配可行性和裝配序列優(yōu)劣性。為達到此目標，需要考慮的優(yōu)化標準很多。本文主要考慮對產(chǎn)品裝配影響較大的幾個因素，以裝配可行性、裝配重定向性、裝配體的穩(wěn)定性、裝配的聚合性和裝配連續(xù)性為評價指標，構造目標函數(shù)。將幾何可行性、重定向性、裝配穩(wěn)定性、裝配聚合性和裝配連續(xù)性評價指標進行加權求和即可確定裝配序列的適應函數(shù)，如式(1)所示。

(1)

式中：N為組成裝配體的零部件數(shù)目；nf為不滿足幾何可行性的零件數(shù)目；nd為裝配方向改變次數(shù)；ns為裝配不穩(wěn)定的零件數(shù)目；nt為裝配工具的改變次數(shù)；nc為反映裝配連續(xù)性的目標值；w1、w2、w3和w4分別為裝配方向改變、裝配穩(wěn)定性、裝配聚合性和裝配連續(xù)性的權重系數(shù)，0≤w1,w2,w3,w4≤1，且w1+w2+w3+w4=1。w1、w2、w3和w4由公式(2)計算獲得。

(2)

式中，n為評價標準的數(shù)目，這里n=4；k為評價標準的重要性排名。

2.2 標準粒子群算法的離散化

由于標準粒子群算法不適用于裝配序列規(guī)劃問題的求解，本文提出了離散粒子群算法用于裝配序列規(guī)劃問題的求解，重新構造粒子位置、速度及其運算公式如下：

定義1 粒子的位置。將組成裝配體的所有零部件的有序排列，作為粒子的位置。第i個粒子的位置矢量表示為Xi=(xi1,xi2,…,xij,…,xiN)，其中xij∈{1，2,…,N}為零件的編號，并且如果j≠k，xij≠xik。

定義2 粒子的速度。用于改變粒子的位置，在此定義為對粒子位置的一種變換，即調整零部件排列順序的一種變換序。第i個粒子的速度矢量表示為Vi=(vi1,vi2,…,vij,…,viN)，其中vij∈{0,1，2,…,N}。

定義3 位置與速度的加法。設一粒子的位置和速度分別為X1=(x11,x12,…,x1N)和V1=(v11,v12,…,v1N)，定義X1與V1的加法為X1⊕V1=X2,X2為新位置。該位置矢量的求取方法如下：

fori=1 toN

ifvi1=0，位置矢量不變

else 交換X1中的零件編號v1i和v1j。

定義4 位置間的減法。兩個位置相減的結果是一個速度，設X1=(x11,x12,…,x1N)，X2=(x21,x22,…,x2N)，則定義X2ΘX1=V,其中V=(v1,v2,…,vN)為新速度。V按以下方式確定：如果x1i=x2i，vi=0；否則vi=x2i。

定義5 速度的數(shù)乘。設粒子的速度V1=(v11,v12,…,v1N)和系數(shù)c，c∈[0,1]，定義速度與系數(shù)的乘法為：c?V1=V2,V2=(v21,v22,…,v2N)，V2的確定方法為

(3)

式中r是一個0到1之間均勻分布的隨機數(shù)。

定義6 速度的加法。兩個速度相加的結果是一個新速度，設兩個速度分別為V1=(v11,v12,…,v1N)與V2=(v21,v22,…,v2N)，定義二者的加法為：V1⊕V2=V3。V3=(v31,v32,…,v3N)，V3的確定方法為

(4)

2.3 離散粒子群算法的改進

本文提出的改進型離散粒子群算法主要對標準型螢火蟲算法的粒子速度和位置的更新公式進行改進，并增加粒子修復的操作。

2.3.1 混合優(yōu)化模型

通過以上對粒子位置和速度以及相關操作的特殊定義，采用PSO全局模型和局部模型的混合優(yōu)化模型，給出求解裝配序列規(guī)劃問題的離散粒子群優(yōu)化操作下粒子速度和位置的更新公式。

(5)

(6)

粒子位置的更新公式如式(7)所示。

(7)

全局和局部混合模型的執(zhí)行過程如下：設t為當前迭代次數(shù)，tmax為算法的最大迭代次數(shù)，Gt為一個變量，且Gt=t/tmax，rand是隨機產(chǎn)生的一個0到1之間均勻分布的隨機數(shù)；如果 rand>Gt，粒子的速度更新公式選用局部模型，按公式(5)計算，否則采用全局模型按公式(6)進行更新。

2.3.2 粒子的修復操作

裝配體中零件通常分為功能件和連接件兩類，大部分功能件是通過連接件進行連接，被連接的功能件和連接件之間都存在固定的裝配順序，這種固定的裝配順序隱含著最基本、最重要的優(yōu)先關系。通過對功能件和不同類型連接件之間固定裝配順序的整理，建立基于連接件的優(yōu)先及緊鄰關系。

粒子的修復是指將初始群體和每次更新后產(chǎn)生的新粒子中違反優(yōu)先及緊鄰關系的粒子"修復"為符合優(yōu)先及緊鄰關系的合理、有效粒子，從而使粒子沿著好的方向搜索，提高搜索效率，且避免過早地收斂，使得最終結果的各項評價指標更優(yōu)。

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

輸入量：裝配體零件列表；三個直角坐標軸方向的干涉矩陣；裝配體的鄰接矩陣；支撐矩陣；最大迭代次數(shù)tmax，各優(yōu)化指標(裝配方向改變、穩(wěn)定性、聚合性、連接性)的權重，最大和最小慣性權重wmax、wmin，學習因子c1、c2。

步驟 1：根據(jù)裝配體的連接關系和定義的規(guī)則，自動提取優(yōu)先及緊鄰關系；

步驟2：根據(jù)零部件質量、體積和鄰接關系矩陣，計算確定裝配序列的初始件；

步驟3：隨機產(chǎn)生初始群體的位置和速度，設當前迭代次數(shù)t=1；

步驟4：根據(jù)優(yōu)先及緊鄰關系修復種群中所有粒子的位置；

步驟5：根據(jù)公式(1)計算每個粒子的適應值，并確定個體最優(yōu)值Pi和全局最優(yōu)值Pg；

步驟6：計算Gt，產(chǎn)生一個隨機數(shù)rand，rand∈[0,1]；

步驟7：如果rand>Gt，按公式(5)和公式(7)更新粒子的速度和位置；否則，按公式(6)和公式(7)更新粒子的速度和位置；

步驟8：如果t≥tmax，轉到步驟9，否則t=t+1，轉到步驟4；

步驟9：輸出求得的最優(yōu)序列Pg，繪制收斂曲線。

3 應用實例

為驗證算法的有效性，采用C#語言實現(xiàn)該粒子群算法，并以安全閥裝配體為應用實例對該算法進行驗證。圖1為安全閥裝配體的剖視圖，該裝配體由32個零件組成。

1.閥體；2.閥座；3.閥瓣；4.反沖盤；5.墊片A1；6.導向套；7.墊塊；8.閥桿；9.彈簧座1；10.調節(jié)圈；11.墊片A2；12.閥蓋；13.調節(jié)螺桿；14.螺塞墊；15.螺塞；16.螺塞墊；17.緊定螺釘；18.六角薄螺母；19.螺帽；20-23.雙頭螺柱；24-27.六角螺母；28.墊片B；29.六角薄螺母；30.彈簧座2；31.閥帽；32.彈簧

圖1 安全閥裝配體

設置群體規(guī)模為26，迭代次數(shù)tmax=500，慣性權重w=0.9。學習因子c1=c2=0.5，重定向性的權重w1=0.4，穩(wěn)定性的權重w2=0.3，連續(xù)性和聚合性的權重w3=w4=0.15。在隨機產(chǎn)生初始粒子群的位置后，經(jīng)過500次迭代，算法求解的最優(yōu)/近優(yōu)裝配序列及適應值如表1所示。

最優(yōu)序列適應值分別為：幾何不可行零件數(shù)為0；重定向性為0.083，方向改變2次；穩(wěn)定性為0.08；連續(xù)性為0.18；聚合性為0.36。該序列的最終適應值為0.083×0.4+0.08×0.3+0.18×0.15+0.36×0.15=0.138。由結果可知，此最優(yōu)序列滿足幾何可行性要求且符合實際裝配工藝的有效序列。算法的收斂曲線如圖2所示，由圖2可知，當?shù)?90次后，算法開始收斂，最佳適應函數(shù)值穩(wěn)定在0.138，平均適應度函數(shù)隨著迭代次數(shù)的增加不斷降低并最終收斂。

表1 最優(yōu)/近優(yōu)裝配序列及適應值

圖2 算法的收斂曲線

4 結論

(1)構建了鄰接矩陣、干涉矩陣和支撐矩陣表達零件之間的約束關系。給出了表達零件與子裝配體關系的收縮矩陣建立方法。

(2) 綜合考慮裝配可行性、裝配難度、裝配效率和裝配成本等因素的影響，提出了有工程意義的適應度函數(shù)的表達式。

(3) 針對裝配序列規(guī)劃問題的特點，對基本粒子群算法的各個操作重新定義，提出了更加完善的面向裝配序問題的離散粒子群算法。

(4) 試驗證明，改進的離散粒子群算法方法能高效快速地搜索到與實際裝配工藝相接近的最優(yōu)或近優(yōu)裝配序列，是一個行之有效的裝配序列規(guī)劃方法。

[1]劉德忠, 費仁元, Hesse S. 裝配自動化[M](第2版). 北京: 機械工業(yè)出版社, 2007.

[2]Homem De Mello LS,Sanderson AC.A correct and complete algorithm for the generation of mechanical assembly sequences[J]. IEEE Trans Robot Automation,1991,7(2)：228-240.

[3]Chen,R S.Optimization of assembly plan through a three-stage integrated approach[J]. International Journal of Computer Applications in Technology,2004,19(1)：28-38.

[4]Sinanoglu C,Borklu H R.An assembly sequence-planning system for mechanical parts using neural network[J]. Assembly Automation,2005,25(1)：38-52.

[5]周開俊, 李東波. 基于遺傳模擬退火算法的產(chǎn)品裝配序列規(guī)劃方法[J]. 計算機集成制造系統(tǒng), 2006, 12(7)：1037-1041.

[6]Romeo M.Marian, Lee H.S.Luong,Kazem Abhary.A genetic algorithm for the optimization of assembly sequences[J]. Computers & Industrial Engineering, 2006, 50：503-527.

[7]于嘉鵬，王成恩，王健熙.基于最大—最小蟻群系統(tǒng)的裝配序列規(guī)劃[J]. 機械工程學報，2012，48(23)：152-166.

[8]曾冰，李明富，張翼，等. 基于螢火蟲算法的裝配序列規(guī)劃研究[J]. 機械工程學報，2013，49(11)：177-184.

[9]Kennedy J,Eberhart R C.Particle swarm optimization[A].Proceedings of the IEEE International Conference on Neuaral Networks,Piscataway[C]. NJ:IEEE Service Center,1995：1942-1948.

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

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

Assembly Sequence Planning Based on Improved Particle Swarm Optimization Algorithm

YU Hong,SHUI Li

(Shenyang Ligong University,Shenyang 110159, China)

Aiming at the problem of assembly sequence planning,all the relevant operations of particle swarm algorithm which is always applied to optimize in continuous space were redefined, and the improved particle swarm algorithm was proposed by improving the Update formula of particle swarm algorithm and particle optimization.The adjacency matrix,interference matrix and supporting matrix are constructed to describe the assembly relationship of assembly parts.To obtain optimal assembly sequence，five criterions including geometric feasibility,redirection,stability,continuity and aggregation are weighted combined in fitness.An safety valve assembly application case demonstrates the availability of the improved particle swarm algorithm Key words： assembly sequence planning;particle swarm algorithm;multi-objective optimization

2015-05-18

于宏(1974—)，女，講師，博士，研究方向：復雜產(chǎn)品數(shù)字化設計、CAD/CAM技術等.

1003-1251(2015)04-0029-05

TP391

A