Research on Memetic Algorithm for Assembly Sequence Planning
-
摘要: 针对遗传算法在求解装配序列规划问题中收敛速度慢、产生重复解等问题,提出一种基于模因算法的装配序列规划方法。将模因算法中全局搜索与局部搜索相结合动态更新种群的策略引入,采用装配优先约束矩阵和干涉矩阵建立装配规划模型,并以装配单元之间的相异性之和构建适应度函数。在非干涉解空间中进行全局搜索,获得装配规划方案,再通过二叉树中序遍历调序算法将较优方案转化为可行解。通过交叉操作和变异操作后,在可行解空间内进行局部搜索,获得较优解。通过典型柱塞油泵装配规划验证了该算法的可行性和可靠性;并将其与遗传算法进行比较,证明其更有效。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.
-
Key words:
- assembly sequence planning /
- memetic algorithm /
- genetic algorithm /
- fitness function
-
表 1 零件装配信息集
零件编号 装配工具 装配方向 P1 T1 -Z P2 T2/T3 -Y P3 T2/T3 -Y P4 T2/T3 +Y P5 T2/T3 +Y P6 T2 -Z P7 T2 -Z P8 T1/T2 -Z P9 T2 -Z P10 T1 -Z P11 T3 -Z P12 T2 +X P13 T2 +X P14 T1 +X P15 T3 +X 表 2 装配规划的优化方案
零件编号 P1 P6 P7 P8 P9 P12 P13 P14 P10 P11 P15 P4 P5 P2 P3 装配方向 -Z -Z -Z -Z -Z +X +X +X -Z -Z +X +Y +Y -Y -Y 装配工具 T1 T2 T2 T2 T2 T2 T2 T1 T1 T3 T3 T3 T3 T3 T3 -
[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/jsjjczzxt200806014Li 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.006Li 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/Y3439436Shi 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/jxgcxb201223022Yu 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/jxgcxb201311024Zeng 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/jxgcxb201503025Gao 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/njhkht2012z1001Lu 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/jsjjczzxt201002004Yu 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/jxgcxb201601018Zhang 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.011Shu 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/jsjjczzxt201412009Wang 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