二维矩形零件排样算法的研究

二维矩形零件排样算法的研究 研究与开发 二维矩形霉件排辑算法的研究 蒋瑞斌,刘熠 (湖南生物机电职业枝术学院,湖南长沙4】0082) 二维矩形件的排样问题是指将一系列尺寸大小等 的矩形零件在矩形板树中按最优方式进行排布要求零 并满足一定的工 件排放在板材内各个零件互布重叠. 艺要求二维矩形件的排样是二维不规则零件排样的基 础从理论上看,该类问题属于具有最高计算复杂性的 优化计算问题:NP完全问题对于这类问题,以目前计 算理论和算法,求解是相当困难的:遗传算法是近几十 年来发展的一种借鉴生物界自然选择思想和自然遗传机 制的全局随机搜索算法.它把问题的可能解构成一个种 群把每一个可能的解看成种群中的个体运行时,算 法在整个解空间内随机搜索,按一定的评估策略(或适 应度函数)对每一个个体作出评价.不断使用选择,交 叉,变异这三种遗传算子,使问题的解不断进化.直至 产生最伲解.:由于遗传算}占垒局寻优等复杂问题上具 有独特优越性.很多学者把它运用到了排样问题七,井 在此基础上提出了多种算法= 1编码的确定 用遗传算法求解同趣,必须先确定编码方穗.为了表 示的方便,一般采用了十进制码方式.料每一矩形进行编 号,i=1.2,--,零件编号构成一个幢数串P.【p. pz,…,,1印.,表示了一种排样图(一个个体)其 中,每一位整数代表十炬彤.并且每一位整数可以有正 负之舒,正号表示零件不发生旋转.负号表示将零件旋转 90度这样,一个整数串就是一个个体.每一个悼对应一 种排样图;m个个体构成一个群体 采用这种编码方式每一个矩形有横放,竖放两种 形式,在本文中规定横放为正竖放为负对于图l所 示排样图的编码可以表示为f'=卜】,2,3.4,一5.一6, 一 7.8} 圉l8十矩形件构成的最忧排样躅 2用遗传算法求解二维不规则零件排样的主 要方法 "B1算法","下台阶算法","最低水平线算法"都 是国内外学者提出来的基于遗传算法的二维矩形件优化排 样算法,其中,"下台阶算法"是在BL算法的基础上 提出的改进.而"最低水平线算法"则是在"下台阶算 法"的摹础上提出的改进. 由遗传算法产生一个个体的编码后.必须能快速地求 出其对应的排样图得到各个零件在扳材上的排列位置信 息或所选板材的参数(长度,宽度,占用面积等)然后 根据该个体对应的排样图,计算出适应度函数值,井对该 个体进行评价 文献[1]基下最左最下"原则.提出了BL算 法".具体步驿如下: 收藉日期r2?6__06—15;恬订日期:006—0一l8 亘匦]一 ?将Pl放在板材的左下角,若Pl为负值,则将其旋 转90度后再排放,求出排放后所占板材的最大高度; ?将(:2,3…,,1)置于板材右边最大高度处后, 交替着向下,向左移动,首先尽可能地向下移动,然后 再尽可能地向左移动,直至无法再向下向左移动为止 (即接触到其它零件或板材边界),并求出此时的最大高度; 重复上述过程,直至所有零件排放完毕,最后所得的 最大高度即为所需板材的高度. 文献[2]通过研究发现"BL算法"对于某些排样图 无法求解出最优化结果,如图1所示的排样图显然是一个 最优排样图,但用"BL算法"即使穷举所有的排列也无法 求解出最优解.所以文献[2]在"BL算法"的基础上进 行了改进,提出了"下台阶算法",具体步骤如下: ?将零件PI排放在板材的左下角,若为负值则将其旋 转90度后再排放,求出排放后所占板材的最大高度; ?将(i=2,3,…,,1)置于右边最大高度处,向下 向左移动,且向下移动优先,直至无法向下向左移动为 止(即接触到其他零件或板材边界),并求出此时的最大 高度. 重复上述过程,直至所有零件排放完毕,最后所得最 大高度即为所需板材长度. 文献[3]通过研究,发现"BL算法"除了前面所述 的缺陷之外,还容易出现左侧偏高的现象,而"下台阶算 法"则容易出现右侧偏高的现象,所以在此基础上又提出 了一种改进算法——最低水平线算法.具体排样过程如 下. ?设置初始最高轮廓线为板材的最下面的边. ?每当要排入一个零件就在最高轮廓线上集中选取 最低的一段水平线,如有数段,则选取最左边的一段.测 试该段线的宽度是否大于或等于待排零件的宽度,如果该 段线的宽度大于要排入零件的宽度,则将该零件在此位置 排放,同时更新零件最高轮廓线;否则,查询与最低水平 线段相邻的左,右两段水平线,将最低水平线提升至与之 相邻且高度较低的一段平齐,同时更新零件最高轮廓线. ?重复第2步,直至能排入该零件. 重复上述过程,直至所有零件排放完毕. 3空洞搜寻插入法 本文在认真研究了"最低水平线T 算法"之后,认为该算法固然优于前l 两种算法,但仍有不足之处.在"最l 低水平线算法"的第2步:当最低水l 平线的宽度如果小于待排矩形件的宽" 度时,它采用的处理方法是将最低水I 平线提升至与之相邻且高度较低的一l 段平齐,同时更新零件最高轮廓线并I 重复该步骤直到能排下该矩形件.本 文认为这样的处理会造成最低水平线 以上的部分浪费,即在排样图中形成空洞.很显然,如果 能在这些空洞中排入其他还未排的矩形件就可以大大地提 高板料的利用率.出于这种考虑,本文在此算法的基础上 提出了一种改进算法——空洞搜寻插入法.具体步骤如 下. ?设置初始最高轮廓线为板材的最下面的边. ?每当要排入一个零件就在最高轮廓线集中选取最 低的一段水平线,如有数段,则选取最左边的一段,测试 该段线的宽度是否大于或等于要排零件的宽度:如果该段 线的宽度大于要排人零件的高度,则将该零件在此位置排 放,同时更新零件最高轮廓线;否则,查询与最低水平线 段相邻的左,右两段水平线,将最低水平线提升至与之相 邻且高度较低的一段平齐,同时更新零件最高轮廓线. ?将最低水平线提升后所形成的空洞视为一块新的板 料,从该零件所在位置起向后搜索一个宽度和高度都小于 该空洞的矩形件,如果没有则将最低水平线提升至与相邻 的且高度较低的一段平齐,更新零件最高轮廓线并重复第 2步,直至能排入该零件. ?否则,按最左最下的方式排入新搜寻到的这个矩形 件,并互换这两个零件在个体中的位置,同时根据新排入 的零件重新计算最低水平线; 重复上述过程,直至所有零件排放完毕. 4遗传算法的求解过程 (1)初始种群 给定,1个零件,随机产生由m个编码构成的初始种 群,用"最低水平线法"计算每一个个体的适应度. (2)遗传算子 ?交叉算子 将父辈群体中的个体随机两两配对,进行交叉操作, 产m个个体构成子辈群体.一般采用了两种交叉算子: 单点叉和双点交叉. 坚异算子 对进行了交叉操作的子辈个体,采用两种变异算子进 行变异.变异包含两个方面:一种是旋转变异,即按照某 个概率对矩形件进行横竖旋转;另一种是位置变异,即按 照某个概率对矩形件排放的顺序进行交替. 图2将一个15x40的大矩形分成25个小矩表 ?选择算子 用"空洞搜寻插入法"求变异后的m个子辈个体的适 应度.将父辈个体与子辈个体的适应函数值由大到小排 序,取排在前面的m个个体作为下一代的父辈个体. (3)终止准则 重复执行上述的?,?,?,直到计算出来的解的适 应度值达到要求或满足预定的进化代数,则停止计算,输 出计算结果. 5算例和结论 将一个15x40的大矩形分成25个小矩形,如图2所 示.现以40为定宽,长度不限的板材为例,求最小排样 高度(黑色粗实线代表排样起始边). 用"最低水平线算法",在群体规模为m=20的情况 下,取交叉概率为l,单点交叉与双点交叉各占一半,变 异概率PI=P~--O.3,100代内终止时能达到l7,2000代终 止时得到的高度为l6.而用本文提出的"空洞搜寻插入 法"在同样的群体规模,交叉概率,变异概率的情况下 100代内就可以达到l6.由以上可以看出,"空洞搜 寻插入法"的计算效率更高. 参考文献: [1]S.Jokobs.Ongeneticalgorithmsforthepackingofpolygons [J].EuropeanJournalofOperationalResearch,1996,88: l65一l81. [2]刘德全,藤弘飞.矩形件排样问题的遗传算法求解[J].小 型微型计算机系统,1998,19(12):20—25. [3]贾志欣,殷国富,罗阳.二维不规则零件排样问题的遗传算 法求解[J].计算机辅助设计与图形学,2002,12 (5):467--470. 第一作者简介:蒋瑞斌,男,1973年生,湖南长沙人,硕士研究 生.研究领域:机械工程.已发表论文4篇.(编辑:向飞) (上接第47页) (a)截面形状(b)截面扫描线(C)截面形状(d)截面扫描线 图3截面扫描线生成过程 (5)算法验证 图3所示是利用此种算法所生成的截面扫描线,可以 看出,图3(a),(c)的截面形状都比较复杂,生成扫描 过程所涉及到的数据处理量也比较大,但程序生成扫描线 的过程相当快,通过对大多数图形进行测试,生成扫描线 的过程都没有出现错误,说明此种算法的通用性较强,能 够对大多数图形进行处理.此外,在一个层面上采用X, Y方向交叉重复扫描可以使熔化后凝固的金属再次重熔凝 固,这样可以有效地减轻球化现象,使熔化的金属更加均 匀地分布在一个层面上,提高了表面质量. 5结论 在快速成型工艺中,扫描方式的选择直接影响成型件 的最终质量,重复扫描和分区扫描相结合的路径生成算法 简单明了,其中扫描线与轮廓线交点数组的大小根据点数 的多少采用动态分配内存的方式,省去了在求到层面图形 的所有极大,极小值点后再进行内存分配的操作,因而进 行比较的操作次数减少,路径生成速度快.分区避免了长 线扫描,因而可以有效减小翘曲变形;一个层面上重复扫 描可以减小层间的内应力,减轻球化现象.从而可以提高 熔化层的表面质量.此外还可以添加一些附加的操作,如 在进行加工前先将基板进行预热,加强首层与基板的粘结 程度;还可以在每层内部扫描完毕后加边框扫描,这样可 以有效减少边界上翘. 参考文献: [1]OverC,MeinersW,WissenbachK,cta1.RapidManufac- turingofmetalpartsandtoolsusinglasermelting[A]. Proceedingsofthe2ndInternationalWLT—Conferenceon lase~inManufacturing[C],Munchen,2003. [2]AbbottDH,ArcellaFG.IJaserformingtitaniumcomponents [J].AdvanceMaterials&Processes,1998,153(5):29— 34. 【3]WohlersT.RapidPrototyping:Currenttechnologyandfuture potential[J].RapidPrototypingJournal,1995,l(1):l1一 l9. [4]张庆茂.送粉式激光熔覆层质量与工艺参数之间的关系[J]. 焊接,200l,22(4):47-51. [5]张延杰.SIS/HIP技术用于钛的净成型加工[J].稀有金属 快报,1999,12(5):6—7. [6]KozoOSAKADA,MasanoriSHIOMI.LaserPrototyping[z]. (2004)[2005—05-23]. 第一作者简介:许丽敏,女,1982年生,天津人,硕士研究生. 研究领域:激光材料成型及合成技术.(编辑:向飞)