资源描述：
《基于模拟退火算法的矩形件排样》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、·应用研究·王桂宾周来水邓冬梅基于模拟退火算法的矩形件排样65基于模拟退火算法的矩形件排样王桂宾周来水邓冬梅(南京航空航天大学机电学院,江苏南京210016)摘要:针对矩形件排样问题,提出了最低轮廓线最佳匹配算法。该算法根据最低轮廓线排放矩形,使板材浪费降至最低。并将其与模拟退火算法相结合,可获得近似最优的排样结果。最后给出不同规模的算例,结果表明,该算法比最低水平线算法排样结果好,是解决矩形件排放的有效方法。关键词:矩形件排样;最低轮廓线最佳匹配算法;模拟退火算法中图分类号:TP391.72文献标识码:A文章编号:1672-1616(2006)15-0065-03矩形件优化排
2、样问题广泛地出现于机械制造、零件的一个排列,即排放顺序;然后采用一定的排轻工、家具、造纸、印刷及玻璃切割等行业。矩形件放方法按给定顺序依次排放零件。矩形零件的排排样问题通常是指将一系列矩形零件R=(R1,放顺序和排放算法共同决定板材的最终利用率。R2,⋯,Rn),其中n为矩形件的数目,互不重叠地文献[7]采用了最低水平线算法,该算法的步骤如排布在一宽为W、长(高)为L的矩形板材P内,在下:满足一定工艺要求的前提下,使得排放区域的废料第一步,设置初始最高轮廓线为板材最下面的尽可能少,从而达到节省板材的目的。边。矩形件排样属NP完全问题,除非待排零件个第二步,每当要排入一个零件Ri
3、时,就在最高数很少,否则无法求得最优解。矩形件优化排样问轮廓线集中选取最低的一段水平线,如有数段,则题可以分为两大部分:排样算法规则和排样顺序的选取最左边的一段,如果该段线的宽度大于要排入优化。优化过程是首先给出(一个或一组)初始排零件的宽度,就将该零件在此位置排放,更新零件样顺序,采用给定的排样算法进行排样;然后搜索最高轮廓线;否则,查询与最低水平线段相邻的左、出最优排样顺序,使材料利用率最高。搜索算法的右两段水平线,将最低水平线提升至与高度较低的主要作用是搜索最优排样顺序。20世纪90年代一段平齐,更新零件最高轮廓线;重复此过程,直至[1～4]能排入零件。以来,国外学者不断
4、探索遗传算法(GA)、模拟退火算法(SA)、禁忌搜索(TS)、人工神经网络等随第三步,重复上述过程,直至所有零件排放完机搜索算法与一定的排放方法相结合来解决矩形毕,最后所求最大高度即所需板材长度。[5][6]该算法存在如下两点不足:(1)排放R时,如件排样问题。国内以曹矩、刘德全和贾志i[7]果有数段最低水平线,则选取最左边的一段,势必欣等博士的研究较为深入,提出了最低水平线算法、下台阶算法,并与GA、SA算法相结合进行会导致和BL一样的左侧偏高;(2)当最低水平线求解。本文根据最低水平线的思想提出了一种新的宽度小于待排矩形件的宽度时,直接更新轮廓启发式算法———最低轮廓线最佳
5、匹配算法,该算法线,简单作此处理会造成当前最低水平线以下的相在同样的排列下能得到更优的排样图,适用于矩形应空闲区域的浪费,因为宽度小于当前要排的矩形件的优化排样。件的宽度,但可能大于其他未排放矩形件的宽度。1.2最佳匹配搜索策略1最低轮廓线最佳匹配排放算法针对最低水平线的排放缺点,本文提出了一种1.1最低水平线算法简介新的启发式搜索策略即最佳匹配搜索策略(Best矩形件排样问题的求解过程是:首先确定所有FitSeach)。该策略如下:收稿日期:2006-06-06作者简介:王桂宾(1981-),男,江苏海安人,南京航空航天大学在读硕士研究生,主要研究方向为制造业信息化。6620
6、06年8月中国制造业信息化第35卷第15期排放零件Ri时,如果有若干条轮廓线可以排(2)计算新解的评价函数f(x)和旧解的评价放,则搜索宽度最适合的进行排放,即排放该矩形函数f(x)的差值Δf;后,当前轮廓线剩余宽度最小;若所有最低轮廓线(3)如果Δf<0,接收新解,转c;如果Δf>段均不能放下Ri,则逐条判断其宽度是否大于剩0,依照概率,exp(-Δf/Tk)>random[0,1]接收余零件的最小宽度。若是,则在剩余零件中搜索宽新解,random[0,1]是[0,1]区间内的随机数。度合适的件Rj,并互换Ri和Rj的位置,将其提升c.令Tk+1=αTk,k←k+1,其中α∈
7、[0,至相邻轮廓线的高度;否则就封闭该轮廓线。1],若满足收敛判据,则退火过程结束;否则,转b。1.3最低轮廓线最佳匹配排放算法其中退火温度T控制着求解过程向最小值的优化最低轮廓线最佳匹配排放算法的流程如图1方向进行,同时又以概率exp(-Δf/Tk)来接收劣所示。质解。因此算法可以跳出局部极值点。理论上只要初始温度足够高,退火过程足够慢,算法就能收敛到全局优解。2.2关键参数的确定2.2.1解的表达及邻域搜索将矩形件编号的任意排列作为一个解,采用十进制表示,如排列A(3,2,4,1)表示先
