This paper addresses the equal circle packing problem, and proposes an efficient Quasi-physical Quasi-human (QPQH) algorithm. QPQH is based on a modified Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm which we call the local BFGS and a new basin hopping strategy based on a Chinese idiom: alternate tension with relaxation. Starting from a random initial layout, we apply the local BFGS algorithm to reach a local minimum layout. The local BFGS algorithm fully utilizes the neighborhood information of each circle to considerably speed up the running time of the gradient descent process, and the efficiency is very apparent for large scale instances. When yielding a local minimum layout, the new basin-hopping strategy is to shrink the container size to different extent to generate several new layouts. Experimental results indicate that the new basin-hopping strategy is very efficient, especially for a type of layout with comparatively dense packing in the center and comparatively sparse packing around the boundary of the container. We test QPQH on the instances of n = 1,2,...,320, and obtain 66 new layouts which have smaller container sizes than the current best-known results reported in literature.


翻译:本文处理平等圆形包装问题, 并提出高效的 准物理 准人类 QPQH 算法 。 QPQH 以修改的 Broyden- Fletcher- Goldfarb- Shanno (BFGS) 算法为基础, 我们称之为本地 BFGS, 以及基于中国方格的新盆地购物策略: 以放松为根据的交替压力。 我们从随机初始布局开始, 应用本地 BFGS 算法达到本地最小布局 。 本地 BFGS 算法充分利用每个圆圈的周边信息, 以大大加快梯度下降过程的运行时间, 大型案例的效率非常明显 。 当生成本地最小布局时, 新的流域购物策略是将集装箱大小缩小到不同程度, 以生成若干新布局 。 实验结果表明, 新的流域购物策略非常高效, 特别是对于在集装箱中心布局中包装较密集的布局型布局, 和在集装箱边界上比较不为人所知的包装。 我们用n= 1, 1,..., 320 和获得新布局小的大小为66 新布局。

0
下载
关闭预览

相关内容

知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
专知会员服务
159+阅读 · 2020年1月16日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
算法|随机森林(Random Forest)
全球人工智能
3+阅读 · 2018年1月8日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
3+阅读 · 2018年10月11日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
算法|随机森林(Random Forest)
全球人工智能
3+阅读 · 2018年1月8日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员