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

四 川 大 学 学 报 ( 工 程 科 学 版 )JOURNAL OF SICHUAN UNIVERSITY ( ENGINEERING SCIENCE EDITION)第 33 卷 第 5 期2001 年 9 月Vol . 33 No . 5Sept . 2001文章编号 :100923087 (2001) 0520035204矩形件排样的模拟退火算法求解贾志欣 ,殷国富 ,罗阳 ,徐雷( 四川大学 制造科学与工程学院 , 四川 成都 610065)摘 要 :讨论了用模拟退火算法求解矩形件排样问题 。在对问题数学模型分析的基础上 ,给出了模拟退火算法求解的关键步骤和方法 ,并通过算例讨论了模拟退火算法中三个主要参数初始温度 、冷却系数以及终止温度对排样 结果的影响 。实验结果表明 :采用模拟退火算法求解排样问题是适合的 。关键词 :矩形件 ;排样 ;模拟退火算法中图分类号 : TH122文献标识码 :AApplication of Simulated Annealing to the Rectangular Packing ProblemJ IA Zhi2xin , YIN Guo2f u , LUO Yang , XU Lei( College of Manufacturing Sci . and Eng. , Sichuan Univ. , Chengdu 610065 ,China)Abstract :In this paper a two2dimensional cutting stock problem is solved by applying a general global optimization algo2rithm , the simulated annealing ( SA) method. The algorithm applies to orthogonal cutting problem. Three key parameters of simulated annealing method are discussed and their influence on the result of layout are also shown. Experimental re2 sults show that the SA method is proper for solving the rectangnl ar packing problem.Key words :rectangular ; cutting2stock problem ; simulated annealing ; optimization矩形件排样问题是指在给定的矩形板材上将一系列矩形零件按最优方式进行排布 , 即给定 n 个等 , 都需要在可接受的时间里得到最优或近似最优解 。对于非矩形的不规则零件的排样问题 , 可通过计 算机图形学处理技术将一个或几个零件单排 、对排 等方式组合在一个包容矩形中 , 然后对包容矩形进 行排样 , 从而转化为矩形件排样问题 , 可见矩形件排 样优化问题的解决具有重要的意义 。从数学计算复 杂性理论看 , 矩形件排样优化问题属于 N P 完全问题1 , 2 , 8 , 9 , 即在多项式时间内得不到最优解 , 但由于生产实际的需要 , 人们又迫切需要利用现代科技对 这一问题给出一些能满足生产需要的求解方法 。为 此 , 不少学者在这方面作了许多工作 , 提出了一些近 似算法17 。本文探讨了用模拟退火算法来解决矩形件正交 优化排样问题 , 即在定宽长度不限的板材上正交地 排放所给定的矩形件 , 使所需的板材高度最小 。零件 R = ( R1 , R2 , Rn) , 将零件置于宽度为 W0 ,高度为 L 板材 P 上 , 使得板材的利用率最高 , 并要求满足下列约束条件 :1)2)3)Ri , Rj 互不重叠 , i j , i , jRi 必须放在 P 内 , i = 1 , 2 ,满足一定的工艺要求 。= 1 , 2 , n ;, n ;最大限度地节约材料 , 提高材料利用率是生产中提高效益的一个重要手段 。由于排样问题的广泛 存 在 , 如板金下料 、报刊排版 、玻璃切割 、服装裁剪收稿日期 :2001 205 221作者简介 :贾志欣 (1970 - ) , 女 , 讲师 , 博士生. 研究方向 :计算机 辅助设计与制造.1数学模型对于矩 形 件 排 样 问 题 , 即 给 定 n 个 零 件 R =2 模拟退火算法求解2. 1模拟退火算法思想简述模拟退火算法起源于统计物理学中对固体退火 过程的模拟8 , 9 , 它采用 Boltzmann 接受准则接收新解 , 用称为冷却系数的参数控制算法进程 , 使算法在 多项式时间里给出一个近似最优解 。求解过程如下 :1) 始化退火温度 Tk ( 令 k = 0) , 初始解为 X0 ;2) 在温度 Tk 下重复执行如下操作 , 直至达到 温度 Tk 的平衡态 :在解 x 的邻域中产生新的可行解 x;计算新解的评价函数 f ( x) 和旧解的评价函 数 f ( x) 的差值 f ;如果 f 0 ,依照概率 , exp ( - f / Tk ) random0 ,1接收新解 , random 0 , 1 是 0 , 1 区间内的随机数 。( R1 , R2 , Rn) , 将零件置于宽度为 W0 , 高度为 L板材 P 上 , 从数学角度分析是一整数规划问题 。为便于分析 , 首先定义以下变量 : I = 1 , 2 , n 是矩形件的一组编号 ; L min 为所需板料的高度 ( 由于所需板料的高度小时 , 材料利用率高 , 故取 L min 为求取最小值的参数) ; ( xi , yi ) 为矩形件 R 的左下角点坐标 ;l liWi , L i 为矩形件 Ri 的宽度和高度 ; ( xi , yi ) 为矩形件u uRi 的右上角点的坐标 ; lij = 0 或 1 , 当 Ri 置于 Rj 的左侧时取 1 , 其他取 0 ; bij = 0 或 1 , 当 Ri 置于 Rj 的下侧 时取 1 , 其他取 0 ; L 为某个已知的 L min 的上界 。矩形件的排样问题可表达为 :minL minxi W0L mini Ii Ii I(1)( 2) ( 3) ( 4) (5) (6) (7) (8)( 9)u= Tk , k k + 1 , 其中 (0 , 1) ,3) 令Tk +1yiu若满足收敛判据 , 则退火过程结束 ; 否则 , 转 2) 。其中退火温度 T 控制着求解过程向最小值的优 化方向进行 , 同时又以概率 exp ( - f / Tk ) 来接收劣质解 。因此算法可以跳出局部极值点 。从理论上只要初始温度足够高 , 退火过程足够慢 , 算法就能收敛 到全局优解 。xii=xl + Wiuyii Ii j Ii j Iyl + L iiuxij xl + W0 (1 -lij)bij )10uyii yl + L (1 -u I , il ij + lji + bij + bjii , jj应用模拟退火算法解决矩形件的排样问题解的形式以及邻域结构L min , xi , yi , xi , yi2. 22. 2. 1u u l l= 0 , 1lij , bij将矩形件的任一编号排列作为一个解 , 即对于n 个矩形零件解空间的大小为 n ! , 通过交换相邻零 件的位置得到新解 。如对于排列 2 , 3 , 1 , 4 表示先排 放 2 号零件 , 接着放 3 号 、1 号零件 , 最后放 4 号零件 ; 任意交换两相邻零件的位置 , 如交换 3 , 1 的位置 , 就可以得到一个新解 2 , 1 , 3 , 4 。在本文算法中不允许 零件旋转 90 。约束 (1) 、(2) 限 定 矩 形 件 在 板 材 内 部 ; 约 束(3) 、(4) 保证零件的左下角点与右上角点的尺寸关 系 ; 约束 ( 5) 、( 6) 分别表达了如果 Ri 置于 Rj 的左侧 , Ri 置于 Rj 的下侧时的宽度 、高度方向的邻接限制 ;约束 (7) 要求 Ri 与 Rj 是上下位置关系或左右位置关 系 , 从而保证 Ri 与 Rj 互不重叠 。在上述约束变量中 , xi 与 yi 不是必须的 , 因为u u2. 2. 2解转换为排样图它们可由 ( 3) 、( 4) 得到 。这里将其列出只是为了说明清楚 。去掉这两个变量 , 在上述问题中有 2 n + 1 个由于每一个零件编号排列解 , 只有将其转换为排样图后 , 才能计算其高度值 , 进而计算相邻解的排 样图高度差 。因此 , 对于任一排列 , 如何将其转变为连 续变量和 2 ( n2 -n) 个 2 进制变量 , 有 2 n + 2 ( n2 -n) + n ( n - 1) / 2 = 2 . 5 n2 - n/ 2 个约束 , 不包含非线 ; 否则 , 查询与最低水平线段相邻的左 、右两段水平线 , 将最低水平线提升至与高度较低的一段平齐 ,更新零件最高轮廓线 , 重复此过程 , 直至能排入零件 。重复上述过程 , 直至所有零件排放完毕 。对于编码 1 , 2 , 3 , 4 , 采用该方法的排样过程如 图 1 所示 。图 1 最低水平线法排放零件过程示意图Fig. 1 The packing procedure of lo west horizontal algorithm表 1 关于初始温度 、冷却参数以及终止温度的实验数据Ta b. 1 Experiment date on 3 para meters : initial temperature , cool ra te an d ter minal te mpera ture 对同一个的排样问题 , 同样的排列 “, 最低水平线法”的排样结果优于 BL 算法 。如对于本文例 1 所 示的排样问题 , 采用零件宽度降序的到的排列用 BL 算法得到的排样高度为 2 1 , 采用“最低水平线法”得到的高度为 18 。排样图高度所用 CPU时间 t/ s固定参数调整参数2. 2. 3终止条件减量为 1 %减量为 2 % 减量为 3 % 减量为 5 %171716179531当满足以下条件之一时 , 算法终止 :1) 排样图的高度值与某一已知的所需高度下 界 L 0 的比值小于 (1 + %) ;2) 温度 T 达到终止温度 Te ;所需板材高度下界 L 0 可以通过零件的面积和nT0 = Tmax 5 %Te = T0 1 %Te = T0 1 %减量 = 3 %T0 = Tmax 8 %T0 = Tmax 5 %171742T0 = Tmax 5 %减量 = 3 %Te = T0 2 %171932WiL iT = T 4 %e 0i = 1与板材宽度的比值得到 。即 : L 0 =W0注 :表中 CPU 时间是在 P 800 的微机上运行所需时间 ; Tmax 为矩形件的最大高度取 T0 = ( 矩形件的最大高度) 5 % , Te = T0 1 % , 减量为 3 % 得到高度为 16 的排样图 , 如图 3 所 示 。3算例分析为测试算法的性能 , 首先对已知最优解的算例进行求解 。算例 1将一个 15 40 的大矩形分成 25 个小矩形 , 如图 2 示 , 现以 40 为定宽 , 高度不限的板材 , 求最小排样高度 。图 3 采用模拟退火算法得到的排样图 (排样图高度 = 16)Fig. 3 Packing pattern generated by simulating algorithm ( height = 16)对零件数为 10 80 的 48 个排样问题进行测试 , 分别用摸拟退火算法和启发式算法即宽度降序 法求解 。模拟退火算法的三个参数取 T0 = ( 矩形件的最大高度) 5 % , Te = T0 1 % , 减量为 3 % , 运算结果表明 , 虽然启发式算法能在 1 s 内得到结果 , 但 模拟退火算法的解优于启发式算法的解 。表 2 列出其中 8 个问题的数据 。图 2 25 个矩形的最优排样图 ( 排样图高度 = 15)Fig. 2 Optimal packing pattern of 25 rectangles , height = 15计算表明 :同一排样问题 , 初始温度 、冷却参数以及终止温度有一组最佳组合值 , 使得问题的解质 量较高 。即这三个参数的确定应与具体的问题相关 。 表 1 列出了部分实验数据 。表 2 8 个排样问题的运算结果 Ta b. 2 Result of 8 c utting2stoc k proble m 3) 对于矩形件的排样问题 ,任何算法都难以保证总能得到最优 解 , 最 好 采 用 启 发 式 算 法 、遗 传 算 法 、模拟退火等多种方法分别求解 ,再从多种较优方 案中择优选用 。SA 算法所 SA 算法排启发式算法排样图高度序号零件个数需时间 t/ s样图高度1100 . 4114 . 0150. 1参考文献 :2224129 . 2177. 31曹 炬 ,周 济 . 矩形件排样优化的一种近似算法 J . 计算机辅助设计与图形学学报 ,1995 ,7 (3) :190195.黄宜军 ,施德恒 ,许启富 . 板金 CAD 中的一个较优的排料 算法 J . 计算机辅助设计与图形学学报 ,2000 ,12 (5) : 380383.刘嘉敏 ,张胜男 ,黄有群 . 二维不规则形状自动排料算法 的研究与实现 J . 计算机辅助设计与图形学学报 ,2000 ,12 (7) :488491.33016140 . 1181. 544031165 . 1189. 5256785060708064114173258169 . 5185 . 5286 . 5308 . 3198. 3216. 3321. 1350. 13注 :表中时间是在 P 800 的微机上运行所需时间 。4 Stefan Jokobs. On genetic algorithms for the packing of polygonsJ . Eur J of Oper Res , 1996