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

作　　者：HUANG WenQi YE Tao 

机构地区：[1]School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China

出　　处：《Science China(Information Sciences)》2011年第7期1333-1339,共7页中国科学（信息科学）（英文版）

基　　金：supported by the National Natural Science Foundation of China (Grant No.60773194);the National Basic Research Program of China (Grant No.2004CB318000)

摘　　要：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.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.

关 键 词：equal circle packing global optimization quasi-physical method HEURISTIC 

分 类 号：TS272[农业科学—茶叶生产加工] TH122[轻工技术与工程—农产品加工及贮藏工程]