(19)中华 人民共和国 国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202111213455.8 (22)申请日 2021.10.19 (65)同一申请的已公布的文献号 申请公布号 CN 113642264 A (43)申请公布日 2021.11.12 (73)专利权人 深圳须弥云图空间科技有限公司 地址 518054 广东省深圳市南 山区粤海街 道海珠社区滨海 大道3369号有线信息 传输大厦25F25 04 (72)发明人 不公告发明人 　 (74)专利代理 机构 北京嘉科知识产权代理事务 所(特殊普通 合伙) 11687 代理人 陈俊宏 (51)Int.Cl. G06F 30/27(2020.01)G06N 3/12(2006.01) (56)对比文件 孙佳正等.改进的双种群 遗传算法在矩形件 排样中的应用. 《计算机 工程与应用》 .2017,第 第 54卷卷(第15期),第139-146页. 宋雪枫等.基 于遗传算法的矩形件排样问题 求解. 《煤矿机 械》 .2011,第第32卷卷(第05期), 第119-121页. 审查员 范广坡 (54)发明名称 基于遗传算法的排样方法及装置 (57)摘要 本公开涉及计算机技术领域， 提供了一种基 于遗传算法的排样方法及装置。 该方法包括： 基 于标准件信息和排样件信息， 确定基因编码方 式； 基于基因编码方式， 生成初始种群， 初始种群 包括多个基因编码， 基因编码包括标准段编码和 排样段编码， 对应标准件和排样件的排样方案； 获取每个基因编码的适应度； 基于适应度， 确定 优势基因编码； 对优势基因编码进行双点位交叉 操作和双点位变异操作， 生成下一代基因编码， 以构成优势种群； 若满足预设终止条件， 则确定 优势种群中优势基因编码对应的排样方案为目 标排样方案。 本公开提高了种群迭代速率， 不仅 可以快速获得目标排样方案， 降低材料损耗， 而 且极大提高了 计算效率。 权利要求书4页 说明书15页 附图5页 CN 113642264 B 2022.02.15 CN 113642264 B 1.一种基于 遗传算法的排样方法， 其特 征在于， 包括： 基于标准件信息和排样件信息， 确定基因编码方式； 基于所述基因编码方式， 生成初始种群， 所述初始种群包括多个基因编码， 所述基因编 码包括标准段编码和排样段编码， 对应标准件和排样件的排样方案； 获取所述多个 基因编码中每 个基因编码的适应度； 基于所述适应度， 确定符合预设要求的适应度对应的基因编码为优势基因编码； 具体 的： 根据每个基因编 码的适应度对所述初始种群的基因编 码进行排序， 获得基因编码序列； 将所述基因编码序列中适应度最高的基因编码确定为优势基因编码； 或者， 将所述基因编 码序列中适应度高于预设阈值的基因编码确定为优势基因编码； 对所述优势基因编码进行双点位交叉操作和双点位变异操作， 生成下一代基因编码， 以构成优势种群； 若满足预设终止条件， 则确定所述优势种群中的优势基因编码对应的排样方案为目标 排样方案； 所述基于标准件信息和排样件信息， 确定基因编码方式， 包括： 基于标准件信息， 确定标准段编码的编码方式， 其中所述标准件信息至少包括标准件 类别和标准件尺寸， 所述标准段编码包括编码位数以及编码顺序； 基于排样件信息， 确定排样段编码的编码方式， 其中所述排样件信息至少包括排样件 类别和排样件尺寸， 所述 排样段编码包括编码位数以及编码顺序； 基于所述标准段编码的编码方式和所述 排样段编码的编码方式， 确定基因编码方式； 所述标准件信息还包括标准件的优先级， 则所述基于标准件信息， 确定标准段编码的 编码方式， 包括： 基于所述标准件类别， 确定所述标准段编码的编码位数； 对于具有优先级的标准件， 按照各所述标准件的优先级， 依次确定所述标准段编码中 对应位置的编码， 且在后续过程中保持不发生改变； 对于不具有优先级的标准件， 随机确定所述标准段编码中对应位置的编码； 所述对所述优势基因编码进行双点位交叉操作和双点位变异操作， 生成下一代基因编 码， 以构建优势种群， 包括： 将一个优势基因编码中标准段编码的至少两个位置与另一个优势基因编码中标准段 编码的对应位置确定为标准段 交叉位置， 同时将一个优势基因编 码中排样段编 码的至少两 个位置与另一个优势基因编 码中排样段编 码的对应位置的编码确定为排样段 交叉位置； 其 中， 当所述标准段编码没有指定优先级时， 所述标准段交叉位置在所述标准段编码中随机 选择， 当所述标准段编码指 定优先级时， 则具有优 先级的编码位置不进 行交叉操作， 所述标 准段交叉位置在所述标准段编码的其 他位置中随机 选择； 将至少两个优势基因编码的标准段交叉位置的编码进行调换， 同时将至少两个优势基 因编码的排样段交叉位置的编码进行调换， 获得交叉基因编码； 将所述交叉基因编码中标准段编码的至少两个位置确定为标准段变异位置， 同时将所 述交叉基因编码 中排样段编码的至少 两个位置确定为排样段变异位置； 其中， 当所述标准 段编码没有指定优先级时， 所述标准段变异位置在所述标准段编码 中随机选择， 当所述标 准段编码指定优先级时， 则具有优先级的编码位置不进行变异操作， 所述标准段变异位置权　利　要　求　书 1/4 页 2 CN 113642264 B 2在所述标准段编码的其 他位置中随机 选择； 将所述交叉基因编码的标准段变异位置的编码进行调换， 同时将所述交叉基因编码的 排样段变异位置的编码进行调换， 获得 下一代基因编码； 根据所述优势基因编码和所述下一代基因编码， 构建优势种群。 2.根据权利要求1所述的方法， 其特征在于， 所述获取每个所述基因编码的适应度， 包 括： 基于每个基因编码的排样段编码的编码顺序， 依次将所述排样段编码中每位编码对应 的排样件确定为当前排样件； 基于所述标准段编码的编码顺序， 依次将所述标准段编码中每位编码对应的标准件确 定为当前 标准件； 基于所述标准件信 息和排样件信 息， 确定所述当前排样件在所述当前标准件是否满足 排样要求； 若所述当前排样件在所述当前标准件上满足排样要求， 则确 认所述当前排样件的排样 位置为所述当前标准件， 并返回所述基于排样段编码的编码顺序， 依 次将所述排样段编码 中每位编码对应的排样件确定为当前排样件步骤； 若所述当前排样件在所述当前标准件上不满足排样要求， 则返回所述基于所述标准段 编码的编码顺序， 依次将所述标准段编码中每位编码对应的标准件确定为当前标准件步 骤； 遍历所述排样段编码中所有编码对应的排样件后， 基于所述标准件的总尺寸以及所述 标准件上排布的排样件的总尺寸， 确定每 个基因编码的适应度。 3.根据权利要求2所述的方法， 其特征在于， 所述标准件信 息包括标准件的类别和标准 件的尺寸， 所述 排样件信息包括 排样件的类别和排样件的尺寸； 所述基于所述标准件信 息和排样件信 息， 确定所述当前排样件在所述当前标准件是否 满足排样要求， 包括： 基于所述当前标准件的尺寸及其排布的排样件的尺寸， 确定所述当前标准件的剩余尺 寸； 基于所述当前排样件的尺寸和所述当前标准件的剩余尺寸， 确定所述当前排样件是否 可以排布于所述当前 标准件上。 4.根据权利要求2所述的方法， 其特征在于， 所述标准件信息包括标准件的类别、 标准 件的尺寸、 标准件的属性信息， 所述排样件信息包括排样件的类别、 排样件的尺寸、 排样件 的属性信息， 所述属性信息包括 开槽方式、 颜色、 材质中的至少一种； 所述基于所述标准件信 息和排样件信 息， 确定所述当前排样件在所述当前标准件是否 满足排样要求， 包括： 确定所述当前排样件的属性信息与所述当前 标准件的属性信息是否一 致； 若所述当前排样件的属性信 息与所述当前标准件的属性信 息一致， 则基于所述当前标 准件的尺寸及其 排布的排样件的尺寸， 确定所述当前 标准件的剩余尺寸； 基于所述当前排样件的尺寸和所述当前标准件的剩余尺寸， 确定所述当前排样件是否 可以排布于所述当前 标准件上。 5.根据权利要求2所述的方法， 其特征在于， 所述基于所述标准件的总尺寸以及所述标权　利　要　求　书 2/4 页 3 CN 113642264 B 3