基于UG二次开发技术的计算机辅助夹具定位系统的研究和开发.doc

_二维零件排样算法的研究李凌辉，谢友宝，蔡洪伟，吴娟（南昌航空大学，江西南昌，330063）摘 要：本文首先用数据库保存待排零件的数据信息，然后提取零件的最小包络矩形并编码，再使用最低水平线法将零件排样转化成矩形件的正交排样图，最后结合遗传算法实现二维零件排样，此算法具有自动化程度高，优化性能好，快速高效等特点。关键词：二维排样，最低水平线法，最小包络矩形，编码，遗传算法The reaserch on algorithm of two-dimensional parts layoutLi Linghui,Xie Youbao, Cai Hongwei ,Wu Juan(Nangchang Hangkong University, Nanchang, 330063)Abstract:This article first uses the database to preserve the data infromation of the nesting parts, then extracts the minimum enclosure rectangle and codes, and applies the Lowest Horizontal Line algorithm to transform parts layout into the rectangular orthogonal parts blank layout graphics ,finally unifies the genetic algorithm to realize two-dimensional parts layout, this algorithm has high automation, good optimized performance , fast and efficient and so on .Keywords: two-dimensional layout，the Lowest Horizontal Line algorithm，the minimum enclosure rectangle，code，the genetic algorithm精品资料1引言企业的生产效率，产品的质量与成本，是一个企业生存和发展的关键，因此材料成本在工业生产中显得尤其重要。板类零件性能优越，制造工艺简单，成本低廉，被广泛应用于汽车,飞机,造船,电器等行业中，而板类零件都存在一个共同的排样问题，能否研究出一套优化的排样方案，对于降低材料浪费，提高企业的经济效率有着重要的理论意义和现实意义。 二维排样在排样问题中应用最广泛，航空企业中飞机的几千个薄板零件需要下料，造船业中钣金件的裁切，服装业中布料的裁剪均属于此类问题。有关零件排样算法，目前已经有很多较好的方案，如模拟退火算法，矩形包络算法，启发算法,神经网络算法等，但是每种方法都有自己的优点和不足之处，其排样技术还是不够成熟。笔者综合了几种零件排样算法的思想，提出了另外一种排样算法可以较好的解决此问题。2排样问题介绍二维零件的排样问题是指将一系列形状各异的零件在矩形板材中按最优方式进行排布, 使其板材的利用率最高。排样问题可以从两个方面加以说明，一是排样零件的调度，即从零件库中选出零件,为零件排样做准备；另一个是如何确定零件的最佳排放位置, 编写相关算法并检测算法优化性能。3二维零件排样方法3.1零件图形数据的提取和保存排料过程中，通过与AutoCAD的接口提取各零件实体的数据信息，它以DXF文件格式记录，零件实体中具体的数据信息包括直线（LINE），圆（CIRCRE），圆弧（ARC），样条（SPLINE）等。获得零件实体的信息之后，找出实体间的拓扑关系，对零件实体段点进行排序处理，使其成为一个封闭的轮廓，满足零件表达的要求。得到零件的图形数据以后，根据零件的不同规格分类编号，放入数据库中保存，数据库保存零件数据应遵循以下原则：（1）科学全面性：尽量多的反应零件主要特征，如：长度，宽度，弧度，面积，凹凸性等；（2）代码唯一性：同一类型零件应该具备相同的编码，不同类型的零件编码不同；（3）易扩展性：为以后新加入的零件类型提供友好的数据库接口程序。3.2零件预处理排样的零件对于任意形状规则,按类型可分为凸多边形、凹多边形或为两者的混合体。分别求出它们的最小包络矩形面积（零件的最小包络矩形是指外切零件的矩形中面积最小的那一个）。对凹多边形,可能存在较大的空白区域,可采用人机交互的方法用小零件（由小到大的顺序）尽量添满空白区域。现在对零件的排样问题转变成了零件矩形件在板材上的排样问题了。3.3排样零件数学模型在宽度确定，高度(或长度)不限的板材上排放给定的矩形件。设板材宽度为W,待排零件种类数为N，第i个零件的长度为，宽度为，数量为,，零件沿板材宽度方向进行排放，零件排样后在板材上所达到的最大高度为H,则优化排样的目标函数为: 当排样零件较多时，计算量将变得很大，计算时间也将变长。为了加速搜索，减少计算量，本文采用一些约束条件来简化寻优过程：（1）同种零件尽量排布在一起;（2）零件沿板材宽度方向排放，可以水平排放，也可以旋转90度之后再排放;（3）零件相互靠近，但不能相互重叠，也不能超出板材边界之外;（4）零件矩形件排样方式遵行最底水平线法和遗传算法规则的要求。设在坐标系统上，板材最左下角的坐标为(0，0)。矩形件i排放在板材上，其左下角和右上角坐标分别以，表示，则有：当矩形件横排时： 当矩形件竖排时：设任意两个排样的矩形件a和b的左下角和右上角的坐标分别为：，和,则满足下面任意一个条件，矩形件不会相互重叠：(1)； (2)； (3)； (4) ；对于任意的矩形件i，为了不超出板材之外，必须满足下列条件:(1) (2)； (3)；3.4排样解码方法遗传算法是一种把问题的可行解作为种群,把每一个可能的解看作种群的个体,算法运行时在整个解空间内随机搜索,按一定的评估策略对每一个个体作出评价,不断地使用选择、交叉、变异这三种遗传算子,直至产生最优解。（1）确定编码方法用遗传算法求解问题，必须先确定编码方法。不同的编码方法,遗传算子实现的方式也不同。本文采用了十进制编码方式,将每一矩形进行编号（i=1,2,n），零件编号构成一个整数串，1n,表示了一种排样图的一个解。其中,每一位整数代表一个矩形,并且每一位整数可以有正负之分,正号表示零件不发生旋转,负号表示将零件旋转90度。这样一个整数串就是一个个体,每一个体对应一种排样图，m个个体构成一个群体。（2）算法的选择基于“最左最下”原则的BL算法如下：第一步：将放在板材的左下角,若为负值,则将其旋转90后再排放,求出排放后所占板材的最大高度；第二步：将 (i=2,3,n)置于板材右边最大高度处,交替向下向左移动.。首先尽可能地向下移动,然后再尽可能地向左移动,直至无法再向下向左移动为止(即接触到其它零件或板材边界),并求出此时的最大高度;重复上述过程,直至所有零件排放完毕,最后所得的最大高度即为所需板材的高度。现使用“下台阶”算法对第二步进行了改进。在向下向左移动时,采用了向下优先的原则,克服了BL算法对某些最优排样图排列的缺点。对于编码1,-2,3,-4, BL算法与“下台阶”算法的排放过程分别如图1和2所示： 1234 图（1）“BL”算法 1234图（2）“下台阶”算法分析BL算法和“下台阶”算法可以发现,BL算法并非最优排样,容易发生板材左侧排放偏高的情况，而“下台阶”算法则易发生右侧偏高的情况。本文提出一种基于零件最高轮廓线的解码算法最底水平线算法,具体过程如下：第一步：设置初始最高轮廓线为板材的最下面的边；第二步：每当要排入一个零件时,就在最高轮廓线集中选取最低的一段水平线,如有数段,则选取最左边的一段,测试该段线的宽度是否大于或等于要排入零件的宽度。如果该段线的宽度大于要排入零件的宽度,则将该零件在此位置排放,更新零件最高廓线;否则,查询与最低水平线段相邻的左、右两段水平线,将最低水平线提升至与高度较低的一段平齐,更新零件最高轮廓线。重复第二步,直至能排入该零件。重复上述过程,直至所有零件排放完毕。对于编码1,-2,3,-4,采用最底水平线法方法的排样过程如图3所示。在排放1,2矩形后,最右端排放矩形3，如果最低水平线的宽度小于矩形3的宽度,则提升该与相邻的左段水平线平齐,这时最低水平线变成了靠左边一段,将矩形3排放,照此方法放入矩形4。121321（a） （b） （c）144444444411234432121（d） （e） （f）图（3）“最底水平线法”排放零件3.5适应度函数遗传算法中利用适应度函数评价解的好坏,适应度函数值越优,解的质量就越高，对排样问题,取排样图的最大高度的倒数为适应度函数值。若两个排样图具有相同的高度,适应度值仍有好坏之分。从余料再利用的角度看,本文采用如下的适应度函数；f(P)=B/B1,其中B是排入矩形件的面积,B1是排样图整体高度轮廓线以下的板材面积。4遗传算法求解过程4.1初始种群给定n个零件,随机产生由m个编码构成的初始种群,用“最低水平线法”计算每一个体的适应度。4.2遗传算子(1)交叉算子将父辈群体中的个体随机两两配对,进行交叉操作,产生m个个体构成子辈群体。本文采用了两种交叉算子:单点交叉和双点交叉。设两个进行交叉的个体为和。单点交叉是在1n范围内随机生成一个交叉位b1,从P中将位于b1之前的元素拷贝至子辈个体new Individual1中作为前面的元素,剩余元素按Q中出现的先后顺序拷贝至new Individual1;同样的方法可以产生另一新个体new Individual2。双点交叉是在1n范围内随机生成两个交叉位b1,b2,从P中将位于b1,b2之间的元素拷贝至子辈个体new Individual1中作为前面的元素,剩余元素按Q中出现的先后顺序拷贝至new Individual1,从而得到新个体new Individual1;同样的方法可以产生另一新个体new Individual2.(2)变异算子对进行了交叉操作的子辈个体,采用两种变异算子进行变异。第一种是旋转变异,随机产生一个旋转位bit,以概率对子辈个体中位于bit之后的矩形进行旋转;第二种是位置变异,以较小的概率,在1n范围内随机产生两个整数bit1,bit2,对子辈的个体中的位于bit1,bit2的两个零件对调。(3)选择算子用“最低水平线法”求变异后的m个子辈个体的适应度。将父辈个体与子辈个体的适应度函数值由大到小排序,取排在前面的m个个体作为下一代的父辈个体。5结束语算法的优化性是相对的，本文的算法还可以继续研究下去，在使用最底水平线法和遗传算法排放完矩形件后，矩形件或板料中还有很多小空白域区，我们可以根据经验采用人机交互方式在这些小空域区中合理放置更多更小的零件，也可以根据这些小空域区和零件的特征属性，再寻找一种优化的小零件排样算法。参考文献1 Liu Jiamin,Zhang Shengnan.Research and imlementation of two dimensional irregular of Computer Aided Design And Computer Graphics,2000,12(7): 488491(in Chinese).2刘聪,吴兵锐.浅谈AutoCAD的接口DXF文件J.山东煤炭科技.2002(1)：38-39.3Jia Zhi xin,Yin Guofu,Luo Yang,etal application of smiulated annealing to the rectangular packing problem J.Journal of Si Chuan University, 2001,33(5):3538(in Chinese).4刘萍，陆金桂.基于遗传算法的二维排样优化方法J.南京化工大学学报，2001,23(5)9-21.5龚志辉,黄星梅.二维矩形件优化排样算法的改进研究J.湖南大学学报:自然科学版,2003,30(3):47-49。6卢险峰.最优化方法应用基础(M) 上海:同济大学出版社，2003-08.作者简介：李凌辉 , 男, 湖北黄冈人, 硕士生, 研究方向：制造系统中的软件技术Welcome ToDownload !欢迎您的下载，资料仅供参考！