基于遗传模拟退火算法的矩形件优化排样  

Packing optimization of rectangles based on improved genetic annealing algorithm

作　　者：杨卫波[1,2] 王万良[1] 张景玲[3] 赵燕伟[3] 

机构地区：[1]浙江工业大学信息工程学院,杭州310023 [2]温州大学物理与电子信息工程学院,浙江温州325035 [3]浙江工业大学特种装配制造与先进加工技术教育部重点实验室,杭州310014

出　　处：《计算机工程与应用》2016年第7期259-263,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.51275477;No.61379123;No.61402409);浙江省自然科学基金(No.LQ14F030005)

摘　　要：为了探索更高效的矩形件优化排样方法,提出了一种改进的自适应遗传模拟退火算法。设计了基于矩形件的排样次序及旋转变量的两层染色体编码方法,并采用基于临界多边形的BL定位策略实现矩形件的布局;通过构造启发式算法生成排样初始种群,然后各个种群之间通过相互竞争实现优秀个体的迁移与共享,最终搜索到最优解。标准测试问题的实验结果验证了所提算法的可行性与有效性。To explore more efficient methods for the packing optimization problem of rectangles, an Improved Adaptive Genetic Simulated Annealing（IAGSA）algorithm is presented. The two-layer coding method based on the packing sequence and rotation variable of rectangular parts is designed, and the bottom-left-condition placement strategy based on no fit polygon is proposed to complete the layout of rectangular parts. The heuristic algorithm is constructed to generate packing initial populations. The migration and sharing of outstanding individual are achieved by mutual competition among all populations, and the optimal solution is found eventually. The simulation results on classic benchmarks demonstrate the feasibility and effectiveness of the presented IAGSA.

关 键 词：矩形件排样 启发式布局算法 临界多边形 模拟退火算法 自适应遗传算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]