(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202110280341.9 (22)申请日 2021.03.16 (65)同一申请的已公布的文献号 申请公布号 CN 113032921 A (43)申请公布日 2021.06.25 (73)专利权人 山东科技大 学 地址 266590 山东省青岛市黄岛区前湾港 路579号 (72)发明人 郑为民　司明超　 (74)专利代理 机构 青岛润集专利代理事务所 (普通合伙) 37327 专利代理师 张云花 (51)Int.Cl. G06F 30/17(2020.01) G06F 30/27(2020.01)G06Q 10/04(2012.01) G06Q 50/04(2012.01) G06N 3/00(2006.01) G06F 111/08(2020.01) (56)对比文件 CN 1071695 57 A,2017.09.15 CN 105956663 A,2016.09.21 CN 110688219 A,2020.01.14 CN 10980 0849 A,2019.0 5.24 CN 110390360 A,2019.10.2 9 张子成.基 于模拟退火的布谷鸟算法在组合 优化问题中的应用. 《中国优秀博硕士学位 论文 全文数据库(硕士)信息科技 辑》 .2018, 单宇晗.基 于自适应 遗传算法的矩形排样方 法研究. 《计算机与数字 工程》 .2020,(第10期), 审查员 冯冲 (54)发明名称 基于并行自适应参数布谷鸟搜索与最低水 平线的排样算法 (57)摘要 本发明公开了基于并行自适应参数布谷鸟 搜索与最低水平线的排样算法， 涉及工业矩形排 样领域。 基于并行自适应参数布谷鸟搜索与最低 水平线的排样算法使用改进的布谷鸟搜索算法 将每一种随机生成的矩形排样顺序和状态看作 一个解， 通过算法中适应度函数计算出每个解的 优劣程度， 保留每个种群最优解 即每个种群的历 史最优方案， 最后得出最优排样方案及排样结果 图。 算法利用种群并行及参数自适应策略改进布 谷鸟搜索算法， 通过不断迭代从而寻找最佳矩形 排样顺序和状态。 在寻找最优值过程中， 通过改 进的最低水平线算法依据规则排布各个矩形， 并 保存当前最优解。 权利要求书1页 说明书7页 附图2页 CN 113032921 B 2022.12.13 CN 113032921 B 1.基于并行自适应参数布谷鸟搜索与最低水平线的排样算法， 其特征在于， 使用改进 的布谷鸟搜索算法将 每一种随机生成的矩形排样顺序和状态看作一个解， 通过算法中适应 度函数计算出每个解的优劣程度， 保留每个种群最优解即每个种群的历史最优方案， 最后 得出最优排样方案及排样结果图； 改进的布谷鸟搜索算法具体为： 解集的更新通过L évy飞行结合参数调整方向及步长实 现， 种群解集的每次更新都会通过适应度函数判断当前种群及个体的最优解是否需要更 新， 每次通过L évy飞行更新后的种群个体有一定概率Pa会被代替， 通过偏好随机游走生成 新的解， 生成的新的解再次通过适应度函数筛查； 基于布谷鸟搜索算法的并行自适应参数布谷鸟搜索PACS过程为： 种群间采用相邻子种 群最优个体影响其他种群较差个体， 随机生成0到1的影响权重因子q， 由个体当前位置 与 相邻种群最优个 体位置 得出该个体下一代位置 即式(1)所示： 对比所有种群最优个体得到整体最优个体Gbest， 生成影响权重因子a及影响个体 数l， 在 每个子种群中得 出l个非该种群内最优个 体新位置 2.如权利要求1所述的基于并行自适应参数布谷鸟搜索与最低水平线的排样算法， 其 特征在于， 每个解包括两部分， 负责存储排样矩形顺序的数组和负责存储按排样顺序的每 个矩形的状态数组。权　利　要　求　书 1/1 页 2 CN 113032921 B 2基于并行自适应参数布谷鸟搜索与最低水 平线的排样算法 技术领域 [0001]本发明涉及工业矩形排样领域， 具体涉及 一种基于并行自适应参数布谷鸟搜索与 最低水平线的排样算法。 背景技术 [0002]在工业生产过程中， 在大型原材料基础上裁剪所需要的板材的步骤极为常见， 而 很大一部分原材料 由于裁剪方式的不科学， 导致一部分材料会被浪费， 从而相对加大了不 必要的成本， 降低了经济效益。 此时， 关于裁剪的策略应运而生——排样技术， 而排样技术 中， 矩形排样技术占据重要部分， 甚至很多不规则图形排样也可以将其近似为矩形进行排 样操作。 [0003]矩形排样问题是经典的NP难度问题， 具有高复杂性， 目前还没有公认的最优解法。 受前人研究成果启发， 结合人类的生活习惯得到整齐度的概念， 人们都希望剩余材料可以 再次被利用， 并且使用的材料相对较少。 剩余材料可以再次被利用这个概念， 要求剩余的材 料未被使用过， 即本次使用的材料最高水平线以下便是用去的所有材料。 使用材料相对较 少则是要求所有矩形被排放完之后最高水平线尽可能低。 目前的求解思路是采用启发式算 法找到最优解或近似最优解， 并希望近似最优解无限接近最优解。 排样问题的实际应用广 泛， 生活之中随处可见。 该问题的原材料和待排放的物体只是抽象概念， 原材料既可以是箱 形容器也可以是板材、 版面、 玻璃、 地面空间等等， 而待摆放的物品可以是板材上裁剪下 的 零件、 版面上的文章字体、 具体应用时的玻璃板块等， 因此， 排样问题较多的应用于工业的 材料(玻璃、 纸品)切割、 报纸的版面排布、 货物装箱、 结成电路的布局等领域， 甚至人们人常 生活中的物品整理、 日程安排也可以归为排样问题范畴。 在各式各样的排样问题中， 矩形件 排样问题在实际生产生活中占比最大， 所以矩形件排样问题也成为了排样问题的基础。 所 以矩形排样问题的解决对工业 生产和人们日常生活有一定改善作用。 [0004]原启发式算法的不断提出与发展， 使得人们在求最值等优化问题上有了重要解决 方式。 它们可以用于解决工业、 金融、 数学等领域相关问题。 布谷鸟搜索算法被提出后， 其使 用者进行多次改进以适应解决各个领域的相关问题， 并取得显著效果。 如修正布谷鸟搜索 算法(MCS)， 多目标布谷鸟搜索算法(MOCS)， 混沌布谷鸟搜索算法(CCS)， 二进制布谷鸟搜索 算法(BCS)等。 之前有过关于智能算法应用于排样问题的实例， 如遗传模拟退火算法应用于 矩形件排样问题研究， 改进离散萤火虫算法应用于二维排样问题优化研究， 遗传算法应用 于圆形件排样问题， 蚁群算法应用于钣金件排样问题。 尽管前些年有其他算法应用到排样 问题上， 但随着智能算法的发展创新， 多种新的策略被提出并证明在解决某些问题上有了 新的突破。 与其他启发式算法相比， CS算法的关键参数少于其他同类算法， 算法易于实现。 采用Lévy飞行搜索机制使该算法具有更好的全局搜索能力， 同时该算法相 对较新， 不过CS 算法在某些 方面还有很大的改进空间。 [0005]随着科技的不断发展， 众多学者提出了大量的方案去解决此类问题， 在计算机技 术的帮助下， 取得了一定的成效， 但效果依然无法达到最佳， 关于钣金方面的裁剪问题， 目说　明　书 1/7 页 3 CN 113032921 B 3