网站建设要准备些什么,海南网站建设哪家专业,上犹网站建设,南充住房和城乡建设厅网站转自#xff1a;https://bbs.huaweicloud.com/blogs/196289【摘要】 二维不规则异形件主要有两种策略#xff1a;分别是基于可行解的排样策略和基于重叠移除的排样策略。所谓基于可行解的排样策略#xff0c;是指在排样过程中零件之间始终是不重叠的#xff0c;而基于重叠移… 转自https://bbs.huaweicloud.com/blogs/196289 【摘要】 二维不规则异形件主要有两种策略分别是基于可行解的排样策略和基于重叠移除的排样策略。所谓基于可行解的排样策略是指在排样过程中零件之间始终是不重叠的而基于重叠移除的排样策略是指在排样过程中允许零件之间发生重叠在搜索过程中采用一定策略减少零件重叠的程度直至最终得到可行解为止。 1 二维异形件排样算法 上一篇博客提到二维异形件排样算法涉及到高速几何算法、排样策略和优化算法并且系统综述了临界多边形NFP的求解算法感兴趣的童鞋可以查看博文https://bbs.huaweicloud.com/blogs/175385 2 二维异形件排样策略 二维不规则异形件主要有两种策略分别是基于可行解的排样策略和基于重叠移除的排样策略。所谓基于可行解的排样策略是指在排样过程中零件之间始终是不重叠的而基于重叠移除的排样策略是指在排样过程中允许零件之间发生重叠在搜索过程中采用一定策略减少零件重叠的程度直至最终得到可行解为止。下面分别详细介绍。 2.1 基于可行解策略 基于可行解的排样策略的好处是排样方案总是可行的。设计该类算法需要考虑两个主要因素零件的可行放置位置和零件摆放的评估方法。最经典的策略是“左底法”即将零件摆放在所有可行点中最靠左的位置若出现多个最左点则选择最底下的位置。 如何确定零件的可行放置位置呢上文我们知道NFP可以表征两个简单多边形“相切”的情况因此当固定一个简单多边形时第二个简单多边形可以选择其相对第一个简单多边形的NFP上的点作为可行放置点。当然这样的点有无穷多个因此一般只选择NFP的顶点也可能再加上线段中点作为可行放置点。 你可能会有这样的疑问当只有两个简单多边形时当然可以这样摆放但是如果已经摆放了若干个简单多边形再摆放下一个简单多边形时该如何保证其不与所有的多边形都不重叠呢这的确是一个非常好的问题也正是开发异形件切割排版算法遇到的第一个难题。解决方案主要有两个一是将已经排版的简单多边形合并成一个大多边形然后再进行排版如图1所示二是考虑所有NFP的顶点以及NFP每条线段的交点然后再判断这些点是否在某个NFP的内部如果该点不在任何一个NFP内部则该点为可行点否则不是可行点。第一个方案的问题是零件之间的空隙将无法再放其他的简单多边形造成原料浪费第二个方案的问题计算成本大。 图1. 基于可行解的排样选点策略图片来源参考文献[1] 零件排放位置该如何评估呢常见的方法如表1和图2所示 表1. 异形零件摆放位置评估方法 图2. 零件摆放位置评估常见方法图片来源参考文献[2] 上述基于可行解策略得到的排样方案效果一般不会太好还需要智能优化算法改善结果。常见的智能优化算法有遗传算法、模拟退火算法、价值修正、束搜索等方法下面详细介绍一下束搜索方法。 图3. 束搜索方法示意图图片来源参考文献[3 束搜索Beam Search是一种启发式图搜索方法在每一步深度扩展的时候剪掉一些质量比较差的节点留下一些质量较高的节点。这样就减少了空间消耗并提升了时间效率。具体而言如图3a所示束搜索使用广度优先策略创建搜索树在树的每一层按照局部启发式评价方法对节点进行排序留下预先指定个数filter width的节点而后再对这些节点进行全局启发式评价再次留下预先指定个数beam width节点。仅这些节点在下一层次继续扩展其余节点就被剪掉了。图3b展示了filter width3beam width2时的搜索过程。束搜索评价函数采用顺序搜索评价函数加和模式选择表1中Incentive列中的L1和R1Balanced列中的O2令评价函数等于L1R1-O2。 束搜索还需要考虑零件的排序常见的零件排序方法有如下几种1面积2长度3宽度4周长5凸包面积6包络矩形面积等等。一般采用零件面积进行排序。 2.2 基于重叠移除的排样策略 所谓重叠移除算法如图4示是指在初始可行解的基础上减少原料长度并通过交换、平移等邻域搜索技术改变当前的排版方案在改变时允许裁片之间发生重叠然后采用分离技术消除重叠得到改进可行解。上述过程不断交替进行直到达到算法终止条件为止。 图4. 重叠移除方法示意图图片来源参考文献[4] 首先使用启发式方法得到一个可行解假设原料长度为L。若得到了可行解则缩小原料长度若没有得到可行解则适当增加原料长度。之后扰动当前解实施上述优化程序。该过程迭代进行直到达到算法终止条件。最终选择原料长度最小的可行解作为算法的输出。 重叠移除排版算法的详细介绍将在后续博客中更新欢迎大家关注。 参考文献 [1] Oliveira J F, Gomes A M, Ferreira J S. TOPOS–A new constructive algorithm for nesting problems[J]. OR-Spektrum, 2000, 22(2): 263-284. [2] Bennell J A, Song X. A beam search implementation for the irregular shape packing problem[J]. Journal of Heuristics, 2010, 16(2): 167-188. [3] Bennell J A, Song X. A beam search implementation for the irregular shape packing problem[J]. Journal of Heuristics, 2010, 16(2): 167-188. [4] Elkeran A. A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering[J]. European Journal of Operational Research, 2013, 231(3): 757-769. 登录后可下载附件请登录或者注册 【版权声明】本文为华为云社区用户原创内容未经允许不得转载如需转载请发送邮件至huaweicloud.bbshuawei.com如果您发现本社区中有涉嫌抄袭的内容欢迎发送邮件进行举报并提供相关证据一经查实本社区将立刻删除涉嫌侵权内容。
