留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

不等圆Packing问题的多策略优化方法

梁利东 何东 朱良恒

梁利东,何东,朱良恒. 不等圆Packing问题的多策略优化方法[J]. 机械科学与技术,2022,41(9):1394-1402 doi: 10.13433/j.cnki.1003-8728.20220143
引用本文: 梁利东,何东,朱良恒. 不等圆Packing问题的多策略优化方法[J]. 机械科学与技术,2022,41(9):1394-1402 doi: 10.13433/j.cnki.1003-8728.20220143
LIANG Lidong, HE Dong, ZHU Liangheng. Multi-strategy Optimization Method for Unequal Circle Packing Problem[J]. Mechanical Science and Technology for Aerospace Engineering, 2022, 41(9): 1394-1402. doi: 10.13433/j.cnki.1003-8728.20220143
Citation: LIANG Lidong, HE Dong, ZHU Liangheng. Multi-strategy Optimization Method for Unequal Circle Packing Problem[J]. Mechanical Science and Technology for Aerospace Engineering, 2022, 41(9): 1394-1402. doi: 10.13433/j.cnki.1003-8728.20220143

不等圆Packing问题的多策略优化方法

doi: 10.13433/j.cnki.1003-8728.20220143
基金项目: 安徽省高校自然科学研究重点项目(KJ2018A0102,KJ2019A0147)
详细信息
    作者简介:

    梁利东(1972−),副教授,博士,研究方向为计算机辅助设计制造及信息工程,mark_liang2003@126.com

  • 中图分类号: TP391

Multi-strategy Optimization Method for Unequal Circle Packing Problem

  • 摘要: 基于拟物算法思想及性能分析,提出一种求解不等圆Packing问题的高性能启发式算法。该方法以定步长序列梯度下降拟物算法为基础,运用相对势能作为排样布局的约束函数以消除图形尺寸的影响,并采用变邻接系数的邻接矩阵加速方法提升运算效率。在优化策略中,首先提出了改进分支搜索方法,以延长分支长度来扩大搜索范围实现对优胜劣汰策略的拓展;在迭代后期通过领域算子进行多重模拟退火来提升个体多样性和避免局部最优。在不同形状容器算例以及国际公开算例集上的大量实验表明,该算法是一种高效、稳定的不等圆Packing算法
  • 图  1  拟物算法的几何图像表示

    图  2  本文算法的总体结构

    图  3  相对势能与绝对势能对比

    图  4  使用邻接矩阵前后对比

    图  5  3种算法的性能比较

    图  6  实际运算场景下两种拟物算法势能收敛性对比

    图  7  利用交换算子与抛掷算子生成新邻域的过程

    图  8  变长分支搜索策略流程图

    图  9  不同长度分支搜索性能对比

    图  10  模拟退火算法流程图

    图  11  不同初始温度下模拟退火算法的求解质量对比

    图  12  多重退火势能温度变化曲线

    图  13  MABS算法在不同形状容器中的最优布局

    图  14  不规则图形及其最小包络圆

    图  15  不规则图形Packing求解应用

    表  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
    下载: 导出CSV
  • [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.006

    ZHANG 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-14

    HUANG 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-2138

    WANG 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.008

    WANG 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-1257

    YU 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.015

    LIU 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.015

    ZHANG 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-2229

    HE 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-1001

    HUANG 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]. 武汉: 华中科技大学, 2011

    FU Z H. Feasible approaches for solving the arbitrary sized circle packing problem[D]. Wuhan: Huazhong University of Science and Technology, 2011 (in Chinese)
  • 加载中
图(15) / 表(1)
计量
  • 文章访问数:  93
  • HTML全文浏览量:  109
  • PDF下载量:  19
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-10-26
  • 刊出日期:  2022-09-05

目录

    /

    返回文章
    返回