不等圆Packing问题的拟物型邻域搜索算法  

Neighborhood search algorithm associated with Quasi-physicalmethod for solving unequal circle Packing problem

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

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

出　　处：《华中科技大学学报（自然科学版）》2012年第4期1-4,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

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

摘　　要：将拟物方法与邻域搜索过程结合,得到求解不等圆Packing问题的拟物型邻域搜索算法(QP-NS).拟物方法用于连续优化,可从任一初始格局收敛至对应的局部最优格局;邻域搜索过程迭代地将当前格局替换为其邻域中的最优格局,直至无法继续改进当前格局为止.QP-NS可在不严重破坏当前格局的前提下稳定地改进当前格局,鲁棒性较强.基于14个国际公开算例的计算实验表明:QP-NS可在60s内改进10个算例的此前最优解,并与其余4个算例的此前最优解持平.A hybrid meta-heuristic algorithm called QP-NS was developed, which consisted of a Quasiphysical method and a neighborhood search procedure, to solve the two-dimensional unequal circle packing problem. The Quasi-physical method was used to obtain a local optimal configuration from an initial configuration. The neighborhood search procedure iteratively updated the incumbent configuration with its best neighboring configuration until the stop criterion was met. The proposed approach was very robust, because the high-quality solutions had much more opportunity to be accepted than low-quality ones. Experiments results show that QP-NS produces very competitive results with re- spect to the results reported by previous literature, in terms of both solution quality and runtime. For 14 representative instances taken from the literature, QP-NS succeeds in improving 10 best known results and matching all the left 4 best known results within 60 s.

关 键 词：NP难问题 拟物方法 组合优化 装填问题 启发式 邻域搜索 

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