An efficient quasi-physical quasi-human algorithm for packing equal circles in a circular container
2018
Abstract We propose an efficient quasi-physical quasi-human (QPQH) algorithm for the equal
circle packingproblem. 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
layouttypes 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
layoutshaving smaller container sizes than the current best-known results reported in the literature.
Keywords:
-
Correction
-
Source
-
Cite
-
Save
42
References
4
Citations
NaN
KQI