An action-space-based global optimization algorithm for packing circles into a square container
An action-space-based global optimization algorithm for packing circles into a square container
复制标题
基于动作空间的全局优化算法，用于将圆形包装到方形容器中
DOI：
10.1016/j.cor.2014.12.010
复制
发表时间：
2015
影响因子：
4.6
通讯作者：
Yang Chenkai
中科院分区：
文献类型：
--
作者：
He Kun;Huang Menglong;Yang Chenkai
提出了一种基于动作空间的全局优化方法（ASGO），用于求解将不等长的圆装入正方形容器中以使正方形尺寸最小化的问题。从几个随机配置开始，ASGO迭代地运行以下势下降方法和跳盆策略。该算法首先利用有限记忆BFGS（LBFGS）算法寻找势能最小的构形，然后选择变形最大的圆形物体，将其移动到较大的空位或随机选取的空位中。通过调整矩形包装问题定义的动作空间，我们近似每个圆形项目作为一个矩形项目，从而使它更容易找到相对较大的空置空间，为任何给定的配置。在搜索过程中，采用禁忌策略防止循环，提高了搜索的多样性。其他几种策略，例如交换两个相似的圆或交换容器中不同象限中的两个圆，可以组合起来增加配置的多样性。我们在Packomania网站上比较了ASGO在68个基准实例上的性能，并与最先进的结果进行了比较。ASGO在63个实例上获得了具有较小方形容器的配置;同时它在其他5个实例上匹配或接近当前最佳结果。
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.