An action-space-based global optimization algorithm for packing circles into a square container

摘要

This paper proposes an action-space-based global optimization (ASGO) approach for the problem of packing unequal circles into a square container such that the size of the square is minimized. Starting from several random configurations, ASGO runs the following potential descent method and basin-hopping strategy iteratively. It finds configurations with the local minimum potential energy by the limited-memory BFGS (LBFGS) algorithm, then selects the circular items having the most deformations and moves them to some large vacant space or randomly chosen vacant space. By adapting the action space defined for the rectangular packing problem, we approximate each circular item as a rectangular item, thus making it much easier to find comparatively larger vacant spaces for any given configuration. The tabu strategy is used to prevent cycling and enhance the diversification during the search procedure. Several other strategies, such as swapping two similar circles or swapping two circles in different quadrants in the container, are combined to increase the diversity of the configurations. We compare the performance of ASGO on 68 benchmark instances at the Packomania website with the state-of-the-art results. ASGO obtains configurations with smaller square containers on 63 instances; at the same time it matches or approaches the current best results on the other five instances.