(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202110582348.6 (22)申请日 2021.05.27 (65)同一申请的已公布的文献号 申请公布号 CN 113435094 A (43)申请公布日 2021.09.24 (73)专利权人 中国地质大 学 （武汉） 地址 430000 湖北省武汉市洪山区鲁磨路 388号 (72)发明人 龚鑫　刘小波　肖肖　张超超　 (51)Int.Cl. G06F 30/25(2020.01) G06F 30/27(2020.01) G06N 3/12(2006.01) G06F 111/06(2020.01) (56)对比文件 CN 111985012 A,2020.1 1.24 CN 110598893 A,2019.12.20 WO 03027961 A 2,2003.04.03 CN 103678800 A,2014.0 3.26 CN 109214557 A,2019.01.15CN 10415 0759 A,2014.1 1.19 US 2020004804 A1,2020.01.02 US 2018120817 A1,2018.0 5.03 JP 2008046496 A,20 08.02.28 刘胡瑶等.基 于重心NFP的二维不 规则形状 排样算法. 《中国机 械工程》 .20 07,(第06期),97- 100、 105. LI M等.Particle swarm optimizati on for rectangular partsoptimal layout. 《Proc congress on 3rd Internati onal Symposiumo n Instrumentati on Science and Tec hnology》 .2004,327-331. 吴哲等.切割路径优化问题的自适应大邻域 搜索退火算法. 《重庆理工大 学学报(自然科 学)》 .2020,(第09期),238-245、 252. Julia A B等.The Ir regular Cut ting- stock Problem-A New Procedure for Deriving the N o-fit Po lygon. 《Computer&Op- erations Researc h》 .2001,271-287. 审查员 王艳丽 (54)发明名称 一种基于遗传算法的二维不规则零件排样 方法 (57)摘要 本发明提供一种基于遗传算法的二维不规 则零件排样方法， 首先初始化， 给每一个零件固 定一个序号， 根据零件面积降序排序， 初始旋转 角度设置为0 °， 得到每个零件的序列号、 坐标点、 面积， 根据NFP和重心左下定位确定零件初始排 样位置； 之后根据遗传算法对放置顺序和旋转角 度进行更新， 判断孔洞内能否放入其他零件， 如 果能放入则将该零件先放入孔洞内再根据NFP和 重心左下定位顺序排放零件； 根据适应度函数重 复迭代， 直至达到终止条件， 此时的排样结果为 最优排样。 本发明采用了改进的遗传算法， 利用 自适应变异概率跳出局部最优、 重排定序策略避免同一零件重复排样。 权利要求书2页 说明书6页 附图5页 CN 113435094 B 2022.07.05 CN 113435094 B 1.一种基于 遗传算法的二维不 规则零件排样方法， 其特 征在于， 包括以下步骤： S1、 初始化， 读取零件端点坐标点集， 分别处理零件的直线和弧线， 选取规则板材或不 规则板材， 计算n个零件实际面积和 且在后续过程中总面积不变； 将n个零件按照 面积大小降序排列， 将面积大的零件优先放入板材； 零件的旋转角度设置为360 °/x， x为整 数， x＝1， 2， 3， 4. .....n； 初始旋转角度设置为0 °， 将零件的排 放顺序和旋转角度进行编码； S2、 根据遗传算法打乱步骤S1得到的零件排放顺序和旋转角度， 针对零件切割时的损 耗问题， 根据坐标点信息将零件外轮廓进行放大， 内轮廓根据切割损耗进行缩小， 利用NFP 计算零件可排放区域， 依据重心左下定位准则从当前待排零件由原材料右上角开始， 在保 证零件不重叠的情况下， 向下向左不停移动， 直至不能再移动为止， 在可排放区域中确定零 件的放置位置； S3、 根据S2中确定的零件的放置位置放入零件， 较小的零件优先放入孔洞， 增加利用 率， 待所有零件排放结束后根据零件中最左， 最右， 最上， 最下的点集， 计算零件包络块面积 S零件 包 络 块 面积， 适应度函数设置为 面积利用率 L； S4、 将当前的面积利用率Lnew与上一次迭代得到的面积利用率Lold进行对比： 如果Lnew＞ Lold， 则Lold＝Lnew； 如果Lnew＜Lold， 则Lold＝Lold， 适应度函数值更新完成后， 开始下一次迭代， 重复S2和S3； 达 到结束条件后， 输出当前排样结果的最优效果图。 2.根据权利要求1所述的一种基于遗传算法的二维不规则零件排样方法， 其特征在于， 所述选取规则板材的时候， 设置 板材的宽度和高度， 从而得到一个规则的矩形板材； 选取不规则板材的时候， 和读取零件一样， 找到零件的外轮廓和内轮廓， 找到其最左， 最右， 最上， 最下的点， 将不规则板材扩充为一个矩形板材， 把缺 失的部分作为已排放区域， 此时将不规则板材视为一个已经排放过零件的规则板材， 后续排样时方法和规则板材一 致。 3.根据权利要求1所述的一种基于遗传算法的二维不规则零件排样方法， 其特征在于， 根据切割损耗设置切割间隔为m， 求解NFP时零件外轮廓每个端点坐标分别加上m， 从而将零 件“放大”， 内轮廓每个端点坐标分别减去m， 将零件按顺序取出后， 将其重心逐渐往左， 往 下 移动， 直至它的边接触到左边界和下边界， 紧接着 拿出第二个零件根据NFP进 行可排放区域 计算： 1)当滑动法参 考点P位于NFPAB上时， 上一个放置的零件A与即将放置的零件B刚好接触； 2)当滑动法参 考点P位于NFPAB内时， 上一个放置的零件A与即将放置的零件B重 叠； 3)当滑动法参 考点P位于NFPAB外时， 上一个放置的零件A与即将放置的零件B不相交； 根据NFP将两个零件的位置关系转换成了参考点P与NFPAB的位置关系， 使用滑动法求取 可排放区域， 然后根据重心左下定位选择放置位置， 计算NFP的过程中将坐标信息向上取 整， 避免计算机处 理坐标数据时四舍五入导 致重叠问题。 4.根据权利要求1所述的一种基于遗传算法的二维不规则零件排样方法， 其特征在于， 如果存在孔洞的情况下同时满足以下条件， 则根据重心左下定位准则， 将待排零件放入孔 洞： 1)待排零件面积小于孔洞面积；权　利　要　求　书 1/2 页 2 CN 113435094 B 22)K*(x1‑x2)＞x3‑x4； 3)K*(y1‑y2)＞y3‑y4； 其中x1， x2表示孔洞上各点横坐标最大值和最小值， x3， x4表示待排零件各点横坐标最大 值和最小值； 其中y1， y2表示孔洞上各点纵坐标最大值和最小值， y3， y4表示待排零件各点纵坐标最大 值和最小值； 即孔洞的最大宽度和最大高度乘以K后仍大于待排放零件时才能放入该零件， 所述K根 据实际的零件情况确定 。权　利　要　求　书 2/2 页 3 CN 113435094 B 3