基于粒子群优化算法的装配序列规划研究

陈大亨，张 彪，宫 华

(沈阳理工大学 理学院，沈阳 110159)



基于粒子群优化算法的装配序列规划研究

陈大亨，张 彪，宫 华

(沈阳理工大学 理学院，沈阳 110159)

针对装备制造业中存在的装配序列规划问题，建立最小化装配次数和方向改变次数之和为目标的优化模型。针对优化模型提出具有随机性特点的初始种群启发式编码，设计粒子群算法。为避免粒子陷入局部最优，采用不同程度的局部搜索操作方式，达到增强粒子群算法局部搜索的能力。实例验证表明，该算法在解决装配序列规划问题上具有优势，求解效果较好。

装配序列规划；粒子群算法；局部搜索

装配序列规划(Assembly Sequence Planning,ASP)问题是装备制造企业的一个重要研究课题，是整个产品周期的一个重要的基础环节。产品的装配过程占产品全部生产环节的20%～70%的时间和费用。合理的装配序列能够减少产品的装配时间，降低产品整体的生产费用，提高企业竞争力。在一些装备制造企业，特别是军工等特殊行业的制造企业，装配序列的产生很大程度上还是依赖人工经验，由于人工经验的有限，得出的装配序列并非最优序列，因此利用先进的智能计算方法产生优化的装配序列将会为这些企业的生产节省成本。

装配序列指产品各零件的装配顺序和装配方向的排序，是典型的难解组合优化问题。一方面大量学者基于几何约束分析解决装配序列产品规划问题。Su[1]系统地提出一种几何约束分析方法用于产生最优的装配序列。Mello 等[2]提出一种几何约束割集算法产生待装配产品的所有装配序列。Hsu 等[3]基于知识分析设计近优的启发式装配序列。另一方面基于智能优化算法解决装配序列规划问题得到广泛的关注。Tseng 等[4]提出遗传算法(GA)解决装配序列规划问题。王珍等[5]研究了基于蚁群算法的引信产品的装配序列规划问题。Sinanoglu[6]利用人工神经网络开发出机械零件装配序列规划系统。Lv 等[7]使用离散粒子群算法解决ASP问题。Zhang等[8]将免疫算法和粒子群算法进行结合解决ASP问题。Somayé等[9]基于近优解在解空间呈现近似的均匀分布的性质，设计跳出局部搜索(BLS)算法，该算法具有很强的邻域搜索能力。

结合文献[9]的工作，本文以产品各零件之间的干涉关系作为几何约束，以最大化满足几何约束次数和最小化装配方向改变次数为目标，建立产品装配序列规划模型。提出带有随机性的启发式算法产生初始种群，设计粒子群算法，采用局部搜索操作提高算法跳出局部最优的能力。本文所提出的算法不仅具有较高收敛速度，同时避免陷入局部最优。通过实例验证，并与现有算法进行比较，验证了该算法的有效性。

1 问题描述

ASP问题假设如下：装配体的各零件均为不可形变零件，即不可通过形变改变几何约束；结合实际装配操作，将装配方向设定为±X,±Y,±Z；各零件不可重复装配，一次操作只能装配一个零件。

1.1 符号说明

N：组成一个机械产品的零件个数；pi：产品的第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 几何约束

采用干涉矩阵表示描述产品在所有装配方向上的几何约束，即第i个零件pi在任意装配方向上对其他零件是否存在干涉。干涉矩阵通常根据±X、±Y、±Z方向建立，假设共有N个零件，则干涉矩阵可表示如下：

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

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

为得到第i个装配的零件及其装配方向，假设已得到有m个零件的子装配体Xsub=[p1,p2,…,pm],第i个零件pi能否顺利装配取决于Iik的值，k∈±x,y,z。Iik定义如下：

Iik的值由如下公式计算：

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

1.3 目标函数

2 算法描述

2.1 基本粒子群算法

(1)

(2)

式中：w为惯性权重；c1和c2为学习因子；r1和r2为[0,1]之间均匀分布的随机数。根据迭代次数线性变化的惯性权重为

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

(3)

式中：ωmax为惯性权重最大值0.9；ωmin为惯性权重最小值0.1；Dmax表示PSO算法的最大迭代次数。

2.2 初始化粒子种群

本文提出一种兼具启发性和随机性的产生初始解方法，以减少无效搜索的可能。该方法细致描述如下所示：

步骤1：输入各装配方向的干涉矩阵IMk，通过对各矩阵求和得到干涉矩阵DIM；

步骤2：随机选择第一个零件的装配方向d1，之后选择在该方向具有与其他零件最少干涉次数的零件作为第一个零件p1；

步骤3：产生1-N的随机整数(代表零件编号)，依次作为装配序列的第2-N个零件，当产生和p1相等的编号，顺延一位；

步骤4：随机产生第2-N个零件的装配方向d2至dn；

步骤5：重复步骤1～4，直到为初始种群中所有粒子赋值。

2.3 局部搜索策略

基本粒子群算法容易陷入局部最优，影响算法寻找全局最优解的能力。对于ASP问题，Somayé和Ellips研究成果表明，多个局部最优解近似均匀的分布在解空间中。利用粒子群算法的快速寻优能力，增强其局部搜索能力，将会是一种行之有效的求解ASP 问题的方法。本文根据该问题解的形式，设计出四种可增强局部搜索能力的操作：(1)在当前装配序列中随机选择一个零件

并随机改变其装配方向；(2)在当前装配序列中随机选择两个零件，并交换其装配次序和方向，并将这两个零件之间的所有其他零件颠倒次序；(3)在当前装配序列中随机选择一个零件，随机将其插入序列其他位置，后续零件依次后移一位。

在算法搜索过程中，规定当某一粒子的函数值连续Imax代没有更新，即认为该粒子陷入局部最优。将从上述(1)～(3)局部搜索操作中选择，若粒子陷入局部最优的代数越大，需选择强度更大的操作进行影响。该算法流程如图1所示。

图1 带有深度邻域搜索策略的粒子群算法流程图

3 实例验证

通过实例验证本文所提出的算法。图2是一个典型的机械产品的零件框图。

图2 产品结构方框图

本文所提出的算法参数如下：学习因子c1=c2=2。粒子种群规模K=40，最大迭代次数Dmax=200。采用C语言编程，以2.0GRAM，2.20GHzCPU的计算机为平台进行实验。将求解结果与其他算法求得结果进行比较，如表1所示。

表1 本文算法与其他算法结果对比

求解过程收敛图如图3所示。

图3 本文算法求解过程收敛图

本文提出的粒子群算法在迭代200次的情况下可以得到最优解。该序列装配方向改变次数为0次，装配过程满足几何约束11次，即每个零件的装配操作都不对其他零件产生干涉。运行30次，除有1次得到函数值为109的序列外，其余都可产生函数值为110的序列，表明该算法的稳定性较好。与其他算法比较可以看出，该算法与Somayé 等提出的BLS算法在迭代100次的情况下具有相同的实验效果，好于遗传算法(GA)的求解结果。本文算法在84代已经产生最优解，具有较快收敛速率，程序运行时间为1.2s。粒子群算法本身具有的编码简单，易于操作等特点，使得所提出的算法在解决ASP问题上仍具有很大的优势。

4 结束语

装配序列规划问题对于装备制造行业提高产品的装配质量和装配效率具有重要意义，通过优化装配序列达到减少产品装配时间和费用，进而缩短生产制造周期，提高企业竞争力。本文以产品各零件之间的干涉关系作为几何约束，以最大化满足几何约束次数和最小化装配方向改变次数为目标，建立产品装配序列规划模型。根据对现有求解方法的对比，提出具有随机性要求的初始解随机产生方法，并提出局部搜索操作方式的粒子群算法，增强算法的局部搜索能力。通过实例验证，与现有的算法进行比较，得到的最优装配序列质量较高，算法稳定性较好，收敛速度较快。在不同企业的实际装配过程中，产品具有很强的多样性，零件的数量可能很大，存在可形变的零件等问题也较为常见。对于此类产品的装配序列规划问题是今后的研究方向。

[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]王珍，陈芳，张杰.基于蚁群算法的引信装配序列优化[J].探测与控制学报,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.

(责任编辑：马金发)

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

国家自然科学基金资助项目(71101097)；辽宁省“百千万人才工程”培养资助项目(2014921043)

陈大亨(1973—)，男，工程师；通讯作者：宫华(1976—)，女，教授，博士，研究方向：组合优化、生产调度。

1003-1251(2016)04-0038-04

O224

A