矩形件排样的模拟退火算法求解

《矩形件排样的模拟退火算法求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、四川大学学报(工程科学版)JOURNALOFSICHUANUNIVERSITY(ENGINEERINGSCIENCEEDITION)第33卷第5期2001年9月Vol.33No.5Sept.2001文章编号:100923087(2001)0520035204矩形件排样的模拟退火算法求解贾志欣,殷国富,罗阳,徐雷(四川大学制造科学与工程学院,四川成都610065)摘要:讨论了用模拟退火算法求解矩形件排样问题。在对问题数学模型分析的基础上,给出了模拟退火算法求解的关键步骤和方法,并通过算例讨论了模拟退火算法中三个主要参数初始温度、冷却系数以及终止温度对排样结果

2、的影响。实验结果表明:采用模拟退火算法求解排样问题是适合的。关键词:矩形件;排样;模拟退火算法中图分类号:TH122文献标识码:AApplicationofSimulatedAnnealingtotheRectangularPackingProblemJIAZhi2xin,YINGuo2fu,LUOYang,XULei(CollegeofManufacturingSci.andEng.,SichuanUniv.,Chengdu610065,China)Abstract:Inthispaperatwo2dimensionalcuttingstockprobl

3、emissolvedbyapplyingageneralglobaloptimizationalgo2rithm,thesimulatedannealing(SA)method.Thealgorithmappliestoorthogonalcuttingproblem.Threekeyparametersofsimulatedannealingmethodarediscussedandtheirinfluenceontheresultoflayoutarealsoshown.Experimentalre2sultsshowthattheSAmethodis

4、properforsolvingtherectangnlarpackingproblem.Keywords:rectangular;cutting2stockproblem;simulatedannealing;optimization矩形件排样问题是指在给定的矩形板材上将一系列矩形零件按最优方式进行排布,即给定n个等,都需要在可接受的时间里得到最优或近似最优解。对于非矩形的不规则零件的排样问题,可通过计算机图形学处理技术将一个或几个零件单排、对排等方式组合在一个包容矩形中,然后对包容矩形进行排样,从而转化为矩形件排样问题,可见矩形件排样优化问题的解决具有

5、重要的意义。从数学计算复杂性理论看,矩形件排样优化问题属于NP完全问题[1,2,8,9],即在多项式时间内得不到最优解,但由于生产实际的需要,人们又迫切需要利用现代科技对这一问题给出一些能满足生产需要的求解方法。为此,不少学者在这方面作了许多工作,提出了一些近似算法[1～7]。本文探讨了用模拟退火算法来解决矩形件正交优化排样问题,即在定宽长度不限的板材上正交地排放所给定的矩形件,使所需的板材高度最小。零件R=(R1,R2,,Rn),将零件置于宽度为W0,高度为L板材P上,使得板材的利用率最高,并要求满足下列约束条件:1)2)3)Ri,Rj互不重叠,i≠j,

6、i,jRi必须放在P内,i=1,2,满足一定的工艺要求。=1,2,,n;,n;最大限度地节约材料,提高材料利用率是生产中提高效益的一个重要手段。由于排样问题的广泛存在,如板金下料、报刊排版、玻璃切割、服装裁剪收稿日期:2001205221作者简介:贾志欣(1970-),女,讲师,博士生.研究方向:计算机辅助设计与制造.1数学模型对于矩形件排样问题,即给定n个零件R=2模拟退火算法求解2.1模拟退火算法思想简述模拟退火算法起源于统计物理学中对固体退火过程的模拟[8,9],它采用Boltzmann接受准则接收新解,用称为冷却系数的参数控制算法进程,使算法在多项

7、式时间里给出一个近似最优解。求解过程如下:1)始化退火温度Tk(令k=0),初始解为X0;2)在温度Tk下重复执行如下操作,直至达到温度Tk的平衡态:①在解x的邻域中产生新的可行解x′;②计算新解的评价函数f(x′)和旧解的评价函数f(x)的差值△f;③如果△f<0,接收新解,转3);如果△f>0,依照概率,exp(-△f/Tk)>random0,1接收新解,random[0,1]是[0,1]区间内的随机数。(R1,R2,,Rn),将零件置于宽度为W0,高度为L板材P上,从数学角度分析是一整数规划问题。为便于分析,首先定义以下变量:I={1,2,,n}是矩

8、形件的一组编号;Lmin为所需板料的高度(由于所需板料的高度小时,