基于自適應變異粒子群優(yōu)化算法的產(chǎn)品裝配序列規(guī)劃*

陳海彬，郭建文，孫振忠，王 松，張智聰

（1.東莞理工學院機械工程學院 東莞 523808；2.華南理工大學機械與汽車工程學院 廣州510640）

基于自適應變異粒子群優(yōu)化算法的產(chǎn)品裝配序列規(guī)劃*

陳海彬1，郭建文1，孫振忠1，王 松2，張智聰1

（1.東莞理工學院機械工程學院 東莞 523808；2.華南理工大學機械與汽車工程學院 廣州510640）

為提高產(chǎn)品虛擬裝配序列規(guī)劃水平，提出了面向裝配序列規(guī)劃的自適應變異粒子群優(yōu)化算法。算法針對產(chǎn)品裝配序列規(guī)劃離散性的特點，在基本粒子群算法的基礎(chǔ)上，對粒子位置、速度與粒子速度和位置更新操作進行了重定義，通過引入遺傳算法中的變異算子來提高算法跳出局部最優(yōu)的能力，同時改變慣性權(quán)重的取值方式以加快算法的收斂速度。以一柱塞泵的裝配規(guī)劃實例來分析該算法的性能，驗證了自適應變異粒子群優(yōu)化算法的可行性；與遺傳算法和粒子群算法的比較證明自適應變異粒子群優(yōu)化算法更有效。

自適應；變異粒子群；裝配序列規(guī)劃

0 引言

研究表明，在制造企業(yè)中裝配費用占整個生產(chǎn)費用的比例大于40%，裝配時間占整個工作時間的40%～60%［1］。裝配規(guī)劃是在確保裝配可行的基礎(chǔ)上，確定裝配軌跡、順序、輔助工具等裝配方案。良好的裝配規(guī)劃能有效地提高裝配質(zhì)量和效率，降低裝配成本［2］。裝配序列規(guī)劃［3］（Assembly Sequences Planning，ASP）是裝配規(guī)劃的重要組成，其實質(zhì)是在一定的約束條件下，從大量的可供選擇的裝配序列中確定滿足需求（如時間、費用、可靠性等）的最優(yōu)方案，可視為一種NP問題。

近年來，遺傳算法［4］、蟻群算法［5］、模擬退火算法［6］、人工神經(jīng)網(wǎng)絡(luò)［7］、粒子群算法［8］（Particle Swarm Optimization，PSO）等智能優(yōu)化算法在ASP中得到應用。然而，當種群規(guī)模較小時，遺傳算法收斂速度就會很慢，不易得到理想裝配序列［9］；模擬退火算法對解空間的拓展不夠好，不容易搜索到最有效的區(qū)域，搜索效率低［10］；人工神經(jīng)網(wǎng)絡(luò)算法缺乏全局搜索能力；蟻群算法在搜索后期容易出現(xiàn)停滯現(xiàn)象。相對于其它智能算法，粒子群算法是解決ASP的較優(yōu)方法，但粒子群算法同樣存在早熟收斂的不足［11］。

為此，本文提出基于自適應變異粒子群優(yōu)化算法（Adaptive Particle Swarm Optimization Algorithm with Mutation，AMPSO）以解決產(chǎn)品裝配序列問題。方法針對ASP離散性特點，重定義粒子位置、速度及位置和速度的更新操作，引入變異算子來保證算法不過早收斂。實驗表明算法能有效提高ASP的效率和質(zhì)量。

1 目標函數(shù)的構(gòu)造

1.1 評估指標

2 基于AMPSO的產(chǎn)品裝配序列

2.1 基本PSO算法的重定義

2.2 算法的改進及實現(xiàn)步驟

AMPSO算法通過加入變異算子，一方面可以提高算法的局部搜索效果；另一方面可以保持群體的個體差異性，防止早熟收斂現(xiàn)象的發(fā)生，增加了粒子最終收斂到全局最優(yōu)解的概率。

（1）粒子初始化。ASP的解為一可行的裝配序列矩陣AS，同時AS又由裝配零件序列AP、裝配方向序列AD和裝配工具序列AT組成。隨機初始化產(chǎn)生AP序列，由其確定最優(yōu)AD和AT序列。

（2）初始適應度計算。根據(jù)式（4）可以直接計算各粒子的適應度函數(shù)值，并確定初始個體最優(yōu)序列和初始全局最優(yōu)序列。

（3）慣性權(quán)重計算。慣性權(quán)重ω按照式（7）取值：

其中，fgb為目前找到的全局最優(yōu)裝配序列適應度函數(shù)值，fd為全局最優(yōu)裝配序列期望適應度函數(shù)值。

（4）粒子更新。裝配零件序列AP根據(jù)式（5）和式（6）更新，而裝配方向序列AD和裝配工具序列AT則由更新后的AP序列得到，AD和AT序列為更新后的AP序列的最優(yōu)序列。

（5）適應度更新。由公式（4）更新粒子群的適應度值，并更新各粒子的個體最優(yōu)序列和全局最優(yōu)序列。

（6）多樣性因子更新。采用種群適應度值的標準方差σ作為衡量種群多樣性的指標，其按照下式（9）取值：

其中，n是粒子群的粒子數(shù)，fi是第i個粒子的適應度，fa為粒子群的平均適應度：

（7）變異。為避免早熟發(fā)生，特引入變異算子使得當前全局最優(yōu)裝配零件序列g(shù)Best發(fā)生變異，根據(jù)文獻［13］，變異概率pm計算公式如下：

其中，k∈［0.1，0.3］，σd為種群收斂臨界標準差，其取值與實際問題有關(guān)，一般遠小于σ的最大值，fd為期望最優(yōu)適應度，i為當前迭代次數(shù)，run為最大迭代次數(shù)。當滿足上述變異條件，而且滿足fgb≥cf，則同時將隨機生成的新種群替換舊種群。

（8）如果i＜run，轉(zhuǎn)到步驟3；否則轉(zhuǎn)至步驟9。

（9）輸出找到的最優(yōu)序列g(shù)Best。

3 實例及比較分析

3.1 應用實例

圖1為柱塞泵模型。模型由14個零件和子裝配體組成，各零件可用裝配工具如下所示：P1（T1）、P2（T2/T3）、P3（T2/T3）、P4（T2/T3）、P5（T2）、P6（T2）、P7（T1/T2）、P8（T2）、P9（T1）、P10（T3）、P11（T2）、P12（T2）、P13（T1）、P14（T3）。參數(shù)設(shè)置：cf=5，cs= 0.5，ct=0.2，cd=0.3，c1=0.5，c2=0.5，σd= 0.1，fd=2.1，k=0.2，sizepop=100，run=600。

圖1 某柱塞泵的三維實體模型

通過多次試驗分析，全局最優(yōu)適應度值為2.1，但全局最優(yōu)裝配序列有多個，如下序列為其中一個：P1（-Z&T1）→P5（-Z&T2）→P6（-Z&T2）→P7（-Z&T2）→P8（-Z&T2）→P11（+X&T2）→P12（+X&T2）→P13（+X&T1）→P9（-Z&T1）→P10（-Z&T3）→P14（+X&T3）→P4（+Y&T3）→P2（-Y&T3）→P3（-Y&T3）。

圖2是50次試驗各代平均適應度和最優(yōu)適應度的平均值變化趨勢；50次試驗中有多次獲得全局最優(yōu)適應度值2.1。圖3是其中一次試驗的各代最優(yōu)適應度和平均適應度的變化趨勢。

從圖2可以看出，50次試驗中，第0代平均適應度均值為26.9501，而最優(yōu)適應度均值為12.558，可見初始隨機生成的裝配序列整體質(zhì)量較差，而且存在較多的不可行裝配序列，但在算法結(jié)束的時候平均和最優(yōu)適應度均值都能得到較好的結(jié)果，這說明該算法對初始裝配序列的質(zhì)量要求不高，對裝配序列是否可行沒有依賴。同時，從圖2中還可以看出，最優(yōu)適應均值和平均適應度均值穩(wěn)步下降。從圖3可以看出，平均適應度值發(fā)生了多次局部跳躍增大的現(xiàn)象，這是因為當前種群多樣性較弱，陷入了局部最優(yōu)，根據(jù)變異機制，發(fā)生了變異，種群得到了更新，增強了種群的多樣性。從最優(yōu)適應度和平均適應度曲線最終重合可知，種群經(jīng)過多次變異之后最終收斂。

圖2 平均和最優(yōu)適應度的平均值

圖3 最優(yōu)和平均適應度

3.2 算法比較分析

為了驗證AMPSO算法的有效性和優(yōu)越性，現(xiàn)將AMPSO算法與遺傳算法（Genetic Algorithm，GA）和PSO算法相比較。現(xiàn)仍然采用上述的相同實例進行裝配序列規(guī)劃，仿真環(huán)境和算法參數(shù)不變。其中GA的交叉概率取為0.8，變異概率為0.1，PSO算法的慣性權(quán)重取值為0.6?，F(xiàn)比較三種算法迭代次數(shù)為600，重復運行次數(shù)為50，種群規(guī)模分別為20、50和100情況下的性能。

表1算法試驗結(jié)果對比

從表1可以看出，在50結(jié)果中，AMPSO和PSO算法都能得到較多的可行裝配序列，但是在種群規(guī)模較小的情況下，遺傳算法將會得到較少的可行裝配序列，且種群規(guī)模與可行序列數(shù)呈正相關(guān)；在相同種群規(guī)模下，AMPSO和PSO算法找到的最優(yōu)裝配序列比GA好；在不同種群規(guī)模下，GA始終沒有找到全局最優(yōu)解，而PSO和AMPSO算法可以有效的找到全局最優(yōu)解，并且AMPSO算法找到全局最優(yōu)解的個數(shù)要明顯多于PSO，這說明AMPSO算法有著最強的尋找全局最優(yōu)解的能力；在運行時間上，AMPSO和PSO算法要略多于GA。

本文以適應度函數(shù)值的標準方差為衡量種群多樣性的指標，比較三種算法的種群適應度函數(shù)值得標準差均值隨著迭代次數(shù)增加的變化情況，三種算法在種群規(guī)模為100，重復運行50次情況的下種群多樣性對比曲線如下圖4所示。

通過圖4可以看出，遺傳算法的多樣性一直沒有太大變化，這說明其收斂速度慢，而算法迭代次數(shù)的前部分AMPSO有著比PSO更快的收斂速度，但是在后期其波動較大，這是由于AMPSO算法加入了變異因子，當種群陷入局部最優(yōu)時，根據(jù)變異機制，種群發(fā)生了變異，改善了種群的多樣性，從而加大了算法收斂到全局最優(yōu)解的概率，從全局看，AMPSO和PSO算法的種群多樣性都穩(wěn)步下降。

圖4 種群多樣性對比

4 結(jié)束語

本文在基本PSO算法的基礎(chǔ)上，對粒子位置、速度與粒子速度和位置更新操作進行了重定義，并且通過引入GA中的變異算子來提高算法跳出局部最優(yōu)的能力，提出了一種基于AMPSO的ASP方法。仿真實例結(jié)果表明：與GA和基本PSO對比，該算法具有收斂速度快、尋優(yōu)能力強和能有效避免陷入局部最優(yōu)解的優(yōu)點，能有效提高產(chǎn)品裝配序列規(guī)劃的效率和質(zhì)量。

［1］王峻峰，李世其，劉繼紅，等.計算機輔助裝配規(guī)劃研究綜述［J］.工程圖學學報，2005（2）：1-5.

［2］寧黎華，古天龍.裝配序列規(guī)劃問題求解的一種混合算法［J］.計算機集成制造系統(tǒng)，2007，13（4）：762-767.

［3］李原，張開富，王挺，等.基于遺傳算法的飛機裝配序列規(guī)劃優(yōu)化方法［J］.計算機集成制造系統(tǒng)，2006，12（2）：188-191.

［4］LAZZERINI B，MARCELLONI F.A genetic algorithm for generating optimal assembly plans［J］.Artificial Intelligence in Engineering，2000，14（4）：319-329.

［5］Mingxing Deng，Qiuhua Tang，Zhe Lei.An improved assembly sequence planning approach using ant colony algorithm［J］.International Review on Computers and Software，2011，6（7）：1307-1312.

［6］MILNER JM，GRAVESSC，WHITNEY D E.Using simulated annealing to select least-cost assembly sequences［C］//Proceeding of IEEE International Conference on Robotics and Automation.San Diego，1994（3）：2058-2063.

［7］HONG D S，CHO H S.A neural network based computational scheme for generating optimized robotic assembly sequences［J］.Engineering Application Artifical Intelligence，1995，8（2）：129-145.

［8］Kennedy J，Eberhart RC.Particle swarm optimization［C］// Proceedings of IEEE International Conference on Neural Networks.Perth：IEEE，1995：1942-1948.

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

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

［11］呂振肅，侯志榮.自適應變異的粒子群優(yōu)化算法［J］.電子學報，2004，32（3）：416-420.

［12］劉繼紅.復雜產(chǎn)品協(xié)同裝配設(shè)計與規(guī)劃［M］.武漢：華中科技大學出版社，2011.

［13］劉衛(wèi)寧，李一鳴，劉波.基于自適應粒子群算法的制造云服務組合研究［J］.計算機應用，2012，32（10）：2869-2874.

（編輯 李秀敏）

Product Assem bly Sequences Planning Based on Adaptive Particle Swarm Optim ization Algorithm w ith M utation

CHEN Hai-bin1，GUO Jian-wen1，SUN Zhen-zhong1，WANG Song2，ZHANG Zhi-cong1
（1.SchoolofMechanical Engineering，Dongguan University of Technology，Dongguan 523808，China；2.School of Mechanical&Automotive Engineering，South China University of Technology，Guangzhou 510640，China）

In order to improve the level of product virtual assembly sequence planning，the productassembly sequences planning based on adaptive mutation particle swarm optimization algorithm is proposed.In view of the discreteness characteristic of the product assembly sequences planning，on the basis of the basic particle swarm optim ization algorithm，the particle position，velocity and their update operation are redefined，themutation operator of genetic algorithm is introduced to improve the ability to jump outof local optimum，at the same time，by changing the value of inertia weightway to accelerate the algorithm convergence rate. The characteristics of adaptive particle swarm optim ization algorithm w ithmutation are showed via assembly planning experiment of a plunger pump.The experiment proved thatadaptive particle swarm optim ization algorithm w ith mutation is feasible，and the efficiency of adaptive particle swarm optimization algorithm w ith mutation is compared w ith the efficiency of genetic algorithm and particle swarm optim ization algorithm，the experiment show that the adaptive particle swarm optimization algorithm w ith mutation ismore efficient.

self-adaption；mutation particle swarm；assembly sequences planning

TH166；TG506

A

1001-2265（2015）07-0153-04 DOI：10.13462/j.cnki.mmtamt.2015.07.043

2015-01-19；

2015-03-30

國家自然科學基金項目（71201026）；廣東省教育廳科技創(chuàng)新項目（2013KJCX0179）；東莞市社會科技發(fā)展項目（201310810101）；東莞市高等院校、科研機構(gòu)科技計劃一般項目（2014106101007）

陳海彬（1984-），男，廣東省汕尾人，東莞理工學院工程師，研究方向為數(shù)控與特種加工遙控維護規(guī)劃研究；通訊作者：孫振忠（1969-），黑龍江肇源人，東莞理工學院教授，碩士生導師，研究方向數(shù)字化制造，（E-mail）hbchen@dgut.edu.cn。