面向装配序列规划的模因算法研究

张金敏; 胡晓宇

doi:10.13433/j.cnki.1003-8728.20190041

面向装配序列规划的模因算法研究

doi: 10.13433/j.cnki.1003-8728.20190041

兰州交通大学机电工程学院, 兰州 730070

基金项目:

国家自然科学基金项目 51375049

详细信息

作者简介:
张金敏(1966-), 副教授, 硕士生导师, 研究方向为智能设计方法及优化, zhangjm@mail.lzjtu.cn

中图分类号: TH162;TP391
计量
- 文章访问数: 436
- HTML全文浏览量: 147
- PDF下载量: 27
- 被引次数: 0
出版历程
- 收稿日期: 2018-07-12
- 刊出日期: 2019-11-05

Research on Memetic Algorithm for Assembly Sequence Planning

School of Mechanical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

摘要

摘要: 针对遗传算法在求解装配序列规划问题中收敛速度慢、产生重复解等问题，提出一种基于模因算法的装配序列规划方法。将模因算法中全局搜索与局部搜索相结合动态更新种群的策略引入，采用装配优先约束矩阵和干涉矩阵建立装配规划模型，并以装配单元之间的相异性之和构建适应度函数。在非干涉解空间中进行全局搜索，获得装配规划方案，再通过二叉树中序遍历调序算法将较优方案转化为可行解。通过交叉操作和变异操作后，在可行解空间内进行局部搜索，获得较优解。通过典型柱塞油泵装配规划验证了该算法的可行性和可靠性；并将其与遗传算法进行比较，证明其更有效。
- 装配序列规划 /
- 模因算法 /
- 遗传算法 /
- 适应度函数
Abstract: To improve the general genetic algorithm for solving the assembly sequence planning (ASP) problem that it has slow search speed and massive repeated solutions, an ASP method based on the memetic algorithm (MA) was proposed. The strategy of dynamically updating the number of population by combining global search with local search is introduced. The assembly sequence planning model that adopts the constraint matrix and the interference matrix was constructed, and the fitness function for calculating the sum of similarity between assembly units was established. The assembly sequence planning is globally searched in the non-interference solution space. In order to traverse binary trees, the sorting algorithm is adopted to transform an optimal assembly sequence planning solution into a feasible solution. The optimal solution is locally searched in the feasible solution space through crossover and mutation operations. The assembly sequence planning process of a typical plunger pump is used as an example to prove the feasibility of the proposed ASP method. Compared with the genetic algorithm, the algorithm proposed in the paper is more effective.
- assembly sequence planning /
- memetic algorithm /
- genetic algorithm /
- fitness function

HTML全文

图 1 具体的装配染色体

下载: 全尺寸图片幻灯片

图 2 基于中序遍历调序算法的装配可行解转化

下载: 全尺寸图片幻灯片

图 3 基于适应率向导的交叉块的生成

下载: 全尺寸图片幻灯片

图 4 基于适应率向导的交叉操作

下载: 全尺寸图片幻灯片

图 5 基于无约束装配单元变异操作的流程图

下载: 全尺寸图片幻灯片

图 6 无约束装配单元的变异操作

下载: 全尺寸图片幻灯片

图 7 柱塞泵装配示意图

下载: 全尺寸图片幻灯片

图 8 模因算法和遗传算法适应度比较

下载: 全尺寸图片幻灯片

表 1 零件装配信息集

零件编号	装配工具	装配方向
P₁	T₁	-Z
P₂	T₂/T₃	-Y
P₃	T₂/T₃	-Y
P₄	T₂/T₃	+Y
P₅	T₂/T₃	+Y
P₆	T₂	-Z
P₇	T₂	-Z
P₈	T₁/T₂	-Z
P₉	T₂	-Z
P₁₀	T₁	-Z
P₁₁	T₃	-Z
P₁₂	T₂	+X
P₁₃	T₂	+X
P₁₄	T₁	+X
P₁₅	T₃	+X

下载: 导出CSV

表 2 装配规划的优化方案

零件编号	P₁	P₆	P₇	P₈	P₉	P₁₂	P₁₃	P₁₄	P₁₀	P₁₁	P₁₅	P₄	P₅	P₂	P₃
装配方向	-Z	-Z	-Z	-Z	-Z	+X	+X	+X	-Z	-Z	+X	+Y	+Y	-Y	-Y
装配工具	T₁	T₂	T₂	T₂	T₂	T₂	T₂	T₁	T₁	T₃	T₃	T₃	T₃	T₃	T₃

下载: 导出CSV

参考文献(18)

[1]	Molloy E, Yang H, Browne J. Feature-based modelling in design for assembly[J]. International Journal of Computer Integrated Manufacturing, 1993, 6(1-2):119-125 doi: 10.1080/09511929308944562
[2]	Wang Y, Liu J H, Li L S. Assembly sequences merging based on assembly unit partitioning[J]. the International Journal of Advanced Manufacturing Technology, 2009, 45(7-8):808-820 doi: 10.1007/s00170-009-1993-z
[3]	Lazzerini B, Marcellon F. A genetic algorithm for generating optimal assembly plans[J]. Artificial Intelligence in Engineering, 2000, 14(4):319-329 doi: 10.1016/S0954-1810(00)00011-X
[4]	Xing Y F, Wang Y S. Assembly sequence planning based on a hybrid particle swarm optimisation and genetic algorithm[J]. International Journal of Production Research, 2012, 50(24):7303-7312 doi: 10.1080/00207543.2011.648276
[5]	李荣, 付宜利, 封海波.基于连接结构知识的装配序列规划[J].计算机集成制造系统, 2008, 14(6):1130-1135 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200806014 Li R, Fu Y L, Feng H B. Assembly sequence planning based on connecter-structure knowledge[J]. Computer Integrated Manufacturing Systems, 2008, 14(6):1130-1135(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200806014
[6]	Wang Y, Liu J H. Chaotic particle swarm optimization for assembly sequence planning[J]. Robotics and Computer-integrated Manufacturing, 2010, 26(2):212-222 doi: 10.1016/j.rcim.2009.05.003
[7]	李原, 张开富, 王挺, 等.基于遗传算法的飞机装配序列规划优化方法[J].计算机集成制造系统, 2006, 12(2):188-191 doi: 10.3969/j.issn.1006-5911.2006.02.006 Li Y, Zhang K F, Wang T, et al. Assembly sequence planning optimization for aircraft assembly based on GA[J]. Computer Integrated Manufacturing Systems, 2006, 12(2):188-191(in Chinese) doi: 10.3969/j.issn.1006-5911.2006.02.006
[8]	史士财, 李荣, 付宜利, 等.基于改进蚁群算法的装配序列规划[J].计算机集成制造系统, 2010, 16(6):1189-1194 http://d.old.wanfangdata.com.cn/Thesis/Y3439436 Shi S C, Li R, Fu Y L, et al. Assembly sequence planning based on improved ant colony algorithm[J]. Computer Integrated Manufacturing Systems, 2010, 16(6):1189-1194(in Chinese) http://d.old.wanfangdata.com.cn/Thesis/Y3439436
[9]	Wang J F, Liu J H, Zhong Y F. A novel ant colony algorithm for assembly sequence planning[J]. The International Journal of Advanced Manufacturing Technology, 2005, 25(11-12):1137-1143 doi: 10.1007/s00170-003-1952-z
[10]	于嘉鹏, 王成恩, 王健熙.基于最大-最小蚁群系统的装配序列规划[J].机械工程学报, 2012, 48(23):152-166 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201223022 Yu J P, Wang C E, Wang J X. Assembly sequence planning based on max-min ant colony system[J]. Journal of Mechanical Engineering, 2012, 48(23):152-166(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201223022
[11]	曾冰, 李明富, 张翼, 等.基于萤火虫算法的装配序列规划研究[J].机械工程学报, 2013, 49(11):177-184 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201311024 Zeng B, Li M F, Zhang Y, et al. Research on assembly sequence planning based on firefly algorithm[J]. Journal of Mechanical Engineering, 2013, 49(11):177-184(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201311024
[12]	高博, 阎艳, 张发平, 等.基于文化基因算法的装夹规划方法[J].机械工程学报, 2015, 51(3):162-169 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201503025 Gao B, Yan Y, Zhang F P, et al. Setup planning method based on memetic algorithm[J]. Journal of Mechanical Engineering, 2015, 51(3):162-169(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201503025
[13]	Ludwig S A. Memetic algorithms applied to the optimization of workflow compositions[J]. Swarm and Evolutionary Computation, 2013, 10:31-40 doi: 10.1016/j.swevo.2012.12.001
[14]	卢鹄, 黄翔, 堵鹏, 等.基于加权有向图的飞机装配顺序规划[J].南京航空航天大学学报, 2012, 44(S1):1-5 http://d.old.wanfangdata.com.cn/Periodical/njhkht2012z1001 Lu H, Huang X, Du P, et al. Aircraft assembly sequence planning based on weighted directed graph[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2012, 44(S1):1-5(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/njhkht2012z1001
[15]	于嘉鹏, 王成恩, 张闻雷.复杂产品装配关系矩阵自动生成方法[J].计算机集成制造系统, 2010, 16(2):249-255, 270 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201002004 Yu J P, Wang C E, Zhang W L. Automatic acquiring method for assembly relation matrix of complex product[J]. Computer Integrated Manufacturing Systems, 2010, 16(2): 249-255, 270(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201002004
[16]	张闻雷, 曲蓉霞, 许美蓉, 等.复杂产品装配干涉矩阵自动生成方法[J].机械工程学报, 2016, 52(1):139-148 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201601018 Zhang W L, Qu R X, Xu M R, et al. Method for automatic generation of assembly interference matrix of complex products[J]. Journal of Mechanical Engineering, 2016, 52(1):139-148(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201601018
[17]	舒启林, 郝永平, 王德俊.集成化的装配顺序自动生成算法[J].东北大学学报, 2002, 23(07):652-655 doi: 10.3321/j.issn:1005-3026.2002.07.011 Shu Q L, Hao Y P, Wang D J. Integrated automatic generation of assembly sequences[J]. Journal of Northeastern University, 2002, 23(7):652-655(in Chinese) doi: 10.3321/j.issn:1005-3026.2002.07.011
[18]	王松, 孙振忠, 郭建文, 等.基于混合蛙跳算法的复杂产品装配序列规划[J].计算机集成制造系统, 2014, 20(12):2991-2999 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201412009 Wang S, Sun Z Z, Guo J W, et al. Assembly sequence planning based on shuffled frog leaping algorithm[J]. Computer Integrated Manufacturing Systems, 2014, 20(12):2991-2999(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201412009