改进粒子群算法的装配序列规划方法

于 宏，水 丽

(沈阳理工大学 机械工程学院，辽宁 沈阳 110159)

改进粒子群算法的装配序列规划方法

于 宏，水 丽

(沈阳理工大学 机械工程学院，辽宁 沈阳 110159)

针对装配序列规划问题的特点，重新定义应用于连续空间优化的粒子群算法的各种相关操作，并对粒子群算法的更新公式及粒子优化进行改进，提出面向装配序列规划问题的改进型离散粒子群算法。构建邻接矩阵、干涉矩阵和支撑矩阵，描述零部件之间的装配关系。建立包括可行性、重定向性、稳定性、连续性和聚合性为评价指标的适应函数，实现多目标优化。以安全阀装配序列规划实例验证了改进粒子群装配序列优化算法的有效性。

装配序列规划；粒子群算法；多目标优化

装配是装备制造业的重要环节，是装备研制的重要方面，其结果直接关系到产品质量、性能、寿命和可维护性。装配在复杂产品的制造成本和生产周期中所占的比例日益增大[1]，因此，装配规划在产品设计开发过程中具有非常重要的地位。装配序列规划是装配规划的核心，装配序列的优劣直接影响装配资源配置、装配线设计、装配成本、装配质量和装配效率。

目前，国内外的学者对装配序列规划进行了大量的研究，现有的装配序列规划方法主要分为两大类：精确计算方法和启发式方法。精确计算方法如树搜索或图搜索方法[2-3]，通常采用割集算法，能确保全局最优解的产生；然而对零件数目较多的复杂产品，将会出现装配序列组合爆炸问题，使该方法求解难度增大，很难得到理想结果。近20 年来广大研究者开始将现代智能优化计算方法应用到装配序列规划领域中来，如人工神经网络方法[4]、模拟退火算法[5]、遗传算法[6]、蚁群算法[7]、和萤火虫算法[8]等，为复杂产品的装配序列求解提供了强有力的方法。

与上述智能优化算法相类似，粒子群优化算法(particle swarm optimization,PSO)也是一种基于群体智能的优化算法。该算法是Kennedy等[9]受鸟群捕食行为的启发于1995年提出的。最初粒子群算法用于解决连续优化问题，在函数优化和其他连续性问题中得到广泛应用。近年来，粒子群算法也被成功地应用到离散性组合优化问题中，如旅行商和各种调度问题。但是对装配序列规划问题，PSO算法应用较少[10]，且在算法的实现上，都采用标准的粒子群算法流程。鉴于此，本文针对装配序列规划问题对粒子群算法进行改进，提高搜索效率，避免算法快速收敛局部最优，改善最优解的质量。

1 装配关系模型

使用智能优化算法求解装配序列，需采用合适的形式表示装配模型中各零部件之间的装配关系，建立装配关系矩阵是常用的表示方法。本文采用了邻接矩阵、干涉矩阵和支撑矩阵表达零件之间的约束关系。当需要建立零件与子装配体的关系矩阵时，可通过矩阵合并操作，生成相应的收缩矩阵。

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 收缩矩阵

以上矩阵中的各元素表示的是零件与零件之间的相互关系。而在进行装配序列规划时，为降低计算复杂度，装配体中的零件通常被组合成若干个子装配体，每个子装配体作为一个整体被视为一个零件参与规划。这时需要将仅包含零件信息的邻接、干涉和支撑矩阵转化成包含零件及子装配体信息的各相关矩阵。转化的过程是对原始的邻接、干涉和支撑矩阵中组成子装配体的相关零件所对应的行元素和列元素进行抽取、合并，从而形成一个新的矩阵，该矩阵称为收缩矩阵。

2 改进型离散粒子群算法模型

2.1 适应度函数的构造

在装配序列规划领域，最优的装配序列应是装配困难度最低、装配效率最高、装配成本最低的可行序列。因此评价一个装配序列应该从两个方面入手，即装配可行性和装配序列优劣性。为达到此目标，需要考虑的优化标准很多。本文主要考虑对产品装配影响较大的几个因素，以装配可行性、装配重定向性、装配体的稳定性、装配的聚合性和装配连续性为评价指标，构造目标函数。将几何可行性、重定向性、装配稳定性、装配聚合性和装配连续性评价指标进行加权求和即可确定装配序列的适应函数，如式(1)所示。

(1)

式中：N为组成装配体的零部件数目；nf为不满足几何可行性的零件数目；nd为装配方向改变次数；ns为装配不稳定的零件数目；nt为装配工具的改变次数；nc为反映装配连续性的目标值；w1、w2、w3和w4分别为装配方向改变、装配稳定性、装配聚合性和装配连续性的权重系数，0≤w1,w2,w3,w4≤1，且w1+w2+w3+w4=1。w1、w2、w3和w4由公式(2)计算获得。

(2)

式中，n为评价标准的数目，这里n=4；k为评价标准的重要性排名。

2.2 标准粒子群算法的离散化

由于标准粒子群算法不适用于装配序列规划问题的求解，本文提出了离散粒子群算法用于装配序列规划问题的求解，重新构造粒子位置、速度及其运算公式如下：

定义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 速度的数乘。设粒子的速度V1=(v11,v12,…,v1N)和系数c，c∈[0,1]，定义速度与系数的乘法为：c⊗V1=V2,V2=(v21,v22,…,v2N)，V2的确定方法为

(3)

式中r是一个0到1之间均匀分布的随机数。

定义6 速度的加法。两个速度相加的结果是一个新速度，设两个速度分别为V1=(v11,v12,…,v1N)与V2=(v21,v22,…,v2N)，定义二者的加法为：V1⊕V2=V3。V3=(v31,v32,…,v3N)，V3的确定方法为

(4)

2.3 离散粒子群算法的改进

本文提出的改进型离散粒子群算法主要对标准型萤火虫算法的粒子速度和位置的更新公式进行改进，并增加粒子修复的操作。

2.3.1 混合优化模型

通过以上对粒子位置和速度以及相关操作的特殊定义，采用PSO全局模型和局部模型的混合优化模型，给出求解装配序列规划问题的离散粒子群优化操作下粒子速度和位置的更新公式。

(5)

(6)

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

(7)

全局和局部混合模型的执行过程如下：设t为当前迭代次数，tmax为算法的最大迭代次数，Gt为一个变量，且Gt=t/tmax，rand是随机产生的一个0到1之间均匀分布的随机数；如果 rand>Gt，粒子的速度更新公式选用局部模型，按公式(5)计算，否则采用全局模型按公式(6)进行更新。

2.3.2 粒子的修复操作

装配体中零件通常分为功能件和连接件两类，大部分功能件是通过连接件进行连接，被连接的功能件和连接件之间都存在固定的装配顺序，这种固定的装配顺序隐含着最基本、最重要的优先关系。通过对功能件和不同类型连接件之间固定装配顺序的整理，建立基于连接件的优先及紧邻关系。

粒子的修复是指将初始群体和每次更新后产生的新粒子中违反优先及紧邻关系的粒子"修复"为符合优先及紧邻关系的合理、有效粒子，从而使粒子沿着好的方向搜索，提高搜索效率，且避免过早地收敛，使得最终结果的各项评价指标更优。

2.4 算法的实现步骤

输入量：装配体零件列表；三个直角坐标轴方向的干涉矩阵；装配体的邻接矩阵；支撑矩阵；最大迭代次数tmax，各优化指标(装配方向改变、稳定性、聚合性、连接性)的权重，最大和最小惯性权重wmax、wmin，学习因子c1、c2。

步骤 1：根据装配体的连接关系和定义的规则，自动提取优先及紧邻关系；

步骤2：根据零部件质量、体积和邻接关系矩阵，计算确定装配序列的初始件；

步骤3：随机产生初始群体的位置和速度，设当前迭代次数t=1；

步骤4：根据优先及紧邻关系修复种群中所有粒子的位置；

步骤5：根据公式(1)计算每个粒子的适应值，并确定个体最优值Pi和全局最优值Pg；

步骤6：计算Gt，产生一个随机数rand，rand∈[0,1]；

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

步骤8：如果t≥tmax，转到步骤9，否则t=t+1，转到步骤4；

步骤9：输出求得的最优序列Pg，绘制收敛曲线。

3 应用实例

为验证算法的有效性，采用C#语言实现该粒子群算法，并以安全阀装配体为应用实例对该算法进行验证。图1为安全阀装配体的剖视图，该装配体由32个零件组成。

1.阀体；2.阀座；3.阀瓣；4.反冲盘；5.垫片A1；6.导向套；7.垫块；8.阀杆；9.弹簧座1；10.调节圈；11.垫片A2；12.阀盖；13.调节螺杆；14.螺塞垫；15.螺塞；16.螺塞垫；17.紧定螺钉；18.六角薄螺母；19.螺帽；20-23.双头螺柱；24-27.六角螺母；28.垫片B；29.六角薄螺母；30.弹簧座2；31.阀帽；32.弹簧

图1 安全阀装配体

设置群体规模为26，迭代次数tmax=500，惯性权重w=0.9。学习因子c1=c2=0.5，重定向性的权重w1=0.4，稳定性的权重w2=0.3，连续性和聚合性的权重w3=w4=0.15。在随机产生初始粒子群的位置后，经过500次迭代，算法求解的最优/近优装配序列及适应值如表1所示。

最优序列适应值分别为：几何不可行零件数为0；重定向性为0.083，方向改变2次；稳定性为0.08；连续性为0.18；聚合性为0.36。该序列的最终适应值为0.083×0.4+0.08×0.3+0.18×0.15+0.36×0.15=0.138。由结果可知，此最优序列满足几何可行性要求且符合实际装配工艺的有效序列。算法的收敛曲线如图2所示，由图2可知，当迭代290次后，算法开始收敛，最佳适应函数值稳定在0.138，平均适应度函数随着迭代次数的增加不断降低并最终收敛。

表1 最优/近优装配序列及适应值

图2 算法的收敛曲线

4 结论

(1)构建了邻接矩阵、干涉矩阵和支撑矩阵表达零件之间的约束关系。给出了表达零件与子装配体关系的收缩矩阵建立方法。

(2) 综合考虑装配可行性、装配难度、装配效率和装配成本等因素的影响，提出了有工程意义的适应度函数的表达式。

(3) 针对装配序列规划问题的特点，对基本粒子群算法的各个操作重新定义，提出了更加完善的面向装配序问题的离散粒子群算法。

(4) 试验证明，改进的离散粒子群算法方法能高效快速地搜索到与实际装配工艺相接近的最优或近优装配序列，是一个行之有效的装配序列规划方法。

[1]刘德忠, 费仁元, Hesse S. 装配自动化[M](第2版). 北京: 机械工业出版社, 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]周开俊, 李东波. 基于遗传模拟退火算法的产品装配序列规划方法[J]. 计算机集成制造系统, 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]于嘉鹏，王成恩，王健熙.基于最大—最小蚁群系统的装配序列规划[J]. 机械工程学报，2012，48(23)：152-166.

[8]曾冰，李明富，张翼，等. 基于萤火虫算法的装配序列规划研究[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]王丰产，孙有朝，李娜.多工位装配序列粒子群优化算法[J].机械工程学报，2012，48(9)：155-162.

(责任编辑：马金发)

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—)，女，讲师，博士，研究方向：复杂产品数字化设计、CAD/CAM技术等.

1003-1251(2015)04-0029-05

TP391

A