基于小生境遗传模拟退火算法的不规则件优化排样

基于小生境遗传模拟退火算法的不规则件优化排样 史俊友，苏传生，翟红岩 (青岛科技大学 机电工程学院，山东 青岛 266061) 摘要：对于二维不规则图形零件在排样区域上的最优排列，将排样和制造工艺联系起来，将多边形 各边向外扩充，为零件预留加工余量；然后采用遗传模拟退火算法与小生境技术相结合，寻找排样 件在排样时的最优次序及各自的旋转角度，再用基于“最低水平线与填充算法相结合”策略的启发 式排样算法实现二维不规则件自动排样，得到满意的优化排样结果。 关键词：遗传模拟退火算法；小生境；加工余量；最低水平线；优化排样 中图分类号：TP 391.7 文献标识码： A Optimal layout of irregular parts based on Niching Genetic Simulated Annealing Algorithm SHI Jun-you，SU Chuan-sheng ，ZHAI Hong-yan (College of Mechanical and Electrical Engineering，Qingdao University of Science and Technology，Qingdao 266061 ，China ) Abstract：To solve the two-dimensional irregular parts packing problem, firstly the problem is associated with manufacturing process, every side of polygons is expanded in consideration of the machining allowance. Then genetic simulated annealing algorithm and niche are integrated to look for the best sequence of the irregular parts and each parts optimum rotating angle, finally the lowest horizontal algorithm and filling algorithm are combined to complete the automatic layout. The satisfactory results of optimal layout have been obtained. Key words： genetic simulated annealing algorithm；niche ；machining allowance；the lowest horizontal algorithm；optimal layout 最大限度地节约材料，提高材料利用率是实际生产中的一个基本原则，由于在工业生产中排样 问题广泛存在，因而解决它具有深远的理论意义和现实意义。寻找通用性好、求解质量和效率高、 易于实现的排样问题求解算法一直是该领域所追求的目标 1。 遗传算法和模拟退火算法是当今优化技术领域应用最广泛的智能优化算法 2,3。然而，大量研究 表明 4，遗传算法存在早熟收敛、局部寻优能力差等许多不足，这使得最终搜索结果可能是局部最 优解。模拟退火算法能够跳出局部最优解，具有较强的局部搜索能力，但其把握搜索过程的能力不 强。近年来，许多研究人员把不规则零件排样转化为矩形件排样来处理，这种方法简单易行，但由 于没有充分考虑零件具体的外形特征，会导致材料利用率的降低。 为此本文充分考虑不规则件自身的形状特征，将排样和制造工艺联系起来，将多边形各边向外 扩充，为零件预留加工余量，对扩充后的零件，求取其最小包络矩形，并对一些形状互补的零件构 造矩形排样单元进行优化组合，使零件区域在最小包络矩形中所占的比例尽可能大，对组合后的图 形再求取最小包络矩形，同时对多边形的外轮廓与包络矩形之间产生的空白区域进行填充；从遗传 模拟退火算法优化策略的构造出发，融合小生境技术的思想，形成一种小生境遗传模拟退火算法 NGSA 算法，算法具有较强的全局和局部搜索能力，在此基础上开发了不规则件优化排样系统。 收稿日期：2008-12-03 作者简介：史俊友(1970-)，男(汉)，教授 2 1 排样模型 零件在板材上的定位实际上只需 3 个参数即可完成。这 3 个参数是该零件的一个给定点在板材 上的坐标( X，Y)和该零件的排放角度 。当这 3 个参数确定后，该零件的其它各顶点坐标都可由这 3 个参数计算。设 Gj(j J，J 为零件集合) 为零件 j 的图形，( xj，y j)为该零件的给定点的坐标，则该 零件在板材上的定位可表示为下述过程：先将该零件以该定点为轴旋转角度 j，然后再将定点 (xj， yj)在板材作位移(x j， yj)。这时零件 j 在板材上的方位可表示为 Gj(xj，y j， j)。零件的数量 为 n，S j 为零件 j 的面积。L 为板材的长，D 为板材的宽，排样图形外接矩形高度为 H，宽度为 W。定义排样布局的原材料利用率 ， 为排样零件的面积和与排样图形外接矩形的面积的比值。 零件优化排样的模型为 5： (1)j1H njSW Gj (xj，y j， j )G ( xk， yk， k ) = ， j k (2) S.t. 0 Yji ( xj，y j， j ) L ji = 0，1， n j (3) 0 Xji ( xj，y j， j ) D ji = 0，1， n j (4) 式(2)表示零件 j 与零件 k 互不重叠； 和 为考虑jiXjiY 加工余量后零件 j 的第 i 个顶点的坐标，式(3)和式(4) 表示 零件不能排在板材之外。 2 零件预处理 2.1 多边形的近似表示 排样过程中，通过与 CAD 的接口，可以方便地提取零 件中各实体的信息。在获取零件中的各实体信息后，还需 进一步得知零件中各实体之间的拓扑关系。所以必须对实体的端点进行排序处理，使其成为一个封 闭的轮廓，满足零件表达的要求。 加工余量的大小对零件的加工质量和制造的经济性均有较大的影响。对每个不规则件考虑其加 工余量 r，将零件多边形各边向外扩充 r 距离，各边延长相交，得到与原多边形相似的新多边形， 如图 1 所示。由原多边形各顶点坐标求出考虑加工余量后各多边形顶点坐标，并将此作为进行优化 计算的基本数学信息。 2. 2 多边形外包络矩形的求取 不规则件的优化排样通常采用近似法，即把不规则件近 似为矩形件来处理，从而简化为矩形件排样问题。但如果在 近似过程中未充分考虑零件的形状特征，把不规则件简单地 当成矩形件来处理，有可能导致材料利用率的降低。 采用求取零件最小包络矩形的方法，先设定一矩形包络 率，对包络率满足要求的零件用最小包络矩形替代，对不满 足要求的零件进行优化组合，使零件区域在最小包络矩形中 所占比例尽可能大，对组合后的图形再求取最小包络矩形， 二维不规则件排样问题就转化为矩形件排样问题。 针对零件图形内部有空白区域的情况，在不发生干涉的前提下，选择合适的零件对内空白区域 图 2 空白区域填充 Fig.2 The filling of blank space r 图 1 多边形加工余量 Fig.1 The machining allowance of polygon 3 进行填充，如果有多个零件可以填充到一个空白区域中，采用最佳面积适配法。设区域面积为 SE， 各零件面积为 Si，且 SiS E，计算 S=min(SE - Si)，S 所对应的零件即为填充的零件。空白区域填充 6如 图 2 所示。 3 算法描述 3.1 GASA 混合优化策略 遗传模拟退火算法是将遗传算法与模拟退火算法相结合而构成的一种优化算法，引入了局部 搜索过程；以遗传算法运算流程为主体流程，将模拟退火机制融入其中，进一步调整优化群体。整 个算法的执行过程由两部分组成：首先通过遗传算法部分的进化操作(侧重全局搜索) 产生较优良的 一个群体，再利用模拟退火算法部分的退火操作(侧重局部搜索 )来进行基因个体的优化调整，运行 过程反复迭代，直到满足终止条件为止。这种算法思想策略，从对全局最优解的搜索角度和算法的 进化速度上来提高模拟退火遗传算法的性能。 3.2 小生境技术 在生物学中，把某种特定环境及其在此环境中生存的组织称为小生境(niche) 7，而把有共同特 性的一些组织称作物种。基本遗传算法在进行个体交配时采用的是随机方式，这增强了对问题解空 间的搜索能力，但也带来了交配的有效性以及优化效率不太理想等问题。为解决这些问题，在基本 遗传算法中引入小生境技术。其不仅能够有效地保证群体中解的多样性，而且在问题求解的收敛速 度、计算精度、全局搜索能力等方面表现出明显的效果，是一种较有效的方法。 3.3 NGSA 混合优化策略 NGSA 算法应用于不规则件的求 解过程可描述为： (1) 设置进化代数计数器 t = 1，随 机产生含 M 个个体的初始种群 P0(t)， 同时求出各个体的适应度 Fi(i = 1，2，M )； (2) 对种群 P0(t)中的个体按其适应 度大小降序排列，记录前 N 个个体 (NM)为较好群体 P1(t)，以免部分适应 度高的个体在遗传操作中被淘汰掉； (3) 采用遗传算法进行选择、交叉、 变异等操作，生成群体 P2(t)； 对种群 P0(t)进行预选择操作， 得种群 Pop1(t)，选择操作时，先进行 赌盘选择，再采用精英选择。 采用单点交叉算子对种群 Pop1 (t)进行交叉操作，得种群 Pop2 (t)； 采用均匀变异算子对种群 Pop2 (t)进行变异操作，得到种群 P2(t)； (4) 以 P2(t)为初始种群，对其中各 个体进行模拟退火运算，得到新的规模为 M 的群体 P3(t)； (5) 将 P1(t)、P 2(t)、P 3(t)合并构成一个规模为 N + M2 的新群体 P4(t)，采用小生境技术进行 淘汰，两两比较各个体间的海明距离，若两者间的海明距离在预先指定的数值之内，对适应度较低 的个体施加一个较强的罚函数，极大地降低其适应度，即增加其被淘汰的概率； 开始 结束 初始化算法参数 ， 确定解码 、 编码方案 初始化 种群 M ， 设置进化代数计数器 评价当前种群各个体 ， 记录前 N 个个体 是否满足收敛准则 执行 G A 的选择 、 交叉 、 变异操作 得到 S A 的初始种群 ， 确定抽样数目 进行 S A 搜索 进行 S A 搜索 计数器替换 计数器替换 输出优化 排样结果 对 M + N 个遗传个体 、 M 个模拟退火个体构成的新 群体进行小生境技术淘汰运算 Y N . . . . . . 图 3 NGSA 算法流程图 Fig.3 The flow chart of NGSA algorithm 4 (6) 对 P4(t)进行评价，取出其中较好的前 M 个个体构成 P0(t)，降低退火温度，转步骤(2)，循 环执行。 (7) 判断是否满足收敛条件，如不满足终止条件，则更新进化代数计数器，即 t = t + 1，转至(6)； 若满足终止条件，则终止运算，输出计算结果。算法流程如图 3 所示。 3.4 NGSA 算法的设计实现 (1) 编码机制 由于二进制编码不能直接反映多边形的排样方式，因此本文采用十进制整数编码方法，它具 有编码和解码操作简单、遗传操作便于实现等优点。将所有参加排样不同类型的零件按面积大小排 列并加以编号，染色体的长度与排样件的类型数相同。此编码方式是基于一种排列顺序的基因编码 方式，即所有排样类型的一个排列顺序作为一个染色体。编码设计的关键是在染色体中产生不同编 号的遗传算子，相应的解码方法则根据所采用的解码方法把具体的零件定位在板材上。 (2) 解码方法 由遗传算法产生一个个体的编码后，能否快速求出其对应的排样图是一个关键，同时只有求 出该个体所对应的排样图，才能计算其对应的适应度值，并对该个体进行评价。笔者采用一种基于 零件最高轮廓线的“最低水平线” 8和填充算法相结合的解码方法。对于在多张板材上排放零件的 问题，当零件的最高轮廓线 y 坐标大于板材的长度或者最高轮廓线的终点 x 坐标大于板材的宽度时， 更换新板材，更新最低水平线及最高轮廓线，然后在新板材上按顺序继续排放零件。 4 运行实例 笔者应用小生境遗传模拟退火算法开发了实用的不规则件 优化排样系统。已证明该系统能有效地解决任意二维不规则零 件的最优排样问题。以下算例可以证明此算法的有效性和可行 性。 (1) 矩形板材上的优化排样 实例 1：多种不规则件 NGSA 算法排样 从过程装备制造厂零件数据库中随机选取了一组具有不同 形状的多种类、单数量零件进行混合排样计算。从板材库中选 择矩形板材宽为 600mm，设置算法基本运行参数：群体规模为 50，最大迭代数为 100，交叉率为 0.6，变异率为 0.06，马可夫 链长度为 8000，衰减参数为 0.95，迭代初始温度为 500，容差 为 0.0001，小生境之间的参数距离为 2.5，零件种类为 30，各 零件加工余量都为 2mm。调用 NGSA 算法确定零件的排放顺 序和旋转角度，用基于“最低水平线法”策略的动态扫描线算 法与填充算法相结合的定位算法确定零件在板 材的位置。排样结果如图 4 所示。 实例 2：多种矩形件 NGSA 算法排样 从某工厂实际激光切割加工中心选取一组 矩形零件如表 1，取群体规模为 30，最大迭代 数为 100，交叉率为 0.5，变异率为 0.05，马可 夫链长度为 9000，衰减参数为 0.95，迭代初始 温度为 900，容差为 0.0001，小生境之间的参 数距离为 2.0，选择矩形板材长 800mm，宽为 600mm。排样结果如图 5 所示。 从排样结果可以得出，本文提出的算法不 图 4 多种不规则件排样结果 Fig.4 The layout drawing of many irregular parts 图 5 多种矩形件排样结果图 Fig.5 The layout drawing of many regular parts 5 仅适用于不规则零件的排样，也适用于矩形零件的排样，同时系统还能正确处理单张板材和多张板 排样问题，当一张板排完后，如零件还未排完，系统将在下一张新板进行排样。 表 1 矩形零件清单 Tab.1 The bill of rectangular parts 零件编号 零件长(mm) 零件宽(mm) 加工余量(mm) 零件数量 零件厚(mm) 8-01 60 15 2 30 4 8-02 80 60 2 20 4 8-03 78 26 2 20 4 8-04 60 30 2 30 4 8-05 90 40 2 20 4 8-06 60 30 2 30 4 8-07 45 32 2 20 4 8-08 23 12 2 20 4 8-09 20 10 2 30 4 (2) 不规则板材上的优化排样 实例 3：从某企业零件切割加工中心零件库中 随机选择一组具有任意形状的多边形零件，部分零 件多数量，取各零件加工余量都为 5mm，在一个 不规则的多边形原材料板块上利用 NGSA 算法进行 自动排样。排样结果如图 6 所示。从排样结果可以 看出排放的比较紧密，取得了较好的排样结果，由 此也证明了该算法在不规则板材上进行排样的有效 性及实用性。 根据上述测试实例可以验证 NGSA 算法的有效 性和实用性，同时也进一步证明不规则件优化排样 系统完全适合现在制造业中各种需求的混合排样， 其排样速度比较快，不仅满足企业材料利用率的要 求，而且也达到了节约原材料、提高企业的生产效 率、降低产品的成本，提高经济效益的目的。 5 结语 实践证明，NGSA 混合优化策略结合了 GA、SA 和小生境的特点，弥补了各自的弱点，它是 一种优化能力、效率和可靠性较高的全局优化方法。可以得到一种实用高效的优化排样算法，对提 高板材利用率有很大的现实意义，它的研究对智能优化理论的发展与应用也很有意义。 参考文献 1 Julia A Ben Nell，Kathryn A Downs-land，William B Downs-landThe irregular cutting-stock problem-a new procedure for deriving