等圆Packing问题高效求解算法研究

发布时间：2021-05-15 12:59

　　作为一类经典的NP难度问题,考虑空间紧密布局的Packing问题一直在工业界和学术界有着很高的研究价值。根据容器和装载物体形状差异,Packing问题可以细分为很多类。深入研究了等圆Packing问题,即在二维圆形容器中装入给定数量的半径相等的二维圆形物体,要求容器中物体和物体、物体和容器边界均无重叠,目标是最小化圆形容器的半径。本文分别针对容器内小圆数目不超过320的小规模等圆Packing和小圆数目超过320的大规模等圆Packing问题,提出了两种有效的算法。对于待放圆的数量小于等于320的小规模问题,提出了一种高效的拟人拟物算法。将待放圆视为弹性小球,重叠时产生弹性势能,使用经典的拟牛顿法BFGS算法,通过局部优化策略加快计算速度;当整体势能达到局部最优的时候,设计了先缩小大圆半径再松弛的新的高效跳坑策略,使下一轮梯度下降达到一个更好的格局;如此反复迭代,直到找到一个全局最优解。实验结果表明,该算法在圆形物体的数量n为1到320的这320个典型算例中找到了66个比当前国际最优解更优的布局方案。对于待放圆的数量较高的大规模问题,对整个系统进行梯度下降的策略很难在合理时间内得到布图... 

【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：56 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 研究背景及意义
    1.2 国内外研究现状
    1.3 本文主要研究内容
    1.4 论文组织结构
2 问题描述
    2.1 数学模型
    2.2 物理模型
3 求解小规模等圆Packing问题的拟物拟人算法
    3.1 BFGS算法
    3.2 局部BFGS算法
    3.3 跳坑策略
    3.4 容器调整策略
    3.5 高效拟物拟人算法(QPQH)
    3.6 本章小结
4 基于机器学习求解大规模等圆Packing问题
    4.1 随机梯度下降法(Stochastic gradient descent,SGD)
    4.2 随机局部BFGS算法
    4.3 基于分组梯度下降的跳坑策略
    4.4 本章小结
5 实验结果与分析
    5.1 参数调整
    5.2 小规模等圆Packing实验结果
    5.3 大规模等圆Packing实验结果
    5.4 本章小结
6 总结与展望
    6.1 总结
    6.2 展望
致谢
参考文献
附录1:攻读硕士学位期间参与的科研项目
附录2:攻读硕士学位期间发表论文目录


【参考文献】：
期刊论文
[1]Packing unequal circles into a square container based on the narrow action spaces[J]. Kun HE,Mohammed DOSH,Yan JIN,Shenghao ZOU.  Science China（Information Sciences）. 2018(04)
[2]基于穴度的三维时空优化问题的贪心调度算法[J]. 朱鹏,何琨,曹伟刚,杨欢.  计算机科学与探索. 2016(08)
[3]四维时空高效利用的装箱调度问题及其可计算性证明[J]. 黄文奇,何琨.  计算机学报. 2013(09)
[4]三维装箱工作的优化调度问题[J]. 黄文奇,何琨.  华中科技大学学报(自然科学版). 2010(12)
[5]人机交互的遗传算法及其在约束布局优化中的应用[J]. 钱志勤,滕弘飞,孙治国.  计算机学报. 2001(05)



本文编号：3187680