计算机工程 ›› 2012, Vol. 38 ›› Issue (08): 260-263.doi: 10.3969/j.issn.1000-3428.2012.08.083

• 开发研究与设计技术 • 上一篇    下一篇

用于求解二维圆形排样问题的自适应混合算法

赵政宝,楚纪正,尚 颖   

  1. (北京化工大学信息科学与技术学院,北京 100029)
  • 收稿日期:2011-08-31 出版日期:2012-04-20 发布日期:2012-04-20
  • 作者简介:赵政宝(1986-),男,硕士研究生,主研方向:智能算法,分布式计算;楚纪正,研究员、博士生导师;尚 颖,讲师、博士研究生
  • 基金项目:

    国家“863”计划基金资助项目(2007AA04Z191)

Adaptive Hybrid Algorithm for Solving 2D Circle Packing Problem

ZHAO Zheng-bao, CHU Ji-zheng, SHANG Ying   

  1. (School of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China)
  • Received:2011-08-31 Online:2012-04-20 Published:2012-04-20

摘要: 针对二维圆形版面不等圆排样问题,在最小局部距离定位布局策略的基础上,引入紧凑度和适应度,提出基于拟矩形排样的自适应启发式算法,并与以自然数编码的遗传算法相结合构建混合算法。该混合算法发挥两者的全局搜索能力与局部寻优能力。在标准测试算例上,与一些经典算法进行比较,结果表明,该算法能够在更短的时间内获得更为满意的结果。

关键词: 圆形排样问题, 拟矩形排样, 启发式算法, 二分搜索, 遗传算法, NP难问题

Abstract: An efficient adaptive algorithm is proposed as heuristic algorithm based on quasi-rectangle packing and the Minimun Local Distance Position(MLDP) strategy, through the introduction of compactness and fitness. Combining heuristic algorithm with genetic algorithm based on natural number coding, a hybrid algorithm for the 2D unequal circle packing problem is presented. The hybrid algorithm gives full play to the global search capability of genetic algorithm, and takes full advantage of local search capability of adaptive heuristic algorithm. Experimental results of standard test instances from literatures indicate that more satisfactory results can be achieved with the new approach than related classic algorithms in a relatively shorter time.

Key words: circle packing problem, quasi-rectangle packing, heuristic algorithm, binary search, genetic algorithm, NP hard problem

中图分类号: