求解等圆Packing问题的拟物型全局优化算法  

Quasi-physical global optimization method for solving the equal circle packing problem

作　　者：黄文奇[1] 叶涛[1] 

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

出　　处：《中国科学：信息科学》2011年第6期686-693,共8页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:60773194);国家重点基础研究发展计划(批准号:2004CB318000)资助项目

摘　　要：等圆Packing问题是一个著名的几何难题,也是全局优化领域的一个天然明白客观公正的算法试金石.文中为等圆Packing问题提出了一个拟物型的全局优化算法.在算法中,N个圆饼在弹性挤压力的作用下平缓地运动,到达某个局部最优格局;适当的时期,又在高强度的引力和斥力的作用下剧烈地运动,跳出局部最优格局的陷阱,到达前景可能更好的地方.使用N(N=1,2,...,150)等圆最紧布局的国际记录对算法进行了测试.对这150个算例中的37个算例,此算法找到了比之前此国际最优记录更优的布局方案;对于剩下的113个算例,都找到了优度与当前国际记录持平的布局方案.The equal circle packing problem is a well-known challenge in geometry. It is also a natural, clear and fair test system for global optimization. This paper presents a quasi-physical global optimization algorithm for solving the equal circle packing problem. The algorithm simulates two kinds of movements of N elastic disks： smooth movement driven by elastic pressures and violent movement driven by strong repulsive forces and attractive forces. The smooth movement makes the disks reach a locally optimal configuration, while the violent movement makes them jump out of the local optimum trap and reach a more promising place. The algorithm is tested on the widely studied instances of N = 1,2,...,150. We find better packings than the reported best-known ones on 37 instances and reproduce the best-known results on the remaining 113 instances.

关 键 词：等圆PACKING问题 全局优化 拟物方法 启发式算法 

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