An efficient quasi-physical quasi-human algorithm for packing equal circles in a circular container
An efficient quasi-physical quasi-human algorithm for packing equal circles in a circular container
复制标题
一种高效的准物理准人类算法，用于在圆形容器中填充相等的圆
DOI：
10.1016/j.cor.2017.12.002
复制
发表时间：
2018
影响因子：
4.6
通讯作者：
Liu Jingfa
中科院分区：
文献类型：
--
作者：
He Kun;Ye Hui;Wang Zhengli;Liu Jingfa
提出了一种求解等圆装箱问题的高效拟物拟人（QPQH）算法。QPQH是基于我们修改的Broyden-Fletcher-Goldfarb-Shanno（BFGS）算法，我们称之为本地BFGS，和一个新的基于中国谚语的跳盆策略：交替紧张与放松。从一个随机的初始布局开始，我们应用局部BFGS算法来达到局部最小布局。局部BFGS算法充分利用了每个圆的邻域信息，大大加快了梯度下降过程的计算速度，这种效率在大规模实例中非常明显。当产生局部最小布局时，新的盆跳跃策略被用来在不同程度上收缩容器大小，以产生多个新的布局。实验结果表明，新的跳盆策略非常有效，特别是对于容器中心填充相对密集、边缘填充相对稀疏的布局类型。我们测试了QPQH的情况下，其中n= 1，2，100，320，并获得了66个新的布局具有较小的容器大小比目前最知名的结果在文献中报道。
We propose an efficient quasi-physical quasi-human (QPQH) algorithm for the equal circle packing problem. QPQH is based on our modified Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm, which we call the local BFGS, and a new basin-hopping strategy based on a Chinese proverb: 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 computation of the gradient descent process; this efficiency is very apparent for large-scale instances. When yielding a local minimum layout, the new basin-hopping strategy is used to shrink container sizes to different extents, to generate several new layouts. Experimental results indicate that the new basin-hopping strategy is very efficient, especially for layout types with comparatively dense packing in the center and comparatively sparse packing around the boundary of the container. We tested QPQH on instances in which n= 1, 2,⋯, 320, and obtained 66 new layouts having smaller container sizes than the current best-known results reported in the literature.