求解不等圆Packing问题的带全局变换禁忌搜索算法  

Tabu search algorithm combined with global perturbation for packing arbitrary sized circles into a circular container

作　　者：黄文奇[1] 付樟华[1] 许如初[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《中国科学：信息科学》2012年第7期843-858,共16页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:60773194;61070235)资助项目

摘　　要：圆形Packing问题考察如何将N个半径任意给定的圆形物体互不嵌入地置入一个半径尽可能小的圆形容器内.圆形Packing问题是个经典的NP难度问题,具有重要的理论价值和广泛的应用背景.本文将拟物算法与禁忌搜索相结合,辅以跳离局部陷阱的全局变换策略,得到求解二维不等圆Packing问题的带全局变换禁忌搜索算法GP-TS.拟物算法用于连续优化,可从任一初始格局收敛至局部最优格局;禁忌搜索在禁忌规则和特赦准则的约束下不断地将当前格局替换为其邻域中的最优格局;若禁忌搜索所得格局不满足约束条件,则执行全局变换策略,在不完全破坏当前格局结构的前提下跳离局部陷阱,然后进行新一轮的禁忌搜索,直至满足终止条件为止.数字实验结果表明,GP-TS能在可接受的计算时间内改进多个国际公开算例的已知最优解.The arbitrary sized circle packing problem （ACP） is concerned about how to pack a number of arbitrary sized circles into a smallest possible circular container without overlapping. As a classical NP-hard problem, ACP is theoretically important and is often encountered in practical applications. Based on the already existing Quasi-physical method, this paper proposes a hybrid algorithm named GP-TS which combines tabu search with global perturbation to solve the two-dimensional ACP. The Quasi-physical method is a continuous optimization method which is used to obtain a local optimal configuration from any initial configuration. The tabu search procedure iteratively updates the incumbent configuration with its best neighboring configuration according to some forbidden rule and aspiration criterion. If the configuration obtained by the tabu search procedure does not satisfy the constraints, the global perturbation operator is subsequently applied in order that the search jumps out of the current local optimum without destroying the incumbent configuration too much. After that, the tabu search procedure is launched again. GP-TS is performed by repeating this process until the stop criterion is met. Computational experiments based on 3 sets of representative instances show that GP-TS can improve many best known results within reasonable time.

关 键 词：NP难 装填问题 组合优化 启发式 禁忌搜索 全局变换 

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