(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111439737.X (22)申请日 2021.11.30 (71)申请人 郑州轻工业大 学 地址 450000 河南省郑州市高新 技术产业 开发区科 学大道136号 (72)发明人 王英聪　黄春　王延峰　张丰鹏　 张静宜　刘驰　焦娇　孙军伟　 王妍　凌丹　张勋才　栗三一　 李盼龙　刘鹏　 (74)专利代理 机构 郑州优盾知识产权代理有限 公司 41125 代理人 栗改 (51)Int.Cl. G06Q 10/04(2012.01) G06N 3/00(2006.01)G06F 30/27(2020.01) G06F 30/17(2020.01) G06F 16/2453(2019.01) G06F 119/14(2020.01) (54)发明名称 一种基于改进鸡群算法的圆形件卷材排样 优化方法 (57)摘要 本发明提出了一种基于改进鸡群算法的圆 形件卷材排样优化方法， 步骤为： 将圆形件卷材 排样问题 转化为最小化干涉量的判定问题； 采用 网格覆盖 策略初始化鸡群； 利用分离算法优化每 个鸡群个体的干涉量； 建立鸡群的等级制度， 根 据适应度建立公鸡 ‑母鸡引领关系， 根据多样性 建立母鸡 ‑小鸡引领关系； 公鸡通过交换动作 自 主觅食， 母鸡通过平移动作跟随公鸡觅食， 小鸡 通过赋值动作跟随母鸡觅食， 优化干涉量更新排 样方案； 判断当前种群的最优排样方案是否合 法， 记录合法排样方案缩小矩形卷材的长度； 更 新迭代次数和等级参数， 判断是否满足鸡群重构 条件； 输出合法排样方案。 本发明将鸡群算法和 变邻域法组合， 可以有效提高矩形卷材的利用 率， 搜索效率高。 权利要求书4页 说明书12页 附图4页 CN 114066099 A 2022.02.18 CN 114066099 A 1.一种基于改进鸡群算法的圆形件卷 材排样优化方法， 其特 征在于， 其 步骤如下： 步骤1： 根据矩形卷材和待排圆形件的参数， 设置目标函数， 将圆形件卷材排样问题转 化为最小化干涉量的判定问题； 步骤2： 初始化鸡群算法参数， 采用网格覆盖策略初始化鸡群， 得到鸡群个体的初始排 样方案； 步骤3： 利用分离算法优化每个鸡群个体所对应排样方案的干涉量， 将干涉量作为鸡群 个体的适应度； 步骤4： 建立鸡群的等级制度， 根据适应度建立公鸡 ‑母鸡引领关系， 根据多样性建立母 鸡‑小鸡引领关系； 步骤5： 公鸡通过交换动作进行自主觅食， 调用分离算法优化干涉量并更新 排样方案； 步骤6： 母鸡通过平 移动作跟随公鸡觅食， 调用分离算法优化干涉量并更新 排样方案； 步骤7： 小鸡通过 赋值动作跟随母鸡觅食， 调用分离算法优化干涉量并更新 排样方案； 步骤8： 判断当前种群的最优排样方案是否合法， 若是， 则记录合法排样方案， 并缩小矩 形卷材的长度， 返回步骤3； 若否， 进入步骤9； 步骤9： 判断迭代次数 是否达到最大迭代次数， 若是， 进入步骤1 1； 若否， 进入步骤10； 步骤10： 更新迭代次数和等级参数， 判断迭代次数和等级参数是否满足鸡群重构条件， 若是， 返回步骤4； 若否， 返回步骤5； 步骤11： 终止算法， 输出合法排样方案， 包括矩形 卷材的长度、 圆形件的坐标和排样图。 2.根据权利要求1所述的基于改进鸡群算法的圆形件卷材排样优化方法， 其特征在于， 所述圆形件卷材排样问题为： 在宽度W固定、 长度L不限的矩形卷材上排放n个圆形件， 其中 第i个圆形件 ci的半径为ri， i＝1， 2， …， n； 目标函数为所需要的矩形卷材长度L最小， 即卷材 利用率最大； 圆形件卷材排样问题转化为数学模型为： 设置矩形卷材左下角为坐标原点， 以矩形卷 材的长度 方向为X轴、 宽度方向为Y轴建立直角坐标系， 令第i个圆形件ci的圆心坐标为(xi， yi)， 则寻找一个排样方案S＝(x1， y1， x2， y2，…， xn， yn)， 使得矩形卷材的长度L最小： minL或 者卷材利用率U最大： 并满足所有圆形件均排 放在矩形 卷材内部且 任意两 个圆形件互不干涉的约束： 其中， rj为第j个圆形件cj的半径， (xj， yj)为第j个圆形件cj的圆心坐标。 3.根据权利要求2所述的基于改进鸡群算法的圆形件卷材排样优化方法， 其特征在于， 所述判定问题为： 在矩形卷材的长度L确定下， 判断是否存在一个排样方案可将所有圆形件 排放到矩形卷材上， 若是， 则称排样方案合法， 缩小卷材长度L， 继续搜索合法排样方案， 从 而逼近矩形卷材的最优长度； 将矩形卷材的长度最小化问题转化为排样方案的干涉量最小权　利　要　求　书 1/4 页 2 CN 114066099 A 2化问题； 所述排样方案的干涉量的计算方法为： 令dvi表示圆形件ci与矩形卷材垂直边的干涉 量， dhi表示圆形件ci与矩形卷材水平边的干涉量， dij表示圆形件ci与圆形件cj的干涉量， 则 排样方案S＝ (x1， y1， x2， y2，…， xn， yn) 在矩形卷材的长度为L时的干涉量 其中， dvi＝max{xi+ri‑L， ri‑xi， 0}， dhi＝ max{yi+ri‑W， ri‑yi， 0}， 所述排样方案合法的条件是： 当干涉量O(S， L)＜10‑20时， 称排样方案S合法。 4.根据权利要求1或3所述的基于改进鸡群算法的圆形件卷材排样优化方法， 其特征在 于， 所述步骤2中初始化鸡群算法参数： 设置鸡群规模N， 公鸡规模NR， 母鸡规模NH， 小鸡规模 NC， 且N＝NR+NH+NC， 最大迭代次数tmax， 等级参数G 的取值范围[a， b]； 初始时令迭代次数t＝ 1， 等级参数G＝a； 所述步骤8中缩小矩形 卷材的长度的方法为： 将矩形 卷材的长度L缩小至 0.95L； 所述步骤10中鸡群重构条件为： t％G＝0， 且％为求余运算， 迭代次数t更新为t＝t+1， 等级参数G更新 为 5.根据权利要求4所述的基于改进鸡群算法的圆形件卷材排样优化方法， 其特征在于， 所述网格覆盖策略的实现方法为： 从坐标原点出发， 沿着X轴和Y轴的方向将矩形卷材划分 为一些正方形网格、 剩余部分为若干长方形网格， 正方形网格的边长为 则矩形 卷材被划分成 个网格， 从中随机选择n个网格放置n个圆形 件， 且将圆形件的圆心与正方形网格或长方形网格的中心重叠， 生成鸡群个体的初始排样 方案； 其中， 表示向上 取整。 6.根据权利要求1或5所述的基于改进鸡群算法的圆形件卷材排样优化方法， 其特征在 于， 所述步骤5、 步骤6和步骤 7中更新排样方案的方法为： 采用贪婪策略更新排样方案， 即当 O(Snew， L)＜O(S， L)时， 接受新的排样方案Snew， 否则保留原来的排样方案S不变； 所述分离算法寻找当前排样方案的最小干涉量， 包 含如下步骤： Step 1： 计算当前排样方案S的干涉量O(S， L)； Step 2： 根据拟物法计算每个圆形件所受的合力， 即干涉量O(S， L)对圆形件的圆心坐 标的负梯度； Step 3： 利用拟牛 顿法L‑BFGS优化干涉量O(S， L)。 7.根据权利要求6所述的基于改进鸡群算法的圆形件卷材排样优化方法， 其特征在于， 所述步骤4中鸡群 的等级制度为： 将N个鸡群个体按照适应度由小到大排序， 前NR个个体定 义为公鸡， 中间NH个个体定义为母鸡， 最后NC个个体定义为小鸡； 所述公鸡 ‑母引领关系的建立方法为： 将公鸡按照适应度由大到小排序， 排序后第g个 公鸡的适应度等级为FRg＝g， g＝1， 2， …， NR； 母鸡选择跟随第g个公鸡觅食的选择概 率为：权　利　要　求　书 2/4 页 3 CN 114066099 A 3