（机械制造及其自动化专业论文）基于子装配体识别和遗传算法的装配顺序规划.pdf

荩丁子姨配体识别和遗传算法的装配顺序规划 摘要 装配顺序规戈1 ( 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 ) 本质上是n p 组合优化难题，可行 装配顺序的生成更是这一难题中的核心问题。本文针对装配顺序规划中的难点，采用基 于子装配体识别和遗传算法的装配顺序规划方法进行了研究。本文主要工作如下： 第一，本文研究了装配模型的建立方法。首先从c a d 系统获得装配体模型的基础 数据，在此基础上根据本文使用的装配顺序规划方法的需要对基础数据进行处理，通过 自动化分和人机交互结合的方式建立装配模型。装配模型中包含了子装配体识别和遗传 算法所需要的信息：联接信息、全局阻碍信息、支撑信息，详细给出了描述上述信息的 产品的接触联接无向图、集成拆卸阻碍矩阵、支撑矩阵的建立方法。同时介绍了可行装 配拆卸顺序几何可行性的判断方法，及子装配体、零件到位后的稳定性判定方法。通过 实例对判定方法加以说明。 第二，根据装配模型中接触联接无向图，介绍了根据联接关系和基础零件特征的基 础零件的识别方法；根据装配体的装配模型提供的接触联接无向图、集成拆卸阻碍矩阵、 支撑矩阵的基础上，提出了i 型子装配体和i i 型子装配体的识别算法。通过实例对算法 进行了验证。 第三，采用遗传算法进行装配顺序生成与评价。采用符号编码方法，选择相应的合 适的遗传算子，根据装配中的一般原则设计了适应度函数，分别对子装配体以及整体装 配体进行装配顺序生成与评价。 第四，根据以上方法，以减速箱为实例进行装配顺序规划，验证了本文提出的算法 的有效性。与其他文献对比，得出本课题的提出的模型及识别方法可以更全面准确的识 别两种子装配体，本课题的遗传算法可以更有效快速的得到可行的最优的装配顺序。 关键词：装配顺序规划：遗传算法；装配模型；子装配体 荩丁子装配体识 l 怫l 遗传舒法的装配顺序规划 a b s t r a c t a s s e m b l ys e q u e n c e sp l a n n i n gi se s s e n t i a l l yap r o b l e mo fn pc o m b i n a t i o no p t i m i z a t i o n ， a n dt h eg e n e r a t i o no ff e a s i b l ea s s e m b l ys e q u e n c e si st h ec o r ei s s u ei nt h i sp r o b l e m i nt h i s p a p e lt h ed i f f i c u l t yo fa s s e m b l ys e q u e n c e sp l a n n i n g i ss t u d i e db yt h em e t h o dw h i c hi sb a s e d o ns u b - a s s e m b l yi d e n t i f i c a t i o na n dg e n e t i ca l g o r i t h m s i nt h i sp a p e r ，t h ep r i m a r yj o bi sa s f c i l l o w s ： f i r s t l y ，t h ee s t a b l i s h e da p p r o a c ho fa s s e m b l ym o d e li ss t u d i e d f i r s to fa l l ，t h eb a s i cd a t a o fa s s e m b l ym o d e lc a nb eo b t a i n e df r o mt h ec a ds y s t e m ，w h i c hs h o u l db ep r o c e s s e d a c c o r d i n gt ot h em e t h o do fa s s e m b l ys e q u e n c ep l a n n i n gu s e di n t h i sp a p e r ，a n dt h e nt h e a s s e m b l y m o d e li se s t a b l i s h e d b y t h e p a t t e r n o fa u t o m a t e dd i s t i n g u i s h m e n ta n d h u m a n c o m p u t e ri n t e r a c t i o n a s s e m b l ym o d e lc o n t a i n st h ei n f o r m a t i o nn e e db ys u b a s s e m b l y i d e n t i f i c a t i o na n dg e n e t i ca l g o r i t h m s ：c o n n e c t i o ni n f o r m a t i o n ，g l o b a li m p e d i n gi n f o r m a t i o n a n ds u p p o r ti n f o r m a t i o n a n dt h ee s t a b l i s h e dm e t h o d so fc o n t a c tc o n n e c t i o nu n d i r e c t e dg r a p h ， g l o b a li m p e d i n gm a t r i xa n ds u p p o r tm a t r i xd e s c r i b i n gt h ep r o d u c to ft h ei n f o r m a t i o na r e p r o v i d e di nd e t a i l a l s ot h ed e c i s i o nm e t h o d so ft h eg e o m e t r yf e a s i b i l i t yi n t h ef e a s i b l e a s s e m b l y d i s a s s e m b l ys e q u e n c ea n dt h es t a b i l i t yi n t h es y s t e mw h e nt h es u b - a s s e m b l i e s ， c o m p o n e n t sa r ei np l a c ea l ei n t r o d u c e d a tl a s t t h ed e c i s i o nm e t h o d sa r ei l l u s t r a t e db ya n e x a m p l e s e c o n d l y ，a c c o r d i n gt ot h ec o n t a c tc o n n e c t i o nu n d i r e c t e dg r a p hi nt h ea s s e m b l ym o d e l ， t h er e c o g n i t i o nm e t h o do fb a s i cp a r t sb a s e do nt h ec o n n e c t i o nr e l a t i o na n dt h ef o u n d a t i o np a r t f e a t u r ei si n t r o d u c e d ；t h er e c o g n i t i o n a l g o r i t h m o ft y p eia n dt y p ei is u b a s s e m b l yi s p r o p o s e db a s e do nt h ec o n t a c tc o n n e c t i o nu n d i r e c t e dg r a p h ，g l o b a li m p e d i n ga n ds u p p o r t m a t r i xp r o v i d e db ya na s s e m b l ym o d e l t h ea l g o r i t h mi s i n s p e c t e da n dv e r i f i e db ya n e x a m p l e t h i r d l y ，t h eg e n e t i ca l g o r i t h mi s u s e df o rg e n e r a t i o na n de v a l u a t i o no fa s s e m b l y s e q u e n c e b ya d o p t i n g t h e s y m b o le n c o d i n gm e t h o da n ds e l e c t i n g t h ec o r r e s p o n d i n g a p p r o p r i a t eg e n e t i co p e r a t o r s ，t h e f i t n e s sf u n c t i o ni sd e s i g n e da c c o r d i n gt ot h eg e n e r a l p r i n c i p l e so ft h ea s s e m b l y a n dt h e nt h ea s s e m b l ys e q u e n c e so fs u b 。a s s e m b l ya n do v e r a l l 哈尔滨f ：样人学硕 j 学佗论文 a s s e m b l ya t er e s p e c t i v e l yg e n e r a t e da n de v a l u a t e d f i n a l l y ，a c c o r d i n gt ot h ea n a l y s i sa b o v e ，t h ee f f e c t i v e n e s so ft h em e t h o di nt h i sp a p e r h a s b ev e r i f i e d ，b yt h ee x a m p l eo ft h ea s s e m b l ys e q u e n c ep l a n n i n go f p o s i t i v es p e e dg e a r b o x t h e m o d e la n di d e n t i f y i n gm e t h o di nt h i s p a p e r ，v e r i f i e db yc o m p a r i n gt o t h em e t h o d so f r e f e r e n c e s i sm o r ec o m p l e t e l ya n da c c u r a t e l yt o i d e n t i f yt h et w ok i n d so fs u b a s s e m b l i e s a n dt h eg e n e t i ca l g o r i t h mc o u l do b t a i nt h eo p t i m i z a t i o na s s e m b l ys e q u e n c em o r ee f f e c t i v e l y a n d r a p i d l y 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 ；a s s e m b l ym o d e l ； s u b a s s e m b l yi d e n t i f i c a t i o n 第1 章绪论 1 1 研究的背景及意义 第1 章绪论 在全球一体化不断加剧的环境中，当今制造业也将与其他行业一样，面临着来自于 全球市场同益增大的竞争压力。为了迅速适应市场需求的变化，提高自身的竞争力，制 造企业必须使产品满足开发时问短、质量高、成本低、服务优良、环保效果良好及适应 能力强等条件，从而来满足顾客的不同要求。那些在市场竞争中处于劣势地位的企业， 往往是由于没有注重产品的开发环节，因此产品开发是制造企业在市场竞争中取胜的关 键。 在产品生命周期的众多环节中，产品装配其中十分重要的环节1 。据相关统计，在 工业国家，大约1 3 的人力在产品的生产工程中从事产品装配相关的活动，约3 0 一5 0 生产费作为装配和调试的费用2 。1 ，约4 0 6 0 生产制造总工时用于产品的装配。因 此，在产品的装配阶段发生问题，将导致产品设计与加工制造的改变，不但会延长产品 的开发周期，而且会增加产品的开发成本，不利于企业提升自身的竞争力。 装配工艺是产品装配过程的具体化，是产品装配过程中使用的方法与技艺。装配工 艺的主要内容包括装配组织形式、装配单元、装配方法、装配顺序、装配路径、装配工 夹具、装配时间定额等p 1 。其中，装配序列规划是装配工艺规划的核心。在装配序列规 划中，产品装配顺序规划的目标是根据产品设计阶段所得到的各个零件的几何信息及相 互之间的关系，生成全部可执行的装配顺序，表示装配操作和装配任务执行的次序，描 述装配过程中的优先约束关系。 目前在产品生产的过程中，设计者一般是凭借产品的实际功能和经验，在完成产品 设计的同时制定出产品的装配顺序。这些装配序列往往是在人的以往经验的基础上，以 模糊判断的形式生成的，人类的直觉理解很难确保问题解决的萨确性和一致性。而且设 计者在设计阶段难以顾及完成产品装配环境中的各种资源( 工人、装配设备等) 的性能指 标，装配顺序一旦确定之后很少改变，固定不变的装配顺序又很难保证在不同的装配环 境中都是最优的。尤其对于结构复杂的大型产品，随着零件数量增加，装配顺序数量随 之剧增，依靠人工生成装配顺序十分繁琐，易于出错，最优的装配顺序可能被忽略。同 时，适于手工装配的操作顺序一般不能应用于自动装配机器，不同的装配顺序会直接影 响到产品装配时的可操作性及最优性，不同的装配序列又可以指导我们设计与之相适应 哈尔滨i ：矽，! 人学硕十学何论文 的装配系统。所以系统化、计算机化装配序列的生成迫在眉睫。 利用计算机进行产品装配顺序规划，可以弥补产品设计者经验方面的不足，形成统 一的评价标准，避免由于遗漏好的装配方案而造成的装配成本与时间的浪费，从而获得 易被忽略的更好的装配顺序。对复杂产品的装配，可以从所有可行的成千上力条配顺序 中找到最佳方案，同时在产品设计阶段，根据装配顺序规划反馈的信息，帮助产品设计 者改进设计。装配顺序规划逐渐成为制造自动化过程中的一个重要任务和c i m s 研究的 一个重要组成部分。 鉴于上述分析，本文拟对装配顺序规划进行研究，主要包括：装配信息的获取、建 立产品装配模型；子装配体识别；装配顺序生成及优化等。这些技术内容可以在产品设 计早期阶段发现产品装配中存在的潜在问题与缺陷，及早解决问题，从而提高产品质量； 还可提前进入工艺准备与工装设计阶段及投入生产，实现设计与生产并行，大大缩短产 品的开发周期；同时，通过对装配工艺的设计与优化、装配性能的评价与优化，可以提 高装配效率与质量，促进批量生产能力的形成。因此本文对装配序列规划的研究，具有 一定的理论意义和工程应用价值。 1 2 相关领域的研究综述 1 2 1 产品装配信息模型 建立产品的装配模型即装配建模，是装配顺序规划的基础。好的装配模型可以为后 续工作提供良好的基础，它必须能够完整正确的传递不同的装配体之间相关参数和信 息。完整的装配模型的信息包括装配体中各零部件件之间的层次关系，确定装配中零部 件件的位置和方向的装配关系等。产品装配体的c a d 模型描述了组成零部件的几何特 性及空间关系，这些是图形显示及某些人机交互所需要的信息，但它不能为装配顺序规 划提供直接可用的信息，必须经过数据转换和提取才能使用。目前对装配体的装配信息 进行建模，主要有三种模型：图结构关系模型，层次模型、基于虚链结构的混合模型。 1 图结构关系模型 图结构关系模型是以图的形式来描述装配体中各零件之间的相互关系。零件问关系 表达比较直观。 法国学者b o u r j a u l t 提出用二维拓扑结构关联图表达的关联图模型，该模型g p ，u 是由节点和边组成的连通图，p 是节点的集合，表示产品的零部件，l 为连接节点的边 的集合，表示零件间联系嗍，该方法的优点是仅需要识别出产品中零件间存在物理装配 2 第1 章绪论 关系就可以得到产品的装配关联图模型。 图1 1 b o u r j a u l t 装配模型 h o m c md em e l l o 和s a n d e r s o n 提出了一种五维拓扑装配模型：a s s = c4 r a - f u n c t i o n s ) ，其中p 为零件集合，c 为零件问的连接关系实体的集合，a 为各连接关系 对应的装配操作实体的集合，尺为对应于p o c u a 中元素间对应关系的集合，a - f u n c t i o n s 为pu cu 彳中的属性函数集合，函数将实体、关系与他们的特征项关连唧。该模型定义 对其所能表达的装配体有一些限制，模型形式复杂，模型建立有一定的难度。 图1 2 h o m e nd em e l l o 和s e n d e r s o n 装配模型 2 层次模型 层次模型是根据装配体中零部件的层次关系，用装配树的形式表示0 1 。树的根结点 ( 树的顶端) 代表装配体，叶结点( 树的末端) 代表不可拆分的零件，树的中间结点代表零 件或者子装配体。结点之间的连接边表示装配体与零件之间从属关系。装配体可以分解 为若干个零件、子装配体，子装配体又可以进一步分解为若干零件、子装配体，由此表 现出装配体的层次性。 装配的层次关系体现了产品设计者的意图和产品结构，同时体现了实际形成装配体 的装配顺序。不同层次零件的装配存在先后顺序约束，下层零件的装配应优先与上层零 3 哈尔滨f ：科人学硕十学何论文 件的装配，不用子装配体中的零件可以并行装配。因而模型隐含了部分装配顺序。因此， 基于层次模型的装配顺序求解降低了复杂度，但缺点是零件、子装配体之间具体的装配 关系表达不够直观。 图1 3装配的层次结构 3 虚拟链模型 l e e 等基于“虚链”建立了装配模型，结合了图结构模型和层次模型的优点。装配 体被存储在带有“虚链”的图结构中，任何两个有配合关系的零部件问有存在有一个“虚 链”来描述配合关系和配合特征的信息j 2 1 。由于“虚链”的引入，所以装配体数据能 被层次化地存储。但这种模型的缺点是一致性维护相对比较困难。 1 2 2 装配顺序的规划 1 2 2 1 传统装配顺序规划方法 图1 4虚拟链模型 4 第1 章绪论 装配顺序规划是典型的组合优化问题，其实质就是根据装配模型的各种几何约束条 件和装配技术要求下工艺约束条件，求解出满足各种约束条件、可行的、性能优良的装 配顺序。可行的装配顺序是指满足几何上不干涉，装配过程中装配工具能进行预订的操 作并且装配操作符合对应的工厂习惯和技术要求的装配顺序。装配顺序规划主要有以下 几种规划方法： ( a ) 优先约束法 优先约束法是根据装配过程中零部件之间存在的几何约束和物理约束关系，建立合 适的装配优先关系，并以此关系来规划装配顺序。b o u r j a u l t 根据操作的几何可行性，产 生一系列的y e s n o 形式的问答，这些问题的答案明确后可推导出所有优先关系f 1 3 j 。 w h i t n e y 改进了提问和回答的方式，但问题的难度对大大增加，提问是任意选择某个装 配联接关系，要求设计人员回答出在该装配联接关系有哪些装配关系必须先建立，哪些 在其之后建立4 堋。用户要对每个装配连接关系依次回答直至所有关系被问完为止。这 种方法需要人机交互参与且用户要穷举所有装配优先关系。在回答问题的过程中，用户 的工作量很大而且很难保证问题答案的准确性和一致性，这会影响装配优先关系的完备 性和正确性，从而容易生成一些不可行装配顺序或者遗漏一些合理可行的装配顺序。 ( b ) 矩阵运算法 矩阵运算方法将装配体中零件之间的连接关系以矩阵方式记录，用线性代数运算的 方法简化联接关系矩阵，得到简化后的矩阵所对应的一定的装配顺序。d i n i 和s a n t o c h i 利用三种矩阵来表达装配体信息：干涉矩阵描述零部件间的干涉情况；联接矩阵描述了 零部件间联接关系类型；接触矩阵描述零部件间的物理接触装配情况铘。通过接触矩阵 和干涉矩阵对装配顺序的可行性进行推理，进而得出可行的装配顺序。 ( c ) 割集法 以h o m e md em e o l i 的研究为代表，用于“可拆即可装”的情况，将装配顺序的寻 找问题转化为对零件关系模型的拆分问题，该方法是利用图论的割集的思想，通过求出 零件关系模型所有割集，判别分割出来的子装配体的拆卸可行性，然后对得到的可行的 子装配体进一步分割，直至分割为单个零件q 。一个装配割集对应一个拆卸( 装配) 操作， 分割顺序的逆顺序对应的就是装配体的装配顺序。割集法是一种纯数学方法，其生成的 很多割集都不满足实际装配过程中的各种优先约束关系，仅仅具有数据意义。割集法的 关键在于装配体拆卸过程中零部件的优先约束的获取和对子装配识别。 ( d ) 知识推理法 知识推理法主要是利用已知装配顺序的固定装配结构与装配体的局部进行匹配，从 哈尔滨i 榭人z 硕十学位论文 而推理出装配顺序。h u a n g 和l g e l l 7 i s ) 采用一阶谓词逻辑来表达装配体的结构、顺序约 束关系和装配资源约束等知识，研制了基于知识推理的装配规划系统。系统以装配体的 三维c a d 模型为输入，辅以人机交互操作来获取零部件的装配优先约束、通过图搜索 算法求解装配体配合特征图的最小割集来产生装配顺序。基于知识的装配顺序的求解方 法，适用范围窄，仅对于特定产品的装配顺序求解比较有效，并且领域知识的获取和表 达需要较深的专业知识。 1 2 2 2 装配顺序规划软计算方法 通常情况下，从传统装配顺序规划方法中产生的都不是最优的装配顺序。为了使装 配成本最小，降低开发总成本，寻找最优的装配顺序或对已经得到的装配顺序进行优化 显示出了必要性。近些年来，人们在装配顺序规划过程中引入基于智能计算的软计算方 法，取得了一定的成果。 1 9 9 4 年，z a d e h 教授将智能技术与模糊逻辑相结合，提出了软计算方法川。随着信 息技术和计算机智能化的发展，软计算方法已经成为几种适用计算技术的总称，即神经 网络、模拟退化算法、遗传算法、模糊逻辑控制等。软计算作为种新的计算模式，为 解决多变量、非线性系统提供了一种有效的方法。不同于传统的“硬计算”追求问题的 精确解，软计算允许存在不精确性和不确定性，所得到的是问题的精确或者不精确的近 似解。 软计算解决复杂化问题时具有很大的灵活性，因为它应用了来源于不同思想的新颖 的方法。对于一个多变量非线性系统而言，软计算方法解决途径具有低成本，较高智能 和可实际操作的特定使它在装配顺序规划中得到了广泛的应用。 ( 1 ) 神经网络方法 神经网络方法模拟人类形象思维，具有自组织、自学习能力，能以并行方式处理信 息，运行速度快，因而它在优化问题求解方面有巨大的优势。神经网络是有大量神经元 广泛互连而成的复杂网络系统。单一神经元可以有许多输入、输出，其输出是输入函数。 神经元之间的相互作用通过联接的权值体现。若将优化计算问题的目标函数对应于网络 能量函数，优化问题的求解过程就对应于网络动态向能量函数极小值方向移动的过程， 稳态点则是优化问题的局部或全局最优解。下面是目前神经网络用于装配序列规划研究 情况。c h e n 为了克服装配序列优化组合爆炸问题，提出一种方法：首先将装配几何约束 关系转变为装配优先关系，然后运用神经网络进行装配顺序化m 。h o n g 和c h o 提出使 用神经网络方法进行机器人装配顺序的优化，他们在研究中考虑装配约束、装配方向改 变和子装配体稳定性等因素建立网络能量的方程，然后基于优先约束推理和专家系统提 6 第1 章绪论 供的装配成本驱动网络的进化方程从而得到优化的装配顺序i l l 。王东云等采用神经网络 进行机器人自动装配规划，他首先利用与或约束知识表示装配体中零件之l h j 的装配先后 关系，构造满足此有限约束条件的h o p f i e l d 神经网络，神经网络的稳定状态对应于一个 可行的装配顺序，然后利用h o p f i e l d 神经网络求解满足此优先约束条件的最佳装配顺序 阎。冯禹等采用基于人工神经网络技术对产品可装配性进行评价，他根据b o o t h r o y d 方 法中提供的实验数据，通过神经网络学习建立了评价模型，依此模型对表征装配体可装 配性的装配时间等指标进行评价，为优选设计方案和改进设计提供决策支持吲。 神经网络的缺点是缺乏全局搜索能力、容易产生不优化的装配顺序，并且常常只能 得到一个局部最优的装配顺序。另外，网络的灵敏度受到参数的选择和初始条件的限制 影响较大；在应用前神经网络须进行训练，而训练时要由专家提供较多可行的装配顺序 作为样本。而样本可能是针对某种类型的产品，并不一定适用于其他类型的产品，致使 该方法应用范围窄。 ( 2 ) 模拟退火算法 模拟退火算法( 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 ) 源于固体退火过程的模拟，通过 模拟固体的退火过程来求解组合优化问题的全局最优解，是一种适合于求解大规模组合 优化问题的有效近似算法。 m o t a v a l l is a e i d 将模拟退火算法应用于装配顺序规划，根据装配体的装配模型得出 装配优先关系，运用多属性理论将装配过程中装配方向的重定向次数和总装配时间组合 成单一目标函数，作为装配顺序优化的评价函数1 。h o n g 和c h o 利用模拟退火算法， 使由装配约束和装配过程的成本映射成的装配顺序能量函数扰动地逐步减小，经过多次 迭代，直至能量函数不再变化为止，最后得到装配成本最低的装配顺序，在优化过程中， 随机选择两个零件并交换其位置产生新的装配顺序瞄1 。m i l n e rj m 等采用装配顺序网络 表达装配顺序，用一种类似于遗传算法的方法扰动顺序网络中路径，产生大量的可行装 配顺序，然后依照模拟退火算法从中寻找装配成本最小的顺序，在给出的实例中，出现 大量成本相近但不同的顺序陋。 模拟退火算法在有较强的局部搜索能力的同时能避免在搜索过程中陷入局部最优， 但陔方法对整个搜索空间的状况了解较少，这样有可能搜索过程并不是在最有希望的搜 索区域进行，由此导致算法的运算效率不高。 ( 3 ) 遗传算法 遗传算法是模仿生物( g e n e t i ca l g o r i t h m ，g a ) 是模仿自然界中生物进化的过程的随机 搜索算法。鉴于遗传算法在解决非线性规划及一些组合优化问题中取得的成功，该算法 7 哈尔滨f 科人学硕十学何论文 被引入到装配顺序规划研究中。 1 9 9 5 年，b o n n e v i l 等首先将遗传算法引入用于求解装配顺序规划的问题，首先由设 计专家预先给定的初始的可行装配顺序，并将装配顺序用装配树来表达，然后将这些装 配顺序作为参加进化运算的染色体组成初始种群，利用交叉、变异两种简单遗传操作产 生后代个体，在进化过程中通过一定的评价、选择机制生成子代种群口7 1 。c h e n 在装配顺 序规划中使用复制、交叉、变异、剪贴和断连五种遗传算子寻找装配顺序优化解，他随 机给定规模固定的初始种群，依概率选择装配顺序，然后运用遗传算子进行操作产生后 代个体，子代和父代个体按照适应度值选择组成下一代个体阐。在c h e n 后续研究中， 他又提出了几种新的遗传算子用于提高装配顺序规划的性能，这些研究表明，遗传算子 执行概率对装配顺序规划的收敛性能和最终解的质量有直接的影响，所以控制遗传算子 执行概率可以提高该算法的性能陋1 。 g u a n q m l 等提出用基因团编码描述产品装配的相关信息，将装配序列表示为基因团 排列组成的染色体，改进了传统的基因算法，通过交叉和多层次变异实现基于基因团编 码的多信息装配序列并行优化。该算法受初始种群影响较大，如果初始装配序列全都不 可行，而且所有单个序列中的各个基因团都是随机的，将不可能引导优化计算向好的方 向发展，优化计算将不可收敛和收敛到非优化的解。 从理论上来说，使用遗传算法找到全局最优装配序列要求参加演化计算的种群规模 要足够大，迭代次数要无限多，但在计算资源和时i 日j 限制下是达不到要求的。因此，遗 传算法求解装配规划问题的效率和结果依赖于初始种群规模及其质量、遗传算子及其操 作概率等因素。 ( 4 ) 蚁群算法 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 是一种基于群体的模拟进化算法，它的思 想来源于自然界中蚂蚁的集体觅食行，正反馈和分布式计算的特点使得该算法与启发式 相结合成为求解复杂组合优化问题的一种新方法p 。f a i l l i 和d i n i 将蚁群算法用于装配 拆卸序列优化的研究，给出了算法中各个参数对算法性能的影响，但是他们的算法没有 涉及到如何判断装配顺序的几何可行性，并且所给出的网络模型过于复杂，不利于自动 化建立1 3 2 1 。w a n g 等给出了从拆卸顺序的几何可行性出发的解决装配拆卸列规划问题的 蚁群算法，但是该算法最终的解具有局限性，并且最优解必须由有经验的技师从最终解 空间中选取，同时算法中没有考虑零件和子装配体的稳定性，因此生成的顺序不能全面 反映工程情况p m 。 蚁群算法作为一种具有分布、并行、全局收敛能力等优点的新型智能优化方法，在 8 第1 币绪论 解决a s p 问题时能快速得到一组可行的装配顺序。但由于初期路径上信息素医乏，该 算法一般需要较长时问爿能搜索出问题的最优解或者较优解，并且搜索后期容易有停滞 现象出现。 经过以上综述分析，各个方法各有所长，因此目前各种不同的方法相结合，取长补 短，是装配顺序生成方法的必然的发展趋势。 1 3 本文的研究内容及章节安排 本文研究的主要内容是： 1 对装配顺序规划的生成与优化技术进行分析，提出了产品装配建模方法和构建 了装配信息模型，在建立装配模型的基础上，论述装配顺序规划几何可行性判别方法和 稳定性的判别方法。 2 本文着重研究了装配顺序规划中子装配体的识别技术，提出赋权接触联接无 向图的建立方法，得到其邻接矩阵，根据无向图的接触联接关系并结合干涉矩阵支撑 矩阵，对子装配体识别算法，子装配体识别完成后以子装配体为整体对装配体的无向图 和相关矩阵简化，并建立独立的子装配体无向图和矩阵，为后续工作做好准备。 3 深入研究遗传算法，对其各种算子操作及相关参数的设计确定的方法最后用遗 传算法选择适当的算子对层次化的装配模型进行装配顺序规划。 4 以某减速器为例，根据上述方法对其进行装配顺序规划，以实例验证本文提出 方法的有效性。 本文共分为五章，具体的章节安排如下： 第1 章是绪论部分，主要介绍装配顺序规划研究的背景和意义，详细论述了国内外 学者在该相关领域的研究情况，并指出了论文的主要内容和章节安排。 第2 章主要研究装配顺序的建模方法，建立相关矩阵，根据该模型在装配顺序生成 过程中装配顺序的可行性和稳定性的判定方法。 第3 章根据装配的赋权接触联接无向图，分别设计了基础零件、i 型子装配体及 l i 型子装配体的识别方法及具体流程。结合实例对算法进行实现， 第4 章基于遗传算法的装配顺序规划方法。对遗传算法进行简要介绍，同时介绍了 遗传算法的各种算子及相关参数。分析模型及规划目标，建立合适适应度函数，选择适 当的遗传算子操作。结合装配顺序的可行性和稳定性的判定方法，设计出了在遗传计算 过程中适应度函数中参数的计算方法。 9 哈尔滨i ：稗人学硕 j 学何论文 第5 章将子装配体识别和遗传算法对装配顺序规划问题的求解相结合，设计整体规 划方法。以减速器为实例，对其进行装配顺序规划，对方法进行具体的实现。 1 0 第2 寺装配顺序的儿何可行件j 稳定件 2 1 概述 第2 章装配顺序的可行性与稳定性 装配顺序规划是具有强约束的组合优化问题，其目的是寻找到最优装配顺序来指导 产品装配，达到降低产品装配成本和提高装配质量的目标。在本论文研究中，装配顺序 规划主要是根据装配体模型中零部件联接情况，确定它们之间的几何约束和稳定性约束 关系，然后使用遗传算法来生成合理的、较优的装配顺序。产品中零件之间的几何约束 和装配过程的稳定性约束直接关系着装配顺序的可行性及产品的装配质量。装配顺序只 有满足几何约束和稳定性约束才能实现装配操作，最终完成装配任务，保证装配操作的 可靠性和装配质量。求解a p s 问题的遗传算法本质上是一类随机搜索算法，得到装配 顺序很有可能违反装配几何约束关系和装配过程稳定性约束。违反装配几何装配约束关 系的装配顺序，装配操作存在干涉情况，是几何不可行顺序，使用该顺序指导装配，装 配任务最终是无法完成的。违反装配过程稳定性约束的装配顺序，会直接影响装配工具 的复杂性，装配操作的可靠性、装配精度和装配成本。论文中我们采用装配顺序评价函 数即适应度函数来评价装配顺序的优劣，表达装配顺序的满意程度，需要分析、判别装 配顺序的几何可行性和装配过程的稳定性，对几何不可行装配顺序和装配过程不稳定的 装配顺序进行删选，扩大装配顺序个体之间的评价函数值差异，以保证遗传算法求解装 配顺序规划问题的可靠性。因此，在装配顺序规划中分析、判别装配顺序的可行性与装 配过程中的稳定性具有重要意义p 1 。 2 2 产品的装配模型 产品的装配模型为顺序规划提供装配体和零部件的相关信息，是对产品装配顺序进 行规划的基础。因此装配体模型选择正确与否，会大大影响装配顺序的几何可行性及稳 定性的分析。本文在第1 章已经介绍过产品装配信息模型的表达，本文选择层次模型和 关系模型结合来表达装配体。在零件数量较少、关系较为简单时，图结构可以很好的表 达装配体模型，但随着零件数量增加、零件之间关系的愈加复杂，图结构也愈加复杂， 图结构不能满足后续规划的需要。图模型也可以用相应的矩阵模型来表示，而用矩阵模 型来表达装配体模型更易于计算机存储与表达，同时也有利于装配体模型根据需要进行 更新和扩展，并且矩阵结构更易于推理分析。 哈尔滨l j j f l ! 人学硕 学付论文 根据装配顺序规划步骤中需要信息不同，将结合使用图模型和矩阵模型。本章采用 集成拆卸阻碍矩阵和支撑矩阵来对装配体进行建模，并在此基础上对产品装配顺序进行 几何可行性与稳定性分析。在第3 章中，将建立更适合子装配体识别的赋权无向图模型， 具体方法见第三章。 2 3 装配顺序的几何可行性 本文中装配顺序的规划都是基于逆向拆卸法，即“可拆即可装 的方法。逆向拆卸 法：也称为间接法，假定拆卸的零件都是刚性的，则拆卸与装配可逆，通过拆卸确定装 配体拆卸顺序的逆序就可以作为装配体的装配顺序。直接分析安装好的装配体，很多约 束干涉都已确定，这使得拆卸比装配具有更多的约束条件，效率更高且易于程序实现。 利用拆卸法根据零件的几何数据信息和拆卸阻碍干涉检验来分析装配体，从而得到几何 上可行的顺序。 几何可行装配顺序中，不仅零件在装配到位后，零件之间不存在干涉，而且在装配 过程中零件也应当没有阻碍干涉现象出现。零件到位后存在干涉的原因：零件几何形状、 尺寸上的缺陷导致，这些缺陷主要是因为零件在设计、制造过程中的错误产生的。这种 干涉可以在装配体中零件位置确定后通过静态干涉检测的办法解决。在装配过程中产生 干涉的主要原因：第一，装配路径的不合理导致：第二，不合理的零件装配顺序导致。 第一种原因造成的干涉是由于在装配空间中零件的位姿及运动变换矩阵的表示不正确。 本章只考虑装配顺序、装配方向的选择不匹配或者装配顺序选择不合理造成的阻碍 问题，通过建立集成拆卸阻碍矩阵的方法分析、判断装配顺序的几何可行性，推导零件 的可行装配方向集。 2 3 1 集成拆卸阻碍矩阵 零件的拆卸阻碍矩阵表示零件沿某方向移动到无限远的过程中与其他零件的阻碍 干涉情况。考虑零件沿x 、y 、z 轴正负方向上与其他零件的阻碍关系，从而推导出装配 过程中零件的可行性方向。如果直接使用全局阻碍矩阵表达零件间阻碍关系，必然要建 立6 个装配方向上的拆卸阻碍矩阵，矩阵中存在的一些冗余信息会影响判别方法的效率。 本节引入集成拆卸阻碍矩阵，用于描述装配体中任意零件在6 个方向伍、y 、z 、吠、儿 吃) 上拆卸时与其他零件是否有阻碍干涉情况，通过该矩阵分析、判别零件的几何可行性， 可以推导出装配体中任一零件的可行拆卸方向。假定某一装配体彳= p 1 ，p 2 ，胁 ， 由九个零件组成，那么需要建立该装配体的集成拆卸阻碍矩阵是一个咒行，6 ，l 列的矩 1 2 第2 章装配顺序的j l f , f 可行性j 稳定性 阵，d ： l d = t j , 一1 0 似i 埘i 泣 1 0 0 拟i 趟l 挝 1 0 毋0 倒l 谢i 噬 1 0 辞0 钗l 耐l 珑 i o 一0 娃l 蚵l 证 1 0 0 0 “i 捌i 碗 1 0 0 0 “l 侧i 碰1 0 0 0 饭i 恻i 谨1 0 0 0 ，d f l 耐i 眭 ( 2 1 ) 其中，矩阵元素知( ( f ，j 1 1 , 2 ，咒) ) ，d 仁，y ，z ，x 7 ，y 7 ，z ) ，x ，y ，z 表示z ，y ，z 的负 方向) 表示零件p i 沿d 方向拆卸时是否被零件胁所阻碍发生干涉，l i j a = 1 表示有阻碍产生； 否则表示不产生阻碍。规定当f 巧时对于任意的方向d ，五埘= 0 。 为了更好的说明集成拆卸阻碍矩阵的建立方法，以图2 1 所示的装配体结构，考察 该装配体中零件沿坐标轴正负六个方向装配时与其它零件相互阻碍干涉的情况。该装配 体有5 个零件组成，因此其集成拆卸阻碍矩阵是一个5 行，6 x 5 列的矩阵。现在考察拆 卸零件1 时，零件2 对零件1 的阻碍情况，确定矩阵中元素厶列的取值。先考察沿坐标 轴识方向的阻碍干涉情况，零件1 沿戗方向拆卸时被零件2 阻碍，所以h = 1 。同样， 零件1 沿杪、佗、- y 、吃方向拆卸时也被零件2 所阻碍，所以：，= ，l 五= 1 1 2 y i 严，1 2 z = 1 。 而零件1 沿坐标轴的吱方向拆卸时，零件2 不会对其产生阻碍，所以矩阵元素1 1 ：，。= 0 。 同理，可以确定集成拆卸阻碍矩阵中其他各元素的取值。图2 2 给出了此装配体的集成 拆卸阻碍矩阵。 2 巍齄 3 德 4 垫露 图2 1 某装配体结构图 1 3 y x 哈尔滨1 j 稗人学硕f j 学何论文 i d = 0 0 0 0 0 01 0 1 1 1 11 1 1 0 1 l1 0 1 1 1 11 0 1 1 1 l 0 1 1 1 1 10 0 0 0 0 00 0 1 1 1 11 0 0 0 0 01 0 0 0 0 0 1 1 0 1 1 10 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 01 0 0 0 0 0 0 11 11 10 1 0 0 0 0 0 1 0 0 0 00 0 0 0 0 01 0 0 0 0 0 0 11 11 10 1 0 0 0 00 1 0 0 0 00 1 0 0 0 00 0 0 0 0 0 图2 2 集成拆卸阻碍矩阵 2 3 2 装配顺序的几何可行性分析 采用逆向拆卸法求解装配顺序时，要求拆卸零件移动时至少在一个方向上不受其他 任何零件的阻碍；否则拆卸就是不成功的，该拆卸顺序的逆序即装配顺序不能满足几何 可行性。 假定某装配体拆卸过程中，零件p f 是在某状态下待拆卸的零件，那么判定零件肌 在某个方向d 上与其他零件所有零件的拆卸阻碍的情况可以通过公式运算得出： 屯= t ua 2 da a i n d ( 2 2 ) 如果l = 0 成立，则零件鼽在d 方向上拆卸就不会被阻碍，若屯= 0 则表示存在零 件阻碍p i 从d 方向上拆卸。换而言之，若存在一个方向k ( k 工，y ，z ，x ，y ，z ) ，零件 肼在该方向上拆卸时没有零件对其阻碍，即k 一0 ，则说明零件p f 满足拆卸的几何可行 性，否则零件就不满足几何可行性而不能被拆卸。为了保持矩阵l 在拆卸过程中能够实 时地正确的表示在拆卸过程中零件之间的阻碍情况，当某个零件p “0 七，1 ) 被成功拆卸 下来后，对任意的_ 和d ( _ l 2 ，刀) ，d z ，y ，z ，x ，y ，z ，) ) ，令集成阻碍矩阵中的元素 乇= 0 ，即零件肌在任何方向上对任何零件都不会产生阻碍。 以图2 1 所示装配体为例，在所有零件均未被拆卸的初始状态，判断各个零件拆卸 时的几何可行性，零件5 可以拆卸，拆卸方向为懈方向。而其他零件部满足拆卸的几何 可行性，不能被拆卸。当成功拆卸下零件5 之后，矩阵元素j r 脚= 0 ( j e 1 , 2 ，以) ， de x ，y ，z ，x7 ，y 7 ，z ，1 ) 要被更新为“0 ”。更新后的集成拆卸阻碍矩阵如图2 3 所示。 i d ； 0 0 0 0 0 01 0 1 1 1 11 1 1 0 1 11 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 10 0 0 0 0 00 0 1 1 1 1 1 0 0 0 0 00 0 0 0 0 0 1 1 0 1 1 10 0 1 1 1 10 0 0 0 0 01 0 0 0 0 00 0 0 0 0 0 0 l11110 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0