三维CAD模型模块划分的蚁群聚类图分割方法

　　为了使三维CAD模型模块划分的结果保持较好的结构完整性，提出一种面向图分割的蚁群聚类算法。用属性连接图表示复杂的CAD模型并进行简化;通过对模型连接方式和零件属性的分析，获得零件的结构、功能和材料相关性并建立综合相关度矩阵;根据零件的连接层次系重构了蚁群聚类的局部范围界定和密度函数计算方法，实现了面向图分割的的蚁群聚类。采用上述方法对某型飞机襟翼模型进行模块划分，验证了所提方法的正确性和有效性。

　　引言

　　模块划分技术是模块化设计和大规模定制生产的基础，是满足客户多样化需求的有效手段，同时也可应用于三维计算机辅助设计(Computer　Aided Design，CAD)模型检索领域。由于产品级CAD模型具有零件多、结构复杂的特点，检索的计算量较大，以分而治之的思想将模型划分为有一定结构和功能意义的模块，并行地进行对应模块对比分析，能够降低检索的时间和空间复杂度。

　　目前，学者们已经提出了多种模块划分方法。其中：文献分析了零件之间的关联度后采用Pmedian方法进行模块划分;文献提出了基于启发式方法的图解模块划分方法;文献从零件交互角度进行了产品全生命周期的模块划分;文献利用模块驱动因素来定义设计需求和模块构建之间的联系;文献从产品全生命周期的角度分析零件的交互关系，并采用模糊聚类和模拟退火算法进行模块划分;文献以零件间物理和功能上的相关度为依据，基于蚁群聚类算法进行模块划分;文献通过信息熵理论综合衡量客户需求、产品的装配、成本和维修等因素，使用模糊聚类进行模块划分;文献以产品全生命周期中的各因素对产品零部件交互的影响为依据进行模块划分;文献综合模块聚合度、耦合度和设计需求趋同度建立了划分优化模型，并用遗传算法进行求解。上述方法主要面向客户定制生产和模块化设计，从用户需求和产品生命周期的角度出发分析零件的相关性，但只根据相关性还不足以完全表达复杂的拓扑连接结构，以此为依据划分的模块中还可能存在相互不连接的零件，从而造成模块内部结构不完整。

　　为解决上述问题，在模块划分时除了要分析零件相关性，还要考虑其拓扑连接关系，即在相关性和连接层次关系的共同影响下分析零件的耦合关系，以实现模块内聚合关系的最大化，同时保持结构的完整性，这样划分出的模块更有助于进行模块化设计，并能并行地进行结构相似性分析。因此，本文提出一种面向图分割的蚁群聚类算法，通过将模型转换为属性连接图，将模块划分问题转化为图分割问题;通过对零件功能、装配连接和材料的相关性分析，建立综合相关性矩阵并作为划分基础;面向图分割问题改进蚁群聚类算法，在保持子图连通性的情况下进行模块划分，最终使模块具有较为完整的结构和相对独立的功能。

　　1、零件相关性分析

　　CAD模型中存在模块化的结构，即属于同一模块的零件有紧密的连接关系，能共同作用并实现某项子功能。因此在进行模块划分时首先要对零件间的这种相关关系进行分析。为了便于分析，需要将包含多种几何、工程信息的CAD模型转换为图结构(如图1)，图中节点P 代表零件，边L 表示零件间的连接装配关系，然后附加划分所需的属性信息A(P)和A(L)，形成属性连接图G={P，L，A(P)，A(L)｝，如图1b所示。在此基础上分别从结构、功能和材料三个角度进行模型中零件的相关性分析，作为模块划分的依据。

　　4、结束语

　　本文分析了现有的模块划分方法在模型拓扑结构分析上的局限性，提出了基于图分割的模块划分方法，该方法将模型转换为属性连接图的形式，通过在图上进行蚁群聚类分析并进行图分割，最终达到将CAD模型划分为模块的目的。其中，通过分析零件的拓扑连接关系和功能、属性相关性得到综合相关性矩阵;根据图结构的特点提出了局部范围界定方法，避免了将空间距离远、连接间隔大的零件划分为同一模块的问题;改进了密度函数的计算方法，对局部范围中的零件按结构层次关系综合相关性，使聚类更有针对性。并以此建立了面向图分割的蚁群聚类算法。实例分析表明，所提方法能较好地对模型进行划分。由于模块划分的要求和目的不尽相同，后续研究中还需要对结构、功能和材料相关性的评价方法进行优化，使评价更加准确;并根据应用领域的不同，进一步丰富相关性分析的角度，以适应不同的模块划分。