This paper addresses the equal circle packing problem, and proposes an efficient Quasi-physical Quasi-human (QPQH) algorithm. QPQH is based on a modified Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm which we call the local BFGS and a new basin hopping strategy based on a Chinese idiom: alternate tension with relaxation. Starting from a random initial layout, we apply the local BFGS algorithm to reach a local minimum layout. The local BFGS algorithm fully utilizes the neighborhood information of each circle to considerably speed up the running time of the gradient descent process, and the efficiency is very apparent for large scale instances. When yielding a local minimum layout, the new basin-hopping strategy is to shrink the container size to different extent to generate several new layouts. Experimental results indicate that the new basin-hopping strategy is very efficient, especially for a type of layout with comparatively dense packing in the center and comparatively sparse packing around the boundary of the container. We test QPQH on the instances of n = 1,2,...,320, and obtain 66 new layouts which have smaller container sizes than the current best-known results reported in literature.
翻译:本文处理平等圆形包装问题, 并提出高效的 准物理 准人类 QPQH 算法 。 QPQH 以修改的 Broyden- Fletcher- Goldfarb- Shanno (BFGS) 算法为基础, 我们称之为本地 BFGS, 以及基于中国方格的新盆地购物策略: 以放松为根据的交替压力。 我们从随机初始布局开始, 应用本地 BFGS 算法达到本地最小布局 。 本地 BFGS 算法充分利用每个圆圈的周边信息, 以大大加快梯度下降过程的运行时间, 大型案例的效率非常明显 。 当生成本地最小布局时, 新的流域购物策略是将集装箱大小缩小到不同程度, 以生成若干新布局 。 实验结果表明, 新的流域购物策略非常高效, 特别是对于在集装箱中心布局中包装较密集的布局型布局, 和在集装箱边界上比较不为人所知的包装。 我们用n= 1, 1,..., 320 和获得新布局小的大小为66 新布局。