曲兴田, 张昆, 王学旭, 王宏一
吉林大学 机械与航空航天工程学院，吉林 长春 130025
收稿日期：2019-01-11
基金项目：国家自然科学基金资助项目(51875248)。
作者简介：曲兴田(1962-), 男, 吉林德惠人, 吉林大学教授。

摘要：针对单一算法无法实现复杂装配体装配序列智能规划以及缺乏深度人机交互而导致的改进效果不佳等问题，提出一种混合循环算法.该算法以遗传算法为主体，利用干涉矩阵和接触矩阵调整随机生成的装配序列，以装配方向及工具的统一性构建适应度函数；其次结合模拟退火算法，在迭代前加入退火操作，利用Metropolis准则接受交叉和变异后的个体序列；引入粒子群算法的跟踪极值思想，直接选择个体最优和群体最优序列与后代交叉；最后结合虚拟现实技术建立装配模拟平台，从装配稳定性及工具操作空间两个维度进一步优化序列.基于该方法以汽车后桥总成装配序列规划为例进行验证，表明所得装配序列符合实际生产，该方法切实有效.
关键词：装配序列智能规划遗传算法粒子群算法模拟退火算法虚拟现实
Hybrid Cycle Algorithm-based Intelligent Assembly Sequence Planning of Complex Assembly
QU Xing-tian, ZHANG Kun, WANG Xue-xu, WANG Hong-yi
School of Mechanical and Aerospace Engineering, Jilin University, Changchun 130025, China
Corresponding author: QU Xing-tian, E-mail:quxt@jlu.edu.cn
Abstract: A hybrid cycle algorithm was proposed aiming at solving the problems that single algorithm cannot realize intelligent assembly sequence planning of complex assembly and the lack of deep human-computer interaction causes poor improvement effects. This algorithm, based on genetic algorithm, uses interference matrix and contact matrix to adjust random assembly sequence and constructs fitness function on the basis of the uniformity of assembly direction and tool. In addition, combining with simulated annealing algorithm, adding annealing operation and using Metropolis criterion, individual sequences were obtained and accepted by crossover and mutation. Meanwhile, by introducing particle swarm optimization, optimal sequence of individuals and groups were selected to cross with the offspring directly. Finally, assembly simulation platform combined with virtual reality were built and the sequence was optimized from the two dimensions of assembly stability and tool operation space. In conclusion, taking automobile rear axle assembly as an example, it is shown that the assembly sequence obtained fits actual production and the method is effective and practical.
Key words: intelligent assembly sequence planninggenetic algorithmparticle swarm optimization algorithmsimulated annealing algorithmvirtual reality
提高产品设计、加工到装配过程的效率和准确性是制造企业发展的重点.运用现代化方法针对复杂装配体进行装配序列规划(assembly sequence planning, ASP)，以低成本、高效率、高精度生成最优装配序列，成为未来制造业装配工艺规划领域的重要研究内容.国内外很多学者在ASP领域进行了深入研究.Zhang等^[1]利用接触矩阵及优先约束关系生成汽车车身装配序列.Bedeoui等^[2]额外考虑部件质量和重心位置两个变量，提高装配的稳定性.Samadhi等^[3]提出一种基于三维实体模型自动检测组件装配时的无碰撞路径，从而生成装配序列.Ben Hadj等^[4]提出对产品模型进行简化，规定标准件的装配方式，减少碰撞分析.而随着人工智能算法的普及和虚拟装配技术的发展，遗传算法^[5-7]、蚁群算法^[8]被普遍应用于优化拆卸及装配过程，于宏等^[9]成功将粒子群算法扩展到ASP领域，改进后的算法增强了全局寻优能力.Iacob等^[10]则基于产品的几何约束条件，开发虚拟拆装仿真平台.刘振宇等^[11]开发了约束行为管理器(CBM)以提高虚拟环境中装配关系识别的效率.吴昌盛等^[12]基于典型装配情景建立装配过程库，以实现用户装配意图捕获.Fujimoto等^[13]和夏平均等^[14]利用虚拟环境下的装配操作对算法求解出的装配序列提出新的评价准则，实现了进一步优化.
在这些方法中，单一算法易陷入早熟且进化速度较慢，同时后续模拟装配的过程中，平面人机交互无真实装配体验，序列优化效果不佳，导致无法获得合理的装配序列.因此本文提出一套复杂装配体的装配序列智能规划方法：以遗传算法为主体，嵌入模拟退火算法和粒子群算法，形成混合循环算法，实现快速全局寻优；而后结合虚拟现实技术(virtual reality，VR)，增强人机交互性，从而对算法所得序列进行改进.主要内容：叙述接触矩阵和干涉矩阵的快速获取方式；论述混合循环算法的原理及实现步骤；引入VR技术模拟装配进一步优化序列；给出计算汽车后桥总成装配序列的验证实例.
1 接触矩阵和干涉矩阵接触矩阵和干涉矩阵是混合循环算法中序列可行性判断及调整的条件.以汽车前刹车调整臂装配模块为例，结合图 1和表 1，介绍接触矩阵及干涉矩阵的快速获取方法.
图 1(Fig. 1)

图 1 调整臂结构图Fig.1 The view of adjusting arm structure

表 1(Table 1)

表 1 调整臂结构明细表Table 1 The structure list of adjusting arm 序列 名称 装配方向 1 外壳 — 2 螺钉 -Z 3 弹簧 -Z 4 钢球 -Z 5 后盖 +Y 6 蜗杆轴 -X 7 油杯 -X 8 涡轮 -Y 9 铆钉 -Y 10 前盖 -Y 11 蜗杆 -Y 12 防尘盖 +X

表 1 调整臂结构明细表 Table 1 The structure list of adjusting arm

接触矩阵表示某零件在完整装配体中与其余零件的接触情况，用于在装配下一个零件(除起始件)时，判断此前装配中是否存在与之接触的零件已经装配，从而保证装配的稳定性.
在软件中设置静态碰撞检测，如图 2所示，计算装配体模块中所有零件的接触及碰撞关系，因为软件中模型的螺纹及齿形配合处是模糊装配，所以碰撞检测中出现负值，按接触件处理即可.系统自动生成接触关系矩阵后，需对其进行后处理，若零件j与零件i在装配完成后的状态下存在接触关系，则记为X(j, i)=1，否则记为X(j, i)=0，依次生成对称接触矩阵X.
图 2(Fig. 2)

图 2 静态碰撞检测Fig.2 Static collision detection

干涉矩阵表示零件自装配体沿坐标轴拆卸至无穷远处与其余零件的干涉情况.
在软件中模拟零件的拆卸过程，检测其动态碰撞.假设所有零件沿+X, -X, +Y, -Y, +Z, -Z这6个方向中的一个进行装配，以调整臂装配为例，选择外壳为初始基准件, 在保证所有零件位置不变的情况下，按零件编号，拆卸基准件以外的零件，沿其反装配方向移动至完全与装配体分离(图 3)，期间系统计算并红色高亮显示干涉位置，记录所有干涉零件编号后，恢复初始完整装配体状态，对下一个零件进行相同操作，依此类推.若零件j拆卸过程中与零件i发生碰撞，则记为M(j, i)=1，即j需要在i装配前装配；不发生碰撞则记为M(j, i)=0，依次生成干涉矩阵M，其中基准件对其余零件均标记为1，即在所有零件装配前装配.
图 3(Fig. 3)

图 3 动态碰撞检测Fig.3 Dynamic collision detection

2 混合循环算法介绍2.1 混合循环算法的原理遗传算法是一种借鉴生物界自然选择和遗传机制的随机搜索算法，本文以该算法为主体，对其改进后形成混合循环算法，改进如下：
1) 在适应度计算前，增加可行性判断操作.因零件数量增加使得排序方式呈指数型增长，且其中大部分为不可用序列，所以为降低运算量，提高优化效率，增加该操作过程.
2) 引入模拟退火算法的思想.遗传算法初期按适应度筛选易陷入早熟，导致后期所有个体适应度趋于一致，种群进化停滞不前，因此在进化前引入温度控制，并利用Metropolis准则按概率接受交叉、变异后的个体序列，使个体适应度差异逐渐放大，避免局部最优解.
3) 引入粒子群算法的跟踪极值思想.改变遗传算法的选择操作，直接选择个体最优序列和群体最优序列与后代种群交叉，继承优秀片段，再更新群体最优序列和个体最优序列，加快寻优速度.
2.2 混合循环算法的主要操作过程上述三方面改进后形成的混合循环算法包含了6项主要操作过程，具体操作原理如下.
1) 装配序列初始化.采用单基因染色体编码方式，每个基因对应一个零件的编号，集合所有零件组成一条装配序列染色体，其中对作用相同的一类零件统一编号以简化计算过程.
2) 可行性判断.装配序列可行性判断主要依据干涉矩阵M和接触矩阵X完成，其过程如图 4所示.
图 4(Fig. 4)

图 4 可行性判断流程图Fig.4 The flow chart of feasibility judgment

步骤1，获取初始化种群矩阵C，种群大小NIND，零件数Num，干涉矩阵M，接触矩阵X，令n=1；
步骤2，若n>NIND，则结束，否则令j=2；
步骤3，若j>Num，则执行n=n+1，并转至步骤2，否则令k=1；
步骤4，若k>j-1，则执行j=j+1，并转至步骤3，否则零件j与零件k在接触矩阵X中的对应值为1，则二者接触，否则转至步骤6；
步骤5，若零件j与零件k在干涉矩阵M中对应值为1，则二者发生干涉，零件j应置于k之前，否则零件j置于k之后；
步骤6，执行k=k+1，并转至步骤4.
3) 建立适应度函数.设置装配方向、装配工具两个优化指标.假设装配均以表 2所涵盖的6个方向进行装配，按各个零件的装配方向生成方向矩阵.在序列中，若后一个零件的装配方向与前一个相同，则f=1，否则f=10.
表 2(Table 2)

表 2 装配方向编号Table 2 Assembly direction number 方向 +X -X +Y -Y +Z -Z 编号 1 2 3 4 5 6

表 2 装配方向编号 Table 2 Assembly direction number

将装配工具分为扳手类、螺钉旋具、锤击类、吊装类，按表 3编号，以此生成装配过程工具矩阵.在序列中，若后一个零件的装配工具与前一个相同，则g=1，否则g=10.
表 3(Table 3)

表 3 装配工具编号Table 3 Assembly tool number 工具 无 扳手类 螺钉旋具 锤击类 吊装类 编号 0 1 2 3 4

表 3 装配工具编号 Table 3 Assembly tool number

针对以上两项优化指标，建立适应度函数：
其中：权重值w_f=0.5，w_g=0.5.适应度罚值的计算结果越小，则装配序列越合理.
4) 模拟退火操作.设置初始温度T₀，截止温度T_end，温度冷却系数q，当温度T降至截止温度T_end以下，停止迭代.同时在交叉和变异操作后，假设所得序列适应度罚值为fit_new，此前序列适应度罚值为fit₀，调用Metropolis算法准则判断是否接受变化后的染色体序列，具体如下：
若fit_new < fit₀，则接受变化后序列；
若fit_new>fit₀，则以概率exp(-(fit_new-fit₀)/T)接受变化后序列.
5) 交叉操作.采用去重后补法让子代个体与亲代个体最优序列、群体最优序列分别交叉.随机选取最优序列中两个交叉位之间的区段，将子代序列中与该区段相同的零件删除，最后把该区段置于子代序列末尾，交叉操作结束.
6) 变异操作.随机选择个体序列中两个变异位，交换彼此位置从而完成变异操作.
2.3 混合循环算法的实现步骤基于混合循环算法的原理，其过程如图 5所示.
图 5(Fig. 5)

图 5 混合循环算法流程图Fig.5 The flow diagram of algorithm

1) 初始化控制参数：种群大小NIND, 最大进化次数MAXGEN，退火初始温度T₀，温度冷却系数q，终止温度T_end.
2) 随机生成初始化种群Chrom，判断种群每个个体的可行性并调整，之后计算每个个体的适应度罚值fit，并记录个体最优序列和群体最优序列；
3) 若T < T_end，则算法结束，得出最优装配序列，否则设置循环计数变量Gen=1，继续执行步骤4；
4) 若Gen>MAXGEN，执行T=qT，并转至步骤3，否则继续执行步骤5；
5) 让群体Chrom与个体最优序列、群体最优序列交叉，随后进行变异，计算所有生成的新个体的适应度罚值f，并以Metropolis准则接受新个体；
6) 比较新生个体和最优群体中所有个体的适应度罚值，从而更新最优群体和最优个体序列；
7) 执行Gen=Gen+1，并转至步骤4.
3 虚拟环境下的序列优化算法所得序列忽略装配稳定性和工具操作范围，因此需人工模拟优化.建立产品整体模型，搭载HTC VIVE Pro头盔显示器运行，用户通过手柄按所得序列操作零件进行装配，依据自身装配经验和知识以及装配工具的操作空间提出新的评价准则，以提高装配序列可行性.
按此前所述装配工具，主要包括扳手类、螺钉旋具、锤击类、吊装类，其中吊装类工具多为电机驱动的绳索，与装配体干涉较少，所以在此只考虑其余三种工具.利用VR技术的沉浸感，用户可直接观察工具与装配体间的碰撞情况，从而判断工具操作空间的合理性，判断准则如下：
1) 抓取工具移动至工作位置的过程中不能与装配体发生碰撞.
2) 针对扳手类工具(图 6a)，以安装内六角螺钉为例，内六角扳手的工作段轴线与螺钉轴线重合，工作旋转角度应为60°及其整数倍，所以在该角度区域中不能与装配体发生碰撞；同时，假设内六角扳手工作段的高度为H，螺钉长度为h，则高度方向H+h范围内不能与装配体发生碰撞.
图 6(Fig. 6)

图 6 工具操作空间图Fig.6 The operational space views of assembly tools (a)—扳手类工具；(b)—螺钉旋具；(c)—锤击类工具.

3) 对于螺钉旋具(图 6b)，假设旋具长度为L，螺钉长度为h，则高度方向L+h范围内不能与装配体发生碰撞.
4) 对于锤击类工具(图 6c)，以轴承安装为例，将套筒加载至轴承内圈，假设套筒长度为A，轴承宽度为B，锤击类工具的工作角度为0~80°，因此，在轴向A+B以外的工作角度覆盖区域，不能与装配体发生碰撞.
4 基于混合循环算法的汽车后桥装配序列规划4.1 混合循环算法规划装配序列将后桥总成划分为减速器模块、调整臂模块、制动盘模块、轮毂模块四个子装配体，因为在后桥中两个半桥的结构完全对称，所以实际生产时可同时对两侧进行装配，因此以单侧结构为例，简化总成装配序列规划，如图 7所示，共分为59种零部件，分析各零件及子模块的装配方向及工具，建立装配方向矩阵P，装配工具矩阵U，模拟零件静态接触碰撞及动态仿真碰撞，建立接触矩阵X，干涉矩阵M，利用混合循环算法求解，所得装配序列如表 4所示.
图 7(Fig. 7)

图 7 后桥总成结构图Fig.7 The structure view of rear axle

表 4(Table 4)

表 4 装配序列表Table 4 The list of assembly sequence 最优解: 12— > 13— > 18— > 3— > 1— > 11— > 9— > 4— > 2— > 10— > 8— > 32— > 34— > 33— > 36— > 46— > 45— > 44— > 41— > 48— > 49— > 47— > 50— > 51— > 52— > 53— > 54— > 55— > 20— > 14— > 15— > 16— > 31— > 17— > 22— > 21— > 23— > 25— > 19— > 26— > 24— > 27— > 29— > 30— > 28— > 35— > 37— > 38— > 39— > 40— > 42— > 43— > 5— > 6— > 57— > 59— > 56— > 58— > 7 适应度罚值：274

表 4 装配序列表 Table 4 The list of assembly sequence

4.2 虚拟现实优化装配序列利用产品模型建立VR装配场景，如图 8所示，按混合循环算法所得装配序列进行模拟，验证工具操作空间及装配稳定性，应用新的评价准则生成调整方案(表 5)，进一步优化，生成最优序列(表 6).
图 8(Fig. 8)

图 8 虚拟操作空间Fig.8 Virtual operational space

表 5(Table 5)

表 5 装配序列调整方案Table 5 Adjustment scheme of assembly sequence ①半轴套管13及内油封18可于后期安装，以减少装配方向改变次数； ②定位螺钉14用于定位半轴套管13，应紧接其后安装； ③接合器47与螺栓45配合以固定刹车室壳44，为保持其稳定性应提前； ④在轮毂22安装之前需要对刹车进行调试，调整垫片35至开口销43区段应提前，配合回位弹簧17的安装.

表 5 装配序列调整方案 Table 5 Adjustment scheme of assembly sequence

表 6(Table 6)

表 6 优化后装配序列表Table 6 The list of optimized assembly sequence 最优解: 12— > 3— > 1— > 11— > 9— > 4— > 2— > 10— > 8— > 32— > 34— > 33— > 36— > 46— > 45— > 44— > 47— > 41— > 48— > 49— > 50— > 51— > 52— > 53— > 54— > 55— > 13— > 14— > 18— > 20— > 15— > 16— > 31— > 35— > 37— > 38— > 39— > 40— > 42— > 43— > 17— > 22— > 21— > 23— > 25— > 19— > 26— > 24— > 27— > 29— > 30— > 28— > 5— > 6— > 57— > 59— > 56— > 58— > 7

表 6 优化后装配序列表 Table 6 The list of optimized assembly sequence

5 结论本文以遗传算法为主体，引入模拟退火算法和粒子群算法，建立了面向复杂装配体装配序列规划的混合循环算法，通过干涉矩阵、接触矩阵进行可行性判断，减少不必要的运算量，又由装配方向、装配工具的统一性构建目标优化函数，求解出装配序列.然后以该序列为引导，结合虚拟现实技术模拟装配过程，通过装配稳定性、工具操作范围进一步优化序列.最后以计算汽车后桥总成的装配序列为例，得出一条符合实际装配的序列，证明了所提的整套智能装配序列规划方法切实有效.
参考文献

[1]	Zhang Y Z, Ni J, Lin Z Q, et al. Automated sequencing and sub-assembly detection in automobile body assembly planning[J].Journal of Materials Processing Technology, 2002, 129(1/2/3): 490–494.
[2]	Bedeoui A, Benhadj R, Trigui M, et al. Assembly plans generation of complex machines based on the stability concept[J].Procedia CIRP, 2018, 70: 66–71.DOI:10.1016/j.procir.2018.03.030
[3]	Alfadhlani A, Ari Samadhi T M A, Toha I S, et al. Automatic collision detection for assembly sequence planning using a three-dimensional solid model[J].Journal of Advanced Manufacturing Systems, 2011, 10(2): 277–291.DOI:10.1142/S021968671100220X
[4]	Ben Hadj R, Belhadj I, Trigui M, et al. Assembly sequences plan generation using features simplification[J].Advances in Engineering Software, 2018, 119(1): 1–11.
[5]	Kheder M, Trigui M, Aifaoui N. Disassembly sequence planning based on a genetic algorithm[J].Proceedings of the Institution of Mechanical Engineers Part C—Journal of Mechanical Engineering Science, 2015, 229(12): 2281–2290.DOI:10.1177/0954406214557340
[6]	Belhadj I, Trigui M, Benamara A. Subassembly generation algorithm from a CAD model[J].The International Journal of Advanced Manufacturing Technology, 2016, 87: 2829–2840.DOI:10.1007/s00170-016-8637-x
[7]	Tseng H E, Chang C C, Lee S C, et al. A block-based genetic algorithm for disassembly sequence planning[J].Expert Systems with Application, 2018, 96: 492–505.DOI:10.1016/j.eswa.2017.11.004
[8]	Huang W J, Xu Q C.Automatic generation and optimization of stable assembly sequence based on ACO algorithm[C]//2017 IEEE International Conference on Mechatronics and Automation (ICMA).Takamatsu, 2017: 2057-2062.
[9]	于宏, 王成恩, 于嘉鹏, 等. 基于粒子群算法的复杂产品装配序列规划[J].东北大学学报(自然科学版), 2010, 31(2): 261–264. ( Yu Hong, Wang Cheng-en, Yu Jia-peng, et al. Assembly sequence planning based on particle swarm optimization algorithm for complex product[J].Journal of Northeastern University(Natural Science), 2010, 31(2): 261–264.DOI:10.3969/j.issn.1005-3026.2010.02.028)
[10]	Iacob R, Popescu D, Mitrouchev P. Assembly/Disassembly analysis and modeling techniques:a review[J].Strojniski Vestnik—Journal of Mechanical Engineering, 2012, 58(11): 653–664.DOI:10.5545/sv-jme.2011.183
[11]	Liu Z Y, Tan J R. Constrained behavior manipulation for interactive assembly in a virtual environment[J].The International Journal of Advanced Manufacturing Technology, 2007, 32(7/8): 797–810.
[12]	吴昌盛, 汪代勇, 代英明, 等. 基于框架的虚拟装配运动引导[J].计算机辅助设计与图形学学报, 2010, 22(6): 997–1003. ( Wu Chang-sheng, Wang Dai-yong, Dai Ying-ming, et al. Frame-based motion guidance for virtual assembly[J].Journal of Computer-Aided Design & Computer Graphics, 2010, 22(6): 997–1003.)
[13]	Fujimoto H, Ahmed A, Sebaaly M F.An evolutionary and interactive approach to simulation of assembly planning in virtual environment[C]//24th Annual Conference of the IEEE Industrial Electronics Society.Aachen, 1998: 187-192.
[14]	夏平均, 姚英学, 刘江省, 等. 基于虚拟现实和仿生算法的装配序列优化[J].机械工程学报, 2007, 43(4): 44–52. ( Xia Ping-jun, Yao Ying-xue, Liu Jiang-sheng, et al. Generating optimized assembly sequence by virtual reality and bionic algorithm[J].Journal of Mechanical Engineering, 2007, 43(4): 44–52.DOI:10.3321/j.issn:0577-6686.2007.04.008)