Multi-strategy Optimization Method for Unequal Circle Packing Problem
-
摘要: 基于拟物算法思想及性能分析,提出一种求解不等圆Packing问题的高性能启发式算法。该方法以定步长序列梯度下降拟物算法为基础,运用相对势能作为排样布局的约束函数以消除图形尺寸的影响,并采用变邻接系数的邻接矩阵加速方法提升运算效率。在优化策略中,首先提出了改进分支搜索方法,以延长分支长度来扩大搜索范围实现对优胜劣汰策略的拓展;在迭代后期通过领域算子进行多重模拟退火来提升个体多样性和避免局部最优。在不同形状容器算例以及国际公开算例集上的大量实验表明,该算法是一种高效、稳定的不等圆Packing算法
-
关键词:
- 不等圆Packing /
- 拟物算法 /
- 分支搜索 /
- 多重退火
Abstract: Based on the idea of quasi-physical algorithm and performance analysis, a high-performance heuristic algorithm for solving the unequal circle packing problem is proposed in this study. The new algorithm is based on a fixed-step sequence gradient descent quasi-physical algorithm, and it uses relative potential energy as the constraint function of the layout to eliminate the influence of graph size, and also uses the adjacency matrix acceleration method with variable adjacency coefficient to improve the computational efficiency. In the optimization strategy, an improved branch search method is proposed to extend the branch length to expand the search range and realize the expansion of the survival of the fittest strategy. In the later stage of the iteration, multiple simulated annealing calculations are performed through the domain operator to increase the diversity of solutions and avoid local optimum. A large number of experiments on containers with different shapes and international open examples show that the new algorithm is more efficient and stable for unequal circle packing problem.-
Key words:
- unequal circle packing /
- quasi-physical algorithm /
- branch search /
- multiple annealing
-
表 1 圆形容器中26个国际公开算例的实验结果
算例 ${\phi _{\rm{pre}} }$/% ${\phi _{\rm{MABS}} }$/% $ \Delta \phi $/% 运算时间/s N=5 73.3719 73.3719 0.0000 50.31 N=6 73.3424 73.3424 0.0000 62.24 N=7 76.5132 76.5132 0.0000 79.23 N=8 78.4473 78.4473 0.0000 181.21 N=9 78.7560 78.7560 0.0000 268.50 N=10 79.7707 79.7707 0.0000 348.60 N=11 80.1910 80.1910 0.0000 408.01 N=12 80.1442 80.1442 0.0000 511.68 N=13 81.1684 81.1684 0.0000 590.69 N=14 81.2928 81.2928 0.0000 928.87 N=15 82.2942 82.4116 0.1174 769.39 N=16 82.7579 82.7579 0.0000 927.46 N=17 82.9385 83.0924 0.1539 890.82 N=18 83.3314 83.3684 0.0370 1248.22 N=19 84.0479 83.4731 −0.5748 1653.19 N=20 84.0958 84.0676 −0.0282 1826.36 N=21 84.2419 84.2419 0.0000 1864.35 N=22 84.5924 84.2389 −0.3535 3223.44 N=23 84.7140 84.6198 −0.0942 3052.60 N=24 84.8913 84.8040 −0.0873 3429.64 N=25 85.0276 84.9176 −0.1100 4743.36 N=26 85.2573 84.9360 −0.3213 4899.38 N=27 85.2109 85.3116 0.1007 4418.35 N=28 85.4531 84.8472 −0.6059 5463.88 N=29 85.5653 84.2778 −0.2875 6188.92 N=30 85.9573 85.3326 −0.6247 6433.62 -
[1] ELIAS N T, HUDSON T S. Structural search for dense packing of concave and convex shapes in two dimensions[J]. Journal of Physics: Conference Series, 2012, 402: 012005 doi: 10.1088/1742-6596/402/1/012005 [2] ROMANOVA T, BENNELL J, STOYAN Y, et al. Packing of concave polyhedra with continuous rotations using nonlinear optimisation[J]. European Journal of Operational Research, 2018, 268(1): 37-53 doi: 10.1016/j.ejor.2018.01.025 [3] BAI S, CHE X J, BAI X, et al. Maximal independent sets in heterogeneous wireless Ad Hoc networks[J]. IEEE Transactions on Mobile Computing, 2016, 15(8): 2023-2033 doi: 10.1109/TMC.2015.2508805 [4] CASTILLO I, KAMPAS F J, PINTÉR J D. Solving circle packing problems by global optimization: numerical results and industrial applications[J]. European Journal of Operational Research, 2008, 191(3): 786-802 doi: 10.1016/j.ejor.2007.01.054 [5] SATO A K, MARTINS T C, GOMES A M, et al. Raster penetration map applied to the irregular packing problem[J]. European Journal of Operational Research, 2019, 279(2): 657-671 doi: 10.1016/j.ejor.2019.06.008 [6] 张航, 王子健, 李安娜, 等. 基于启发式算法对木板切割方案的优化模型设计[J]. 齐齐哈尔大学学报(自然科学版), 2020, 36(1): 23-29 doi: 10.3969/j.issn.1007-984X.2020.01.006ZHANG H, WANG Z J, LI A N, et al. Optimization design of optimal plate cutting scheme based on genetic algorithm[J]. Journal of Qiqihar University (Natural Science Edition), 2020, 36(1): 23-29 (in Chinese) doi: 10.3969/j.issn.1007-984X.2020.01.006 [7] 黄文奇, 付樟华, 许如初. 求解不等圆Packing问题的带全局变换禁忌搜索算法[J]. 中国科学:信息科学, 2013, 56(9): 1-14HUANG W Q, FU Z H, XU R C. Tabu search algorithm combined with global perturbation for packing arbitrary sized circles into a circular container[J]. Science China Information Sciences, 2013, 56(9): 1-14 (in Chinese) [8] HIFI M, PASCHOS V T, ZISSIMOPOULOS V. A simulated annealing approach for the circular cutting problem[J]. European Journal of Operational Research, 2004, 159(2): 430-448 doi: 10.1016/S0377-2217(03)00417-X [9] BIRGIN E G, SOBRAL F N C. Minimizing the object dimensions in circle and sphere packing problems[J]. Computers & Operations Research, 2008, 35(7): 2357-2375 [10] 王英聪, 张领. 面向不等圆Packing问题的群智能劳动分工方法[J]. 浙江大学学报(工学版), 2019, 53(11): 2129-2138WANG Y C, ZHANG L. Swarm intelligence labor division algorithm for solving unequal circle packing problem[J]. Journal of Zhejiang University (Engineering Science), 2019, 53(11): 2129-2138 (in Chinese) [11] 王英聪, 张领, 肖人彬. 一种求解等圆Packing问题的柔性位置选择算法[J]. 中国机械工程, 2021, 32(3): 305-313 doi: 10.3969/j.issn.1004-132X.2021.03.008WANG Y C, ZHANG L, XIAO R B. A flexible position selection algorithm for solving ECPP[J]. China Mechanical Engineering, 2021, 32(3): 305-313 (in Chinese) doi: 10.3969/j.issn.1004-132X.2021.03.008 [12] SPECHT E. A precise algorithm to detect voids in polydisperse circle packings[J]. Proceedings of the Royal Society A:Mathematical, Physical and Engineering Sciences, 2015, 471(2182): 20150421 doi: 10.1098/rspa.2015.0421 [13] 余丽娟, 曹娟, 陈中贵. 改进区域划分的圆Packing变分算法[J]. 计算机辅助设计与图形学学报, 2018, 30(7): 1251-1257YU L J, CAO J, CHEN Z G. Improved domain partitions for variational circle packing[J]. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(7): 1251-1257 (in Chinese) [14] 刘景发, 张国建, 刘文杰, 等. 正三角形容器内等圆Packing问题的启发式算法[J]. 计算机辅助设计与图形学学报, 2012, 24(6): 808-815 doi: 10.3969/j.issn.1003-9775.2012.06.015LIU J F, ZHANG G J, LIU W J, et al. Heuristic algorithm for the equal circles packing problem in equilateral triangle container[J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(6): 808-815 (in Chinese) doi: 10.3969/j.issn.1003-9775.2012.06.015 [15] 张维, 杨康宁, 张民. 一种求解不等圆Packing问题的改进遗传模拟退火算法[J]. 西北工业大学学报, 2017, 35(6): 1033-1039 doi: 10.3969/j.issn.1000-2758.2017.06.015ZHANG W, YANG K N, ZHANG M. An improved genetic simulated annealing algorithm to solve the unequal circle packing problem[J]. Journal of Northwestern Polytechnical University, 2017, 35(6): 1033-1039 (in Chinese) doi: 10.3969/j.issn.1000-2758.2017.06.015 [16] 何琨, 杨辰凯, 黄梦龙, 等. 动作空间带平衡约束圆形Packing问题的拟物求解算法[J]. 软件学报, 2016, 27(9): 2218-2229HE K, YANG C K, HUANG M L, et al. Quasi-physical algorithm based on action space for solving the circles packing problem with equilibrium constraints[J]. Journal of Software, 2016, 27(9): 2218-2229 (in Chinese) [17] 黄文奇, 叶涛. 求解等圆Packing问题的完全拟物算法[J]. 系统科学与数学, 2008, 28(8): 993-1001HUANG W Q, YE T. Quasi-physical algorithm for the equal circles Packing problem[J]. Journal of Systems Science and Mathematical Sciences, 2008, 28(8): 993-1001 (in Chinese) [18] 付樟华. 二维不等圆Packing问题的现实求解途径[D]. 武汉: 华中科技大学, 2011FU Z H. Feasible approaches for solving the arbitrary sized circle packing problem[D]. Wuhan: Huazhong University of Science and Technology, 2011 (in Chinese)