（机械制造及其自动化专业论文）基于装配过程模型的装配序列生成及优化研究.pdf

武汉理工大学硕士学位论文 摘要 合理的产品装配序列对装配效率的提高、装配成本的降低和装配质量的保 证有着重要影响。随着产品复杂性的提高和交货期的缩短，快速、有效地获取 产品的优化装配序列己经成为激烈市场竞争环境下企业产品开发的一个必然要 求。另外，计算机技术的飞速发展，为产品装配序列规划技术向着数字化方向 发展提供了条件。因此，研究数字化环境下产品装配序列快速规划具有重要的 理论意义和工程应用价值，是目前国内外工艺领域的研究热点。 装配序列规划的目标包括生成可行的产品装配序列和从可行的装配序列中 选择优化的序列提供给实际生产，指导装配活动的进行。现如今的装配序列规 划方法可以分为传统的方法和软计算方法，它们各有利弊。传统的方法通过精 确的几何推理，有效的保证了序列的几何可行性，但随着组成装配体零件数目 的增加，其产生的装配序列呈几何级数增长，容易形成组合爆炸；而软计算技 术中的遗传算法能够将人的模糊知识融入规划过程中，使得结果具有更好的工 艺可行性，但其运行质量和效率受初始种群的影响显著。 本文在对国内外有关装配序列规划问题研究现状分析的基础上，着重分析 了两种方法的利弊，尝试从两种方法的优势出发，探讨其结合点，考虑利用传 统方法的精确性来弥补遗传算法的随机性，从而得到更合理的装配方案。从这 个思路出发，本文首先定义了产品装配过程模型，提出了通过装配状态来表达 装配过程的思想，并建立了装配体的装配状态空间。在此基础上，分析研究了 装配关系干涉矩阵和关联矩阵，提出了应用矩阵运算验证装配状态有效性的三 个判断规则，给出了矩阵计算的判断方程式，并通过例子验证了该方法的可行 性。论述了基于图搜索策略生成装配序列的算法过程，并分析了其不足之处， 提出了一种结合装配状态有效性判断规则的改进搜索算法，并通过例子说明了 应用该算法生成装配序列的过程。在分析了装配序列规划中遗传算法应用的优 势和不足的基础上，研究了遗传算法中目标函数的设计策略，提出装配状态稳 定性的概念，并依此阐述了建立目标函数的方法，提出了一种基于遗传算法和 改进搜索算法结合的优化算法，最后通过算例验证了算法的可行性。 关键词：装配序列规划，装配过程，图搜索算法，遗传算法 武汉理工大学硕士学位论文 a b s t r a c t f e a s i b l ea n do p t i m a lp r o d u c ta s s e m b l ys e q u e n c eh a sg r e a ti n f l u e n c eo nt h e i m p r o v e m e n t o fa s s e m b l ye f f i c i e n c y , t h er e d u c t i o no fa s s e m b l yc o s ta n dt h e i m p r o v e m e n to fa s s e m b l yq u a l i t y n o w a d a y s ，w i t ht h em o r ec o m p l e x i t ya n d s h o r t e r d e v e l o p m e n tc y c l eo fp r o d u c t , r a p i d l yg e t t i n go p t i m a lp r o d u c ta s s e m b l ys e q u e n c e w i l lb e c o m en e c e s s a r yt oh e l pe n t e r p r i s e st ow i ni nc o m p e t i t i v em a r k e tw i t hs h o r t e r t i m e ，h i g h e rq u a l i t y , l o w e rc o s ta n db e t t e rs e r v i c e t h e r e f o r e ，r e s e a r c h i n go n a s s e m b l ys e q u e n c er a p i dp l a n n i n gi nd i g i t a le n v i r o n m e n th a sg r e a tt h e o r e t i c a l s i g n i f i c a n c ea n de n g i n e e r i n ga p p l i c a t i o nv a l u e t h eg o a lo fa s s e m b l ys e q u e n c ep l a n n i n gc o n s i s t si ng e n e r a t i n gf e a s i b l e s e q u e n c e sa n ds e l e c t i n go p t i m a la s s e m b l ys e q u e n c ef r o mt h er a n g eo ft h ef e a s i b l e a s s e m b l ys e q u e n c e n o w a d a y s ，t h ea s s e m b l ys e q u e n c ep l a n n i n gm e t h o d sc 柚b e m a i n l yc l a s s i f i e di n t ot h et r a d i t i o n a lm e t h o da n dt h es o f tc o m p u t i n gm e t h o d t h e y b o t hh a v ea d v a n t a g e sa n dd i s a d v a n t a g e s t h ef o r m e rm e t h o d sc o u l de f f e c t i v e l y g u a r a n t e et h ef e a s i b i l i t yo ft h eg e o m e t r i cs e q u e n c eb yp r e c i s eg e o m e t r i cr e a s o n i n g h o w e v e r , w i t ht h ei n c r e a s i n gn u m b e ro ft h ec o n s t i t u e n tp a r t ，t h en u m b e ro f a s s e m b l ys e q u e n c em i g h tg r o wq u i c k l yb yg e o m e t r ye x p o n e n t i a la n dl e a dt o c o m p o s i n ge x p l o s i o n t h el a t t e rm e t h o d s ，e s p e c i a l l yt h eg e n e t i ca l g o r i t h m s ，c o u l d g e n e r a t et h eb e t t e rr e s u l tb yu s i n gf u z z yk n o w l e d g e h o w e v e r , t h eq u a l i t ya n d e f f i c i e n c yo fi t sr e s u l ta c c o r dt ot h eq u a l i t ya n df e a s i b i l i t yo ft h ei n i t i a lp o p u l a t i o n t h i st h e s i sa n a l y z et h er e c e n tr e s e a r c ho ft h ea s s e m b l ys 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 ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h es o f tc o m p u t i n gm e t h o d sa n dt h e t r a d i t i o n a lm e t h o d s t r yt oi n t e g r a t et h ea d v a n t a g e so ft w om e t h o d st oe s t a b l i s h m o r ee f f e c t i v em e t h o dt og e n e r a t ef e a s i b l ea n do p t i m a la s s e m b l ys e q u e n c et os o l v e t h ep r o b l e mo fa s eb a s e do nt h i si d e a ，t h i st h e s i sf i r s t l yd e f i n e st h ep r o d u c t a s s e m b l yp r o c e s sm o d e l ，t h r o u g ht h ea s s e m b l ys t a t et oe x p r e s st h ea s s e m b l yp r o c e s s ， a n de s t a b l i s ht h ea s s e m b l ys t a t es p a c e s e c o n d l y , a n a l y z et h ei n t e r f e r em a t r i xa n d t h er e l e v a n c ym a t r i xo fr e l a t i o n s h i po fa s s e m b l y , a n dp u tf o r w a r dt h r e er e g u l a t i o n s t ov e r i f yt h ev a l i d i t ya n df e a s i b i l i t yo fa s s e m b l ys t a t e ，a n dd e s i g nt h em a t r i x 武汉理工大学硕士学位论文 c a l c u l a t i o nf o r m u l a ，a n dv a l i d a t et h ea v a i l a b i l i t yo ft h ep r o p o s e dm e t h o d t h r o u g ht h e e x a m p l e r e s e a r c ho nt h ea l g o r i t h m st h a ta p p l y i n gg r a p hs e a r c hs t r a t e g yt og e n e r a t e a s s e m b l ys e q u e n c e ，a n a l y z ei t ss h o r t c o m i n g s ，e s t a b l i s ha l l i m p r o v e d s e a r c h a l g o r i t h ma n du s ee x a m p l et oi l l u s t r a t et h ef l o wo fa p p l y i n gt h ea l g o r i t h mt o g e n e r a t ea s s e m b l ys e q u e n c e a n a l y z et h ew e a k n e s s e so fg e n e t i ca l g o r i t h m ，r e s e a r c h o nt h ed e s i g nm e a n so fo b j e c t i v ef u n c t i o n ，d e f i n et h ec o n c e p to ft h es t a b i l i t yo f a s s e m b l ys t a t e ，a n db a s e do ni tt ob u i l dt h eo b j e c t i v ef u n c t i o n f i n a l l y , p u tf o r w a r d a ni m p r o v e dg e n e t i ca l g o r i t h mb a s e do ni m p r o v e ds e a r c ha l g o r i t h m ，a n dv e r i f yi t s c o r r e c t n e s st h r o u g ht h ee x a m p l e k e yw 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 ，a s s e m b l yp r o c e s s ，g r a p hs e a r c ha l g o r i t h m s ， g e n e t i ca l g o r i t h m s l 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谓 意。 研究生c 签名，：目扯日期地址! 多 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部内容， 可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ： 导师( 签名) ： 武汉理工大学硕士学位论文 1 1 研究背景 第1 章绪论 信息技术的发展促进了全球大市场的形成，这种趋势对制造业的影响十分 明显。从制造业发展的历程来看，7 0 年代之前的竞争焦点是企业规模和产品成 本，而8 0 年代的竞争焦点则是满足用户需求和综合的上市时间、产品质量、产 品成本和售后服务( t q c s ) 指标。9 0 年代后的市场则要求企业以最短的时间开 发出质量最高的、用户可接受的新产品。迅速开发出满足用户需求的新产品并 尽快上市成为企业赢得市场竞争的关键。 传统的产品开发模式为功能部门制，信息共享存在障碍，串行的流程在设 计早期不能全面考虑产品生命周期中的各种因素。而全球化大市场的形成，要 求企业必须改变经营策略，提高产品开发能力、增强市场开拓能力，传统的产 品开发模式已不能满足激烈的市场竞争要求，在这种背景下，并行工程 ( 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 年美国国防部完整地提出了并行工程这一概念。并行工程是集成地并 行地设计产品及相关过程的系统化方法，它要求产品开发人员从设计一开始即 考虑产品生命周期中的各种因素。它通过组成多学科产品开发队伍、改进产品 开发流程、利用各种计算机辅助工具等手段，使产品开发的早期阶段能及早考 虑下游的各种因素，达到缩短产品开发周期、提高产品质量、降低产品成本， 从而增强企业竞争能力的目标【1 1 。 面向装配的设计( d e s i g nf o r a s s e m b l y ，d f a ) 是并行工程的关键技术之一， 其出发点是在产品设计阶段考虑并解决装配过程中可能存在的问题，以确保零 件快速、高效、低成本地进行装配【2 】o 通常的产品设计不是面向装配的，这是 装配自动化的一个主要障碍，也是使产品装配成为制造业最薄弱的环节之一的 主要原因。据有关研究表明，在产品设计中良好的装配设计，可以减少2 0 4 0 的制造费，同时提高1 0 0 2 0 0 的生产率，在制造过程中，装配时间占总生产 时间的5 0 ，装配费用占制造总费用的2 0 3 0 ，在装配中发生问题，会增加 5 0 的费用。如何有效降低装配费用，是当今企业所面临的突出问题。d f a 就 武汉理工大学硕士学位论文 是为了解决这一问题发展起来的，其思想起源于7 0 年代。开始人们根据实际设 计经验和装配操作实践，制定了一系列有利于装配的设计指南，以帮助设计人 员设计出容易装配的产品。但由于受当时条件所限，这种方法还很难为设计人 员提供真正的有针对性的指导。直到1 9 8 0 年，m a s s a c h u s s e t t s 大学的b o o t h r o y d 教授提出了d f a 这一概念，并被广泛接受。其研究的主要内容包括产品装配建 模和装配序列规划【3 j 。 作为d f a 研究的主要内容之一，装配序列规划( a s s e m b l ys e q u e n c e s p l a n n i n g ，a s p ) 引起了国内外众多学者的兴趣，许多学者在这一领域开展了卓 有成效的研究和探索，并取得了很大的进展。传统的装配序列规划的方法主要 有优先约束法( p r e c e d e n c ec o n s t r a i n tm e t h o d ) 和割集法( c u t s e tm e t h o d ) 。但这两 种方法只适合于零件数较少的装配体的a s p 问题的求解，当组成装配体的零件 较多时，就会产生组合爆炸问题，求解效率很低，且求解过程繁琐。软计算( s o f t c o m p u t i n g ) 以模糊逻辑、神经网络和概率推理为基础，不追求问题的精确解， 以近似性和不确定性为主要特征，所得到的是精确或不精确问题的近似解1 4 】， 既能避免组合爆炸克服传统规划方法的缺陷，同时又能得到较优的装配规划方 案。近年来，基于建模、表达和寻优一体化的装配序列规划软计算方法得到了 广泛关注。但由于装配问题的复杂性和多样性，现有的各种软计算方法在求解 装配序列规划问题的过程中仍存在一些问题，生成可行序列仍有一定的难度， 且难以找到最优装配序列【5 1 。迄今为止，还没有真正找到一种令人满意的装配 序列规划的方法。装配序列规划研究仍然是并行工程和产品设计领域的一个研 究热点。 1 2 研究的目的和意义 在目前的产品生产过程中，设计者一般是凭借经验和产品的功能，在完成 产品设计的同时给出产品的装配序列。这些装配序列往往是基于人的以往经验 以模糊判断的形式而生成的，人的直觉理解很难确保问题的正确性和一致性， 而且设计者在设计时又难于顾及完成产品装配的各种资源( 工人、装配设备等) 的性能指标，装配序列一经确定之后很少改变，固定不变的装配序列很难保证 在不同的装配环境中都是最优的。尤其对于结构复杂的产品，零件数量增加时， 装配序列数随之剧增，依靠人工生成装配序列十分繁琐，易于出错，最优的装 2 武汉理工大学硕士学位论文 配序列可能被忽略。同时适于手工装配的操作序列一般不能用于自动装配机器， 不同的装配序列会直接影响到产品装配时的可行性及最优性。所以系统化、计 算机化装配序列的生成迫在眉睫。 装配序列规划在很大的程度上决定着产品的装配费用。它主要研究产品装 配顺序、方法、工具的描述问题，其中确定产品装配顺序是装配序列规划的核 心。a s p 研究始于8 0 年代初期w e s l e y 和t a k e y a m a 等人的研究工作【6 1 ，尽管经 过了多年的研究，仍然存在很多不完善之处。本课题的研究目的是在分析和总 结现有装配序列规划方法求解a s p 问题的基础上，找出更加有效的装配序列规 划方法。力图更能反映工程实际，能更好地指导产品装配，达到降低装配成本 的目的。因此开展本研究具有十分重要的现实意义。 1 3 国内外相关研究现状 关于装配序列规划的研究，国内外主要集中在装配模型的建立、装配序列 的生成和装配序列的优化三个方面。装配序列是装配规划的核心，产品中零件 之间的几何关系、物理结构及功能决定了产品的装配顺序。 1 3 1 传统的装配序列规划方法 ( 1 ) 优先约束关系法 获取优先约束关系并将其显式表达是最直观的装配顺序生成方法。优先约 束关系指零件之间的装配顺序约束。这种关系随装配体结构设计而确定、内在、 隐含的一种几何约束关系，这种关系一旦违背，则无法完成最终装配。因此装 配顺序规划问题就成为在装配顺序优先关系约束条件下的几何可行装配顺序的 搜索算法设计问题。1 9 8 4 年，b u o r j u a l 提出了利用问题回答系统确定装配顺序 的方法，为了搜索出所有的几何可行装配顺序，b u o r j u a t l 提出了产品的关联图 ( 1 i a i s o n ) 模型表达方法【7 1 。通过对关联图的分析，从装配的几何可行性出发，产 生一系列y e s n o 形式的问题，由对这些问题的回答确定零件的装配优先关系， 进而生成装配序列。然而当装配体中零件数较多时，需要回答的问题量太大， 所以不具有实用性。 f a z i o 和w h i t n e y 在此基础上作了改进和简化，在提问的形式和数量上使人 机交互回答的问题数减少为2 n ，但是需要穷举出所有的装配优先关系，相比之 3 武汉理工大学硕士学位论文 下，对这种问题回答更为困难。b a l d w i n 等人在b u o r j u a l t 和d ef a z i o 工作的基 础上，输入信息为联接图装配模型，为了减少向用户的提问次数，该方法应用 了一系列推理简化规则【8 】使操作人员回答的问题进一步减小，回答问题时出 现遗漏和错误的可能性也大大减少。经过上述人机交互提问和回答后，可以获 取装配顺序优先约束关系，并可求得装配序列。 装配序列优先约束是表达零件装配先后顺序的一种非常紧凑的方法。这种 方法的关键是装配优先约束关系的获取。采用人机交互的方法，工作量大，对 操作人员要求高，而且容易出错。自动获取优先关系则有一定的难度，然而一 旦获得零件装配的优先关系，则能很容易地求得零件的装配顺序。 ( 2 ) 割集法 割集法是基于拆卸策略的装配规划中通常采用的图论算法，即在零件的装 配过程和拆卸过程互逆的前提下，通过零件的拆卸顺序求得零件的装配顺序。 割集法生成装配序列，是指将装配体按一定的约束条件进行拆解，首先拆解成 子装配体，然后再将子装配体拆解成子子装配体，按照这种方式一直继续拆解 下去，直至单个零件，这样就得到了装配体的拆卸顺序，沿着拆卸顺序的逆序 进行装配，最终就可以得到产品的装配序列。割集法的关键是如何实现在一定 约束条件下拆卸任务的分解。 h o m e md em e l l o 最先提出了基于割集法求解装配顺序的方法( 也称拆分 法) ，能够自动推理出完整的装配顺序。通过对产品联接图进行缩并，利用“割 集 算法对联接图进行循环分解，生成所有可能的子装配体，直到不可再分。 并提出了装配序列的a n d o r 图表达方法，图中的节点对应装配过程中的子装 配体或零件，联接弧表示将子装配体或零件联接在一起形成更大子装配体的装 配操作p j 。算法根据装配模型信息中有关各零件之间的相互联接关系，计算出 局部约束关系，并通过定义虚拟联接的方式，将无联接关系但有干涉关系的两 零件之间的约束关系进行描述。通过这两种约束关系可以求解出割集分解的可 行性，同时分析了割集法的计算复杂性。由于装配体中零件数目、零件之间的 联接数等对割集法的复杂程度都有指数级的影响，因此，复杂产品的装配顺序 规划在运用割集法时，其计算复杂性是极其大的。 l a p e r r i e r el 在其g a p p 系统中通过对割集生成的装配状态有向图施加约 束，得到装配状态转换图进而获得装配序列。他总结出割集几何性的验证法为： 在由割集产生的任一子部件中，所有相关零件的拆卸方向的交集不为空【1 0 l 。 4 武汉理工大学硕士学位论文 割集法进行装配序列规划的优点是：可根据零件集合数据库和拆卸干涉检 验来分析所拆分的各个子装配，以生成在几何上所有可行的拆卸顺序。割集法 的局限性是必须满足装配和拆卸互为可逆过程这一前提条件，且有产生组合爆 炸的趋势。 ( 4 ) 知识推理法 用知识推理法求解装配序列，采用一阶谓词逻辑来表达产品结构、序列优 先约束和装配资源约束等知识。系统以产品c a d 模型为输入，通过人机交互 获取零部件的装配优先约束、通过图搜索算法求解产品配合特征图的最小割集 来产生装配序列。 h u a n gyf 从装配体拆卸出发，认为虽然一些算法可以用来产生所有可行 的装配序列，但是没有一种算法可以直接产生最优装配序列。鉴于此，h u a n g 研制了基于知识推理的装配规划系统【1 1 】。系统中采用谓词表达约束知识，通过 推理得到可行的装配序列。 基于知识推理的装配顺序的求解方法，对于特定产品的装配序列求解比较 有效，但其适用面窄，且领域知识的获取需要较深的专业知识。 1 3 2 装配序列规划的软计算方法 一般情况下，从传统装配序列规划方法中产生的装配顺序都不是最优的。 为了使产品装配成本最小化，降低产品开发的总成本，又必要寻找最优的装配 序列( 装配成本最小) 或对已得到的装配序列进行优化。近年来，人们将基于智 能计算的软计算方法引入装配序列规划中，取得了一定的成果。 1 9 9 4 年，z a d e h 教授将模糊逻辑与智能技术结合起来，提出了软计算方法 4 1 。它是随着信息技术和计算机智能化的发展而产生的几种适用计算技术的总 称，即神经网络、遗传算法、模拟退火算法、模糊逻辑控制等。软计算方法为 解决多变量、非线性系统提供了一种有效的方法，是一种新的计算模式。软计 算并不追求问题的精确解，而允许存在不精确性和不确定性，所得到的是精确 或不精确问题的近似解。软计算是目标驱动的，即只要从长远看，计算过程总 是在向目标移动，至于从当前状态到最终状态走的是一条什么路径则是无关紧 要的。同时，特定的领域知识有助于降低计算量和搜索时间，但并不是必要的。 软计算中应用了来源于不同思想的、新颖的最优化方法，因而在解决复杂化问 题时具有更大的灵活性。对于一个多变量非线性系统而言，软计算方法解决途 5 武汉理工大学硕士学位论文 径具有成本低、可实际操作和较高智能的特点，近年来在装配序列规划研究领 域也得到了广泛的应用。 ( 1 ) 神经网络方法 神经网络是模拟人类形象思维的一种人工智能方法，它是由大量神经元广 泛互连而成的复杂网络系统，单一神经元可以有许多输入、输出，神经元之间 的相互作用通过连接的权值体现，神经元的输出是其输入的函数。若将优化计 算问题的目标函数与网络某种状态函数( 通常称网络能量函数) 对应起来，网络 动态向能量函数极小值方向移动的过程就可视作优化问题的求解过程，稳态点 则是优化问题的局部或全局最优解。 h o n g 和c h o 1 2 】用于机器人装配顺序优化的h o p f i l e d 神经网络中，考虑装 配约束、子装配体稳定性和装配方向改变等因素建立网络的能量方程，基于优 先约束推理和专家系统提供的装配成本驱动网络的进化方程得到优化的序列。 但由于神经网络缺乏全局搜索能力，计算结果显示，该方法容易产生不优化的 装配顺序，且常常只能得到一个局部最优的装配序列。另外，参数选择和初始 条件对网络的灵敏度影响大；神经网络在应用前须进行训练，而训练时要由专 家提供较多可行的顺序作为样本。而样本可能是针对某种类型的产品，对其它 类型的产品则不一定适用，该方法的应用范围窄。 ( 2 ) 模拟退火算法 模拟退火算法源于固体退火思想，将一个优化问题比拟成一个热力学系统， 将目标函数比拟为系统的能量，将优化求解过程比拟成系统逐步降温以达到最 低能量状态的退火过程，通过模拟固体的退火过程获得优化问题的全局最优解。 s a e i d 等1 1 3 j 利用模拟退火算法进行装配序列规划时，根据产品装配模型获 得装配优先关系，将装配过程总装配时间和重定向次数运用多属性应用理论组 合成单一目标函数，作为装配序列优化的评价函数。h o n g 和c h o 1 4 】将装配约束 和装配过程的成本映射为装配序列能量函数，利用模拟退火算法使装配序列能 量函数扰动地逐步减小，经过多次迭代，直到能量函数不再变化为止，最后得 到具有最小装配成本的装配序列。 模拟退火算法具有较强的局部搜索能力，并能使搜索过程避免陷入局部最 优，但模拟退火算法对整个搜索空间的状况了解不多，不能使搜索过程进入最 有希望的搜索区域，从而使得算法的运算效率不高。 ( 3 ) 遗传算法 6 武汉理工大学硕士学位论文 在众多软计算方法中，遗传算法得到了众多研究者的重视。遗传算法是模 仿生物自然选择和遗传机制的随机搜索算法，它将问题的可能解组成种群，将 每一个可能的解看作种群的个体，从一组随机给定的初始种群开始，持续在整 个种群空间内随机搜索，按照一定的评估策略即适应度函数对每一个体进行评 价，不断通过复制、交叉、变异等遗传算子的作用，使种群在适应度函数的约 束下不断进化，算法终止时得到最优或次最优的问题解。 装配规划遗传算法的研究重点集中于设计装配序列的基因编码方式以包含 更多的装配过程信息、设计基因操作的形式和改进遗传算法的局部搜索能力上。 l a z z c r i n i 等【1 5 j 的分段编码遗传算法中，将染色体分为3 段编码，第1 段表示参 与装配的零件编号，第2 段表示零件的可行装配方向，第3 段表示装配工具， 从而使染色体包含了部分工艺信息。为了提高算法的性能，文中将装配体分解 为子装配体进行装配，减少了参加装配序列规划的零件数目；g u a n 等【1 6 】采用 基因团编码方式，一个基因团表达一个零件的装配操作，由被装配零件号装配 元、装配工具装配元、装配方向装配元和装配类型装配元组成。在扩大采样空 间选择下一代种群的基础上，通过交叉和多层次变异实现装配序列并行优化。 廖小云和陈湘风【1 7 】在装配序列规划遗传算法中设计了复制、交叉、变异、剪贴 和断连5 种遗传算子寻找装配序列优化解。在s m i t h 掣1 8 】的增强型遗传算法中， 选择下一代个体并不完全依靠适应度，而是先把一定数量较优的个体复制到下 一代，将适应度低但几何可行的序列用于继续产生序列，直到满足下一代种群 中序列个数的需求，从而使算法能跳出局部最优点，在全局范围内搜索最优解。 理论上，找到全局最优装配序列要求参加演化计算的种群规模要足够大， 迭代次数要无限多，但在计算资源和时间限制下是达不到要求的。因此，遗传 算法求解装配规划问题的效率和结果依赖于初始种群规模及其质量、遗传算子 及其操作概率等因素。 从以上综述可见，a s p 研究已经取得了一定的进展，在理论和实践上都有 很大成绩，但是这一问题仍没有得到完善的解决。传统的装配序列规划方法一 般能表达出全部序列解空间，但随着产品中零件数目的增加，解空间的组合爆 炸给序列的存储、选优带来极大的困难；且序列的几何推理方法不易融入人类 的装配知识，难免产生众多几何可行但工艺不可行的序列结果。软计算方法不 追求问题的最优解，以近似性和不确定性为主要特征，并且将人的模糊知识融 入规划过程中，使得结果具有更好的工艺可行性，能够得到较优的装配序列规 7 武汉理工大学硕士学位论文 划方案，但同时也存在一些问题。 1 4 项目支持和本文研究内容 1 4 1 项目支持 本论文得到国家科技部国际科技合作项目：“基于多智能体的数字制造基本 理论与关键技术研究 ( 2 0 0 6 d f a 7 3 1 8 0 ) 的支持。 1 4 2 本文研究内容 装配规划是一个经验和知识密集型的工作，同时又与具体行业和产品有紧 密的关系。传统的装配规划方法的精确推理在保证序列的几何可行性方面具有 优势，而软计算技术能够将人的模糊知识融入规划过程中，使得结果具有更好 的工艺可行性，两者的适当结合将有利于模仿人类装配专家的实际装配规划过 程，从而得到合理的装配方案。 本文在对两种方法深入研究的基础上，从两种方法的优势出发，探讨两种 方法的结合点，力争为a s p 研究提供一种新的思路。本文的主要研究工作内容 如下： ( 1 ) 论述了产品装配过程模型的结构以及建立产品装配过程模型的方法， 定义了装配过程，提出将动态的装配过程通过静态的装配状态来表达的思想， 并建立了产品的装配状态空间； ( 2 ) 根据产品装配连接图得到的装配干涉矩阵、分析了隐含在装配连接图 中的装配优先关系，提出了验证装配状态有效性的规则，讨论了通过矩阵计算 判断装配状态有效性的方法，并通过实例验证了所提出方法的可行性； ( 3 ) 研究了基于图搜索策略生成装配序列的算法，分析了其不足之处，提 出了一种结合装配状态有效性验证规则的改进的搜索算法，并通过实例进行了 说明； ( 4 ) 分析了应用遗传算法在求解装配序列规划问题时的不足，建立了通过 改进的图搜索算法生成问题的可行解、利用遗传算法实施快速优化的遗传算法 和图搜索算法相结合的一种优化算法。实例运行结果表明了算法的有效性。 8 武汉理工大学硕士学位论文 第2 章装配过程模型和装配状态空间 产品装配模型是装配规划的基础，为装配规划提供装配体和零部件的相关 信息。产品装配建模对于装配序列可行性分析有很重要的影响。建模过于简单， 则无法对后续装配序列规划工作提供足够的信息；建模过于复杂，则难以将它 们完备而准确地集成到规划算法中，难以用计算机表达和实现装配序列规划。 常用的装配信息表达模型可分为图模型和矩阵模型。法国学者b u o ri u a t l 提出了联系图模型【1 9 1 ，将零件之间的物理接触关系定义为联系即装配关系，图 中的节点对应零件，边表示所联接的零件间至少有一种装配关系。关系模型进 一步区分了零件之间的接触关系和联接关系，图中包含3 种实体类型：零件、 接触和联接，边表达了实体间的关系。产品等级装配模型【刎将装配体视作具有 层次结构性，即装配体可以分解为子装配体，子装配体又可分解为下级子装配 体和零件的集合，以此表达产品的装配组成。 矩阵比图易于计算机表达和实现。d i n i 和s a n t o c h i 利用干涉矩阵、接触矩 阵和联接矩阵表达产品俐。干涉矩阵描述了零部件间沿坐标轴方向装配时相互 间的干涉情况；接触矩阵描述了零部件间的物理接触状态；联接矩阵描述了零 部件间的联接类型。 本文在对图模型和矩阵模型深入研究的基础上，将图模型的简洁直观、易 于理解和矩阵模型精确唯一、易于计算的特点相结合，并借用面向对象建模的 思路对装配模型进行建模，为装配序列的生成及装配序列的优化提供必要的信 息。 2 1 装配过程模型的定义 从产品的装配过程来看，任何产品都是一步一步的简单装配步骤的层次组 合。装配即是“装”和“配”：装是合并，是数量的增加；配则是合并的条件，即约束， 是相互位置关系的确定1 2 。即，一个产品完整的装配过程是将不同的组件按照 一定的顺序组成总装配体的过程。装配过程总是以零散的单个零件为开端，而 以完整的产品为结束。每一步装配过程都是将零件组成组件，将组件组成更大 的组件，直至完成整个产品的装配。因此，一个完整的装配过程本身就包含有 9 武汉理工大学硕士学佩论文 装配顺序的信息。而在每一步装配过程中，组成总装配体的组件以不同的结合 方式组合而表现为不同的装配状态，所以可以将动态的装配过程通过不同的 静态的装配状态来定义。装配过程和装配状态的关系可以通过下图2 - 1 表示： 匝圈匝困匝困 夕障涉。障鬻 口口 二二 西西匠 图2 - 1 装配过程和装配状态间的关系 基于以上分析，本文对装配过程做出如下定义： 启卫装配过程：表示两个有连接关系的装配状态向一个新的装配状态的 转变。包括初始装配状态、中间装配状态和最终装配状态。一个完整的装配过 程是其所有子装配过程的集合。 根据以上对装配过程的定义，本文将结合装配过程和装配状态之间关系建 立的模型称为装配过程模型。装配过程模型的结构如下图2 - 2 所示。 图2 - 2 装配过程模型结构幽 2 2 装配过程模型的结构分析 从上图的装配过程模型结构图中可以发现其模型结构采用连接图的表达 武汉理工大学硕士学位论文 形式，而运用面向对象的数据组织结构，通过矩阵成员来丰富模型的表达。下 面分别对模型结构中的数据成员进行分析说明。 2 2 1 子装配过程 启义子装配过程：表示装配过程集合中的一个子集。反映两个有连接关 系的装配状态向一个新的装配状态的转变。其数据结构包括三个成员变量，分 别是初始状态、最终状态和操作任务。 ( 1 ) 初始状态：表示子装配过程的开始状态。 ( 2 ) 最终状态：表示子装配过程的结束状态。 ( 3 ) 操作任务( o p t ) ：表示从初始状态到最终状态的转变。 2 2 2 装配状态 定义装配状态( s t a t e 、) ：装配状态是装配过程在某个时间点的表现，也可以 看成是装配过程的一个子集，其数据结构包括组件数量和组成向量两个成员变量。 ( 1 ) 组件数量：表示一个装配状态中所包含的组件数量。 ( 2 ) 组成向量( c o m p v ) ：表示一个装配状态中所包含的组件。其值采用二进 制布尔值表示。当值为真时，表示该装配状态中包含该组件：当值为假时，表 示不包含。 由于不同的装配状态所包含的组件数量有可能相同，但不同的装配状态所 对应的组成向量一定不相同，因此，可以通过组成向量来唯一确定不同的装配 状态。装配状态用s t a t e ( s l v ) 表示，s n 是该装配状态的唯一识别号，表示为与该 装配状态对应的组成向量的元素序列组成的二进制数。例如， c o m p vi ( 1 01 0 ) ，其对应的装配状态为s t a t e ( 1 0 1 0 ) 。 2 3 装配状态空间 任意不同组件的集合都是一个装配状态，而每个装配状态通过对应的组成 向量来表示。因此，一个产品所有的装配状态可以被表示成二进制的矢量集f 2 2 l 。 本文将一个产品所有可能装配状态的矢量集定义为装配状态空间，简称状态空 间。当一个产品由1 1 个组件组成时，其状态空间包含2 “一1 种不同的装配状态。 武汉理工大学硕士学位论文 例如，下图2 3 所示装配体的状态空间包含2 4 1 1 5 种不同的装配状态。表 2 1 将其1 5 种不同的装配状态列举如下。 。 掣! ! 纠：竺竺 c o m 。p ( 1 ) 鬻c o m p ( 4 ) 图2 0 二维空间的装配体示意图和装配连接图 表2 - 1 装配体的装配状态空间组成 l i a i ( 2 ) t 一 c o m p ( 3 r 一 _ _ 、 l i a f ( 3 ) 缀l 串数囊臻配技惹挠糊组捧数鐾装配状态状悉圈 j 二 甜a t e ( 1 0 0 1 。 m t 急( 1 t o o ) ，f * r 州0 1 0 i ；jt ； r s t a t e ( i n l i 。l l 0 r o t e ( 0 0 1 彩 广、 粼1 0 8 1 ) ；一 ，j l j 一， 飞。一。，r 一 2 ， s t a t e ( o o o z ) pf j s l a t o l l 毫 5 0 ，。纠， s t a l i n o ) 。咖。 s 徽( ot o t ) $ 雠l 1 0 1 ) 鬈 蝴嵯1 1 ) 。i ； 3 ： ；一 ：。i ： ，二曩 、 s t a t e ( 1 0 1 1 ) ? i 娃土 p q 4 s 魄t e ( m d i - i r r f ； ； s u i t e ( o l i1 ) 一，j ； 7 i 尹 1 2 武汉理工大学硕士学位论文 2 4 基于矩阵运算的装配状态有效性验证 根据装配过程模型很容易获得装配体的装配状态空间。但不难发现，并不 是所有存在于状态空间中的装配状态都能有效的支持装配过程的进行。例如表 2 - 1 中的装配状态s t a t e ( 1 0 l o ) ，在实际装配过程中不会出现这样的装配状态。因 此，本文按照装配状态是否可能在装配过程中出现，将状态空间中的装配状态 分类为真状态( 可能在装配过程中存在的状态) 和假状态( 不可能在装配过程中存 在的状态) 。 为了区分状态空间中的真状态和假状态，本文提出以下两个状态真假性的 判断规则。 规则j ：对于任何一个真状态，当该装配状态所包含的组件数大于等于2 时，则规定其所包含的组件都是连接在一起，组成一个完整的新组件。例如， 装配状态s t a t e ( 1 0 1 0 ) 中，组件1 和组件3 不满足规则1 ，所以状态s t a t e ( 1 0 1 0 ) 是 假状态。 规则2 ：对于任何一个真状态，不能对后续组件的装配过程产生阻挡或干 涉，即，至少存在一种可行的装配过程保证完成从当前状态到最终状态的转变。 例如，装配状态s t a t e ( 1 0 1 1 ) ，它对后续组件2 的装配过程产生了阻挡和干涉， 即不满足规则2 ，所以状态s t a t e ( 1 0 1 1 ) 也是假状态。 针对以上提出的状态真假性判断规则，本文在对装配体矩阵模型深入研究 的基础上，提出了装配状态间的联接性、兼容性和结合性等概念，试图通过数 学的形式精确的对状态空间中装配状态的真假性做出判断，从而获得真装配状 态集合，为后续的装配序列生成和装配序列优化提供必要的信息保障。 2 4 1 装配状态联接性的定义及验证 定吠装配状态联接性：表示一对不存在公共组件的装配状态间是否存在 公共联接边。用矩阵c o r r e l a t i v i t y s t a t e ( s n m ) ，s t a t e ( s n 。) 】表示，其值采用二进制 布尔值表示。例如， c o r r e l a t i v i t y s t a t e ( s n 。) ，s t a t e ( s n 。) 卜( 1 1 ，21 3 i i ) ，i