基于改进最低水平线方法与遗传算法的矩形件排样优化算法  

Optimization Algorithm for Rectangle Packing Based on Improved Lowest Horizontal Line Method and Genetic Algorithm

作　　者：刘海明[1] 周炯[1] 吴忻生[1] 罗家祥[1] 

机构地区：[1]华南理工大学自动化科学与工程学院,广东广州510641

出　　处：《图学学报》2015年第4期526-531,共6页Journal of Graphics

基　　金：广东省科技计划资助项目-工业高新技术领域(2014A010104004);中央高校基本科研业务费专项资金重点资助项目(2014ZZ0033)

摘　　要：传统的最低水平线方法用于矩形件排样时可能产生较多未被利用的空白区域,造成不必要的材料浪费。针对此缺陷,在搜索过程中引入启发式判断,实现空白区域的填充处理,提高板材利用率。在应用遗传算法优化矩形件排样顺序时,在进化过程中采用分阶段设置遗传算子的方法,改善算法的搜索性能与效果。通过改进最低水平线方法与基于分阶段遗传算子的遗传算法相结合,共同求解矩形件排样问题。排样测试数据表明,所提出的矩形件排样优化算法能够有效改善排样效果,提高材料利用率。For the issue of rectangle packing problem, traditional lowest horizontal line method mightgenerate certain empty blocks that were not used, which would cause unnecessary waste of material.To solve the problem, heuristic estimate is introduced into search process to achieve rectangle fillingfor the empty blocks and improve utilization. For optimization packing sequence of rectangles usinggenetic algorithm, a new strategy of setting different genetic factors by stages of evolution process isapplied to improve algorithm performance. The two improved methods are combined in union tosolve the rectangle packing problem. The test data of packing show that the proposed algorithm caneffectively improve packing results and improve utilization of material.

关 键 词：矩形件排样 优化算法 最低水平线 遗传算法 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]