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

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

将拟物方法与邻域搜索过程结合,得到求解不等圆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.