5期陈勇等:基于遗传模拟退火算法的不规则多边形排样
599
平面最优布局的优化问题,广泛应用于服装、制鞋、船舶、钣金等工业生产中,以提高材料利用率,降低生产成本.矩形排样问题由于其广泛的应用和比较简单的几何特征,研究工作开展得比较早,并且可使
[l][2]
用一些数学规划技术,如线性规划、动态规划、[3][4-5]整数规划、整数线性规划等.但是,由于这些
直方向的移动直至无法再向左或者向下移动.启发式思想的本质是模拟人的智能行为,而排样对象的几何表达方式则是算法实现的关键.2.1
排样对象的几何表达
不规则形状的排样件及板料的几何轮廓由直线段和曲线段组成,因为曲线段可以按一定的精度离散成直线段,所以排样对象最终为可能带有内孔特征或者无效区域的多边形.
设G()为排样件G旋转角度后的图形,
数学规划技术的计算量大,因此不能处理不规则形
[6]
状的排样问题.自Adamowicz第一次提出对不规则排样问题的启发式算法的思想之后,许多学者在
这方面做了大量的研究工作.Yanasse等[7]
提出了基于某种优先级规则的顺序启发式算法,该算法只考虑一种确定的排样顺序,没有多种结果的相互比较,所以其给出的往往只是准优解.基于这种局限性,一些学者尝试用人工神经网络、模拟退火、遗传算法等人工智能方法结合启发式算法求解,并且取
得了很好的效果.Jakobs[8]将遗传算法和启发式算法应用于单张矩形板料上的多边形排样问题中,其
中遗传算法负责给出一个最佳的排样顺序样,启发式算法负责排样的实现.RemeshBabu等[9]
同样利用遗传算法和启发式算法给出了多张矩形板料上的矩形件排样.Han和Na[l0]
将神经网络和模拟退火技术应用于不规则形状的排样件在单张矩形板料上的排样,他们首先利用神经网络技术初始生成一个认为好的布局,然后用模拟退火技术通过平移、旋转等动作逐步改善这个布局.
本文的排样问题是若干个不规则排样件在板料上的排样,问题具有一般性,即排样对象的形状和角度等没有任何限制,而且还可能具有内孔特征或者无效区域.在处理这些极度不规则的排样对象时,使得本来就属于NP完全难题的排样问题变得更加复杂.目前,已有学者提出了一些几何表达方式来
降低问题的复杂性[ll-l3].在本文中,
我们在设计启发式排样算法的同时也提出了一种离散的几何表达方式,可以完全忽略高度不规则形状带来的复杂性影响,以提高启发式算法的效率.
2基于BL策略的启发式排样算法
我们采用遗传模拟退火算法,通过全局优化概率
搜索来产生最佳的排样次序和每个排样件的旋转角度,然后用启发式排样算法进行定位,实现自动排样.
启发式算法采用众所周知的左下角(Bottom-Left-condition,BL)
策略[l4]
,每一个排样件从板料的右上角开始向板料的左下角平移,重复水平和垂
!!G(!)
最大和最小的x,y坐标值分别为Xmax,Xmin,Ymax,Ymin.以间距为lmm的水平扫描线顺序扫描G(!)的多边形区域,经过G(!)的扫描线条数N=int(Ymax-Ymin).计算扫描线与多边形的相交区间,对于一条扫描线,可以分为4个步骤实现:
Stepl.求交.计算扫描线与多边形各边的交点.Step2.交点取舍.交点中,
如果是多边形的局部最高点或者局部最低点的顶点(极值点),交点算作零个或者两个交点;如果是顶点但不是极值点,交点只算一个.
Step3.排序.把所有交点按递增顺序进行排序.Step4.交点配对.第一个与第二个,
第三个与第四个……每对交点代表扫描线与多边形区域的一个相交区间.
这样,排样件可以看作是由一系列水平线段区间组成.如图l所示

.
a

若干扫描线与多边形的相交区间
b多边形的扫描区间表示示意
图l通过扫描线相交多边形来构造扫描区间
对于板料的扫描区间表示,我们增加一个脏位标志(DirtyFiag,DF),板料多边形有效区域内的扫描区
基于遗传模拟退火算法的二维不规则多边形排样问题 基于遗传模拟退火算法的二维不规则多边形排样问题基于遗传模拟退火算法的二维不规则多边形排样问题隐藏>> 学校代码 ...
对于二维不规则图形零件在排样区域上的最优排列,将排样和制造工艺联系起来,将多边形 摘要: 各边向外扩充,为零件预留加工余量;然后采用遗传模拟退火算法与小生境技术...
对于二维不规则图形零件在排样区域上的最优排列,也就是对二维不规则图形的计算机自动排样算法进行优化问题。采用矩形包络算法、遗传模拟退火算法及小生境技术相结合,...
一种二维不规则零件优化... 8页 1下载券 基于遗传模拟退火算法的... 62页...一种基于重心 N FP 的二维不规则多边形排样算法 ,算法主要包括临界多边形计算和...
一种二维不规则零件优化... 8页 1下载券 基于遗传模拟退火算法的... 62页...一种基于重心 N FP 的二维不规则多边形排样算法 ,算法主要包括临界多边形计算和...
遗传模拟退火混合算法在钣金自动排样中的研究_专业资料。在钣金制造中,如何进行... 基于混合遗传模拟退火算... 1人阅读 3页 3.00 不规则件优化排样的...
求解矩形件优化排样的自适应模拟退火遗传算法_专业资料。矩形件优化排样是一个...第2 卷O 第1 1期 计 算机 辅 助设计 与 图形 学学 报 JOURNAI OFCOMP ...
不规则件优化排样的小生... 4人阅读 6页 2.00 基于模拟退火遗传算法...(070020 10—2520)3—06—4 基于遗传 模拟 退火 算法 的铣 削 用量 优化 ...
基于遗传模拟退火算法的移动机器人静态路径规划_专业资料。采用多边形法描述了机器人的工作环境模型,应用简化编码长度的技术简化了工作路径编码方式.对于基于遗传算法...
一个基于遗传算法和模拟退火 算法的求解布局问题( 矩形件排样优化) 算法, 并...( 对于非矩形的不规则形状零件的排样 问题, 可通过计算机的图形处理技术将一个...
热门文档