作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2007, Vol. 33 ›› Issue (09): 189-190,.

• 人工智能及识别技术 • 上一篇    下一篇

求解矩形装箱问题的一种近似算法

陈胜达,张德富,刘艳娟   

  1. (厦门大学计算机科学系,厦门 361005)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-05-05 发布日期:2007-05-05

An Evolutionary Approximation Algorithm for Strip Rectangular Packing Problem

CHEN Shengda, ZHANG Defu, LIU Yanjuan   

  1. (Department of Computer Science, Xiamen University, Xiamen 361005)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-05-05 Published:2007-05-05

摘要: 提出了利用近似算法求解二维矩形装箱问题的最小高度的一种方法。该方法基于启发式递归策略和遗传算法。利用启发式递归策略把所有大小各异的矩形都装入宽度固定的矩形容器中,并计算装完后所需容器的高度,用遗传算法的进化能力优化高度,使得所需容器的高度尽可能小。计算数据证明这种方法能够得到很好的结果,特别是对数据量大的测试问题,效果更好。

关键词: 装箱问题, 启发式, 递归, 遗传算法

Abstract: An evolutionary approximation algorithm to find a minimum height for two-dimensional strip rectangular packing problem is presented. This method is mainly based on heuristic strategies and genetic algorithm. The heuristic strategies are used to calculate the height of the packing order, and then the evolutionary capability of genetic algorithm to reduce the height is used. The computational results on well-known benchmark problems show that the presented approximation algorithm can compete with other algorithms based on genetic algorithm. Especially for large test problems, it performs better.

Key words: Packing problems, Heuristic, Recursive, Genetic algorithm

中图分类号: