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

Adaptive Hybrid Algorithm for Solving 2D Circle Packing Problem

作　　者：赵政宝[1] 楚纪正[1] 尚颖[1] 

机构地区：[1]北京化工大学信息科学与技术学院,北京100029

出　　处：《计算机工程》2012年第8期260-263,267,共5页Computer Engineering

基　　金：国家"863"计划基金资助项目(2007AA04Z191)

摘　　要：针对二维圆形版面不等圆排样问题,在最小局部距离定位布局策略的基础上,引入紧凑度和适应度,提出基于拟矩形排样的自适应启发式算法,并与以自然数编码的遗传算法相结合构建混合算法。该混合算法发挥两者的全局搜索能力与局部寻优能力。在标准测试算例上,与一些经典算法进行比较,结果表明,该算法能够在更短的时间内获得更为满意的结果。An efficient adptive algorithm is proposed as heuristic algorithm based on quasi-rectangle packing and the Minimun Local Distance Position（MLDP） stratcgy, through the introduction of compactness and fitness. Combining heuristic algorithm with genetic algorithm based on natural number coding, a ilybrid 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.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]