论文部分内容阅读
【摘 要】为深入研究机电装配体拆卸序列的自动生成和优化问题，本文首先建立了装配体的自由-干涉矩阵，并将其作为描述机电装配体结构的数学模型，并在此基础上提出了“拆卸楔”概念和具体算法，依照此法计算机电装配体上各个零件的拆卸序列和方向，最后基于遗传计算的早敛问题提出搜索-遗传组合优化算法，将搜索算法中的集中策略适当引入到遗传算法中，可以获得相对健壮的搜索行为。此外，本文还提出了一种关于初始拆卸序列群体的自动生成算法，实践表明，这种自动生成算法能够有效的解决机电装配体拆卸序列的优化组合问题，而且生成的拆卸序列在数据方面均优于单纯遗传算法结果。
【关键词】机电装配体；拆卸序列；遗传算法；搜索算法；优化组合
随着人们环保意识的提高，制造业所产生的废料作为主要污染源逐渐受到全社会的广泛关注，因此，如果有一种方法能够对固体废弃装配体进行科学有序的重新组合，不仅可以回收零件材料，而且还便于毒害物质处理。机电装配体拆卸序列指人们将零件从装配体上拆卸下来的顺序，这个过程直接影响到拆卸的耗时和所选工具种类，以往人们常常根据经验来安排拆卸序列，拆卸效率不高，因此，有必要创建一种系统化、自动化的拆卸序列组合模式。
一、构建装配体结构模型
要清晰的研究装配体拆卸序列，首先需要了解和清除描述各零件之间的拓朴信息和几何关系，并在此基础上考虑拆卸序列组合的可行性，利用自由-干涉矩阵表达最优关系。图1就是一个典型的自由-干涉矩阵，0-7表示各个零件，-x、+x、+y表示零件可拆卸的方向，图1中仅有8个零件，矩阵表达虽然比较简单，但是这种方法能够用于零件数量更多、更加复杂的装配体拆卸优化，而且随着零件数量的增多，矩阵规模也会随之增大，但是从矩阵中可以清楚地了解零件之间的关系。无干涉拆卸序列可以通过自由-干涉矩阵检测出来，零件可以从装配体上无干涉拆卸下来的方向就是该零件的“拆卸楔”[1]。
图1 装配体干涉-自有矩阵示例
二、遗传算法和搜索算法的优化组合
（一）遗传算法
遗传算法是在模拟生物进化过程中衍生出来的一种优化算法，近年来在遗传算法领域的研究热度有增无减，并逐渐渗透到计算机科学、组合优化、工程设计、优化调度等各个领域。遗传算法以目标函数（也称适应度函数）为基础，目的在于由机电产品原生产厂家对大批量生产之后的废弃物进行拆卸回收，为此，需要由原生产厂家将产品装配线改造为产品拆卸线，在拆卸生产线上，要实现全部零件拆卸就需要涉及零件转向问题，只有确保装配体能够转换方向或者实现翻转，才能使装配体上的零件全部拆卸完毕，这个转向过程需要投入大量资金，而且还要用到专业的机械手和夹具，因此，需要设计最少装配体转向次数，目标函数可以表述为：
fitness= 2n-r（ds）， 可行的拆卸序列，
fitness= 2， 不可行的拆卸序列.
其中，n表示装配体上需要拆卸的零件数量，r（ds）表示需要经过的拆卸转向次数，由于不可行的拆卸序列会因为不满足最优几何条件导致拆卸过程中出现干涉问题，因此，计算开始时需要赋予低值目标，并使其在以后的迭代计算中逐渐被淘汰掉[2]。
（二）搜索算法
搜索策略最早是由Glover于1986年提出来的，这种方法是在局部邻域搜索研究上扩展出来的一种新的算法，是一种全局优化算法。搜索算法通过在计算中引入一个存储结构和禁忌标准来避免出现迂回搜索问题，并赦免一些禁忌的优良状态，进而保证有效全局搜索，最终实现全局搜索最优化。
（三）遗传算法与搜索算法组合优化算法
将遗传算法和搜索算法进行组合优化涉及离散最优问题，近年来出现的新型算法在组合优化问题中得到了广泛的应用，并在一些难度极高的组合问题中找到了突破口。本次研究在充分考虑装配体拆卸原则的基础上对两种算法进行重组，同时还将装配体零件之间的空间关系和几何约束关系考虑在内。组合算法与单纯使用遗传算法不同，需要引入禁忌表结构，而且还要存放每一次迭代计算之后得出的最优解序列，并用禁忌周期来控制解集，以免出现陷于某个最优解邻域无法摆脱的境地[3]。
（四）优化拆卸序列初始群体
基于遗传算法和搜索算法的组合算法，在研究装配体拆卸序列时，为了达到最优解，需要利用遗传算子（交叉、移序、变异、复制）对初始拆卸序列进行操作，并逐步找到次优解或最优解。现在常用的优化拆卸序列初始群体的方法有两种，一种是直接由用户提供若干可供拆卸序列，另一种是借助随机函数生成器来得到若干初始拆卸序列[4]。通过大量的实验比较可以得知，任何算法的搜索效率都直接取决于初始群体质量，如果在上述第一种初始序列生成方法中，用户提供的群体质量较好，那么搜索效率就会相对较高，但是用户在提供拆卸序列初始群体的过程中，也需要耗费大量的人力和物力，此外，第二种随机生成的方法虽然不需要大量的人力参与，在生成的序列中也会存在大量的不可行拆卸序列，同样降低了遗传算法的拆卸序列。
为此，本文提出了一种全新的可以自动生成初始拆卸序列群体的方法，具体方法为：利用装配体的自由-干涉矩阵和“拆卸楔”计算方法，确定零件的可拆卸方向，如果初始群体中的每个零件都含有至少一个拆卸方向，那么此序列就是可行的，因此，可以通过生成一系列可行的拆卸序列为组合优化起点，如此一来，就在上述两种方法之间找到了平衡点，既保证了搜索效率，又大大降低了人力物力成本。通过实验可以得知，初始可行序列个数与末时可行序列个数存在对比关系，总体趋势是随着初始序列个数的增加而增加[5]。
三、应用实例研究
基于遗传算法和搜索算法的优化组合算法已经在微机VC++6.0编程中得到了实际应用，其应用目标是寻找若干拆卸序列，这些拆卸序列与初始序列相比，不仅可以保持几何可行性，而且用到的夹具和转向次数也最少。本文采用多个模拟装配体进行实际检验，发现这些装配体虽然都是用积木块的形式表达的，但是均具有典型性。使用组合算法，在遗传算法中加入搜索算法，其实际应用效果是非常显著的，单纯的采用遗传算法，只能得到近似最优解，但是通过组合算法可以得到更加精确的近似最优解，虽然遗传算法在迭代十几代之后也可以得到精确近优解，但是之后会逐渐收敛，这也说明遗传算法本身并不能产生更加令人信服的候选解，而且还会诱导满目搜索。
四、结语
本文主要介绍了机电装配体零部件的拆卸序列优化问题，在自由-干涉矩阵的基础上提出了计算拆卸方向的方法，将遗传算法与搜索算法结合生成一种全新的组合算法，并通过实际检验证实了这种组合算法的可行性。
参考文献：
[1]赵流现，刘志峰，李新宇，等.基于智能材料主动拆卸技术的产品多级主动拆卸方法及其设计准则研究[J].中国机械工程，2011，07：848-852.
[2]赵柏萱，刘检华，宁汝新，等.一种基于运动规划的选择拆卸序列规划技术[J].机械工程学报，2014，07：136-145.
[3]李海军，姜楗，王云飞. 基于扩展干涉矩阵和遗传算法的拆卸序列规划[J]. 计算机工程与设计，2013，03：1064-1068.
[4]孙占磊，赵罡，韩鹏飞，等. 基于非正交干涉矩阵的飞机装配序列规划方法[J]. 北京航空航天大學学报，2013，05：615-620.
[5]陈颖悦，吴豪杰. 基于改进遗传算法的拆卸序列优化研究[J]. 厦门理工学院学报，2014，05：72-77.
【关键词】机电装配体；拆卸序列；遗传算法；搜索算法；优化组合
随着人们环保意识的提高，制造业所产生的废料作为主要污染源逐渐受到全社会的广泛关注，因此，如果有一种方法能够对固体废弃装配体进行科学有序的重新组合，不仅可以回收零件材料，而且还便于毒害物质处理。机电装配体拆卸序列指人们将零件从装配体上拆卸下来的顺序，这个过程直接影响到拆卸的耗时和所选工具种类，以往人们常常根据经验来安排拆卸序列，拆卸效率不高，因此，有必要创建一种系统化、自动化的拆卸序列组合模式。
一、构建装配体结构模型
要清晰的研究装配体拆卸序列，首先需要了解和清除描述各零件之间的拓朴信息和几何关系，并在此基础上考虑拆卸序列组合的可行性，利用自由-干涉矩阵表达最优关系。图1就是一个典型的自由-干涉矩阵，0-7表示各个零件，-x、+x、+y表示零件可拆卸的方向，图1中仅有8个零件，矩阵表达虽然比较简单，但是这种方法能够用于零件数量更多、更加复杂的装配体拆卸优化，而且随着零件数量的增多，矩阵规模也会随之增大，但是从矩阵中可以清楚地了解零件之间的关系。无干涉拆卸序列可以通过自由-干涉矩阵检测出来，零件可以从装配体上无干涉拆卸下来的方向就是该零件的“拆卸楔”[1]。
图1 装配体干涉-自有矩阵示例
二、遗传算法和搜索算法的优化组合
（一）遗传算法
遗传算法是在模拟生物进化过程中衍生出来的一种优化算法，近年来在遗传算法领域的研究热度有增无减，并逐渐渗透到计算机科学、组合优化、工程设计、优化调度等各个领域。遗传算法以目标函数（也称适应度函数）为基础，目的在于由机电产品原生产厂家对大批量生产之后的废弃物进行拆卸回收，为此，需要由原生产厂家将产品装配线改造为产品拆卸线，在拆卸生产线上，要实现全部零件拆卸就需要涉及零件转向问题，只有确保装配体能够转换方向或者实现翻转，才能使装配体上的零件全部拆卸完毕，这个转向过程需要投入大量资金，而且还要用到专业的机械手和夹具，因此，需要设计最少装配体转向次数，目标函数可以表述为：
fitness= 2n-r（ds）， 可行的拆卸序列，
fitness= 2， 不可行的拆卸序列.
其中，n表示装配体上需要拆卸的零件数量，r（ds）表示需要经过的拆卸转向次数，由于不可行的拆卸序列会因为不满足最优几何条件导致拆卸过程中出现干涉问题，因此，计算开始时需要赋予低值目标，并使其在以后的迭代计算中逐渐被淘汰掉[2]。
（二）搜索算法
搜索策略最早是由Glover于1986年提出来的，这种方法是在局部邻域搜索研究上扩展出来的一种新的算法，是一种全局优化算法。搜索算法通过在计算中引入一个存储结构和禁忌标准来避免出现迂回搜索问题，并赦免一些禁忌的优良状态，进而保证有效全局搜索，最终实现全局搜索最优化。
（三）遗传算法与搜索算法组合优化算法
将遗传算法和搜索算法进行组合优化涉及离散最优问题，近年来出现的新型算法在组合优化问题中得到了广泛的应用，并在一些难度极高的组合问题中找到了突破口。本次研究在充分考虑装配体拆卸原则的基础上对两种算法进行重组，同时还将装配体零件之间的空间关系和几何约束关系考虑在内。组合算法与单纯使用遗传算法不同，需要引入禁忌表结构，而且还要存放每一次迭代计算之后得出的最优解序列，并用禁忌周期来控制解集，以免出现陷于某个最优解邻域无法摆脱的境地[3]。
（四）优化拆卸序列初始群体
基于遗传算法和搜索算法的组合算法，在研究装配体拆卸序列时，为了达到最优解，需要利用遗传算子（交叉、移序、变异、复制）对初始拆卸序列进行操作，并逐步找到次优解或最优解。现在常用的优化拆卸序列初始群体的方法有两种，一种是直接由用户提供若干可供拆卸序列，另一种是借助随机函数生成器来得到若干初始拆卸序列[4]。通过大量的实验比较可以得知，任何算法的搜索效率都直接取决于初始群体质量，如果在上述第一种初始序列生成方法中，用户提供的群体质量较好，那么搜索效率就会相对较高，但是用户在提供拆卸序列初始群体的过程中，也需要耗费大量的人力和物力，此外，第二种随机生成的方法虽然不需要大量的人力参与，在生成的序列中也会存在大量的不可行拆卸序列，同样降低了遗传算法的拆卸序列。
为此，本文提出了一种全新的可以自动生成初始拆卸序列群体的方法，具体方法为：利用装配体的自由-干涉矩阵和“拆卸楔”计算方法，确定零件的可拆卸方向，如果初始群体中的每个零件都含有至少一个拆卸方向，那么此序列就是可行的，因此，可以通过生成一系列可行的拆卸序列为组合优化起点，如此一来，就在上述两种方法之间找到了平衡点，既保证了搜索效率，又大大降低了人力物力成本。通过实验可以得知，初始可行序列个数与末时可行序列个数存在对比关系，总体趋势是随着初始序列个数的增加而增加[5]。
三、应用实例研究
基于遗传算法和搜索算法的优化组合算法已经在微机VC++6.0编程中得到了实际应用，其应用目标是寻找若干拆卸序列，这些拆卸序列与初始序列相比，不仅可以保持几何可行性，而且用到的夹具和转向次数也最少。本文采用多个模拟装配体进行实际检验，发现这些装配体虽然都是用积木块的形式表达的，但是均具有典型性。使用组合算法，在遗传算法中加入搜索算法，其实际应用效果是非常显著的，单纯的采用遗传算法，只能得到近似最优解，但是通过组合算法可以得到更加精确的近似最优解，虽然遗传算法在迭代十几代之后也可以得到精确近优解，但是之后会逐渐收敛，这也说明遗传算法本身并不能产生更加令人信服的候选解，而且还会诱导满目搜索。
四、结语
本文主要介绍了机电装配体零部件的拆卸序列优化问题，在自由-干涉矩阵的基础上提出了计算拆卸方向的方法，将遗传算法与搜索算法结合生成一种全新的组合算法，并通过实际检验证实了这种组合算法的可行性。
参考文献：
[1]赵流现，刘志峰，李新宇，等.基于智能材料主动拆卸技术的产品多级主动拆卸方法及其设计准则研究[J].中国机械工程，2011，07：848-852.
[2]赵柏萱，刘检华，宁汝新，等.一种基于运动规划的选择拆卸序列规划技术[J].机械工程学报，2014，07：136-145.
[3]李海军，姜楗，王云飞. 基于扩展干涉矩阵和遗传算法的拆卸序列规划[J]. 计算机工程与设计，2013，03：1064-1068.
[4]孙占磊，赵罡，韩鹏飞，等. 基于非正交干涉矩阵的飞机装配序列规划方法[J]. 北京航空航天大學学报，2013，05：615-620.
[5]陈颖悦，吴豪杰. 基于改进遗传算法的拆卸序列优化研究[J]. 厦门理工学院学报，2014，05：72-77.