计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (22): 244-248.DOI: 10.3778/j.issn.1002-8331.2008.22.073

• 工程与应用 • 上一篇    

一种用于矩形排样优化的改进遗传算法

蒋兴波1,2,吕肖庆1,刘成城1   

  1. 1.北京大学 计算机科学技术研究所,北京 100871
    2.第二军医大学 卫生勤务学教研室,上海 200433
  • 收稿日期:2008-02-27 修回日期:2008-05-05 出版日期:2008-07-11 发布日期:2008-07-11
  • 通讯作者: 蒋兴波

Improved genetic algorithm for packing problem of rectangles

JIANG Xing-bo1,2,LV Xiao-qing1,LIU Cheng-cheng1   

  1. 1.Institute of Computer Science and Technology,Peking University,Beijing 100871,China
    2.Department of Health Services,Second Military Medical University,Shanghai 200433,China
  • Received:2008-02-27 Revised:2008-05-05 Online:2008-07-11 Published:2008-07-11
  • Contact: JIANG Xing-bo

摘要: 矩形排样优化属于NPC问题,在工业界有着广泛的应用,如布料切割、金属下料和新闻组版等。提出了一种基于环形交叉算子和环形变异算子的自适应遗传算法,并将改进的自适应遗传算法和IBL启发式布局算法相结合,有效地解决了矩形排样优化问题。对比实验结果表明,环形交叉算子和环形变异算子对遗传算法是有效的,所提出的改进混合自适应遗传算法能够在一个较短的时间内找到满意解。

关键词: 自适应遗传算法, 矩形排样优化, 启发式布局算法, 环形交叉算子, 环形变异算子

Abstract: The packing of rectangles is a NP-Complete problem and possesses widespread applications in the industry,such as the cutting of clothing,metal and composition of news.In this paper,circular-based crossover operator and circular-based mutation operator are adopted in the proposed adaptive genetic algorithm.With the combination of Improved Adaptive Genetic Algorithm(IAGA) and Improved Bottom-Left heuristic(IBL) algorithm,the packing of rectangles can be effectively solved.The comparison results show that genetic algorithm is more effective by using circular-based crossover operator and circular-based mutation operator and the satisfactory solution can be obtained in a reasonably short period of time by using hybrid IAGA.

Key words: Adaptive Genetic Algorithm(AGA), packing of rectangles, heuristic placement algorithm, circular-based crossover operator, circular-based mutation operator