基于下料特征的大规模零件分组优化方法

摘要

本发明公开了一种基于下料特征的大规模零件分组优化方法，其具体步骤为：(1)基于相似性特征的零件分组，得到不同的零件相似组，每个零件划归入一个零件相似组；(2)基于下料配合特征的零件重组，重组后的每个零件相似组对应一个优化下料子问题；(3)零件优化补偿，优化过程中对零件的组间分布进行动态补偿，最后合并各组优化结果得到原问题的下料方案。本发明能实现零件的自适应分组，并可获得合理的稳定的零件分组，避免了具体聚类算法对分组结果的影响，缓解了算法在时间效率和材料利用率上的矛盾。

说明书

技术领域

本发明涉及一种基于下料特征的大规模零件分组优化方法，本方法通过零件分组优化 能够缓解算法在时间效率和材料利用率上的矛盾，获得高材料利用率的稳定的下料方案。

背景技术

优化下料问题是具有最高计算复杂性的NP完全问题，零件种类的增加所带来的可行 组合方式的增长是爆炸性的，造成算法寻优时间效率低下，且容易陷入局部最优解，以损 失材料利用率换取时间求解效率的做法已难以满足企业的应用需要，造成算法在时间效率 和材料利用率这2个问题上的矛盾。因此，在算法本身不能很好处理大规模零件下料问题 的情况下，从分组优化角度对大规模零件下料问题进行研究是十分必要的。其可行性基于 以下事实：(1)提高优化时效性。将大规模问题拆分为若干个子问题，通过解空间分散降 低整体求解难度，提高优化时间效率。(2)下料问题的可拆分性。切割方案构成和零件分 布具有明显的局部特征，即每个切割方案只包括部分种类的零件，某种零件也只会在部分 切割方案中存在，通过合理的分组可以将无关的零件强行隔离而不会影响优化效果。(3) 时间效率与材料利用率的统一。相对于原问题，单个分组优化具有明显的时效性优势，为 寻得更优的下料方案提供了时间条件。

现有对零件分组优化下料的研究主要集中在如何获得合理的稳定的零件分组，大多利 用各种聚类算法实现对零件的相似性分组，由于各种聚类算法在初始聚类中心、收敛性、 局部最优解等问题上的局限性，使得分组结果对具体聚类算法的依赖较大，在对零件数据 变化的适应性、分组结果的稳定性等方面还不理想。分组优化过程中，欠缺对零件合理补 偿策略的考虑，需要在不破坏较优分组的情况下提高较次分组的质量以巩固分组效果，提 高整体材料优化利用率。

发明内容

针对现有技术存在的上述不足，本发明的目的在于提供一种基于下料特征的大规模零 件分组优化方法，本方法能实现零件的自适应分组，并可获得合理的稳定的零件分组，避 免了具体聚类算法对分组结果的影响，缓解了算法在时间效率和材料利用率上的矛盾。

本发明的技术方案是这样实现的：

基于下料特征的大规模零件分组优化方法，其具体步骤为：

(1)基于相似性特征的零件分组-零件优化任务下达之后，首先根据零件相似性特征 建立样本零件相似特征关联有权无向图，通过对无向图最小生成树MST的分割生成样本 零件相似组，利用样本零件相似组对所有待下料零件进行过滤分组，从而得到不同的零件 相似组，每个零件划归入一个零件相似组；本步骤利用图论方法对样本零件的相似性特征 关联进行分析，构建样本零件相似特征关联有权无向图MST，通过裁减掉具有下料配合特 征关联的零件边和不满足距离要求的零件边对MST进行分割，自动完成样本零件的相似 性分组，然后将待下料零件添加到距离最近的相似组完成分组。避免了采用具体聚类算法 在收敛性、局部最优解等方面的问题，使得相似分组结果摆脱对具体聚类算法的依赖。

(2)基于下料配合特征的零件重组-将第(1)步得到的各零件相似组分别以抽象零件 代替，再基于零件间的下料配合特征建立抽象零件下料配合特征关联有权无向图，依据该 无向图最小生成树MST体现的零件最优下料配合性实现零件相似组的重组，重组后的每 个零件相似组对应一个优化下料子问题；

(3)零件优化补偿-首先根据重组后的零件相似组的材料优化利用率对各组进行降序 排列，优化过程中对零件的组间分布进行动态补偿，最后合并各组优化结果得到原问题的 下料方案。动态补偿时将被摒弃的零件自动增加到下一分组，实现零件的组间动态补偿， 在不破坏较优分组的情况下提高了较次分组的质量，有利于整体材料优化利用率的提高。

设大规模零件下料问题记为T_cut＝(P，Y，T，S)，其中，零件集 $P=\left\{\right\{p_{{1,m}_1},p_{{2,m}_1},...,p_{n_1,m_1}\},\{p_{1,m_2},p_{2,m_2},...,p_{n_2,m_2}\},...,\{p_{{1,m}_q},p_{{2,m}_q},...,p_{n_c,m_q}\left\}\right\},$p_i，j表示第j种套 裁方式上的第i种零件分布，原材料集零件下料特征关联为 T＝{T_sim，T_syn}，T_sim表示零件间的相似特征集，可用零件间的欧式距离d(p_i，p_j)进行描述， T_syn表示第m_q种原材上的零件下料配合特征集，判别函数如下所示

同一套裁方式上的零件具有下料配合特征关联，判别函数值取1，否则取0； S＝(s₁，s₂，…，s_r)表示优化算法函数集，输出值为材料优化利用率k，材料优化利用率越高 则表示零件间的下料配合性越好；

k＝max{s_l(p_1，j，p_2，j，…，p_i，j，y_j)|i∈(n₁，n₂，…，n_c)，j∈(m₁，m₂…，m_q)，s_l∈S}

设样本零件集为P_mark，最低原材料优化利用率阈值为κ，则样本应满足如下条件

s_l(P_mark，Y)＝max{s_l(p_1，j，p_2，j，…，p_i，j，y_j)|p_i，j∈P_mark，j∈(m₁，m₂…，m_q)}≥κ    (2)

定义1将零件作为顶点N＝P，零件间的相似特征关联作为边 E＝{T_sim(p_i，p_j)|p_i，p_j∈P，i≠j}，将d(p_i，p_j)作为边的权值，则P关于d的加权图 G_d(P)＝(N，E)称为零件相似特征关联有权无向图；

定义2将零件作为顶点N＝P，零件间的下料配合特征关联作为边 E＝{T_syn(p_i，p_j)|p_i，p_j∈P，i≠j}，将材料利用率k作为边的权值，则P关于k的加权图 G_k(P)＝(N，E)称为零件下料配合特征关联有权无向图；

定义3对于零件集P′∈P，p_i≠p_j，g((p_i，p_j)，t_l，y_c)＝0，且d(p_i，p_j)＜β， β为距离阈值，则称P′为抽象零件，代表一个零件相似组；

第(1)步基于相似性特征的零件分组步骤为：

Step1设定材料利用率阈值κ，利用式2选择样本零件集P_mark，计算样本零件间的距 离d(p_i，p_j)，构建样本零件相似特征关联有权无向图G_d；

Step2采用Kruskal算法求解有权无向图G_d最小生成树MST；

Step3利用式1判断样本零件间的下料配合特征，若g((p_i，p_j)，t_l，y_c)＝1，裁减掉连接 两零件的边；

Step4计算距离阈值β，在MST中裁减掉距离大于β的边；

Step5每个连通子树对应一个样本零件相似组，将MST分割后形成的连通子树输出， 形成n个样本零件相似组，P_mark＝{G₁，G₂，…，G_n}；

Step6将距离G_i聚类中心最近的样本零件作为样本零件相似组中心， $P_V=\{p_{v_1},p_{v_2},...,p_{v_n}\};$

Step7依次拾取待下料零件p∈P_deal，计算与样本零件相似组中心的距离将 p添加到对应的相似组；

Step8算法结束，输出零件相似组P＝P_mark+P_deal＝{G₁，G₂，…，G_n}；

第(2)步基于下料配合特征的零件重组步骤为：

Step9重新计算各零件相似组的聚类中心，将距离G_i聚类中心最近的零件作为零件相 似组中心，$P_V=\{p_{v_1},p_{v_2},...,p_{v_n}\};$

Step10若获取s_l∈S，使得s_l(P_V，Y)≥κ，增加与该下料方案对应的零 件间的下料配合特征关联；

Step11生成抽象零件P′，利用对应关系t_max＝{t_i|t_i→s_l→k_max，t_i∈T′_syn}，将最高材料利 用率对应的零件下料配合特征关联作为边，计算k_max＝1/k_max，构建抽象零件下料配合特 征关联有权无向图G_k(P′)；

Step12采用Kruskal算法求解有权无向图G_k(P′)最小生成树MST；

Step13依据MST中边所对应的零件下料配合特征关联，从抽象零件P′中抽取待下料 零件重组为m个分组，$P_{\mathrm{deal}}=\{G_1^T,G_2^T,...,G_m^T\};$

第(3)步零件优化补偿步骤为：

Step14优化之前根据各组的材料优化利用率对各组进行降序排列；

Step15从第一组开始依次优化各组，各组均获得高于材料利用率阈值κ的下料方案， 前一组被摒弃的零件自动增加到下一分组参与优化，形成零件动态补偿的优化过程；

Step16优化完合并各组优化结果输出整体下料方案。

本发明的最大优点是从分组优化角度对大规模零件下料问题进行了研究，利用图论工 具实现零件的自适应分组，避免了具体聚类算法对分组结果的影响，并利用样本零件的导 向作用加速分组过程，获得了合理的稳定的零件分组。本发明通过合理的零件分组实现对 大规模零件下料问题较理想的拆分，缓解算法在时间效率和材料利用率上的矛盾，获得高 材料利用率的稳定的下料方案，可广泛应用于大规模零件下料的实际工程中。

附图说明

图1本发明中基于相似性特征的零件分组原理图；

图2本发明中基于下料配合特征的零件重组原理图；

图3本发明分组优化流程示意图。

具体实施方式

为了求解大规模零件下料问题，从零件分组优化角度进行研究，本发明提供了一种基 于下料特征的大规模零件分组优化方法，通过对大规模零件下料问题较理想的拆分，缓解 了算法在时间效率和材料利用率上的矛盾。

优化下料的本质是基于零件拼合对原材料进行最大程度的填充，把握零件的关键下料 特征是探寻合理分组方法的重点，零件的相似性特征和下料配合特征是最重要的两类下料 特征，零件相似性特征是指零件在外形上的相似特性，零件下料配合特征是指零件在某种 原材料上形成套裁方案时所建立的拼合关系。本发明所采用的技术方案是：将零件的相似 性特征和下料配合特征作为零件分组约束，引入下料零件经验样本对分组过程进行指导， 采用图论方法对零件下料特征关联进行分析，设计一种由三阶段组成的大规模零件分组优 化方法。首先建立样本零件相似特征关联有权无向图，通过对无向图最小生成树MST的 分割生成n个样本零件相似组，利用相似组对待下料零件进行过滤分组---该阶段为以组内 零件要尽可能的相似、不同组间要尽可能的相异为目的的零件相似性分组阶段；然后定义 抽象零件代替零件相似组，基于零件间的下料配合特征建立抽象零件下料配合特征关联有 权无向图，利用无向图最小生成树MST体现的零件最优下料配合性将相似组重组为m个 分组---该阶段为以零件套裁组合性最强为目的的零件相似组重组阶段；优化之前依据各组 的材料优化利用率对分组进行降序排列，优化过程中对零件的组间分布进行动态补偿，最 后合并各组优化结果得到原问题的下料方案---该阶段为以提高材料利用率为目的的零件 优化补偿阶段。大规模零件下料问题描述如下：

设大规模零件下料问题记为T_cut＝(P，Y，T，S)，其中，零件集 $P=\left\{\right\{p_{{1,m}_1},p_{{2,m}_1},...,p_{n_1,m_1}\},\{p_{1,m_2},p_{2,m_2},...,p_{n_2,m_2}\},...,\{p_{{1,m}_q},p_{{2,m}_q},...,p_{n_c,m_q}\left\}\right\},$p_i，j表示第j种套 裁方式上的第i种零件分布，原材料集零件下料特征关联为 T＝{T_sim，T_syn}，T_sim表示零件间的相似特征集，可用零件间的欧式距离d(p_i，p_j)进行描述， T_syn表示第m_q种原材上的零件下料配合特征集，判别函数如下所示

同一套裁方式上的零件具有下料配合特征关联，判别函数值取1，否则取0。 S＝(s₁，s₂，…，s_r)表示优化算法函数集，输出值为材料优化利用率k，材料优化利用率越高 则表示零件间的下料配合性越好。

k＝max{s_l(p_1，j，p_2，j，…，p_i，j，y_j)|i∈(n₁，n₂，…，n_c)，j∈(m₁，m₂…，m_q)，s_l∈S}

设样本零件集为P_mark，为了使对零件分组的指导具有明确的意义和目的，所选定的零 件样本应来源于高效的下料方案。最低原材料优化利用率阈值为κ，则样本应满足如下条 件

s_l(P_mark，Y)＝max{s_l(p_1，j，p_2，j，…，p_i，j，y_j)|p_i，j∈P_mark，j∈(m₁，m₂…，m_q)}≥κ    (2)

定义1将零件作为顶点N＝P，零件间的相似特征关联作为边 E＝{T_sim(p_i，p_j)|p_i，p_j∈P，i≠j}，将d(p_i，p_j)作为边的权值，则P关于d的加权图 G_d(P)＝(N，E)称为零件相似特征关联有权无向图。

定义2将零件作为顶点N＝P，零件间的下料配合特征关联作为边 E＝{T_syn(p_i，p_j)|p_i，p_j∈P，i≠j}，将材料利用率k作为边的权值，则P关于k的加权图 G_k(P)＝(N，E)称为零件下料配合特征关联有权无向图。

定义3对于零件集P′∈P，p_i≠p_j，g((p_i，p_j)，t_l，y_c)＝0，且d(p_i，p_j)＜β， β为距离阈值，则称P′为抽象零件，代表一个零件相似组。

基于相似性特征的零件分组阶段利用图论方法对零件的相似性特征关联进行分析，通 过对无向图最小生成树MST的分割完成样本零件相似分组，利用相似组对待下料零件进 行过滤分组。其原理描述如下：

构建样本零件相似特征关联有权无向图G_d，如图1a所示，子树T_e是G_d的一个连通子 图，经过所有树节点且不包含封闭回路的长度最小子树称为G_d的最小生成树MST。聚类 中具有下料配合特征关联的相似零件会被划分到同一个相似组，这将隐藏掉需要用来指导 相似分组重组的零件配合特征。为了避免相似分组过程中零件下料配合特征的丢失，如图 1b所示，在MST中，首先裁减掉具有下料配合性零件的边c，对MST进行分割；相似分 组需满足组内零件要尽可能的相似，不同组间要尽可能的相异，d(p_i，p_j)距离值大的零件 相似度小，聚类时应划分到不同的相似组，如图1c所示，裁减掉大于距离阈值β的边a、 b，将样本零件聚类为合理的相似组，最终将待下料零件添加到距离最近的相似组完成分 组。通过对MST的分割自动确定合理的分组个数和分组规模，无需事先确定聚类个数和 聚类中心，具有较好的适应性。为了操作的方便性，可取其中，E(d) 为MST中零件距离均值，D(d)为MST中零件距离方差。

基于下料配合特征的零件重组阶段定义抽象零件代替零件相似组，基于零件间的下料 配合特征建立抽象零件下料配合特征关联有权无向图，利用无向图最小生成树MST体现 的零件最优下料配合性进行相似组重组。其原理描述如下：

重新计算各相似组的聚类中心，将距离G_i聚类中心最近的零件作为相似组中心， 若则样本零件对部分待下料零件已不具有代表性， 根据样本零件的下料配合特征关联进行相似组重组可能导致部分零件下料子任务材料优 化利用率降低，获取s_l∈S，使得s_l(P_V，Y)≥κ，增加与该下料方案对应的零件间的下料配 合特征关联，改善相似组间零件下料配合性的减弱。形成的相似组G_i即为抽象零件P′， P′＝(G_i，T′_syn)，G_i为相似组所包含的零件集，T′_syn是相似组间零件的下料配合特征关联， 其中，是样本零件的下料配合特征，是新增的下料配合特征，当各 相似组的聚类中心为样本零件时，某种零件会存在于原材料的多种套裁方案中， 任意两个零件间可能存在多种下料配合特征关联关系，以抽象零件P′为顶点，零件间的下 料配合特征关联T′_syn作为边，如图2a所示节点间则会出现多条边的情况，不同的下料配合 特征关联经过优化算法处理会输出不同材料利用率的下料方案，对应关系为t_l→s_l→k_l， 而下料的最终目的是获得尽可能高的材料利用率，将最高材料利用率对应的零件下料配合 特征关联作为边，解决边的不唯一性问题，构建抽象零件 下料配合特征关联有权无向图G_k(P′)。如图2b所示，子树T_e是G_k的最小生成树MST，由 于MST是边长度和最小的子树，为了获得相对最高的材料利用率，可将t_max所对应的材料 利用率取倒数作为边的权值，即k_max＝1/k_max。按照MST中边所对应的零件下料配合特征 关联可将所有的零件进行下料，并能获得相对最优的下料方案。如图2c所示，依据MST 中边所对应的零件下料配合特征关联，从抽象零件P′中抽取待下料零件可实现对零件相似 组的重组，将待下料零件重组为m个分组，各分组对应一个优 化下料子问题。

通过零件分组，将大规模问题分散为多个子问题，但零件不可能绝对不相关，强硬的 隔离会破坏算法收敛于最优解的条件。通过设定原材料利用率阈值，在同一组内筛选出合 理的下料方案，将被摒弃的零件引入到其他组内参与优化，形成一个零件动态补偿的优化 过程，保证算法收敛于最优解的条件。对于较优分组而言，依靠自身零件组合就能形成高 效的下料方案，若对其进行补偿，反而会破坏零件最优的下料配合性；对于较次分组而言， 对其进行补偿，随着零件种类的增多，零件的下料组合方式也会增加，形成高效下料方案 的可能性变大。因此，本发明建立了优化下料的零件顺序补偿策略，即在优化之前根据各 分组的材料优化利用率对各组进行降序排列，优化过程中将被摒弃的零件自动增加到下一 分组，实现零件的组间动态补偿，在不破坏较优分组的情况下提高了较次分组的质量，有 利于整体材料优化利用率的提高。

本发明具体步骤如下，可以同时参见图3：

1、基于相似性特征的零件分组阶段

Step1设定材料利用率阈值κ，利用式2选择样本零件集P_mark，计算样本零件间的距 离d(p_i，p_j)，构建样本零件相似特征关联有权无向图G_d；

Step2采用Kruskal算法求解有权无向图最小生成树MST；

Step3利用式1判断样本零件间的下料配合特征，若g((p_i，p_j)，t_l，y_c)＝1，裁减掉连接 两零件的边；

Step4计算距离阈值β，在MST中裁减掉距离大于β的边；

Step5每个连通子树对应一个样本零件相似组，将MST分割后形成的连通子树输出， 形成n个样本零件相似组，P_mark＝{G₁，G₂，…，G_n}；

Step6将距离G_i聚类中心最近的样本零件作为相似组中心，

Step7依次拾取待下料零件p∈P_deal，计算与样本零件相似组中心的距离将 p添加到对应的相似组；

Step8算法结束，输出零件相似组P＝P_mark+P_deal＝{G₁，G₂，…，G_n}；

2、基于下料配合特征的零件重组阶段

Step9重新计算各零件相似组的聚类中心，将距离G_i聚类中心最近的零件作为零件相 似组中心，$P_V=\{p_{v_1},p_{v_2},...,p_{v_n}\};$

Step10若获取s_l∈S，使得s_l(P_V，Y)≥κ，增加与该下料方案对应的零 件间的下料配合特征关联；

Step11生成抽象零件P′，利用对应关系t_max＝{t_i|t_i→s_l→k_max，t_i∈T′_syn}，将最高材料利 用率对应的零件下料配合特征关联作为边，计算k_max＝1/k_max，构建抽象零件下料配合特 征关联有权无向图G_k(P′)；

Step12采用Kruskal算法求解有权无向图最小生成树MST；

Step13依据MST中边所对应的零件下料配合特征关联，从抽象零件P′中抽取待下料 零件重组为m个分组，$P_{\mathrm{deal}}=\{G_1^T,G_2^T,...,G_m^T\};$

3、零件优化补偿阶段

Step14优化之前根据各组的材料优化利用率对各组进行降序排列；

Step15从第一组开始依次优化各组，各组均获得高于材料利用率阈值κ的下料方案， 前一组被摒弃的零件自动增加到下一分组；

Step16优化完合并各组优化结果输出整体下料方案。

零件分组中引入已有高效下料方案中零件的整体下料特征指导待下料零件的分组，一 方面可以有效避免未考虑领域知识导致分组的盲目性，另一方面将样本零件的下料配合特 征作为分组约束，可以有效避免零件配合特征在相似分组过程中的丢失。采用图论方法对 零件进行分组，使得组内零件具有较好的互换性，组间零件具有较强的套裁组合性，避免 了具体聚类算法的局限性对分组结果的影响，保证了分组质量。零件优化补偿阶段通过制 定零件顺序补偿策略进一步巩固了分组质量。

在国家863/CIMS目标产品“建筑金属结构计算机辅助设计与生产管理集成系统”中 的条材优化下料子系统上进行实验。在Celeron CPU 2.60GHz和1GB内存的硬件环境下， 通过测试与评估，该软件在此硬件水平下单次优化最大零件种类规模为180，可取样本零 件规模P_mark＝180。设定原材料优化利用率阈值κ＝95％，原材料尺寸为5000mm。抽取实 际应用中四组不同尺寸范围和规模的零件进行下料，待下料零件种类规模P_deal分别为266、 235、214和197，g₁、g₂、g₃、g₄、g₅表示各个分组，将本发明所提方法与无监督HCM 聚类分组优化方法进行对比，后者分组优化时零件动态补偿采取随机方式，优化时间、原 材料利用率和原材料使用数量等优化结果数据如表1和表2所示。

表1本发明所提方法分组优化结果数据

表2无监督HCM聚类分组优化结果数据

从表1与表2的数据对比可知，相对于无监督HCM聚类分组优化方法，本发明所提 方法在优化时间效率、材料利用率及优化结果稳定性方面表现更好。优化时间效率方面， 4组零件下料分别提高了约33％、30％、23％和21％，在利用零件样本指导待下料零件相 似聚类过程中，注意对零件下料配合特征的保护，零件较强的套裁配合性使得优化算法能 较快的收敛于最优解；材料利用率方面，4组下料中本发明所提方法均更优，零件紧密的 下料配合性保证了分组质量，优化中零件采取组间顺序补偿策略，在不破坏较优分组的情 况下提高了较次分组的质量，整体上提高了材料优化利用率；优化结果稳定性方面，HCM 聚类分组受经验和主观判断影响较大，优化中零件组间随机补偿将会破坏较优分组，如表 2中第1组g₃、第2组g₁材料利用率的明显降低。可见，本发明所提方法在处理大规模零 件下料问题时可以获得更优更稳定的下料方案。