基于遗传算法的拆卸序列规划研究
2012-12-21周重威李明宇
刘 奥,周重威,李明宇
(1.华中科技大学机械科学与工程学院,湖北武汉430074;2.宁波赛维思机械有限公司,浙江宁波315135)
拆卸是采用一定的工具和手段,解除对零件造成约束的各种联接,将产品零部件逐个分离的过程。拆卸序列规划,本质上是一个NP 难题,当装配体中零件数量增加时,可拆卸序列的数量也会呈现出指数级的增长。
在解决拆卸序列规划问题时,大多数学者利用网络图结合图论和相关搜索方法,来处理此类问题。
Veerakamolmal 和Gupta 于1997年提出通过产品的模块化的特点以最小化拆装时间和费用,得出一个高效的拆装序列[1]。
Gungor 和Gupta 提出一个拆装的启发式算法[2]。
Moore 等用Petri 网对复杂产品优先关系建模来进行拆装过程规划[3]。
在国内,江吉彬、刘志峰等,提出一种基于工程语义信息的规划算法,解决拆卸序列规划理论算法存在的求解空间过大的问题[4]。
赵树恩和李玉玲采用将模糊推理Petri 网与矩阵运算相结合的形式化推理算法,实现产品拆卸序列决策[5]。
为得到满足产品要求的拆卸序列,且提高拆卸序列规划的效率及实用价值,本文依据关联矩阵和干涉矩阵,产生满足几何约束、且经初次优化的装配序列。其后,应用遗传算法优化上述初次优化的装配序列,以得到满足生产实际的拆卸序列规划。
1 拆卸序列优化模型
1.1 简化拆卸优化模型
本文主要从3个方面简化拆卸模型。
(1)紧固件及其附件的简化。在装配或拆卸的过程中,紧固件及其附件,可以看成普通零件之间的约束。当完成约束或解除约束时,紧固件及其附件即完成拆除。为保证零件间的约束关系完全,将部分标准件消隐,且部分标准件与相接触的零件相固连。
(2)装配体子装配的分离。对子装配体的定义,直接影响到子装配体的分离。对子装配体的定义如下:
子装配体中零件之间的联接关系,使子装配体成为一个不可自发分离的子结构,即子装配体为稳定结构;
子装配体中零件装配完毕后,不影响原装配体中其余零件的装配。
(3)基础件的选择。基础件作为最后拆卸的零件,对其优先选择,可以缩小搜索空间。但是基础件仍然参与联接矩阵与干涉矩阵的生成,会对拆卸产生约束作用。
1.2 联接矩阵
产品是通过零件以一定的装配关系联接而成的具有稳定结构的装配体。本文主要讨论两类基本约束关系:接触关系与可拆卸联接关系。
设装配体P 由N个零件组成,用
来表示所有零件的集合,
W={w1,w2,…wm…wN|wm缀P,且wm互异}
表示一条拆卸序列。
用布尔量B =(pi,pj)表示零件pi与零件pj的联接关系。
对于B=(pi,pj)有如下的约定:
1.3 干涉矩阵
干涉是拆卸过程中零件之间的空间制约关系及其相关性的反应。当拆卸方向选择与笛卡儿直角坐标系相同时,零件的拆卸干涉关系,指的是若产品中零件pi对零件pj的拆卸在 K(K =±X,±Y,±Z)方向上形成干涉关系,则表示在零件pi拆卸完成前,零件pj无法沿K方向拆卸。干涉关系可用干涉矩阵G 来表示,即:
其中,
gijk表示零件pi对零件pj在K方向拆卸的干涉情况。
gijk=0表示无干涉,gijk=1表示干涉存在。
规定当gijk中i=j 时,gijk=0。
由于gijk在某个坐标轴正方向与gjik相同坐标轴反方向有相同值。
1.4 拆卸序列的生成
满足几何约束的拆卸序列流程图,如图1所示。通过识别标准紧固件,可获得各零件间的可拆卸联接关系。
图1 序列生成流程图
本文中,当存在可拆卸紧固联接时,必须保留标准紧固件(如螺栓)而消隐其附件(如螺帽、垫圈等),且将标准紧固件与其后拆除的第一个零件视为一个零件。
拆卸序列生成时,参考遗传算法中轮盘赌的方式,优先选取与被拆零件有联接关系的零件作为后续拆卸对象。其中可拆卸联接关系作为第一选择,接触联接关系作为第二选择,无接触联接关系作为第三选择,通过依次选择满足要求的零件,可保证拆卸序列得到优化。
2 基于遗传算法的拆卸序列优化
本文在遗传运算的过程中,考虑交叉与变异后拆卸序列的几何可行性,对于不满足几何可行性的拆卸序列,将其舍弃,直到得到足够数量的满足几何可行性的子代。
2.1 适应度函数的构造
拆卸时间的长短,在一定程度上反应出拆卸的效率与拆卸的复杂程度。因此,本文从缩短拆卸时间的目标,来优化拆卸的序列。考虑的主要因子有:拆卸方向变换时间、拆卸工具与夹具变换时间。
(1)拆卸方向变换时间。ot(i,w)表示序列W 中零件pi的重定向时间,定义如下:
其中,t1为拆卸方向旋转90°时的拆卸方向变换时间。OT(i,w)表示序列w 中前I个零件的重定向时间之和
(2)拆卸工具变换时间。tt(i,w)表示序列W 中拆卸第i个零件时的拆卸工具变换时间。一般而言,工具之间的变换时间,随着工具的不同而不同。为简化,本文假定工具间的变换时间相同,为t2,则有
TT(i,w)表示序列W 中前i个零件拆卸时的拆卸工具变换之和
(3)拆卸夹具变换时间。拆卸工具与拆卸夹具基本相同,同理可以定义t3、ct(i,w)、CT(i,w)。
除去零件的基本拆卸时间,拆卸序列W 中前i个零件拆卸所需要的时间为DT(i,w),则有
为保证适应度值随时间增加而减小,且适应度函数为正值,定义适应度函数为
其中,C为常数,且C叟DT(i,w)。
2.2 优化算法
(1)编码。本文采用实数编码的方法,在基因组中表达装配体中零件的信息,利用4位码编码。
(2)选择操作。本文采用轮盘赌的方式,来执行选择操作,即适应度较高的拆卸序列被选择参与交叉与变异的概率较高。
(3)交叉操作与变异操作。为简化计算,本文利用吴昊所使用的交叉算子[6]与刘诚提出的变异算子[7]完成交差与变异操作。
(4)拆卸序列几何可行性判断。利用干涉矩阵,对序列中零件依次检测其可拆性,若出现某零件与未拆除零件发生干涉,则摒弃此条拆卸序列,重新进行交叉与遗传操作,直到生成满足几何可行性的拆卸序列。
本文遗传算法的操作流程图如图2。
图2 遗传算法流程图
3 实例
图3是某装配体的装配示意图,该装配体由11个零件组成,选择零件11 作为基础件。
图3 某产品装配图
为优化该装配体的拆卸序列,给定以下初始条件:
初始种群数popsize为10、交叉概率pc=0.8、染色体内部突变的概率pm=0.05,C=500。
利用联接矩阵与干涉矩阵,通过Matlab 编程,得到满足几何约束的部分拆卸序列如下:
计算得到的每一代的最大适应度值如图4所示。
图4 子代中最大适应度值
仿真生成的拆卸序列如表1所示。
表1 拆卸序列规划结果
4 结束语
本文获取了联接矩阵和干涉矩阵,构建了产品拆卸模型。利用干涉矩阵和联接矩阵,产生满足几何约束,且经过初次优化的拆卸序列。利用优化的遗传算法,对拆卸序列进行了优化。最后,利用一个实例,来验证了本方法的可行性以及此种遗传算法的可行性。
[1]Veerakamolmal P,Gupta S M,McLean C R.Disassembly process planning [C].In:First International Conference on Engineering Design and Automation,Bangkok:Thailand,1997.
[2]Gungor A,Gupta SM.An Evaluation Methodology for Disassembly Processes [J].Computers and Industrial Engineering,1997,33(1):329-332.
[3]Moore K E,Gungor A,Gupta S M.Petri Net Approach to Disassembly Process Planning for Products with Complex AND/OR Precedence Relationships [J].European Journal of Operational Research,2001,135(2):428-449.
[4]江吉彬,刘志峰,刘光复.基于工程语义信息的拆卸序列规划算法研究[J].计算机集成制造系统,2006,12(4):625-629.
[5]赵树恩,李玉玲.模糊推理Petri 网及其在产品拆卸序列决策中的应用[J].控制与决策报,2005,20(10):1181-1184.
[6]吴 昊,左洪福.基于改进遗传算法的产品拆卸序列规划[J].中国机械工程,2009,20(6):699-703.
[7]刘 诚,付宜利.引入基因修复技术的产品装配序列规划方法[J].哈尔滨工业大学学报,2010,42(1):79-81.