A coarse-to-fine quasi-physical optimization method for solving the circle packing problem with equilibrium constraints
A coarse-to-fine quasi-physical optimization method for solving the circle packing problem with equilibrium constraints
复制标题
求解带平衡约束的圆堆积问题的从粗到细的准物理优化方法
DOI：
10.1016/j.cie.2013.08.010
复制
发表时间：
2013-12
期刊：
影响因子：
--
通讯作者：
Wenqi Huang
中科院分区：
文献类型：
--
作者：
Kun He;Danzeng Mo;Tao Ye;Wenqi Huang
本文研究了圆填充问题（CPP）的一个重要推广，即带平衡约束的圆填充问题（CPPEC）。它考虑非圆形圆盘在满足平衡约束的情况下在一个大圆形容器内的密集堆积。在卫星模块布局设计的工业背景下，这一NP-hard全局优化问题具有重要的理论和实践意义。本文介绍了求解CPPEC的两个新的准物理模型。一种是模拟由挤压圆盘的斥力驱动的弹性运动，另一种是模拟由连接圆盘质心和容器中心的想象弹性绳的拉力驱动的圆盘的整体平移运动。然后，受制造业中粗到精控制策略的启发，提出了一种粗到精准物理（CFQP）优化方法，该方法在准物理下降过程中采用这两种准物理模型，在搜索过程中结合跳盆法和禁忌法。这样，CFQP不仅可以考虑到搜索空间的多样性，便于全局搜索，而且可以在有前景的局部区域进行精细搜索，找到相应的局部最小值。实验在两组11个有代表性的测试实例上进行。计算结果表明，CFQP在4个实例上取得了新的更好的结果，同时在其他6个实例上与当前的最佳记录相匹配（精确到0.0001）。此外，CFQP比其他文献中发表的均衡偏差更小。此外，我们基于CPP基准生成了34个新的CPPEC实例，并给出了两组34个新CPPEC实例的计算结果，得到的容器半径与CPP上已发表的结果接近。
This paper addresses an important extension of the circle packing problem (CPP), the circle packing problem with equilibrium constraints (CPPEC). It considers the dense packing ofncircular disks in a large circular container at the same time satisfying the equilibrium constraints. Under the industrial background of the layout design on satellite modules, this NP-hard global optimization problem is important in both theory and practice. We introduce two new quasi-physical models for solving CPPEC in this paper. One is to mimic the elastic movement driven by repelling forces from extruded disks, the other is to simulate a whole translation movement of the disks driven by a pulling force from an imaginative elastic rope connecting the centroid of the disks and the center of the container. Then, inspired by the coarse-to-fine control strategy in the manufacture industry, we propose a coarse-to-fine quasi-physical (CFQP) optimization method that adopts the two quasi-physical models for the quasi-physical descent procedure and combines a basin hopping with tabu method for the search procedure. In this way, not only could CFQP take into account the diversity of the search space to facilitate the global search, but it also does fine search to find the corresponding local minimum in a promising local area. Experiments were on two sets of 11 representative test instances. Computational results showed that CFQP achieved new and better results on four instances, at the same time it matched the current best records on the other six (accurate to 0.0001). Moreover, CFQP resulted in smaller equilibrium deviations than that of others published in the literature. In addition, we generated 34 new CPPEC instances basing on the CPP benchmarks, and provided computational results on the two sets of 34 new CPPEC instances, and the container radii obtained are close to the published results on CPP.
登录
查看更多内容
DOI：
--
发表时间：
2001
期刊：
Chinese Journal of Computers
影响因子：
--
作者：
Qianying Zhi
通讯作者：
Qianying Zhi
DOI：
10.1360/crad20061008
发表时间：
2006-10
期刊：
Journal of Computer Research and Development
影响因子：
--
作者：
Lei Kaiyou and Qiu Yuhui
通讯作者：
Lei Kaiyou and Qiu Yuhui
影响因子：
1.7
作者：
T. Kubach;Andreas Bortfeldt;H. Gehring
通讯作者：
T. Kubach;Andreas Bortfeldt;H. Gehring
DOI：
10.1016/j.cie.2006.06.004
发表时间：
2006-07
期刊：
Comput. Ind. Eng.
影响因子：
--
作者：
Wenqi Huang;Mao Chen
通讯作者：
Wenqi Huang;Mao Chen
DOI：
--
发表时间：
2010-11
期刊：
--
影响因子：
--
作者：
H. Akeb;M. Hifi
通讯作者：
H. Akeb;M. Hifi