Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (22): 229-232.DOI: 10.3778/j.issn.1002-8331.1708-0033

Previous Articles     Next Articles

Packing of rectangles using adaptive genetic simulated annealing algorithm

XIA Yichong, CHEN Qiulian, SONG Renkun   

  1. School of Computer and Electronic Information, Guangxi University, Nanning 530004, China
  • Online:2018-11-15 Published:2018-11-13



  1. 广西大学 计算机与电子信息学院,南宁 530004

Abstract: An adaptive genetic simulated annealing algorithm applied to the problem of packing optimization of rectangles is studied in this paper. The packing sequence of rectangles is coded by integer. The initial population is constructed by the combination of empirical selection and stochastic generation. And the adaptive crossover probability and mutation probability are adopted to control the convergent speed of genetic algorithm dynamically. A simulated annealing algorithm is used to lead the search scope developed in the direction of global optimal. It uses the heuristic optimization strategy of lowest horizontal line algorithm as decoding method of packing sequence and forms the cutting patterns. Multiple sets of experimental results show that the adaptive genetic simulated annealing algorithm with high solving speed can effectively increase the utilization of sheet.

Key words: packing optimization, adaptive genetic algorithm, simulated annealing, optimization strategy of lowest horizontal line

摘要: 研究一种自适应遗传模拟退火算法,应用于矩形件优化排样问题。以整数编码矩形件的排样序列,采用经验选择与随机生成相结合的策略构造初始种群。运用自适应交叉和变异概率动态地控制遗传算法的收敛速度,通过模拟退火算法引导全局最优搜索,采用启发式最低水平线择优算法对排样序列进行解码,形成排样方式。多组对比实验结果表明,自适应遗传模拟退火算法求解速度较快,可以有效提高板材的利用率。

关键词: 排样优化, 自适应遗传算法, 模拟退火, 最低水平线择优