·52· 智能系统学报 第2卷 的矩形件，其数量及尺寸的数据如表2所示.在卷材 CAO Ju,FENG Song.The application of genetic algo- 上排样，卷材宽度为600mm.运行算法得到的排样 rithm in rectangular object optimal layout [J].Computer 结果如图5所示，卷材的使用长度为1150mm,小 Engineering and Application,1999,5(2):5-7. 于文献[4]的卷材长度1245mm [2]杨威，罗阳，刘胜青.大规模矩形零件优化套排的遗 传算法[U].四川大学学报（工程科学版），2001,33(5) 表2矩形件数据2 59.62. Table 2 Data 2 of the rectangular objects YANG Wei,LUO Yang,LIU Shengqing.Genetic algo- 编号 数量 长/mm 宽/mm rithm for large scale rectangular object optimal embed 5 40 40 20 placement[J].Journal of Sichuan University (Engineer- % 78 15 6 ing science edition),2001,33(5):59-62. 2 19 50 30 [3]韩喜君，丁根宏.基于改进遗传算法的矩形件优化排样 59 50 25 [U].计算机工程与应用，2006,42(25)：63.65. 6 64 50 40 HAN Xijun,DING Genhong.The optimum packing of 35 18 6 rectangles based on improved genetic algorithm [J ] 15 26 45 Computer Engineering and Application,2006,42(25): 2 49 35 15 63.65 3 66 60 40 [4]杨彩，史俊友，顾海明.基于遗传模拟退火算法的矩形 80 80 40 件排样[U].青岛科技大学学报，2004,25(5)：452·456. YANG Cai,SHIJunyou,GU Haiming.Packing of rec- tangular using genetic simulated annealing algorithm[J]. Journal of Qingdao University of Science and Technolo- gy,2004,25(5):452-456. [5]罗意平，刘军，李兵，等.一个实用的矩形件优化排样 启发式算法U].工程图学学报，2003,24(4)：50.58 150 LUO Yiping,LIU Jun,LI Bing,et al.A practical heu 图5卷材上的排样方案 ristic algorithm for rectangle parts packing problem[J]. Fig.5 Layout on the roll Journal of Engineering Graphics,2003,24(4):50-58. 3结束语 [6]陶献伟，王华昌，李志刚.基于填充算法的矩形件排样优 化求解U].中国机械工程，2003,14(13)：1104.1108. 针对已有遗传算法中存在由于编码信息不全而 TAO Xianwei,WANG Huachang,LI Zhigang.Optimal 产生的算法搜索性能不够好的问题，以及实际生产 solution of rectangular part layout based on rectangle fill- 中对排样方案的“一刀切”工艺要求，文中设计了一 ing algorithm[J].China Mechanical Engineering,2003 个具有2层形式的染色体编码，并在遗传算法中调 14(13):1104.1108 用改进后的矩形匹配分割算法实现一个具体排样方 [7]邢文训，谢金星.现代优化计算方法[M],2版.北京：清 华大学出版社，2005. 案.矩形匹配分割算法和遗传算法都是解决矩形件 作者简介： 排样问题的有效方法，前者具有局部搜索性能强而 马炫，男，1962年生，工学博士， 后者全局搜索性能好.将二者结合的算法可以更有 副教授硕士生导师，主要研究方向为智 效地解决大规模多规格的板材和矩形件的排样优化 能信息处理、模式识别.在国内外刊物上 问题.计算实例表明了文中提出的算法可以找到比 发表论文10余篇，著有译著1部. 较好的排样方案.由于算法可以实现板材的“一刀 Email maxuan @xaut.edu.cn 切”要求，并考虑了下料工艺中的切缝宽度问题，不 仅可以应用于不同规格板材的套排，还可用于单块 板材及卷材，具有更好的适用性和实用性.算法已制 成软件在实际生产中应用】 张亚龙，男，1976年生，硕士研究 参考文献： 生，主要研究方向为遗传算法及应用. [1]曹炬，冯松.遗传算法在矩形件优化排样中的应用 [U].计算机工程与应用，1999,5(2)：5.7 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net的矩形件 ,其数量及尺寸的数据如表 2 所示. 在卷材 上排样 ,卷材宽度为 600 mm. 运行算法得到的排样 结果如图 5 所示 ,卷材的使用长度为 1 150 mm ,小 于文献[ 4 ]的卷材长度 1 245 mm. 表 2 矩形件数据 2 Table 2 Data 2 of the rectangular objects 编号 数量 长/ mm 宽/ mm 5 40 40 20 8 78 15 6 12 19 50 30 1 59 50 25 6 64 50 40 9 35 18 6 15 26 45 15 2 49 35 15 3 66 60 40 4 80 80 40 图 5 卷材上的排样方案 Fig. 5 Layout on the roll 3 结束语 针对已有遗传算法中存在由于编码信息不全而 产生的算法搜索性能不够好的问题 ,以及实际生产 中对排样方案的“一刀切”工艺要求 ,文中设计了一 个具有 2 层形式的染色体编码 ,并在遗传算法中调 用改进后的矩形匹配分割算法实现一个具体排样方 案. 矩形匹配分割算法和遗传算法都是解决矩形件 排样问题的有效方法 ,前者具有局部搜索性能强而 后者全局搜索性能好. 将二者结合的算法可以更有 效地解决大规模多规格的板材和矩形件的排样优化 问题. 计算实例表明了文中提出的算法可以找到比 较好的排样方案. 由于算法可以实现板材的“一刀 切”要求 ,并考虑了下料工艺中的切缝宽度问题 ,不 仅可以应用于不同规格板材的套排 ,还可用于单块 板材及卷材 ,具有更好的适用性和实用性. 算法已制 成软件在实际生产中应用. 参考文献 : [1 ]曹 炬 ,冯 松. 遗传算法在矩形件优化排样中的应用 [J ]. 计算机工程与应用 ,1999 ,5 (2) : 5 - 7. CAO J u , FEN G Song. The application of genetic algo2 rithm in rectangular object optimal layout [J ]. Computer Engineering and Application , 1999 ,5 (2) : 5 - 7. [2 ]杨 威 ,罗 阳 ,刘胜青. 大规模矩形零件优化套排的遗 传算法[J ]. 四川大学学报 ( 工程科学版) ,2001 ,33 (5) : 59 - 62. YAN G Wei , LUO Yang , L IU Shengqing. Genetic algo2 rithm for large scale rectangular object optimal embed placement[J ]. Journal of Sichuan University ( Engineer2 ing science edition) , 2001 ,33 (5) :59 - 62. [3 ]韩喜君 ,丁根宏. 基于改进遗传算法的矩形件优化排样 [J ]. 计算机工程与应用 ,2006 ,42 (25) :63 - 65. HAN Xijun , DIN G Genhong. The optimum packing of rectangles based on improved genetic algorithm [ J ]. Computer Engineering and Application , 2006 , 42 (25) : 63 - 65. [4 ]杨 彩 ,史俊友 ,顾海明. 基于遗传模拟退火算法的矩形 件排样[J ]. 青岛科技大学学报 ,2004 ,25 (5) :452 - 456. YAN G Cai , SHI J unyou , GU Haiming. Packing of rec2 tangular using genetic simulated annealing algorithm[J ]. Journal of Qingdao University of Science and Technolo2 gy , 2004 ,25 (5) :452 - 456. [5 ]罗意平 ,刘 军 ,李 兵 ,等. 一个实用的矩形件优化排样 启发式算法[J ]. 工程图学学报 ,2003 ,24 (4) :50 - 58. LUO Yiping , L IU J un , L I Bing ,et al. A practical heu2 ristic algorithm for rectangle parts packing problem[J ]. Journal of Engineering Graphics , 2003 , 24 (4) : 50 - 58. [6 ]陶献伟 ,王华昌 ,李志刚. 基于填充算法的矩形件排样优 化求解[J ]. 中国机械工程 ,2003 ,14 (13) : 1104 - 1108. TAO Xianwei , WAN G Huachang , L I Zhigang. Optimal solution of rectangular part layout based on rectangle fill2 ing algorithm[J ]. China Mechanical Engineering , 2003 , 14 (13) : 1104 - 1108. [7 ]邢文训 ,谢金星. 现代优化计算方法[ M ]. 2 版. 北京 :清 华大学出版社 ,2005. 作者简介 : 马 炫 ,男 ,1962 年生 ,工学博士 , 副教授 ,硕士生导师 ,主要研究方向为智 能信息处理、模式识别. 在国内外刊物上 发表论文 10 余篇 ,著有译著 1 部. E2mail : maxuan @xaut. edu. cn. 张亚龙 ,男 ,1976 年生 ,硕士研究 生 ,主要研究方向为遗传算法及应用. ·52 · 智 能 系 统 学 报 第 2 卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net