中文翻译-运用紧凑相邻法则对非规则零件图样进行大规模编排

运用紧凑相邻法则对非规则零件图样进行大规模编排 香港 九龙 泰奇大道 香港城市大学 制造及管理工程系 摘要 目前广泛应用的典型编排方法是对单个零件图样的几何倾斜式编排，或者把图样自其初始位置到旋转 180 一步一步地逐个选择式编排。例如直交排布式。然而，这是一种对最佳原材料布置方法的盲目性探索。从几何方面来说，当参与排样的图样有多个时，该方法就变得毫无效率可言。它也不怎么适合处理具有一系列方向约束的零件图样。在本论文中，提出了一种结合紧凑 相邻法则（ 遗传运算法则（ 优化大规模编排工艺的运算方法，该方法同时还考虑到了多方面的初始位置约束。 关键词：原材料的切断问题；编排；紧凑相邻运算法则；遗传算法；初始位置约束 1简介 原材料切断问题在许多工业领域是一个有趣的问题，如服装业，纸张工业，船体制造业各钢铁材料工业。 先开始研究运用线性程序平解决原材料的矩形切断问题。对于原材料的不规则形状切断问题， 试运用一种对我们来说具有启发示的方法来解决。他把这个问题分为两个从属的问题。即所谓的串 丛式和筑巢式编排。串丛式编排是详细地说明选择的零件图样适合于给定的原材料，而巢式编排在其后进行。巢式或串丛式编排可以大概地分为两个大的种类，即，大规模与小规模编排。它们之间的不同在于对给定原材料能编排的零件图样数量的级别。在小规模编排中，只需找到串丛编排和给定原材料的内在方向关系。然而，这个问题在大规模巢式编排时变得非常复杂，因为同时还要考虑到编排的各个相同图样内在的空间关系。根据传统的方法，有两种基本的方法普遍运用于处理这种类型的编排。它们分别是：“相似六边形”方法和“直交编排”方法。 在此，选择了一个典 型的零件图样来解说这两种技术方法。如图 1a 所示，该零件同时具有外凸和内凹的特征。在数字转换器的帮助下得到了零件的轮廓形状，如图 1b 所示。其面积（ 为 平方单位。在 似六边形”法则中，该零件最初以一个外凸的多边形来近似表达，然后，进一步地以包含更少图形要素的外凸多边形来表达，直到得到一个包住零件的六过形，如图 1c 所示。然后，在给定的原村料上，互相不重叠地辅上这个六 图 1.（ a）所选的用于示范 法工作原理的平 板形图样。（ b） c）相近多边形。（ d）相近直角图形。 (e)用相近六边形法则得到的布局图，材料利用率为 （ f） 用正交相近算法得到的布局图，村料利用率为 (g)用 法得到的布局图，材料利用率为 边形图样。用这种方法产生的最终布局图如图 1e 所示。委容易证明，由于这种较差的相近表达原因，尤其是对于某些不规则零件图样，这种方法没有较高的效率。加一个问题是零件的图样或串丛图样只能采取两个位置方向（ 0 或 180 ），因而没有开发的余地或考虑其它允许的编排方向。 在 使用的第二种方法中，通过一个矩形来近似表达单个的零件或串丛图形而得到编排方法，如图 1d 所示。然后，这个矩形以正交的方式复制，得到的最终布局图如图 1f 所示。当零件图样没有或只有部分方向约束时，这种方法应用起来非常容易，例如，单个零件或串丛图形能在某个确定的角度转动，从而适合于原材料的编排。和“相近六边形”法则相似，这种方法的主要不足之处是正交排列在很大程度上依赖于零件的形状。更多的是，在有多 个方向约束的情况下，确定一个适合的旋向往往需要花费更多的时间。 为了增加编排的正确度及速度， 提出了一种紧凑相邻法则（ 该法则考虑到相邻图样的数量关系及它们之间的共同空间。图 1g 所示为由 法产生的布局图，和相似六边形及正交法则相比，在相同区域该方法具有更高的布置密度。然而，从目前形式来看， 要设计用于编排具有完全方向约束的零件图样，对于零件图样有更多的自由度时达不到理想的要求。 本文探索的目的在于通过合并零件图样在初始方向具有的可能自由度和符合普通规则的遗传算法来提高 适应性。优化布局图的生成。这种新的方法被转化输入用面对对象语言编写的 C+计算机程序。这种算法能处理包括有任意直线和圆弧形状的零件的两个方向的平面巢编问题。通过一个有帮助的典型例子，可以看到，在本文中， 重要作用和相关的计算机程序将处于决定性的地位。 2紧凑相邻法则的描述 当零件被移动而形成不同的排列时， 踪变化的相邻零件图样的特征，如图2示简要示意图。当剪切位移面增加时，上面及下面的相邻特征趋向于破坏，这是由于结晶化的方向发生了改变。最后，得到一个该材料的最大紧凑结构和相关数 值。即得到所谓的“全体紧凑利用率”（ 。不论零件能够旋转与否， 出了任何所选材料的最高屈服极限，因而可作为编排过程中一个临界标准指数。找到紧凑相邻的主要步骤包括：（ 1）产生一个“自滑移路径”或者一个非适多边形（ 如图 3a 所示，来引导两个非重叠零件图样的运动关系。 图 2 圆形图样的典型相邻相结图 （ a）正交直角排布形成的单元，216r 。（ b）由于层 的剪切导致的剪切正交排布。（ c）六边形排布的最凑结构单元，236 r 。其中； 示单体的面积； r 表圆形图样的半径； （ 2）定义结晶化方向，如图 3b 所示，在大规模编排中提供基本的数据来建造充满所给材料的全部相邻图样。 3大规模编排的建议算法 本单元 论述通过利用遗传算法而使所提及的 术得到加强。一个平面零件图样可以被分为直线和元弧要素。多边形表示法可以将外凸或内凹的元弧以直线代替。确切的直线段数目决定于所要求的精确度。清除或偏移生成也是一个有助于 术成功的必不可少的过程。一种算法产生所要求的偏移，称作“三点岛屿跟踪”方法，已经与目前的编排系统结合在一起。 图 3 （ a）以自滑移路径方式产生相邻结构时所包含的步骤。（ b）以六边形排布得到的优化相邻结构单元， 到 于大规模编排 在前述章节，已经涉 及到得到最紧凑相邻编排所包括的一些基本步骤。如图3b 所示。接下来的重点是确定一个最适位置来放置第一个图样并扩展这种结构，使其充满整个原材料。编排全方位约束的零件图样时，只需确定一个“编排向量来定认相邻图样的放置位置。然而，当偏排有限的或完全没有约束的图样时，由于要考虑到可能的连接方式，这个问题变得非常复杂。在这种情况下，第一步是根据原始位置限制进行球形布排或不依靠原始位置约束而在原材料内部区域随意确定相邻图样位置。例如，定义一个向量后，确定“编排方向因而就确定了一个适宜相邻图样排布生长的方向。全部所需的几何计算如图 4 的简括。优化们最终决定一个最紧凑相邻结构。有理由相信，没有某种独特的数学方法来计算这些参数。另外，我们并不能得到一个彻底的研究结果因为计算时间上的限制，尤其是编排某些具有许多要素和外凸特征的零件及要花费太长的时间用于计算的零件。因此，在本文论述中 ，应用了一种目前普遍流行的优化方法，即 的主要原理如下节所述。 图 4 根据前个定义位置，以编排向量3 2 于优化布局 处理预见性问题时保持着流行的趋势。基于其性能，这些问题的最适解决方法不仅存在，而且类似于有性繁殖，通过与其它的候选方法交换信息而形成的新的一代。在进行任何遗传操作之前，须定义最适宜功能和偏码方法。如前所提及的，对零件进行编排的目的 在于通过配合串丛图样而使它们占据一最小的面积从而减少废料。为了表示一个详细布局的紧凑性，可以确信最直接的方式就是使它和原材料的区域发生某种联系。 ),(在此， x 是给定原材料的面积， y 是从给定的原材料上切下的所有零件图样的面积总和。 编码可以直接或间接地影响优化过程，这是因为我们的重点是确定转换位置（例如：偏排向量旋转角度（如：偏排 角度此它们被选作偏码参数来引导交叠和遗传操作的交换待征。 3 3 遗传算法 该方法最初由 出， 目的在于通过模仿自然界的进化过程优化解决相关问题的方法。和人类的进化相似，一个典型的 法包括以下的遗传待征。 3 3 1 初始化 首先，通过随意选取所有参数的值产生第一次遗传操作结果。在实际工作应用中，经常出现限制自由级转的情况，在级进模设计中，由于设置一致的导向装置，减少随意后进行的薄板冲压时的弯曲角和相似装置有较高的费用。用此有许多 原始位置区域限制。图 5 所示为两个具有不同约束和非约束区域的典型零件，结果，可以假设零件被限制折当前情形下的两个极限角度位置。因此。任意产生一个偏排角度 面的不等式被证明满足条件： , （ )1,1,在此， N 和如：21 ,）和零件 图 5 旋转约束和第一个无约束区域的次级限制关系（ a）固定图样（ 1P ）： 01 , 1 ,1=30 ； 1702,1 1902,1 （ b）活动图样（ 2P ）： 01 , 2 601,2 2002,2 ， 2302,2 。 3 3 2 适值计算 根据适宜原理，每一次产生的布局 (i )和适宜值（定着的布局的紧凑性。这个值在随后操作中用来决定将地繁殖步骤选用的候选值。 3 3 3 复制 根据最适值 P，每一分体有一个会被选用于随后的宽度随意选择过程。好的个体，例如 高的 P 值，比低的适合值具有最多的机会被选用，这一点很重要。 3 3 4 叠合 这是决定 F 一代成员的最重要的一步。繁殖的个体称作布局 i 和 j 在叠合操作中交差了，叠合操作有助于利用其偏排角度一个新的 3 3 5 转变 事实上，有多种方法可以完成这种操作。在当前系统中，通过在 15 范围 内随意旋转相邻图样， i+可能性外基本上是成功的。 3 4 多零件图样的大规模编排 对于多零件图样的切断问题，前述的运算法则仍然是有效的。为了增大点大的研究空间，一种丛串过程首先用于收集零件。例如图 6 所示的 8 个零件用技术收集面一种串丛如图 6 所示： 串排以后，有一些操作用于移去所有内部边界。因而在随后的操作中达到更快的计算速度。通过重复上述步骤，最后最终可得到最佳紧凑相邻结构如图 6在该法已适合于大规模的偏排。 为了测验所提示的技术用于大规模偏排的效率，把所得到后结果与传统偏排技 术如正相似法，由于使用的方法在材料利用方面进行比较。在此使用 200有任何位置限制在零件的偏排方面。一个由正交相近法产生的典型布局和两个由所提出的技术得到的布局如图 7 所示。相应的，就如所阅述的，本文年出的技术可以给出一个更加好的解决方法比传统的方法。此外，这种方法经过几次传代可得到更优化的组合。当材料的尺寸更大时更时如此。当材料尺寸增大时，运用 法优化偏排向量 图 6 解决多图样编排时原材料切断问题所涉及的方法 （ a）需编排或串丛的图样。（ b）采用平移方法生成的串丛图样。（ c）以 法产生的六边形排样单元 4 个案研究 为了测验所提出的技术用于大规模编排时的效率，把所得到的结果与传统编排技术如正交相似法（由 先所使用的方法）在材料利用率方面进比较。在此使用 200位的原材料，在零件的编排方面没有任何位置限制。由正交相近法产生的典型排样图和两个由本文中提及的方法得到的排样图如图 7 所示。就如前所阐述的，本文提及的方法比传统的方法能给出 一个更加好的解决方案。此外，这种方法经过几次遗传操作可以得到一个最优的组合。当材料的尺寸较大时更是如此。当材料的尺寸增大时，运用 法优化编排向量 图 7