支持复杂产品并行拆卸序列规划的遗传算法.pdf

第 27 卷 第 7 期 计算机辅助设计与图形学学报 Vol. 27 No.7 2015 年 7 月 Journal of Computer-Aided Design 修回日期：2014-10-08. 基金项目：国家自然科学基金(51205181); 内蒙古自治区自然科学基金(2012MS0707); 内蒙古工业大学中青年学术骨干培养计划专项基金. 张秀芬(1981), 女, 博士, 副教授, 主要研究方向为绿色设计与可拆卸设计; 蔚 刚 (1978), 男, 硕士, 讲师, 论文通讯作者, 主要研究方向为计算机辅助设计与制造; 王 磊(1988), 男, 硕士研究生, 主要研究方 向为报废汽车拆卸序列规划; 萨日娜(1981), 女, 博士, 讲师, 主要研究方向为产品数字化设计. 支持复杂产品并行拆卸序列规划的遗传算法 张秀芬 1), 蔚 刚 2)*, 王 磊 1), 萨日娜 1) 1) (内蒙古工业大学机械学院 呼和浩特 010051) 2) (内蒙古机电职业技术学院 呼和浩特 010070) () 摘 要: 为高效求解复杂产品的并行拆卸序列规划问题, 提出基于遗传算法的复杂产品并行拆卸序列规划方法. 针 对并行拆卸序列规划问题中拆卸序列长度和每步拆卸零部件个数不确定的特点, 提出并行序列染色体编码方法, 分 别将拆卸单元序列和拆卸步长作为染色体的前段和后段, 以此表示一个拆卸序列. 基于该染色体编码, 采用拆卸混 合图描述产品零部件间装配约束关系和拆卸优先级, 并导出拆卸约束矩阵和邻接矩阵, 由矩阵随机获取可行的初始 染色体种群; 将基本拆卸时间和不可行拆卸惩罚因子作为优化目标来构建适应度函数, 确保最优解的可行性; 在初 始染色体种群的基础上, 适应度函数最小为优化目标, 通过遗传、交叉和变异遗传算子实现并行拆卸序列的优化. 最 后通过实例验证了该方法的可行性和实用性. 关键词：并行拆卸; 拆卸序列规划; 遗传算法 中图法分类号：TH122 Parallel Disassembly Sequence Planning for Complex Products Based on Genetic Algorithm Zhang Xiufen1), Yu Gang2)*, Wang Lei1), and Sa Rina1) 1) (The College of Mechanical Engineer, Inner Mongolia University of Technology, Hohhot 010051) 2) (The Inner Mongolia Technical College of Mechanics and Electrics, Hohhot 010070) Abstract: In order to solve the parallel disassembly sequence planning(PDSP) problem efficiently, a method based on genetic algorithm was developed. According to the uncertain characteristics of disassembly se- quence length and the number of parts removed at each step for the PDSP, a chromosome coding method for parallel sequence was presented to express the disassembly sequence and disassembly steps simultaneously. The disassembly hybrid graph (DHG) was constructed to describe the mating contact and disassembly prior- ity relationships among constituting components of the product. From the DHG, the disassembly constraint matrix and adjacent matrix can be deduced so that the chromosome population with a feasibility constraint was generated randomly in order to reduce the search space. The chromosome fitness function combines the total disassembly time and the penalty factor for unfeasible disassembly sequences. Based on the fitness function, the crossover and mutation operation were performed to get the optimum sequence. Finally, an example illustrates the proposed method. Key words: parallel disassembly; disassembly sequence planning; genetic algorithm 1328 计算机辅助设计与图形学学报 第 27 卷 根据零部件拆卸的逻辑次序, 拆卸可以分为 串行拆卸和并行拆卸1. 在串行拆卸中, 每次可以 拆卸一个零部件; 并行拆卸中, 一次可以同时拆卸 多个零部件. 实践中, 特别是在拆卸大型复杂产品 时, 并行拆卸有利于减少拆卸时间, 提高工作效率, 减少辅助时间等. 拆卸序列规划是根据产品结构、 装配关系等信 息, 推理出满足一定约束条件的最优化拆卸顺序 的过程2-5. 优化的拆卸序列有助于节约拆卸成本, 提高拆卸效率. 在串行拆卸序列规划方面常用的 方法包括组件紧固件图、AND/OR 图、Petri 网等 图搜索方法2-6. 这些方法便于数学分析, 但是随 着产品复杂度的提高会出现组合爆炸问题. 随着 研究的深入, 基于人工智能优化的方法的串行拆 卸序列规划成为研究热点, 如遗传算法7、蚁群算 法8-9等. 并行拆卸问题具有拆卸序列长度不确定、 拆卸 任务并行性等特点, 因此并行拆卸比串行拆卸更 为复杂. 并行拆卸规划(parallel disassembly se- quence planning,PDSP)方面的研究文献相对较少. Chen 等10基于匹配图设计了“剥蒜”法用于二维 装配体的并行拆卸序列规划, 尚未应用于三维装 配体的并行拆卸序列规划. Kang 等11通过修改 AND/OR 图构建了扩展过程图, 并提出了基于整 数规划法的并行拆卸序列生成算法, 可以精确获 得最优解, 但是该方法随着产品零部件数目的增 多会产生组合爆炸问题. 文献12提出了基于模块 化方法的选择性并行拆卸序列规划方法, 但该方 法仅仅可以应用于组件互相嵌套的情况. 文献13 提出了基于分支定界法的产品协作拆卸序列规划 方法, 可以自适应地获得拆卸序列, 但是高质量解 的获得必须以牺牲计算时间为代价. 文献14提出 了基于模糊粗糙集的并行拆卸序列规划方法, 可以 快速获得近似最优解, 但是该方法得到的解的质 量一般. 上述研究取得了重大突破, 但是在求解复杂 产品并行拆卸序列规划问题时仍然存在效率低、 易 出现组合爆炸、 适应性低等不足. 遗传算法(genetic algorithm, GA)是一种借鉴生物界适者生存的进化 规律演化而来的人工智能全局搜索算法, 能够在 较大样本空间搜索到全局最优解. GA 已在串行拆 卸序列规划中得到了应用7,15, 但是在并行拆卸序 列规划方面尚未有应用的报道. 为此, 针对并行拆 卸序列规划问题的特点, 本文提出并行拆卸序列 规划问题的染色体编码方案和遗传进化算子, 实 现了复杂产品并行拆卸序列规划的高效求解. 1 基本定义 1.1 产品拆卸混合图模型 产品的拓扑结构可表示为拆卸混合图模型 ffcc ,GV EEE, 其中, 顶点 12 , n v vvV 代表最小拆卸单元(如零件、 子装配体), n 为最小拆 卸单元个数; 物理约束 ff1f2f , k eeeE表示组 件间只存在接触关系, 以无向边表示; 强物理约束 fcfc1fc2fc , m eeeE 表示组件间存在拆卸优先 级和接触约束, 即组件间存在接触约束且在某个 拆卸方向(如,XYZ)上存在拆卸优先级, 以有 向实线边表示; 空间约束 cc1c2c , k eeeE表示 非接触组件间在某个拆卸方向存在拆卸优先关系, 以有向虚线边表示14. 由 G 推导出邻接矩阵 r M和约束矩阵 con M， 即 r . ij n n mr M 其中, ffcfc 1,( , )or,or, . 0,else ij i ji jj i mr EEE 当1 ij mr , 表示单元 j 与 i 存在约束, 则产品中单 元 j 有约束关系的单元数为 1 ( ) n ij i N jmr (1) con . ij n n mc M 其中, cfc 1,or, . 0,else ij i ji j mc EE 当1 ij mc , 表示单元 i 优先于 j 拆卸; 当0 ij mc , 表示单元 i 与 j 间不存在拆卸优先级关系. 则单元 j 的拆卸优先级定义为 1 ( ) n ij i P jmc (2) 当( )0P j , 单元 j 可拆卸; 否则, 不可拆卸. 图 1a 所示为轴承座部件装配图, 螺母 101 与 垫圈201接触且螺母必须先于垫圈拆卸, 属于强物 理约束, 垫圈和上盖3接触但不存在强制的拆卸优 第 7 期 张秀芬, 等: 支持复杂产品并行拆卸序列规划的遗传算法 1329 先关系, 为物理约束; 以此类推, 构建的拆卸混合 图模型如图 1b 所示. 图 1 轴承座部件及其拆卸混合图 1.2 拆卸并行度 将某时刻可同时拆卸的最小拆卸单元数定义 为拆卸并行度, 并记为 DP. 由拆卸并行度定义可知, 并行拆卸的并行度 与操作人员数等有关, 设 k 个操作者集合M 12 , k mmm, 则 P 1Dk. 当拆卸并行度为 1 时, 为传统的串行拆卸问题. 拆卸并行度可以根 据产品复杂程度和操作人员数目设定. 1.3 并行拆卸序列规划问题 设某产品具有 n 个最小拆卸单元(零件或部件), 则产品并行拆卸序列规划问题描述如下： 已知产品 的拆卸混合图 ffcc ,GV EEE, 拆卸并行度 DP 和 n 个节点的基本拆卸时间 12 , n t ttT, 则并 行拆卸序列规划问题就是求满足以下约束条件的 最小拆卸单元的可行拆卸序列：1) 最小化目标函 数(如总拆卸时间); 2) 最大化拆卸并行度; 3) 各零 件的不同拆卸操作不能同时进行. 为减少并行拆卸序列规划问题的复杂性, 进 行如下假设： 1) 操作者工作区域的无干涉; 2) 每步拆卸任务同时执行. 2 并行拆卸序列规划问题求解 2.1 染色体编码 编码是染色体与并行拆卸序列规划问题解之 间的映射过程, 是应用GA求解问题的关键. GA的 染色体结构就是并行拆卸序列规划问题解的形式, 即每个染色体表示一个拆卸序列, 每个基因对应 每步拆卸的最小拆卸单元节点. 并行拆卸序列规划问题要对 n 个待拆卸节点 进行排序, 并且每次选择的节点数目 m 不确定 ( P 1mD), 为此, 并行拆卸序列染色体包含拆 卸单元序列和拆卸步长两部分, 分别用自然数进 行编码. 这 2 部分基因串的长度均为 n, 与图节点 数目相同, 其中拆卸单元序列是基于拆卸优先级 约