基于重心NFP的二维不规则形状排样算法_图文

1、基于重心N FP 的二维不规则形状排样算法刘胡瑶何援军上海交通大学,上海,200030摘要:提出了一种基于重心N FP 的二维不规则多边形排样算法,算法主要包括临界多边形计算和排样定位选优等内容。该算法以多边形来表示板材和待排零件,通过求解临界多边形N FP 来得到多边形之间的所有靠接(排放位置。为了在N FP 中进一步得到优化的靠接位置,在N FP 的基础上提出了重心N FP 的概念,通过选择重心N FP 中的最低重心位置来确定零件的排放位置。在零件的排样次序算法上,提出了顺序递归排样算法和遗传算法,以降低排样过程中形成的空腔所造成的浪费。该算法可处理板材和零件均为不规则形状的排样问题,允许

2、零件在全角度范围内进行旋转,并可处理板材内部带孔洞或者边界形成空腔等特殊情况。关键词:不规则排样;临界多边形;重心N FP ;递归排样;遗传算法中图分类号:TP391文章编号:1004132X (2007060723042D Irregular N esting Algorithm B ased on G ravity Center NFPLiu Huyao He YuanjunShanghai Jiaotong U niversity ,Shanghai ,200030Abstract :This paper p roposed 2D irregular shaped nesting alg

3、orit hm based on gravity center N FP.The p roblems of polygons touching detection and optimum nesting position selection were re 2solved here in.All container region and pieces were rep resented as polygons ,and t he touching posi 2tions can be found by calculation of N FP.In order to get t he optim

4、al nesting position ,t his paper pro 2posed t he co ncept of gravity center N FP.The lowest vertex o n gravity center N FP was selected to nest t he pieces.For t he p roblem of calculation nesting sequence ,t his paper presented a recursive nest 2ing algorit hm and a genetic algorit hm to reduce t h

5、e wasted area.The proposed algorit hm can deal wit h irregular shaped pieces and container ,it can also deal wit h arbit rary rotation of part s and holes on con 2tainer region.K ey w ords :irregular nesting ;no fit polygon (N FP ;gravity center N FP ;recursive nesting ;genetic algorit hm收稿日期:200512

6、12基金项目:国家自然科学基金资助项目(605731460引言二维不规则形状排样问题是一个平面布局优化问题,即在平面板材上布置多个不规则形状的零件,并满足以下约束条件:零件排放在板材内部;各零件之间互不重叠;同时满足一定的工艺要求。其优化目标是,寻求一个零件布局方案,使得浪费的板材面积为最小,亦即材料的利用率为最大。排样问题对造船、服装、模具等材料加工行业有重要意义,材料利用率的提高可直接降低材料浪费,提高经济效益,也符合当今创建节约型社会的需求。与矩形排样相比,不规则排样增加了排样角度和排样位置的任意性,且板材和零件均有可能为任意多边形,板材还可能包含内部孔洞,所以不规则排样问题在几何计算方

7、面具有较高的复杂度。与二维矩形排样相比,不规则排样具有以下特点:板材和零件形状上的任意性。该特点涉及对多边形图形处理的多种算法,如多边形靠接算法(临界多边形N FP 、多边形布尔运算、外包多边形求解等。零件放置规则的任意性。在满足约束条件的情况下,零件可以任意角度在任意位置摆放,矩形排样的最低最左原则或最低水平线原则在不规则排样的情况下已不能满足需要,最低最左等传统放置方法将导致较大的空白区域无法利用。上述特点增加了不规则排样问题的复杂度,尤其是任意角度和位置的排放使得搜索空间变得非常庞大,对于实际排样问题,已不可能找到一种可实用的精确排样算法。因此研究人员提出了多种启发式或内启发式算法来求得

8、近似解。文献1,2详细阐述了二维不规则排样问题的研究现状,指出临界多边形算法和遗传算法将对不规则排样的研究有重要影响。Fujita 等3提出了一种基于排样顺序的遗传算法和局部优化相结合的排327基于重心N FP 的二维不规则形状排样算法刘胡瑶何援军样算法,但是该算法只能处理凸多边形。J a 2kobs 4提出了一种典型的不规则排样算法,即首先找到多边形的最小外包矩形,然后用基于遗传算法的矩形排样方法进行排样,最后对排样结果进行“挤压”运算来得到最终排样结果,Hopper 等1指出该方法无法保证“挤压”算法的有效性。文献5,6也提出了一些基于遗传算法的不规则排样算法,但其排样质量和排样速度还无法

9、满足实际需要。此外,根据图形表示的方法来区分,还存在另一类基于图像像素的图形表示和排样方法7,这种算法的优点是算法简单且适用面广,但该算法存在以下两个主要问题:算法的精度受像素划分的分辨率限制;算法复杂度与图形分辨率的平方O (n 2成正比,当精度要求较高或图形大小相差较大时,过高的时间复杂度限制了该算法的应用。从目前的发展现状来看,现有不规则排样算法的排样质量和速度还有待于进一步提高,因此,本文从不规则排样的三个主要关键技术(临界多边形算法、零件放置规则及排样顺序出发,首先阐述了临界多边形N FP 算法,然后提出了基于N FP 的重心N FP 零件放置规则,最后提出了递归形式的排样算法以及基

10、于次序的遗传算法,并提供了算法实验数据。1临界多边形算法在不规则排样过程中,临界多边形(no fit polygon ,N FP 已被公认为是二维不规则排样问题的基础性几何计算工具。N FP 的意义在于它给出了两个多边形之间所有相互接触的靠接位置,求出所有可能的靠接位置后,排样过程就成为了在靠接位置集合中寻求零件排放位置的优化定位过程。临界多边形的定义如下:给定板材和零件的多边形,先将板材多边形固定,然后用零件多边形做不旋转的刚体运动绕板材多边形内部环形运动一周,运动过程中零件保持在板材内部并和板材内边界接触,则零件上的某个参考点(可取为最低点在运动过程中所形成的轨迹就构成了零件相对于板材的临

11、界多边形(图1。由于临界多边形给出了所有靠接位置的信息,因此在求取临界多边形之后,不规则排样问题就可以简化为基于临界多边形的定位选优过程。现有临界多边形算法主要包括三种:移动碰撞法8。移动碰撞法通过不断求取下一步的碰撞位置来得到临界多边形。 明可夫斯基矢量和法图1临界多边形的形成过程示意图(minkowski sum 9。该方法将N FP 表示为多边形矢量边之和。多边形凸化分割法。该方法将多边形划分为若干个子凸多边形,然后求得子凸多边形的N FP 之和即为最终N FP 。2零件放置规则零件放置规则的含义是指按照一定原则将待排零件排布到板材上,例如在二维矩形排样中,可以按照最低最左原则将待排零件

12、放置到板材的空白处,即将零件不停地往下和往左移动,直到碰到板材边界或已排零件的边界而无法再移动为止。对于不规则形状排样问题,由于几何形状的特殊性,需要寻找一种更合适的零件排样规则。已有研究人员提出了不规则排样的零件放置规则,例如最小外包凸多边形面积原则10、边界重合度原则等,但仍存在复杂度过高和排样质量较低等问题,因此需要研究更合适的放置规则。由于N FP 给出了多边形之间所有靠接位置,因此在求得N FP 之后,零件排样问题就转化为在N FP 上寻找一个合适排布位置的问题,如图2所示 。图2根据NFP 确定靠接位置的示意图在大部分不规则排样过程中,往往将已排零件的总高度作为排样质量的标准,零件

13、占用的总高度越低,说明排样的效果越好。从这个评价指标出发,本文提出了最低重心N FP 原则的排样规则,该排样规则将零件放置到具有最低重心的位置。最低重心N FP 排样规则的出发点是在不发427中国机械工程第18卷第6期2007年3月下半月生多边形干涉的情况下,将排样零件的重心尽量定位于底部,并使得排样后的边界尽量保持水平,以助于后面的排样。为了得到零件可排放的最低重心位置,首先需要计算出零件的重心(正负三角形分割法,然后以重心为参考点求解N FP ,即可得到重心N FP ,通过重心N FP 可得到最低重心位置。由于N FP 的形状会随着零件的旋转角度而变化,为了得到在不同旋转角度下的最低重心位

14、置,可以通过角度搜索来得到旋转情况下的最低重心位置。得到最低重心位置和对应的旋转角度之后,即可确定零件的排样位置,如图3所示 。图3根据重心NFP 的最低点确定零件排样位置的示意图为了较快查找到最低重心位置,可以先旋转较大的角度间隔,例如先以10°为旋转间隔,得到360/10=36个重心N FP ,并从中得到一个具有最低重心位置的旋转角度,然后在该旋转角度的附近范围内进一步细化,以得到更精确的最低重心位置以及对应的旋转角度。3确定零件的排样顺序通过多角度重心N FP ,可以得到单个零件的最低排布重心位置和相应角度,从而可以确定零件的排样位置。然而对于多个零件来说,排样顺序是决定最终排

15、样质量的另外一个主要影响因素,因此需要研究合适的排样顺序算法。常用的排样顺序算法包括启发式算法和内启发式算法。启发式算法通常是根据当前排样条件和先验知识来决定下一个排样零件的序号,例如选择排样后凸包面积最小的零件为下一个排样零件,启发式算法速度较快,但是排样质量受先验知识和排样规则的影响很大,适用于计算时间短而对排样质量要求一般的情况。而内启发式算法包括遗传算法、模拟退火算法、禁忌搜索算法以及蚁群算法等,该类算法可以在给定初始条件的情况下自动搜索到较优解,内启发式算法收敛速度较慢,但容易搜索到较优解和最优解,适用于对计算时间要求不高而对排样结果要求较高的场合。3.1利用递归算法求解排样次序本文

16、从减小排样孔洞面积出发,提出了一种递归式的排样顺序算法,该算法结合了递归算法和启发式算法的特点,总体上采用启发式算法,而在局部范围内应用递归排样,具有启发式算法速度快的优点,同时可得到较好的排样效果。该算法的原理是:首先根据零件面积从大到小排序决定初始的排样顺序,然后在排样过程中,如果发现当前排样零件排样后形成了较大的孔洞面积,且该面积足以容纳其他较小的零件,则在此情况下调整排样顺序,将其他能放入该孔洞的较小零件调整到当前零件之前进行排样,以减小排样过程中所形成排样孔洞面积,该算法的示意图如图4所示。首先根据面积从大到小的次序进行排样,当排完零件1后,发现形成了较大空腔面积,且该空腔面积足以容

17、纳其他较小的零件,首先可容纳的是零件2,因此将零件2的排放次序移到零件1之前,从而排样顺序从321变为231。同理,按照新的排样次序231继续排样,发现零件2排放后形成的空腔仍可排放零件1,因此将零件1的排放次序移动到零件2之前。最终排放次序变为123。按该次序排放,可以尽量减少排放后形成的空腔所浪费的面积 。图4递归排样顺序算法示意图3.2利用遗传算法求解排样次序第一代种群对遗传算法的最终结果有较大影527基于重心N FP 的二维不规则形状排样算法刘胡瑶何援军f =f +式中,f 为初始适应度;f 为变换后的适应度。同时有=f avgf avg -f min =-f min f avgf a

18、vg -f min=f avgK式中,K 为常数;f avg 为平均适应度;f min 为最小适应度。该遗传算法采用了轮盘赌比例选择方法来选取父个体进行交叉产生下一代,比例选择方法可能会导致某些含有较好基因但是适应度较低的个体被过早丢弃,因此在上式中增加来对适应度进行调节,以避免个体的过早淘汰。本文采用OX (order -crossover 顺序交叉算子。将2个父个体的某些染色体进行交叉,最终得新一代个体产生之后,根据变异概率选择一定量的个体进行变异操作。本文随机选择某个序号插入到其他位置来实现变异操作。变异概率可取为011012。染色体中的某2段序号(而不是2个单独序号也可以进行交换,但在

19、此情况下由于变异较大,因此变异概率要相应降低。4算法实验结果4.1测试数据1此测试样例来自于文献4,首先将多边形拟合为矩形,然后利用基于顺序遗传算法的矩形排样算法进行排样,最后用最低最左原则的“挤压”算法对排样后的零件进行进一步挤压。本文采用了相同测试样例,并用本文算法进行了计算,和文献4算法的结果进行了比较(计算机硬件配置:P4115G ,640M 内存,如表1所示 。4.2测试数据2该测试样例数据来自于ESICU P (EU RO special interest group on cutting and packing ,现有文献中未发现有相同样例的排样结果。为了测试不规则板材以及板材内

20、部带孔洞的情况,本文在测试样例中将板材设置为不规则形状并加入了不规则多边形孔洞,如图5所示。5结论针对目前二维不规则形状排样中的N FP 计算、零件放置规则及排样顺序问题,本文分别提出了对应的解决方案:首先给出了N FP 在排样问题中的定义,并综合阐述了N FP 的计算方法;其次,提出了基于重心N FP 的最低重心零件放置原则,使零件在排放时达到当前最低重心位置, 并为后图5板材带孔洞的排样结果(排样高度为55.06mm ,板材利用率为81.4%,计算时间为93.9s 续零件的排放形成一个较为平滑的边界。第三,在排样顺序算法上,提出了递归排样顺序算法和遗传算法,递归算法在排样过程中发现较大面积

21、浪费时,可及时调整排样顺序,以提高材料利用率。总体来看,本文算法适用于二维不规则形状(下转第731页627中国机械工程第18卷第6期2007年3月下半月6.4筛选率8k=2|A(k|=66,筛选率P=5617%。7结论本文系统研究了基于拆卸图模型的拆卸过程规划中的可拆卸性筛子。用多色集理论的可能位移模型描绘零件拆卸过程中的干涉阻挡关系,用可能位移方程组作为可拆卸性筛子,有效筛选掉不合理零件单元,使图模型获得较大的精简,为最终获得准确和完备的拆卸图模型做出了一定的贡献。将子拆卸单元用递阶结构图的形式表示,这种表示方式简洁、直观。用多色集理论的可能位移方程组作为可拆卸性筛子,具有形式化水平高、算法

22、简单、易于编程等方面的优点。参考文献:1李剑锋,陈建,李方义,等.机电产品拆卸回收模型及其拆卸序列生成J.山东大学学报(工学版,2004,34(5:913.2郭茂,蔡建国,童劲松.基于Petri网的产品拆卸模型研究J.中国机械工程,2000,11(9:10071009.3李宗斌.先进制造中多色集合理论的研究及应用M.北京:中国水利水电出版社,2005.4Pavlov V V,李宗斌,戴文娣,等.基于多色集合的产品装配序列仿真J.西安交通大学学报,2001,35(11:12081210.5Pavlov V V.Theoretical Base of Assembly for Air2plane

23、and WhirlybirdM.Moscow:MA I Press,1993.6高建刚,向东,陈海,等.拆卸与或图模型中的连通性筛子J.清华大学学报,2003,43(8:10461048. 7张博,张洪涛,赵珊珊,等.基于多色集合理论的产品装配规划建模及算法研究J.西安交通大学学报,2005,39(11:12541258.8高建刚,段广洪,汪劲松.面向回收设计拆卸与或图方法的研究J.计算机集成制造系统-CIMS,2002,8(7:575579.(编辑马尧发作者简介:闫利军,男,1980年生。西安交通大学机械制造系统工程国家重点实验室博士研究生。研究方向为产品信息建模、仿真和优化。发表论文5篇。

24、李宗斌,男,1946年生。西安交通大学机械制造系统工程国家重点实验室教授、博士研究生导师。赵姗姗,女,1979年生。西安交通大学机械制造系统工程国家重点实验室博士研究生。(上接第726页的排样问题,允许零件在全角度范围内进行旋转,并可统一处理内部带孔洞或者边界形成空腔等特殊情况。实验结果表明本文不规则排样算法的材料利用率普遍可达80%以上,显示出良好的应用前景。参考文献:1Hopper E,Turton H.A Review of the Applicationof Meta-heuristic Algorithms to2D Strip PackingProblemsJ.Artificial

25、 Intelligence Review,2001,16:257300.2Kathryn A D,William B D.Solution Approaches toIrregular Nesting ProblemsJ.European Journal ofOperational Research,1995,84:506521.3Fujita K,Akagji S,K irokawa N.Hybrid Approachfor Optimal Nesting using A G enetic Algorithm andA Local Minimization AlgorithmC/In Proceed2ings of the19th Annual ASM E Design AutomationConference.Albuquerque,NM,USA,1993:477484.4J akobs S.On Genetic Algorithms for the Packing ofPolygonsJ.European Journal of Operational Re2search,1996,88:165181.5Fischer A D,Dagli