Computer Engineering and Applications ›› 2016, Vol. 52 ›› Issue (7): 259-263.

Previous Articles     Next Articles

Packing optimization of rectangles based on improved genetic annealing algorithm

YANG Weibo1,2, WANG Wanliang1, ZHANG Jingling3, ZHAO Yanwei3   

  1. 1.College of Information Engineering, Zhejiang University of Technology, Hangzhou 310032, China
    2.College of Physics and Electronic Information Engineering, Wenzhou University, Wenzhou, Zhejiang 325035, China
    3.Key?Lab?of?Special Purpose Equipment and Advanced Manufacturing Technology, Ministry of Education, Zhejiang University of Technology, Hangzhou 310014, China
  • Online:2016-04-01 Published:2016-04-19

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

杨卫波1,2,王万良1,张景玲3,赵燕伟3   

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

Abstract: 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.

Key words: rectangle packing, heuristic layout algorithm, no fit polygon, simulated annealing algorithm, adaptive genetic algorithm

摘要: 为了探索更高效的矩形件优化排样方法,提出了一种改进的自适应遗传模拟退火算法。设计了基于矩形件的排样次序及旋转变量的两层染色体编码方法,并采用基于临界多边形的BL定位策略实现矩形件的布局;通过构造启发式算法生成排样初始种群,然后各个种群之间通过相互竞争实现优秀个体的迁移与共享,最终搜索到最优解。标准测试问题的实验结果验证了所提算法的可行性与有效性。

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