基于复杂网络的三维CAD装配模型模块单元发掘

韩周鹏 刘 永 巴 黎 史慧帆西安理工大学机械与精密仪器工程学院，西安，710048

0 引言

随着计算机辅助设计(CAD)系统在工业界的广泛应用，企业积累了大量的三维CAD装配模型，它们是企业新产品开发时可借鉴、可重用的重要知识资源[1]。相对于零件模型，三维装配模型蕴含有丰富的设计信息，通过零件装配所体现的结构信息，不仅体现了设计者的设计意图、设计经验等知识，也能更好地与用户需求、产品功能、产品设计方案等问题对应和衔接。在借助CAD系统进行复杂机械产品结构设计过程中，设计者通常是根据产品功能、性能、参数等需求，进行产品三维CAD模型的结构设计的。产品原有设计者在产品设计过程中的设计意图、设计公理、功能、关键结构、模块结构等知识不能通过三维CAD装配模型直接体现[2]，导致企业设计经验不足或缺少原有产品知识储备的设计者较难理解、重用原有三维CAD装配模型，特别是对于企业引入的三维产品模型，模型相关信息可能存在丢失、不完整情况以及设计者自身设计知识与经验不足，仅仅通过三维装配模型信息较难理解三维装配模型的原有设计意图，进而制约着三维装配模型重用质量与效率。因此，对复杂机械产品的三维CAD装配模型进行知识发掘，捕获三维装配模型所蕴含的关键零部件、关键装配结构[3]、通用设计结构[4-5]、模块结构[6]等知识，可以有效还原产品的设计意图，有助于其他设计者对原有设计知识的理解，启发设计者创造性思考，促进产品设计创新[7]。

复杂三维CAD装配模型作为一种特殊的、蕴含着潜在可重用模块结构的模型资源，零件数量繁多且装配约束关系也相对复杂，所蕴含的具有重用价值的潜在结构知识仅仅通过三维CAD装配模型难以显性体现。三维CAD装配模型的模块识别可以弥补产品模块设计意图缺失、不完整的缺陷。王延平等[8]利用属性邻接图表示三维CAD装配模型，通过分析零件的拓扑结构、功能、材料相关性建立了零件间的综合相关度矩阵，给出了面向图分割的蚁群聚类算法，该聚类算法较为繁琐，无法定量地评价模块划分质量。LI等[9]通过提取CAD装配模型中装配约束信息，获得了零件间的连接关系，然后利用零件间相对自由度来评价零件间的依赖强度，将其表达为设计结构矩阵，通过设计结构矩阵聚类实现了三维CAD装配模型的模块划分，但该方法缺少对零件间功能关系的考虑。

在产品设计阶段，通过分析产品设计中零件、部件之间的功能、结构等关联关系，将产品划分为一系列功能独立的模块结构以满足市场不同需求，不仅可以提高产品设计效率，缩短产品设计周期，还可以降低生产与维护管理成本[10]。产品的功能与结构通常为模块划分考虑的主要因素[11]。目前已有的模块划分方法主要可分为基于图的模块划分[12-13]、基于矩阵的模块划分[14-15]和基于智能算法的模块划分[16-17]，基本可以满足产品设计不同阶段的个性化需求。

为了能够从复杂三维CAD装配模型中获得易于重用的模块化结构单元，提高三维CAD装配模型的重用水平，本文提出一种基于复杂网络的三维CAD装配模型模块单元发掘方法。本文方法在前期研究工作的基础上，融合装配零件的多源关联信息综合评价装配零件的关联强度，构建三维CAD装配模型的关联关系网络，并借助复杂网络的社区发现思想，设计一种基于CNM(Clauset-Newman-Moore)的三维CAD装配模型模块单元发掘算法，可以自动柔性地发掘三维装配模型所蕴含的模块单元知识。

1 三维CAD装配模型的关联关系网络

1.1 装配零件关联强度评价

装配体是指零件按照一定的装配约束组合在一起，使每个零件在装配体中具有特定的空间位置及拓扑形式，以满足产品设计的功能与性能的组合体。复杂机械三维CAD装配模型可能由多个不同的模块结构构成，同一模块的装配零件之间具有紧密的物理连接关系，并且能够共同实现产品的某些功能。复杂机械三维CAD装配模型模块知识发掘过程中综合考虑了零件之间的物理连接、功能关联关系及材料相似性关联，能够更加客观、定量地评价装配零件之间的关联强度[18]。

1.1.1装配结构关联分析

零件之间的连接与配合方式影响着装配结构的关联程度，以零件结构的可拆卸性与稳固性作为关联依据进行评价[16]，可实现零件之间装配结构关联强度Is(i，j)的评价，如表1所示。

表1 装配结构关联强度评价准则

1.1.2功能关联分析

装配产品的某一功能可能由一个或多个零件组合共同完成。三维装配模型模块知识可以是具有某种或多种功能的装配结构单元。通过分析零件之间的功能关联，可以将功能联系比较紧密的零件划分在同一模块单元内。零件之间的功能关联主要体现在任意两个装配零件在完成同一功能时的协同程度上[16]。例如，轴与键一起共同完成传递动力的功能时是缺一不可的，一般被认为具有较强的功能关联关系。为了有效评价零件之间的功能关联强度If(i，j)，给出零件之间的功能关联强度评价准则，如表2所示。

表2 功能关联强度评价准则

1.1.3材料相似性分析

材料类型影响着零件的设计与制造，材料相同的零件可能会采用相同的制造工艺或制造设备，所构成的装配结构模块更有利于制造与维护[8]，因此，材料相似性可以作为三维装配模型模块单元发掘的影响因素之一。材料相似性度Im(i，j)可表达为

(1)

1.1.4综合关联强度评价

从结构、功能、材料三个方面对三维装配模型中零件之间关联关系进行分析，并考虑三维装配模型中结构、功能、材料在模块单元中的重要程度，可以将零件之间的综合关联强度I(i，j)表达为

I(i，j)=ω1Is(i，j)+ω2If(i，j)+ω3Im(i，j)

(2)

式中，ω1、ω2、ω3分别为装配结构关联、功能关联与材料相似度的权重，且满足ω1+ω2+ω3=1。

由上可建立综合关联强度矩阵M：

(3)

式中，n为三维装配模型中装配零件数量；M为n×n阶对称矩阵，此矩阵可为三维装配模型的关联关系网络构建提供输入。

1.2 三维装配模型的关联关系网络构建

将三维CAD装配模型中装配零件作为网络节点，零件之间关联关系以网络边的形式描述，其本质上可以看作一种复杂网络系统。依据装配零件之间的综合关联矩阵M，运用复杂网络理论与方法，可以构建成一个无向加权网络N。装配零件之间的关联关系网络N可以表示为

N={V，E，W}

(4)

式中，V为关联关系网络N的节点集合，即装配零件集；E为该网络的边集合，即装配零件的关联关系；W为网络中边的权重集合，即综合关联强度。

关联关系网络N作为无向加权网络，能够较好地描述三维装配模型中零件之间的关联情况。利用复杂网络中社区发现算法可以对该关联关系网络进行社区发现，每个社区结构代表三维装配模型中一个子装配体或模块单元，进而实现三维装配模型中模块单元知识的发掘。为了方便理解社区发现算法，下面将引入邻接矩阵与模块度函数Q两个概念。

1.2.1邻接矩阵A

若关联关系网络N具有n个节点，则对应的邻接矩阵A的元素可表达为

(5)

式中，ωij表示节点i与j之间边的权重，即零件i、j的综合关联强度I(i，j)。

1.2.2模块度函数Q

模块发掘结果的好坏需要一定的标准衡量，模块度作为模块划分的一个有效指标，可以用来评价三维装配模型模块单元发掘是否合理。模块度函数Q是复杂网络中社区发现质量的评价指标，可以用来评价关联关系网络N社区结构发现质量。关联关系网络N的模块度Q[19]可表达为

(6)

(7)

(8)

(9)

(10)

式中，ω为关联关系网络N所有边的权重之和；ki为节点i的所有边权重之和；Ci、Cj为节点i、j所在社区结构；ΔQij为节点i与j合并时模块度增加量。

2 基于CNM社区发现的三维装配模型模块单元发现算法

以三维装配模型的关联关系网络模型为基础，借助复杂网络的社区发现算法，可以发现关联关系网络中的社区结构，进而实现三维CAD装配模型模块单元知识的发掘。

Fast Newman社区发现算法是一种基于凝聚的贪婪算法[20]，其算法过程是将网络N看成n个独立的社区结构，随后将n个社区结构不断两两合并，每次合并选择模块度增量最大的新社区结构，直到社区合并为一个社区；最后，根据模块度函数Q(k)(k=1，2，…，n)最大值确定最佳的社区结构数量，从而得到该网络的最佳社区结构。CNM算法以Fast Newman社区发现算法为基础[21]，采用堆的方式进行计算、更新网络的模块度，额外增加3个辅助数据结构，包括模块度增量矩阵、最大堆和辅助向量来提高算法效率，该算法的时间复杂度为O(nlog2n)，其中，n为网络的节点总数。基于改进CNM社区发现的三维装配模型模块单元发现算法步骤如下。

输入：关联关系网络N，邻接矩阵A；

输出：C(社区结构),Q(模块度函数)；

步骤(1)：初始化网络N中的n个节点作为独立的社区结构，令模块度Q=0；

步骤(2)：利用式(8)、式(9)计算网络N中边的总权重ω、社区结构中每个节点的边权重之和ki；

步骤(3)：合并具有邻接关系的任意2个社区结构，利用式(7)计算对应的模块度增量矩阵ΔQ；

步骤(4)：从最大堆中选取最大的模块度增量，将对应的两社区合并为一个社区并更新模块度矩阵等辅助数据结构；利用式(6)计算模块度函数Q(k)，k=n-1；

步骤(5)：判断社区数量k，若k=1，执行步骤(6)；反之，则执行步骤(2)～步骤(4)；

步骤(6)：以模块度函数Q(k)的最大值确定最佳的社区数量k，输出对应的社区结构与三维装配模型模块单元。

模块度本质上为某一社区结构内的所有边权重之和减去与该社区结构相连的边权重之和，模块度函数Q值越大，说明社团结构越明显。在实际网络社区发现中Q的最大值范围在0.3～0.7。模块度函数值随社区发现数量而变化，所以通过模块度函数可以确定最佳的社区结构数量，避免人工的主观干预。根据三维装配模型自身的装配拓扑结构、功能、材料等关联强度来自动实现模块单元知识的发掘，更能反映模块单元的内外规律与特性。

3 实例分析

以某蜗轮蜗杆减速器三维CAD装配模型为例，提取该三维CAD装配模型的装配关系信息，构建对应的关联关系加权网络模型，利用社区发现CNM算法进行蜗轮蜗杆减速器三维CAD装配模型模块单元知识发掘。图1为某蜗轮蜗杆减速器的三维CAD装配模型示意图，表3所示为该装配模型的零件信息。

图1 蜗轮蜗杆减速器三维装配模型示意图Fig.1 3D CAD assembly of worm reduction box

表3 蜗轮蜗杆减速器的零件信息

通过提取蜗轮蜗杆减速器三维CAD装配模型的装配约束、零件属性信息，可获得零件之间的连接关系信息，如表4所示。

表4 零件连接信息

3.1 零件关联强度评价

利用表1、表2、式(3)关联强度评价准则可对蜗轮蜗杆减速器三维装配模型中零件之间结构、功能及材料相似度的关联强度进行评价。蜗轮蜗杆减速器通过蜗轮齿轮啮合主要起到降速、转换力矩的作用。该三维装配模型的结构、功能信息对模块单元知识发现相对重要，材料可作为辅助参考因素。因此，对该类三维装配模型模块单元知识发掘时，可将结构、功能、材料相似度的权重设置为ω1=0.45，ω2=0.45，ω3=0.1。零件之间的综合关联强度I=0.45Is+0.45If+0.1Im。利用式(2)、式(3)可得到综合关联矩阵，如图2所示。

3.2 装配零件之间的关联关系网络

利用1.2节中关联关系网络构建流程，以综合关联强度矩阵M为基础，通过Gephi可视化工具建立蜗轮蜗杆减速器三维装配模型的关联关系网络N，如图3所示，其中每个节点编号代表零件序号，节点边线性的粗细程度表示边的权重大小。

图3 蜗轮蜗杆减速器的关联关系网络NFig.3 Correlation relationship network N of worm reduction

3.3 模块单元发掘

以MATLAB软件为平台实现了基于CNM社区发现算法编程，可以对蜗轮蜗杆减速器三维装配模型的零件关联关系网络N进行社区发现。社区发现过程如图4所示，其中，图4a表示关联关系网络N社区发现过程；图4b为CNM社区发现的模块度函数曲线。由模块度函数曲线可知，当社区结构数量k=4时，模块度Q取得最大值0.3642，从而可以确定蜗轮蜗杆减速器三维CAD装配模型模块单元发掘的最佳结果为4个模块单元，对应的模块单元零件集合为C1={v10，v11，v20，v21，v23，v24，v25，v26，v33}，C2={v1，v2，v5，v6，v7，v8，v9，v18，v19}，C3={v3，v4，v12，v13，v14，v15，v16，v17，v29}，C4={v22，v27，v28，v30，v31，v32}，模块单元发掘的最终结果如表5所示。表5中蜗轮蜗杆三维装配模型的模块单元发现结果，由于在关联强度评价时考虑了结构、功能、材料因素，所发掘的模块知识在设计-制造-装配过程中具有较高的实用性，与实际模块划分结果也比较吻合。如蜗轮-蜗轮轴模块，不仅在设计时考虑模块内零件(O形密封圈、轴套、键)的尺寸、参数信息，而且在制造、装配环节也可作为同一模块考虑其材料、采购、装配等指标；模块单元内所蕴含的设计、制造、装配相关知识能够帮助设计人员更好地理解、重用该三维装配模型。

(a)基于CNM的社区发现结果 (b)模块度Q函数

表5 模块知识发掘结果

为了进一步分析表2中强度指标与式(2)中权重因子对模块发掘结果的影响，分别对关联强度指标If与权重ω的数值调整，权重变化后模块发掘结果如表6所示。由表6可知，调整强度指标值If后模块发掘结果未变化，而调整权重ω后模块发掘结果发生了变化。强度指标值If对功能关联强度评价准则而言仅仅是数值上的差异，仅仅影响综合关联强度M的相对值，对模块划分结果影响不敏感。权重ω则直接影响综合关联强度M，对模块划分结果较为敏感。式(2)中权重因子的确定是模块划分的关键，影响着模块划分结果的准确性，因此对于权重ω来说需要主观历史经验与客观评价两者综合考虑来确定，以便能够更加准确地发掘三维装配模型中模块结构知识。本文权重ω的确定主要由设计者经验与层次分析法(AHP)来确定。

表6 强度指标If与权重ω对模块发掘的影响

3.4 方法比较

文献[18]Fast Newman算法时间复杂度为O((m+n)n)，其中，n为关联网络节点总数，m为网络总边数，本文所给算法时间复杂度较之有所降低，执行效率较高。文献[8]蚁群聚类方法将襟翼三维装配模型划分为6个模块，且蚁群算法时间复杂度为O(n2)，其中，n为关联关系网络中节点总数量；而通过本文方法发掘的最佳模块数量为3时模块度函数取得最大值，表明此时襟翼装配模型的模块内部具有更高的内聚度，模块间有较弱的耦合。两种方法运行结果对比如图5所示。

图5 本文方法与文献[8]方法对比Fig.5 Comparison between proposed method & reference[8]

为了进一步验证本文方法的普适性，以文献[16]中的柱塞泵为对象，利用本文方法对该柱塞泵三维装配模型模块单元进行发掘。该三维装配模型模块单元发掘过程如图6所示，由图6可知，柱塞泵三维装配模型模块单元发掘最佳模块数量为5，各模块所包含的零件分别为模块C1={1，2，17，20，25，40}，C2={3，5，8，14，23，35，37，38，39，41，42}，C3={4，6，11，12，15，16，36}，C4={7，9，10，13，18，19，26，29，30，34，43，44}和C5={21，22，23，24，27，28，31，32，33，39}。该模块发掘结果与文献[16]中模块划分结果相比，虽然模块1和模块5有部分零件存在差异，但整体来说比较吻合，本文与文献[16]中实例计算结果对比如表7所示。利用本文方法可以有效地发掘三维装配模型中的模块单元，还原三维产品模型的原有模块设计信息。

图6 柱塞泵三维装配模型模块单元发掘过程Fig.6 Modular units knowledge discovering process of 3D assembly model of piston pump

表7 本文方法与文献[16]中实例计算对比

总体而言，本文方法综合考虑了零件之间的物理关系、功能关系与材料相似度因素，符合产品设计-制造-装配过程中的实际操作需求，所提CNM社区发现算法易于编程实施，时间复杂度较低，可以满足设计者在产品设计不同阶段中三维装配模型模块单元知识发现与重用需求。

4 结论

(1)融合装配零件的结构、功能、材料关联信息，给出了三维CAD装配模型零件之间关联强度综合评价方法。

(2)基于复杂网络构建了三维CAD装配模型的关联关系网络；提出了一种基于CNM社区发现的三维装配模型模块单元发掘方法，该方法编程简单且易于实施，时间复杂度为O(nlog2n)。

(3)所提方法可以有效地发掘三维装配模型所蕴含的高质量模块单元知识，有助于提高设计者对三维装配模型模块知识的理解和重用水平。