Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6892682 | Computers & Operations Research | 2018 | 11 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Kun He, Hui Ye, Zhengli Wang, Jingfa Liu,