第2卷第5期 智能系统学报 Vol.2 Na 5 2007年10月 CAAI Transactions on Intelligent Systems 0ct.2007 基于遗传算法的大规模矩形件优化排样 马炫，张亚龙 (西安理工大学自动化与信息工程学院陕西西安710048) 摘要：大规模矩形件优化排样是一个典型的组合优化问题，属于NP-hard问题，实际工程中对一个排样方案一般 有满足“一刀切”的工艺要求，“一刀切”要求增加了对排样的约束.提出的优化算法，将矩形匹配分割算法作为遗传 算法染色体的解码器实现一个排样方案，用遗传算法进行排样方案的全局搜索.算例比较表明，该算法可以求得满 足“一刀切”约束的最优解 关键词：遗传算法；矩形件排样；组合优化 中图分类号：TP301文献标识码：A文章编号：1673-4785(2007)05004805 A genetic algorithm for the layout of large scale rectangular parts MA Xuan,ZHAN G Ya-long (School of Automation and Information Engineering,Xi'an University of Technology,Xi'an 710048,China) Abstract:The optimal layout of large scale rectangular parts is a combinatorial optimization problem,a typ- ical NP-hard one.In practical engineering,quire cutting is often requested,which increases the constraints in the determination of a layout.To satisfy quire cutting requirements,in this paper,an optimization algo- rithm is proposed wherein a rectangular matching and segmentation algorithm is employed as a decoder of chromosomes in a genetic algorithm to determine placement.A global optimal solution for placement can be achieved with this genetic algorithm.Simulation results confirmed the validity of the proposed algo- rithm. Key words:genetic algorithm;rectangular parts layout;combinatorial optimization 矩形件排样是指在给定尺寸的矩形板材上，排了排样的约束条件，而且切割时会产生一定的切缝 放多规格多数量的矩形件时，如何排放可以使板材 宽度.这些都会对排样结果产生影响.文中将矩形匹 的利用率最大.这是一个典型的组合优化问题，在工 配分割算法的局部搜索和遗传算法的全局搜索相结 业领域如冲裁件排样造船、车辆、家具生产、玻璃切 合，提出了一种满足“一刀切”工艺要求的矩形件排 割等行业都存在大量的排样问题.求解最优排样方 样优化算法.设计的编码方法和具有方向交叉的交 案是一个NP-hard问题，至今尚未找到多项式时间叉算子改善了遗传算法的搜索性能.通过算例比较】 算法.因此，对于大规模排样问题，在可接受的时间 表明了算法的有效性 内快速找到次优解的算法引起了人们的关注.很多 学者在这方面做了卓有成效的研究工作文献[1- 1矩形件排样优化算法 3]分别提出了排样问题的遗传算法；文献[4]提出了 1.1排样优化问题 将遗传算法和模拟退火算法结合的遗传模拟退火算 矩形件在矩形板材上的排样问题，可以分为2 法；文献「5]提出了启发式排样算法等等.在实际工 类：一类是在单一板材上排样，称为单排，其中包括 程中，对一个排样方案中的矩形件进行切割时，经常 卷材，卷材可以看成在宽度方向有约束而在长度方 会提出满足“一刀切”的下料工艺要求，如玻璃切割、 向没有约束的矩形板材：还有一类是在多块矩形板 厚型金属板材切割等.“一刀切”的要求实际上增加 材上的排样，称为套排.显然，套排比单排更加复杂 这里主要研究套排问题，排样优化问题可以描述成 收稿日期：200611-18. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 2 卷第 5 期 智 能 系 统 学 报 Vol. 2 №. 5 2007 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2007 基于遗传算法的大规模矩形件优化排样 马 炫 ,张亚龙 (西安理工大学 自动化与信息工程学院 ,陕西 西安 710048) 摘 要 :大规模矩形件优化排样是一个典型的组合优化问题 ,属于 NP2hard 问题. 实际工程中对一个排样方案一般 有满足“一刀切”的工艺要求“, 一刀切”要求增加了对排样的约束. 提出的优化算法 ,将矩形匹配分割算法作为遗传 算法染色体的解码器实现一个排样方案 ,用遗传算法进行排样方案的全局搜索. 算例比较表明 ,该算法可以求得满 足“一刀切”约束的最优解. 关键词 :遗传算法 ;矩形件排样 ;组合优化 中图分类号 : TP301 文献标识码 :A 文章编号 :167324785 (2007) 0520048205 A genetic algorithm for the layout of large scale rectangular parts MA Xuan , ZHAN G Ya2long (School of Automation and Information Engineering , Xi′an University of Technology , Xi′an 710048 ,China) Abstract :The optimal layout of large scale rectangular parts is a combinatorial optimization p roblem , a typ2 ical N P2hard one. In practical engineering , quire cutting is often requested , which increases t he constraints in t he determination of a layout. To satisfy quire cutting requirements , in t his paper , an optimization algo2 rit hm is proposed wherein a rectangular matching and segmentation algorit hm is employed as a decoder of chromo somes in a genetic algorithm to determine placement. A global optimal solution for placement can be achieved with t his genetic algorit hm. Simulation results confirmed t he validity of t he proposed algo2 rit hm. Keywords :genetic algorit hm ; rectangular parts layout ; combinatorial optimization 收稿日期 :2006211218. 矩形件排样是指在给定尺寸的矩形板材上 ,排 放多规格多数量的矩形件时 ,如何排放可以使板材 的利用率最大. 这是一个典型的组合优化问题 ,在工 业领域如冲裁件排样、造船、车辆、家具生产、玻璃切 割等行业都存在大量的排样问题. 求解最优排样方 案是一个 N P2hard 问题 ,至今尚未找到多项式时间 算法. 因此 ,对于大规模排样问题 ,在可接受的时间 内快速找到次优解的算法引起了人们的关注. 很多 学者在这方面做了卓有成效的研究工作. 文献[ 1 - 3 ]分别提出了排样问题的遗传算法 ;文献[4 ]提出了 将遗传算法和模拟退火算法结合的遗传模拟退火算 法 ;文献[ 5 ]提出了启发式排样算法等等. 在实际工 程中 ,对一个排样方案中的矩形件进行切割时 ,经常 会提出满足“一刀切”的下料工艺要求 ,如玻璃切割、 厚型金属板材切割等.“一刀切”的要求实际上增加 了排样的约束条件 ,而且切割时会产生一定的切缝 宽度. 这些都会对排样结果产生影响. 文中将矩形匹 配分割算法的局部搜索和遗传算法的全局搜索相结 合 ,提出了一种满足“一刀切”工艺要求的矩形件排 样优化算法. 设计的编码方法和具有方向交叉的交 叉算子改善了遗传算法的搜索性能. 通过算例比较 , 表明了算法的有效性. 1 矩形件排样优化算法 1. 1 排样优化问题 矩形件在矩形板材上的排样问题 ,可以分为 2 类 :一类是在单一板材上排样 ,称为单排 ,其中包括 卷材 ,卷材可以看成在宽度方向有约束而在长度方 向没有约束的矩形板材 ;还有一类是在多块矩形板 材上的排样 ,称为套排. 显然 ,套排比单排更加复杂. 这里主要研究套排问题 ,排样优化问题可以描述成 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net