（机械设计及理论专业论文）面向装配序列规划的遗传模拟退火算法研究.pdf

华中科技大学硕士学位论文 摘要 装配序列规划在产品开发中占有十分重要的地位，是决定产品装配质量和装配成本 的重要因素。近年来，众多学者在这一领域开展了富有成效的研究和探索。本文针对现 有装配序列规划方法的局限性，特别是基于智能计算的遗传算法和模拟退火算法求解装 配序列规划问题的不足之处，提出构造遗传模拟退火算法进行装配序列规划。 首先，总结了国内外有关装配序列规划研究成果和遗传模拟退火算法在其它优化问 题领域的应用情况。f 详细阐述了遗传算法和模拟退火算法原理、步骤及其应用中的基本 问题，并结合装配序岁n 规划实例，分析了它们求解装配序列规划问题的优缺点及其原因。t 其次，提出将遗传算法和模拟退火算法有机地结合，取长补短，构造遗传模拟退火 算法求解装配序列规划问题。n 羊细论述了算法的思想、方法、步骤及其关键操作，并深 入研究了控制参数选取原则，旨在获得更好的算法性能。，) r ) 再次，研究了装配序列的几何可行性和装配过程的稳定性挺立集成干涉矩阵分析、 判别装配序列的几何可行性，推导零件在装配过程中的可行装配方向集：建立联接矩阵 和支撑矩阵判别装配过程的稳定性一卉 ， 最后，阐述了面向装配序列规划的遗传模拟退火算法的实现方法；潞合产品实例，分 别用遗传算法、模拟退火算法、遗传模拟退火算法进行装配序列规划，并对规划过程和 结果进行了对比分析和说明，验证了遗传模拟退火算法求解装配序列规划i 句题的可行性 和优越性。总结了全文，并对今后的研究工作进行了展望。以万一 关键词：装配序列规划，遗传算法，模拟退火算法，遗传模拟退火算法 4。-_m1_h_hh_ i 华中科技大学硕士学位论文 a b s t r a c t a s s e m b l ys e q u e n c ep l a n n i n gp l a y sa ni m p o r t a n tr o l ei nt h ep r o d u c td e v e l o p m e n tp r o c e s sa n di sa n i m p o r t a n tf a c t o rt h a td e t e r m i n e st h eq u a l i t ya n dc o s to fp r o d u c ta s s e m b l y m a n yr e s e a r c h e r sh a v ed o n e f r u i t f u lw o r k si nt h i sf i e l d i nv i e wo f t h el i m i t a t i o n so f t r a d i t i o n a lm e t h o d s f o ra s s e m b l y s e q u e n c ep l a n n i n g ， e s p e c i a l l yt h o s eb a s e do ng e n e t i ca l g o r i t h ma n ds i m u l a t e da n n e a l i n ga l g o r i t h mr e s p e c t i v e l y , t h eg a s a ( g e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h m ) i sp r o p o s e dt os o l v et h ea s s e m b l ys e q u e n c ep l a n n i n gp r o b l e m f i r s t l y , t h ea u t h o rs u m r n a r i z e st h er e l e v a n tr e s e a r c h e so na s s e m b l ys e q u e n c ep l a n n i n g a n dt h ea p p l i c a t i o no f g e n e t i ca l g o r i t h ma n ds i m u l a t e da n n e a l i n ga l g o r i t h m t h ep r i n c i p l e s p r o c e s sa n db a s i cp r o b l e m so fg e n e t i ca l g o r i t h ma n ds i m u l a t e da n n e a l i n ga l g o r i t h ma l e e x p a t i a t e dr e s p e c t i v e l y f u r t h e r , t h em e r i t sa n dw e a k n e s so fe a c ha l g o r i t h mi na s s e m b l y s e q u e n c ep l a n n i n g a r ea n a l y z e d b yc o m p a r i s o n n e x t ，t h ei d e ao fc o m b i n i n gt h et w oa l g o r i t h m si n t og e n e t i c - s i m u l a t e d a n n e a l i n g a l g o r i t h mi sp u tf o r w a r d ，w h i c ha i m sa ti m p r o v i n gt h ee f f i c i e n c yo fp r o b l e ms o l v i n g t h e m o t i v a t i o n ，m e t h o d ，p r o c e d u r ea n dk e yt e c h n i q u e so fg a s a a r ea d d r e s s e di nd e t a i l ，a n dt h e p r i n c i p l e sf o rs e l e c t i n gp a r a m e t e r s a r es t u d i e dt ua c h i e v eb e t t e rp e r f o r m a n c eo f t h ea l g o r i t h m t h i r d l y , t h eg e o m e t r i c a lf e a s i b i l i t y o fa s s e m b l ys e q u e n c ea n ds t a b i l i t yo fa s s e m b l y p r o c e s sa r es t u d i e d a ni n t e g r a t e di n t e r f e r e n c em a t r i xi sc r e a t e dt oa n a l y z et h eg e o m e t r i c a l f e a s i b i l i t yo f a s s e m b l ys e q u e n c ea n d d e d u c et h es e to f f e a s i b l ea s s e m b l yd i r e c t i o n so f p a r t si n t h ea s s e m b l y p r o c e s s t h el i n k i n gm a t r i xa n ds u p p o r t i n g m a t r i xa r eu s e dt oj u d g et h es t a b i l i t y o f a s s e m b l yp r o c e s s f i n a l l y t h eg a s aa l g o r i t h mf o ra s s e m b l ys e q u e n c ep l a n n i n gi si m p l e m e n t e da n da p r o t o t y p es y s t e mi sd e v e l o p e d 1 1 1 eg e n e t i ca l g o r i t h m ，s i m u l a t e da n n e a l i n ga l g o r i t h ma n d g a s a a r ea p p l i e dt oa s s e m b l yp l a n n i n gs e q u e n c e so fa s s e m b l yc a s e sr e s p e c t i v e l y , a n dt h er e s u l t s v e t 【f yt h ea d v a n t a g eo fo a s aa l g o r i t h mi ns o l v i n gt h ep r o b l e m so fa s s e m b l ys e q u e n c ep l a n n i n g f i n a l l y t h ew o r k o f t h et h e s i si ss u m m a r i z e da n dt h ef u t u r er e s e a r c h sa r eg i v e n k e y w o r d s ：a s s e m b l ys e q u e n c ep l a n n i n g ，g e n e t i ca l g o r i t h m ，s i m u l a t e da n n c a l m ga l g o r i t h m ， g e n e t i c s i m u l a t e da n n e a l i n ga l g o r i t h m i i 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 一 = ： 1 1 研究背景 1 绪论 二十一世纪全球经济一体化趋势不断发展，企业和市场的竞争日趋激烈。竞争有力 地推动着社会进步，使技术得到空前发展；同时竞争也给企业造成了严酷的生存环境。 国际化竞争的环境要求企业对市场瞬息变化作出迅速准确的反应，企业必须以最短的开 发时间( t ) 、最好的质量( q ) 、最低的成本( c ) 、最优的服务( s ) 和最清洁的环境( e ) 提供新产品来满足不同顾客的个性化需求。t q c s e 已成为现代企业共同追求的目标。 长期以来，新产品开发一直采用“抛过墙”式的串行开发模式，其设计、工艺、制 造过程顺序完成。它存在很多不足：部门之间信息交流不畅；产品开发过程中增加了许 多不增值的环节：设计、制造更改反馈频繁，产品开发周期延长。这种传统的串行开发 模式使产品的可制造性、可装配性、可维护性较差，从而导致设计改动量大，产品开 发周期长，产品成本高的结果。在竞争日益激烈的今天，串行开发模式显然已经不太适 用。现代企业迫切需要采用有效的产品开发模式，力图克服传统开发模式的种种弊端。 在这背景下，并行工程( c o n c u r r e n te n g i n e e r i n g ，c e ) 作为种新出现的产品开发模 式，正日益受到国内外众多研究单位和制造企业的重视。 1 9 8 8 年美国国防部完整地提出了并行工程的概念：“并行工程是对产品及其相关过 程( 包括制造过程和支持过程) 进行并行、一体化设计的一种系统化的工作模式。这种 工作模式力图使产品开发人员从设计一开始就考虑整个生命周期中从概念形成到产品 报废的所有因素，包括质量、成本、进度与用户需求”。并行工程是对传统产品开发模 式的种根本性改进，是一种新的设计哲理。与串行开发模式相比，并行工程是集成地、 并行地设计产品及其相关过程的系统化方法，它要求设计人员从设计一开始就考虑产品 生命周期中的各种因素。实施并行工程的目的是缩短产品开发周期，提高产品质量，降 低产品成本n 2 1 1 3 1 。 面向装配的设计( d e s i g nf o ra s s e m b l y ，d f a ) 是并行工程的重要组成部分之一。 1 9 7 7 年，b o o t h r o y dp 和d e w h u r s tg 提出d f a 这一术语。d f a 主要研究在产品设计的 早期阶段，尽早地考虑产品零部件的可装配性、装配过程难易程度、装配成本、装配序 列和装配路径等各种因素，根据面向装配的评价体系进行综合评价和分析，为产品设计 提出合理的修改意见，选出较优的装配工艺，为制定产品装配工艺规程提供指导性意见， 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = 2 = = = = = = = = = = = = = ；= = = 一一= 从而提高产品下游设计与制造的一次成功率【4 】【5 1 。 在8 6 3 c i m s 重大关键技术攻关项目“并行工程”中，d f a 是一项支撑技术，同 时也是作为体现c e 应用效果的重要方面。国内d f a 研究主要集中于装配序列规划、公 差分析与综合、装配过程仿真与动态干涉检查、机构运动分析与仿真等。经过几年的研 究和开发，已取得了一定成果。在国外，一些大的制造企业如i b m ，d e c 等，d f a 已得到广泛应用，取得了显著效益。d f a 正日益成为并行工程领域的一个研究热点和装 配自动化研究领域的一项重要内容。 装配序列规划( a s s e m b l ys e q u e n c e sp l a n n i n g ，a s p ) 是d f a 研究的一个重要内容， 许多学者在这一领域开展了富有成效的研究和探索，取得了很大的进步。然而，迄今为 止，基于图搜索算法的a s p 方法很可能存在装配序列“组合爆炸”现象：近年来出现 的基于智能计算的a s p 方法克服了“组合爆炸”闯题，但装配序列规划过程中生成可 行序列仍有一定难度，且难以找到最优装配序列。因此，装配序列规划研究仍然是并行 工程和产品设计领域的一个研究热点。 1 。2 课曩的提出、目的及意义 本课题来源于国家自然科学基金资助重大项目蔓嵬- 产溜自锈沩凭迸掬罐l 菇衣 孝f 善动砑嘲口子课题，课题名为：支持产品创新设计的知识获取、组织、传递及运用 研究该项目编号为：5 9 9 9 0 4 7 0 - - 2 。 研究表明，在现代制造业中，大约1 3 左右的人力在从事有关产品装配活动。超过 4 0 以上的生产费用用于产品装配，装配工作量占整个产品制造工作量的2 0 7 0 ， 平均起来为4 5 。装配时间占整个产品制造时间的4 0 6 0 ，且装配工作占用的手工 劳动量较大，装配阶段的费用是很高的。因此，提高装配生产率、减少装配成本所带来 的经济效益十分显著。 装配序列规划在很大程度上决定着产品的装配费用。它主要研究产品装配顺序、方 法、工具的描述问题，其中确定产品装配顺序是装配序列规划的核心。a s p 研究最早起 源于人工智能中自动规划的研究，主要用于机器人装配和生产自动化领域。尽管经过了 多年研究，仍然存在很多不完善之处。一方面，当产品零件数目较多时，装配顺序的生 成还是比较困难；另一方面，在诸多可行装配顺序中，如何寻找最优装配顺序也仍然是 装配序列规划研究中的一个难点一j 。 本课题的研究目的是在分析和总结现有装配序列规划方法，特别是利用遗传算法 ( g e n e t i ca l g o r i t h m ，g a ) 和模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m ，s a ) 求解 a s p 问题的基础上，充分运用g a 和s a 求解a s p 问题的优越性：g a 搜索效率较高， 2 华中科技大学硕士学位论文 = = = i = # = = = = ；= = = 一一 能够在较少的时间里寻找到一个近似最优装配序列，算法具有良好的收敛性能；s a 能 够以定的概率接受“恶化”的装配序列解，能够摆脱局部最优装配序列的“陷阱”， 更有可能找到全局最优装配序列。在此基础上，提出种更加有效的装配序列规划方法， 构造遗传模拟退火算法进行装配序列规划，力图找到最优装配序列指导产品装配，达到 降低装配成本的目的。因此开展本研究具有十分重要的现实意义。 f 3 文献综述 1 3 1 装配序列规划研究 装配顺序是装配序列规划最基本的信息，产品中零件之间的几何关系、物理结构及 功能决定了产品的装配顺序。装配序列规划方法分为两大类：直接法和间接法。直接法 是与产品实际装配过程相对应的装配序列规划方法。它是根据产品设计要求，先确定装 配基准和具有特定功能的子装配体，然后根据装配建模系统建立的产品装配等级模型、 零件几何信息以及零部件之间的约束信息规划产品的装配顺序。这类方法和产品设计过 程对应，并可利用产品装配建模过程中零部件装配的序列信息。间接法是通过拆卸装配 体来确定拆卸顺序，以拆卸顺序的逆序作为装配顺序，拆卸法进行装配序列规划必须满 足装配过程和拆卸过程互为逆过程这前提条件【7 】【8 1 。 1 3 1 1 经典装配序列规划方法 ( 】) 基于装配优先关系的装配序列规划方法 装配优先关系( a s s e m b l yp r e c e d e n c er e l a t i o n s ) 是指产品中某组零件之间的装配顺序 先后关系，这种关系是随装配体结构设计而确定的、内在的、隐含的一种几何约束关系， 这种关系旦违背，则无法完成最终装配。例如，若零件p i 装配之后阻碍了零件p l 的 装配，则零件p i 必须优先于零件p i 的装配，否则装配过程无法最终完成，所以零件p i 和p i 之间存在装配顺序优先关系。一旦所有的装配顺序优先关系被完备并正确地推理出 来，装配序列规划问题就成为在装配优先关系约束条件下几何可行装配顺序的搜索算法 设计问题【9 】【10 1 。 b o u r j a u l t 提出了基于装配优先关系的装配顺序生成方法，他最早建立了产品零件的 联接图装配模型【l l 】。联接图装配模型是一种二维拓扑结构图，图中各个节点代表装配体 中的零件，节点之间的连接弧线代表各个零件之间的装配连接关系。b o 嫡a u l t 以联接图 装配模型为基础，通过对联接图分析处理，针对装配操作的几何可行性，产生一系列 y e s - n o 形式的问题，采用人机交互回答这些问题获得产品零件之间的装配顺序优先约束 华中科技大学硕士学位论文 = = = = = = ；= = = = = = = = = = = = = = = = = = = = = = = 。= 一 关系，并以此推导出装配序列。b o u r j a u l t 提出下列两个问题1 1 2 1 1 3 ： 1 、装配关系l j 和l k 完成后，装配关系l i 不能完成吗? 2 、装配关系b 和l k 未完成时，装配关系l i 不能完成吗? 由于该方法需要用“y e s ”或“n o ”回答所有联接关系之间的优先关系，提问题的 个数大约为2 l 2 + 2 l ( l 为装配体中l i a i s o n s 的总数) ，按l 2 增长。当装配体中零件数较 多时，需要回答的问题量太大，不具有实用性。 d e f a z i o 和w h i t n e y 针对b o u r j a u l t 的方法需要回答大量问题的缺点，改进了提问和 回答方式，与b o u r j a u l t 的方法相对应，提出如下两个问剐1 4 】： 1 、哪些装配关系必须在完成装配关系l i 之前完成? 2 、哪些装配关系必须在完成装配关系l i 之后完成? d ef a z i o 和w h i t n e y 设计的提问需要用户通过对产品装配结构进行推理和预测之 后，穷举出各个装配连接所有的装配优先关系，与b o u r j a u l t 设计的提问方式相比较，这 种方式的提问次数减少了，只有装配体中所包含的装配连接数目的两倍，只按l 增长。 提问数量虽然大大减少了，却增加了回答问题的难度，在回答闯题的过程中不可避免地 会出现错误，装配优先约束关系的完备性和正确性也就难以保证。 b a l d w i n 等人在b o u r j a u l t 和d ef a z i o 工作的基础上，输入信息为联接图装配模型， 为了减少向用户的提问次数，该方法中应用了如下三条推理简化准则【”l ： 1 、对于无效的分解或连接方式不提问。 2 、子集准则：如果两个零件由于几何干涉无法装配，那么，在任一零件中增加一 个零件同样不能装配。 3 、超集准则：如果两个组件可以装配，那么去掉两组件中和另外组件不发生装配 关系的任何零件，两组件仍然可以装配。 上述规则可回答b o u r j a u l t 和w h i t n e y 提出的部分问题，使操作人员回答的问题进一 步减小，回答问题时出现遗漏和错误的可能性也大大减小。经过上述人机交互提问和回 答后，可以获取装配顺序优先约束关系，并可求得装配序列。 此外，h e e d o n gk o 和k u n w o o l e e 对装配体中零件的约束进行了分析，提出生成装 配体中零件的部分优先关系层次结构，找出其余的优先关系，从而获得装配序列【i “。 装配优先约束关系是表达零件装配先后顺序的一种非常紧凑的方法。这种方法的关 键是装配优先关系的获取。采用人机交互的方法，工作量大，对操作人员要求高，而且 容易出错。自动获取优先关系则有一定的难度，然而一旦获得零件装配的优先关系，则 能很容易地求得零件的装配顺序。 ( 2 ) 基于拆卸法的装配序列规划方法 若零件的装配过程和拆卸过程互为逆过程，则可以通过零件的拆卸顺序求得零件的 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 一 装配顺序。拆卸法生成装配序列，是将装配体按照一定的约束条件进行拆卸，首先拆卸 成予装配体，然后再将子装配体拆卸成子子装配体，按照这种方式一直继续拆卸下去， 直至拆卸到单个零件，这样就得到了装配体的拆卸顺序，沿着拆卸顺序的逆序进行装配， 最终就可以得到产品的装配序列。拆卸法的关键是如何实现在一定约束条件下的拆卸任 务分解。 h o m e md em e l l o 和s a n d e r s o n 最先提出了用拆卸法求解装配顺序的系统方法f 1 7 】，该 方法能够自动推理出完备的装配顺序，其分析基础是装配体的5 维拓扑装配模型 a s s = ( p ，c ，a ，r ，f ) 。其中，p 表示装配体中各零件实体；c 表示装配体中各零件之 间的连接关系实体，a 表示各连接关系对应的装配操作实体，r 表示p u c u a 实体域中 各实体之间的关系实体；f 表示p u c u a u r 实体域上的属性值。在f 中定义了装配顺 序规划中所需的全部信息，如装配操作类型，零件形状等。它通过获取产品拆卸过程中的 零部件优先关系规划出零部件的拆卸序列，再将拆卸序列反向即可求得产品的装配序 列。他用装配序列的a n d o r 图表达产品中所有可能的装配序列【1 8 1 ，a n d o r 图中的 节点表示装配过程中的子装配体或零件，超弧表示将子装配体或零件联接在一起形成更 大子装配体的装配操作。超弧的起始点对应上一级更大子装配体，终止点对应下一级子 装配体或零件。h o m e md em e l l o 采用了“割集，算法来求得产品所有装配序列的a n d o r 图表达，他首先建立产品的联接图并进行缩并，联接图的割集就对应从产品中拆卸出的 零部件，利用“割集”算法对联接图进行循环分解，直到不可再分为止，并将满足拆卸 条件的子装配体或零件以a n d o r 图的节点进行纪录。将分解的过程用超弧联接，就 形成了产品拆卸序列的a n d o r 图，并根据一定的评价指标选择较优的装配序列【l 9 1 。 此外，h o m e md em e l l o 对割集法的计算复杂性进行了定性和定量的分析计算。认 为装配体中零件数目、零件之间的连接数等对装配顺序推理计算的复杂程度都具有指数 级的影响关系。因此，对于复杂产品的装配顺序规划，割集法的计算复杂性为0 ( 3 “) ， 故存在指数爆炸问题，这将是难以让人接受的。h o m e md em e l l o 证明了他提出的算法 的正确性和完备性。 h o n g 和c h o 等也提出了用拆卸的方法进行装配序列规划。b a l d w i n 在拆卸法的基础 上，提出了装配序列的评价方法，并建立了装配序列交互编辑的工具，使得所产生的装 配序列不仅满足几何可行性，而且满足机械设计和制造的有关要求，使得所规划的装配 序列更具有实用性拉o l 【2 1 1 1 2 2 1 。 拆卸法进行装配序列规划具有如下优点：若判断一零件满足拆卸条件，则该零件一 定满足序列约束。反之，装配过程中某一阶段满足装配条件的零件并不一定满足装配序 列约束条件，因为该零件有可能影响到后续零件的装配。另外，通过几何计算和推理可 从零部件的装配状态演绎出零部件拆卸的初始方向，而从自由状态的零部件却无法推导 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = ；= = = = = = = = = = = = = = = 一 出零部件的装配方向；间接法的局限性是必须满足装配过程与拆卸过程互为逆过程这一 假设条件。 ( 3 ) 其它装配序列规划方法 除了上述基于装配优先关系和基于拆卸法的装配序列规划方法外，还有其它一些装 配序列规划方法。g o t f i p o l u 提出一种新的装配顺序推理方法卸。该方法首先定义了两个 向量：接触向量c = c 1 ，c 2 ，c 3 ，c 4 ，c 5 ，c 6 和干涉向量t = t 1 ，3 2 ，t 3 ，t 4 ，t 5 ，3 6 ，。 其中，i = l ，2 ，3 ，4 ，5 ，6 分别表示斗x ，+ y ，+ z ，- x ，y ，z 六个方向；c i - l 表示 两个零件或子装配在i 方向上有相互接触关系：c - 0 表示两个零件或子装配在i 方向中 无相互接触关系；t i - 1 表示两个零件或子装配在i 方向上有相互干涉关系：t i - o 表示两 个零件或子装配在i 方向上无相互干涉关系。该方法对装配顺序的分析推理过程为：首 先，针对每个装配割集，利用装配体几何设计信息，求出两两零件或子装配之间的接触 向量和干涉向量。接触向量可以计算出两零件之间是否具有装配连接关系，朗装配的可 能性；装配干涉向量可以判断两个零件之间是否具有干涉关系，即装配操作的有效性。 只有装配的有效性和装配可能性同时满足，此装配操作才是可行的。如此这样，可以推 理出所有装配割集的装配可行性，从而求出所有可行的装配顺序。该方法只能适用于正 交方向装配问题，这是由接触向量和干涉向量的性质所决定的。 s w a m i n a t h a n 提出了一种基于经验的装配顺序规划方法【2 4 】。该方法将联接图装配模 型由无向图变成了有向图，并通过对各种可能装配连接方式的归纳总结，得到一些基本 的装配模式及其装配顺序。这样，对一个产品的装配顺序规划推理过程变成：首先是将 装配体表达成有向联接图模型方式。其次，将联接图拆分成三边形、四边形或五边形等 一些标准模块。然后，根据每一模块的有向联接图，通过与归纳总结出的基本模块进行 比较处理，从而得到各个模块的装配顺序。最后，通过一定方式将各模块的装配顺序组 装成整个产品的装配顺序。这种方法只能分析正交方向的装配问题，对于更为一般的装配 问题而言，这种方法便无能为力。因为该方法中应用的所有基本装配模式都是从正交装 配问题中提取出来的，对于非正交方向装配问题是不可能做到的。 1 ，3 1 2 装配序列规划软计算方法 一般情况下，从经典装配序列规划方法中产生的装配顺序都不是最优的。为了使产 品装配成本最小化，降低产品开发的总成本，有必要寻找最优的装配序列( 装配成本最 小) 或对已得到的装配序列进行优化。为了克服经典装配序列规划方法的局限性，近年 来，人们将基于智能计算的软计算方法引入装配规划研究中，取得了一定成果。 软计算( s o f tc o m p u t i l l g ) 是随着信息技术和计算机智能化的发展而产生的几种适用 计算技术的总称，即神经网络、遗传算法、模拟退火算法、模糊逻辑控制等。软计算为 6 华中科技大学硕士学位论文 = = = = = = = = = = = = = i = = = = = = = = = = = = = = = = = = = = = 一 解决多变量、非线性系统提供了一种有效的方法，是一种新的计算模式。与传统的“硬 计算”不同，软计算并不追求问题的精确解，而允许存在不精确性和不确定性，所得到 的是精确或不精确问题的近似解。软计算是目标驱动的，即只要从长远看，计算过程是 在向目标移动，至于从当前状态到晟终状态走的是一条什么路径则是无关紧要的。同时， 特定的领域知识有助于降低计算量和搜索时间，但并不是必要的。软计算中应用了来源 于不同思想的、新颖的最优化方法，包括神经网络、遗传算法和模拟退火算法等，因而 在解决复杂化问题时具有更大的灵活性。对于一个多变量非线性系统而言，软计算方法 解决途径具有成本低、可实际操作和较高智能的特点，近年来在装配序列规划研究领域 也得到了广泛地运用【2 5 j 【2 6 】。 ( 1 ) 装配序列规划神经网络方法 神经网络( n e u r a ln e t w o r k ，n n ) 是模拟人类形象思维的一种人工智能方法，它具有自 组织、自学习能力，能以并行方式处理信息，运行速度快，因而它在智能控制、模式识 别、人工智能等方面的应用都取得了巨大的进展，在优化问题求解方面也具有巨大的优 势。神经网络是由大量神经元广泛互连而成的复杂网络系统。单一神经元可以有许多输 入、输出。神经元之间的相互作用通过连接的权值体现。神经元的输出是其输入的函数。 若将优化计算问题的目标函数与网络某种状态函数( 通常称网络能量函数) 对应起来，网 络动态向能量函数极小值方向移动的过程就可视作优化问题的求解过程，稳态点则是优 化问题的局部或全局最优解。使用n n 求解优化问题首先要把问题映射到神经网络上， 其中构造能量函数这一步至关重要，构造能量函数就是选择合适的函数使其最小值为问 题的最优解，它决定了一个特定问题能否用神经网络求解。神经网络已用于装配序列规 划研究中。 h o n g 和c h o 为了克服装配序列优化组合爆炸问题，提出用神经网络进行机器人装 配顺序优化，该方法频繁产生不优化的装配顺序，常常只能得到一个局部最优的装配序 列【2 7 1 。c h e n 提出一种方法首先将装配几何约束关系转变为装配优先关系，然后运用神 经网络进行装配顺序优化1 2 8 1 。王东云等采用神经网络进行机器人自动装配规划r g 。他首 先利用a n d o r 优先约束知识表示所有产品零件之间的装配先后关系，构造满足此优 先约束条件的h o p f i e l d 神经网络，神经网络的稳定状态对应于一个可行的装配序列， 然后利用h o p f i e l d 神经网络求解满足此优先约束条件的最佳装配序列。冯禹等采用基 于人工神经网络技术对产品可装配性进行评价f 3 0 】。他根据b o o t h r o y d 方法中提供的实验 数据【3 1 1 ，通过神经元网络学习建立了评价模型，依此模型对表征产品可装配性的装配时 间等指标进行评价，为优选设计方案和改进设计提供决策支持a ( 2 ) 装配序列规划遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，o a ) 的思想、原理和方法参见第2 章2 3 节，在此不再 华中科技大学硕士学位论文 赘述。它是模仿生物自然选择和遗传机制的随机搜索算法。鉴于遗传算法在非线性规划 及一些组合优化问题中获得了成功应用，遗传算法被引入装配序列规划研究中。 1 9 9 5 年，b o n n e v i l 等首先运用遗传算法求解装配序列规划问题。他用产品装配树表 达的装配序列作为参加进化运算的染色体，从一套给定的可行装配序列组成的初始种群 开始，利用交叉和变异两种简单遗传算子产生后代个体，在进化过程中，通过一定的评 价、选择机制生成子代种群。该算法在一定条件下能够较快地找到较好的装配序列，而 在特殊条件下可能难于找到最优的装配序列1 3 2 l 。c h e n 在装配序列规划中使用复制、交 叉、变异、剪贴和断连五种遗传算予寻找装配序列优化解。他随机给定规模固定的初始 种群，依概率选择装配序列，然后运用遗传算予进行操作产生后代个体，子代和父代个 体按照适应度值选择组成下一代个体。在后续研究中，c h e n 又提出了几种新的遗传算 子用于提高装配序列规划的性能。他的研究表明，遗传算子执行概率直接影响装配序列 规划的收敛性能和装配序列规划最终解的质量，控制遗传算子执行概率可以提高装配序 列规划的性能【3 3 】【m 】。s e b a a l yf - 等提出改进遗传算法求解装配序列规划问题，他将搜索 空间划分为一些子空间，每个子空间包含一个唯一可行装配序列。遗传算子依一定概率 选择装配序列染色体产生子代群体。在整个进化过程中，通过一个特殊变换机制不断地 将不可行装配序列变为相应子空间中的可行装配序列。该算法不需要搜索整个解空间就 能够得到一个较好的装配序列。这种方法虽然可以提高算法的效率，但启动算法的准备 工作需要花费一定时间来完成【3 5 】。廖小云提出基于遗传算法的自动装配顺序规划。他采 用产品装配树表示装配顺序，通过遗传算子对装配树进行操作，以装配方向改变次数作 为装配顺序的适应值，不需要给出可行初始序列就能够较快地自动产生出满意的装配方 案。他的研究表明，算子的操作率率对算法的收敛性和优化结果有很大影响。对某一个 具体的装配产品，存在一个最佳的算予操作率【3 6 j 。 在上述装配序列规划方法中，参与优化的对象和结果都只是装配序列，即装配序列 中仅包含产品零部件顺序信息而不包含装配操作的一些工艺信息，而装配操作的工艺信 息对于实际生产是至关重要的。与上述不同的是，l a z z e f i n i 提出一种基于分段编码的遗 传算法用于装配序列规划，表示装配序列的染色体包含了部分工艺信息。他将染色体分 为三段编码：第一段表示参与装配的零件编号。第二段表示零件的可行装配方向，第三 段表示装配工具。子代和父代按照定的比例选择进入下一代。这种编码方法复杂，整 个算法较为复杂，结果显示需要过多的演化迭代次数。为了提高算法的性能，他将装配 体分解为子装配体进行装配，减少参加装配序列规划的零件数目。为了产生可行装配序 列，他运用了多种交叉、变异算子p ”。 g u a r iq 等提出用基因团编码描述产品装配的相关信息，将装配序列表示为基因团 排列组成的染色体，改进了传统的基因算法，通过交叉和多层次变异实现基于基因团编 华中科技大学硕士学位论文 = = = = = = = = = ；= = = ；= = = = = = = = = = = = ；= = = = = = = = 一 码的多信息装配序列并行优化。该算法受初始种群影响较大，如果初始装配序列全都不 可行，而且所有单个序列中的各个基因团都是随机的，将不可能引导优化计算向好的方 向发展，优化计算将不可收敛和收敛到非优化的解f 3 8 】。 ( 3 ) 装配序列规划模拟退火算法 模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m ，s a ) 是源于固体退火思想的一种适合 于求解大规模组合优化问题的有效近似算法，其基本思想和原理参见第2 章2 2 节。近 年来，模拟退火算法在装配序列规划研究中也得到了广泛关注。 h o n g 和c h o 将装配约束和装配过程的成本映射到装配序列能量函数，利用模拟退 火算法使装配序列能量函数扰动地逐步减小，经过多次迭代，直到能量函数不再变化为 止，最后得到具有最小装配成本的装配序列。在优化过程中，随机选择两个零件并交换 其位置产生新的装配序列。最后用一个由1 0 个零件组成的电磁继电器装配产品验证了 该算法的有效性p 州。m o t a v a l l is a e i d 等提出将装配过程总装配时间和重定向次数运用多 属性应用理论组合成单一目标函数，作为装配序列优化的评价函数。他根据产品装配模 型获得装配优先关系，然后利用模拟退火算法进行装配序列规划1 4 0 】。m i l n c rj m 等采用 d e f a z i o 和w h i m e y 提出的装配序列网络表达装配序列，用一种类似于遗传算法的方法 扰动序列网络中路径生成大量的可行装配序列，然后依照模拟退火算法从中寻找装配成 本最低的序列，在给出的实例中，出现大量成本相近但不同的序列【4 ”。 1 3 2 遗传模拟退火算法在其它领域的应用 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m ， s a ) 属于人工智能优化设计方法，具有较强的解决问题的能力，是当前较为成功的、广 泛应用于复杂工程问题优化的全局优化算法。它们对优化设计目标函数和约束条件的限 制较少，并能较好地处理实际优化问题中存在的目标函数具有多个局部极值点或在某一 局部不连续、不可微等病态情况。g a 和s a 在解决大空间、非线性规划、全局寻优等 复杂问题时具有传统方法所不具备的独特的优越性。然而g a 和s a 虽然都能从概率的 意义上以随机的方式寻找到全局最优解，但在实际的应用中也可能存在一些问题：g a 存在早熟现象，易于陷入局部最优，s a 获得一个高质优化解的效率不高。如何将g a 和s a 结合，取长补短，构造一种性能更佳的混合优化算法已引起了国内外学者的重视。 众多学者在这一方面开展了卓有成效的研究工作，混合优化算法在一些优化问题领域已 经得到了广泛应用。 在国外，e s b e n s e nh 等运用广义模拟退火遗传算法( s a g a ) 求解多单元布置优化 问题1 4 2 1 。他依赖控制参数的不同设置，分别执行g a 、s a 和混合算法s a g a 。他的研 9 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 一! 一 究表明，与单独运用g a 和s a 求解多单元布置优化闯题相比，混合算法( s a g a ) 能够获 得高质量优化解。h o n g m e i y u 等提出求解大规模系统能量综合问题的混合遗传模拟退火 算法一。他通过g a 和s a 有效结合避免算法出现过早收敛问题。他用大量的计算结果 表明该算法比单独使用g a 和s a 的收敛速度快，而且能够以较大的概率得到全局最优 解。1 1 一k w o nj e o n g 等提出混合自适应模拟退火遗传算法i 矧，该算法保留了g a 和s a 的 优点。与传统g a 、s a 不同的是使用了标准交叉算子和自适应冷却进度表。他用一个非 连续的时间系统识别问题验证了算法的有效性。他的研究表明，该算法比简单g a 和梯 度算法更加有效、优良。同时，使用自适应冷却进度表能够提高算法的收敛速度。此外， w a hb w - 等提出模拟退火遗传算法求解非线性约束规划问题【4 5 1 。m i l dm 等提出混合遗 传模拟退火算法求解组合优化问题，对t s p 问题用提出的算法求得了最短路径【4 6 】。研 究结果表明，该算法是有效的。 在国内，路飞用基于模拟退火机制的多种群并行遗传算法求解j o bs h o p 调度问题 m ”。仿真结果表明，该算法不仅具有较强的全局收敛性，而且具有更快的寻优速度。较 传统的遗传算法和模拟退火算法求解该问题有很大的改进，既有利于优良个体的保留， 提高整个算法的收敛性，又有利于保护群体的多样性，加快进化速度，避免过早收敛的 缺陷，应用此算法求解复杂调度问题是有效的。刘以安等提出求解机动多目标数据关联 问题的遗传模拟退火算法郴l ，该算法极大地提高密集多回波环境下系统跟踪多机动目标 的精度和可靠性。他的仿真结果表明，遗传模拟退火算法明显地优于独立地使用遗传算 法和模拟退火算法。周明等用遗传模拟退火算法求解机器人路径规划h 9 j 。仿真结果表 明，这种遗传模拟退火算法切实可行，它能够有效地提高路径规划的计算速度和保证路 径规划的质量。孙炜等将模拟退火算法中的扰动选择和加速适应度函数的思想融入基本 遗传算法，提出了图的三维可视化的遗传模拟退火算法【5 0 】。该算法有效克服了传统遗传 算法局部搜索能力较差的缺点，是一种性能优良的全局优化搜索算法。试验结果表明该 算法在图的三维可视化效果、效率以及大图的可视化稳定性方面均有较大改进。为了克 服遗传算法过早收敛和局部寻优能力差的缺陷，顾洁等提出用遗传模拟退火算法求解电 网规划问题，克服传统g a 不稳定和局部收敛的局限性，并在计算速度和精度上取得了 令人满意的效果 5 1 1 。 1 3 3 文献综述小缩 装配是产品生命周期的一个重要环节，装配序列规划始终是产品开发者研究的一个 重要内容。图搜索装配序列规划方法对于零件数多的复杂产品不可避免地存在装配序列 组合爆炸问题，一般情况下，它产生的装配序列都不是最优的a 软计算方法进行装配序 1 0 华中科技大学硕士学位论文 列规划近年来得到了广泛关注，神经网络、遗传算法、模拟退火算法是其中的主要成果。 为了获得性能更好的优化算法，混合优化算法越来越受到重视。 1 4 本文主要内容及章节安排 为了充分利用g a 和s a 的优越性，更加有效地