基于遗传-蚁群算法的CAD产品快速建模

丁 博，于晓洋，孙立镌

1.测控技术与仪器黑龙江省高校重点实验室，哈尔滨 150080

2.哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080

3.哈尔滨理工大学 测控技术与通信工程学院，哈尔滨 150080

基于遗传-蚁群算法的CAD产品快速建模

丁 博1，2，3，于晓洋1，3，孙立镌2

1.测控技术与仪器黑龙江省高校重点实验室，哈尔滨 150080

2.哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080

3.哈尔滨理工大学 测控技术与通信工程学院，哈尔滨 150080

1 引言

三维CAD（Computer Aided Design）造型的产品设计与制造已经成为我国制造业的主流模式，由于三维CAD造型具有可视化、数字化和虚拟化等特点，使其成为产品开发各环节不可或缺的基础载体。目前，基于参数化的特征造型技术已经非常成熟[1]。大部分数字化造型设计软件都采用了参数化造型方法，在这些软件中设计人员通过修改特征参数来控制CAD产品的造型变化，每一步操作都需要设计人员的参与，显然这种方法是非常低效的[2]。如何通过设计人员提供的少量特征参数就可以方便、准确、快速地获取理想的三维CAD造型，并且造型的局部细节特征也能够同时获取是提高产品设计效率、缩短产品开发周期的关键。

智能化的产品设计方法主要用于优化设计方案，通过多方案的比较，择优而产生设计方案的最优解[3]。该方法可以使设计人员从复杂的局部美化设计当中解脱出来，简化建模过程。因此，采用智能化算法如遗传算法、粒子群优化算法和蚁群算法实现产品的快速建模成为一个全新的研究领域。国外开发的快速建模系统主要有：Kumiyo等人开发的IAM-eMMa系统和EVIDII系统[4]、Nishino等人开发的IEC系统[5]和美国普林斯顿大学形状检索与分析实验室开发的三维模型搜索引擎[6]。国内对快速建模技术也展开了研究，刘弘等人提出了一种支持外观造型创新设计的进化计算方法，但该方法仅支持简单产品的设计[7]。徐江等人提出了一种基于正交-交互式遗传算法的产品造型设计方法，该方法可以初步满足用户对产品造型设计的需求[8]。王军锋提出了一种基于遗传算法的产品造型设计阶梯求解法，通过改进的遗传算法搜索产品造型设计的最优解，逐级完成造型设计的细化设计[9]。张开兴提出了一种利用蚁群算法的三维CAD模型检索算法[10]。以上研究仅采用单一的智能化算法搜索产品造型设计的最优解，存在收敛效率和准确性不高的问题，同时，仍然需要设计人员的多次参与，容易造成设计人员的心理疲劳。

在此基础上，本文在充分分析CAD特征造型的基础上，采用特征依赖图（Feature Dependency Graph，FDG）表示CAD造型，通过遗传算法和蚁群算法相结合的方法检测FDG的最大节点集合，从而将CAD产品造型快速构模的问题转换成检测FDG的最大节点集合的问题。本文提出的CAD产品快速建模方法将遗传算法和蚁群算法有效结合起来，搜索产品造型设计的最优解。将遗传算法求得的次优解作为初始化信息素分布的依据，提高问题求解速度，通过蚁群算法提高问题求解精度，从而实现设计人员仅需提供的少量特征参数，就可以快速构建出完整的造型，自动完成造型的细化设计，实现特征建模的智能化。

2 CAD造型的特征依赖图表示

特征造型技术是CAD建模的主流技术，特征造型的体系结构是一种三层结构：底层是数据模型，这个数据模型用特征依赖图（Feature Dependency Graph，FDG）表示，FDG包含了造型中的所有特征以及特征间的依赖关系，提供了造型的高层结构[11]；中间层是细胞元几何模型，它能够完整地把特征显示出来，但它不是面向用户的，属于过渡性几何模型；最上层是视图模型，视图是根据用户的需要，如面向生产，面向加工等，从细胞元几何模型映射出来的模型，面向终端用户，最接近真实效果。

FDG由节点和有向边两部分组成，是一个非循环的有向图，其中节点表示特征，有向边表示约束关系。有向边的终点（即箭头所指方向）是子特征，始点是父特征，有向边表示特征之间存在直接特征依赖关系。直接特征依赖关系属于一种单向的驱动关系，即父特征驱动子特征。处于特征依赖图最顶端的节点所对应的特征是祖先特征，最底端的节点所对应的特征是叶子特征。特征依赖图的形式化定义为：FDG=(V，E)，其中，V={1，2，…，n}是特征依赖图的节点集合，E⊆V×V是特征依赖图的边集，特征依赖图如图1所示。

CAD造型把参数化、变量化的基本图元作为特征，使用特征组合构造零件的几何形状。一个CAD造型是由若干特征组成的，各特征之间相对独立。每个特征又包含若干不同的特征水平Fij，例如一个长方体特征，它包含特征水平有不含附加特征长方体、带圆角长方体和带倒角长方体。造型特征矩阵如下所示：

图1 特征依赖图实例

其中，n为造型特征数，m为造型特征中最大的特征水平数，n，m，i，j均为正整数，且1≤i≤n，1≤j≤m。

如果一个模型由三个特征组成，分别用F1、F2、F3表示，F1有三个特征水平，F2和F3分别有两个特征水平，那么造型特征矩阵为：

3 遗传-蚁群算法

遗传算法（Genetic Algorithm，GA）是一种产生最早、影响最大的随机搜索与优化算法。它采用达尔文进化论的适者生存、优胜劣汰的进化思想[12]。作为一种全局搜索方法，具有自适应性好、鲁棒性和通用性等优点[13]。目前，遗传算法在机器学习、模式识别和图像处理等领域都得到了广泛应用。

蚁群算法（Ant Colony Optimization，ACO）是从自然界蚂蚁觅食行为中得到启发而产生的，最初用来解决旅行商问题[14]。蚁群算法具有很强的鲁棒性和搜索较好解的能力，并且易于并行实现[15]。目前，蚁群算法作为一种全新的模拟进化优化方法得到了广泛的应用。

遗传算法和蚁群算法从概念上都属于随机优化算法，并且二者都具备全局搜索、概率随机搜索和易于与其他算法相结合的优点。但是，遗传算法和蚁群算法都可能陷入局部最优。同时，遗传算法还具有计算量大和稳定性差等缺点，导致求解精度和效率低。蚁群算法一般需要较长的搜索时间，而且该方法容易出现停滞现象。

3.1 算法基本思想

本文将遗传算法和蚁群算法有效结合起来，将两个算法的优势进行融合，提出了一种基于混合遗传蚁群算法的CAD产品快速建模方法。遗传-蚁群算法的互补优势在于：（1）蚁群算法可以弥补遗传算法求解精度低的问题，提高求解精度；（2）遗传算法可以适当弥补蚁群算法求解速度慢的问题，提高求解速度。因为蚁群算法在缺乏初始信息素分布时，需要较长的搜索时间，有时甚至出现停滞现象，所以首先使用遗传算法，利用遗传算法的随机性和快速收敛性，生成CAD造型的次优解，再将求得的次优解作为蚁群算法的初始信息素分布，利用蚁群算法的全局收敛能力和并行正反馈对次优解进行优化，最终生成CAD造型的最优解，实现CAD产品造型的快速建模，并自动完成造型的细化设计。

3.2 次优解和最优解的生成算法

3.2.1 基于遗传算法的次优解的生成

（1）生成初始种群：根据设计人员提供的造型特征F= {F1，F2，…，Fn}初始化种群。

（2）编码：产品造型的染色体编码采用由Holland提出的二进制法，即将特征水平Fij进行二进制编码，建立特征水平集合与二进制编码集的映射关系。若某产品含k个特征，且在特征Fi中某水平对应编码为0010，则该水平为Fi中第二个特征水平Fi2，图2表示了由一组特征水平组成的一个模型。

图2 染色体编码示意图

同理，当遗传结束获得满意解时，根据此编码方式可以找到满意解所相应的造型特征水平组合，解码对应问题的解为：{F1j1，F2j2，…，Fkjn}，1≤j1，j2，…，jn≤k，且j1，j2，jn，k为正整数。

（3）适应度函数：CAD产品造型由若干特征组成，特征之间存在主客关系，主特征因素驱动客特征因素。实现快速建模的基础就是：以主特征为主，综合考虑所有的特征。这样有利于算法收敛速度的提高，也是找到实际最优解所必需的。因此，含有主特征的个体，适应度值越大，越容易被选择。按照特征之间的主客关系，设定特征的分值数列{Ti}(i=1，2，…，n)，令祖先特征的数值最大Tmax= {Tq;Tq≥Ti，i=1，2，…，n}，叶子特征的数值最小Tmin={Tp;Tp≤Ti，i=1，2，…，n}。设叶子特征的数值为1，其父特征的数值为2，以此类推，每高一个层次的特征数值加1。然后对特征分值进行[0，1]标准化：

其中i，n均为正整数，1≤i≤n。

（4）选择：采用轮盘赌。

（5）交叉：对适应值较高的染色体个体，随机地选取一个截断点，将母代（所选的两个个体）编码链截断，互换从该截断点起的末尾部分或其他部分生成后代。

（6）变异：随机选取交叉产生个体中的某一位（或多位）进行一进制编码翻转操作。

3.2.2 基于蚁群算法的最优解的生成

通过遗传算法求得次优解F′={F′1，F′2，…，F′n}，依据次优解对蚁群算法进行初始信息素分布，进一步求得最优解。本文以特征依赖图为基础，构建了基于特征依赖图的信息素模型，令信息素模型为Φ(τ1，τ2，…，τn)，其中n=||V，τi表示节点i上积累的信息素的数量，初始值依据遗传算法求得的次优解给出，其值越大意味着该节点被选择的概率越大。某一节点被选中，也就是意味着该节点所对应的特征被选中。被遗传算法选中的节点的信息素初始值设为τ0，未被选中的节点的信息素初始值设为τ′0，且τ0＞τ′0。

定义1（极大节点集合）一个两两之间有边的节点集合，如果该集合不被其他任一个集合所包含，即它不是其他任一集合的真子集，则该集合为特征依赖图的极大节点集合。

定义2（最大节点集合）节点最多的极大节点集合称为特征依赖图的最大节点集合。

蚂蚁k从当前某一信息素浓度较高的节点开始搜索，每增加一个新的节点，相应的当前节点集合Sc进行扩展，直到成为一个极大节点集合。增加的节点是概率选择的，每个节点被选择的概率为：

其中，τi表示节点i上积累的信息素的数量，参数α决定了信息素对路径选择的影响力。

当任意一个蚂蚁k构造完成一个极大节点集合Sc后进行局部信息素更新，信息素的数量按如下公式进行更新。

其中，Sb为初始化最大节点集合，该集合由遗传算法的次优解求得。局部信息素更新的目的在于增加算法在一次迭代过程中解的多样性，从而间接地指导后继蚂蚁选择那些尚未选择的路径，搜索尚未探索的解空间区域。

当所有蚂蚁都构造完一个极大节点集合后，根据Sc计算本次迭代最优解Sop，并根据Sop判断Sb是否需要更新，如果需要更新，按如下公式进行全局信息素更新。

其中，ρ为信息素挥发系数，ω为固定常数，作用是对当前为止最优解上的信息素加强ω倍。全局信息素更新的目的是增加那些属于本次最优解节点上的信息素的数量，使得下一次迭代过程中蚂蚁们能够朝向本次迭代产生的最优解的临近区域进行搜索。全局信息素更新完成后继续迭代，直到找到最优解或算法达到最大迭代次数。通过遗传-蚁群算法求得的最优解得出若干个CAD造型，由用户选择最终造型。

4 算法验证

采用Bespalov等人开发的CAD模型基准库NDR（National Design Repository）[16]验证本文提出的基于遗传-蚁群算法的CAD产品的快速建模方法。NDR对典型CAD模型划分类别，其中包含共700多个各类代表性CAD模型。在实验过程中，遗传-蚁群算法的参数设置为：α=1，ρ=0.90，ω=2，τ0=0.02，τ′0=0.01，最大迭代次数为2 000，蚁群中蚂蚁数目为10。

通过对螺栓的设计，验证本文提出的基于遗传-蚁群算法的CAD产品快速建模方法。螺栓的类型有两种：内六角螺栓和外六角螺栓。螺栓由螺帽和螺杆两个特征组成，螺帽的类型有圆形螺帽和六角螺帽，螺杆的类型有全螺纹螺杆和部分螺纹螺杆，同时定义一个螺栓要给出大径和长度的数值。图3为设计人员给定的特征水平和初始特征参数，作为该造型的大致设计意向，程序在此参数的基础上通过遗传-蚁群算法得到最优方案群，图4为自动生成的4个造型设计方案，最后由设计人员确定最终方案。

图3 初始特征水平参数

图4 基于遗传-蚁群算法的造型设计方案

将本文的算法与文献[7]中所提出的遗传算法进行比较，如图4和图5所示，从检索结果中可以看出，本文算法可以搜索出更多符合设计意图的造型供用户选择，同时，搜索出的造型包含了造型的细节特征，因此造型更加满足用户的需求。为了充分对比两种算法的性能，本文对基准库中的CAD模型进行统计测试，获得了一个平均查全率-查准率曲线，如图6所示，可以看出，本文算法可以搜索到产品的最优化造型设计，性能明显高于普通的遗传算法。

图5 基于普通遗传算法的造型设计方案

图6 两种算法的查全率-查准率曲线

5 结论

本文提出一种三维CAD模型的快速建模方法。首先将CAD模型用FDG表示，然后采用遗传算法和蚁群算法相结合的混合算法，获取完整的CAD模型。实验结果表明，该算法具有良好的全局收敛效率和求解精度，快速构建的模型符合用户的需求。经验证，本文算法的综合性能要明显地高于单一采用遗传算法的产品快速建模方法。

[1]Yang L，Ong S K，Nee A Y C.A new history-independent modeling approach for feature-based design[J].Adv Manuf Τechnol，2012，59：841-858.

[2]路通.三维CAD模型检索综述[J].计算机科学，2012，39（4）：14-22.

[3]Yang Ping.Τopological expression mode approach of satellite gear mechanism for intelligent CAD[J].International Journal of Manufacturing Τechnology and Management，2008，14（1/2）：110-117.

[4]Kumiyo N，Yasuhiro Y，Masao O.Computational support for collective creativity[J].Knowledge-Based Systems，2000，13（7）：451-458.

[5]Nishino H，Τakagi H，Cho Sung-Bae，et al.A 3D modeling system for creative design[C]//Proceedings of the 15th International Conference on Information Networking，2001：479-486.

[6]Funkhouser Τ，Min P，Kazhdan M.A search engine for 3D models[J].ACM Τransactions on Graphics，2003（1）：83-105.

[7]刘弘，刘希玉.支持外观造型创新设计的进化计算方法[J].计算机辅助设计与图形学学报，2006，18（1）：101-107.

[8]徐江，孙守迁.基于正交-交互式遗传算法的产品造型设计[J].计算机集成制造系统，2007，13（8）：1470-1475.

[9]王军锋.基于遗传算法的产品造型设计阶梯求解法[J].工程图学学报，2011（1）：5-9.

[10]张开兴，张树生，李亮.基于蚁群算法的三维CAD模型检索[J].计算机辅助设计与图形学学报，2011，23（4）：633-639.

[11]Bidarra R，Bronsvoort W F.Semantic feature modelling[J]. Computer Aided Design，2000，32（4）：201-225.

[12]刘全，王晓燕，傅启明.双精英协同进化遗传算法[J].软件学报，2012，23（4）：765-775.

[13]闫利军，申清明，刘敏，等.产品设计规划问题建模及遗传算法求解[J].计算机工程与应用，2013，49（1）：67-71.

[14]Csorba M J，Meling H，Heegaard P E.Ant system for service deployment in private and public clouds[C]//Proceedings of the 2nd Workshop on Bio-inspired Algorithms for Distributed Systems，BADS’10，2010：19-28.

[15]Sarhadi H，Ghoseiri K.An ant colony system approach for fuzzy travelling salesman problem with time windows[J]. Int J Adv Manuf Τechnol，2010，50：1203-1215.

[16]Bespalov D，Ip Y，Regli W，et al.Benchmarking CAD search techniques[C]//Proceedings of the 2005 ACM Symposium on Solid and Physical Modeling，2005：275-286.

DING Bo1，2，3,YU Xiaoyang1，3,SUN Lijuan2

1.Τhe Higher Educational Key Lab for Measuring and Control Τechnology and Instrumentations of Heilongjiang Province,Harbin 150080,China
2.College of Computer Science and Τechnology,Harbin University of Science and Τechnology,Harbin 150080,China
3.College of Measure-control Τechnology and Communication Engineering,Harbin University of Science and Τechnology,Harbin 150080,China

Τo improve the design efficiency of CAD modeling,a fast modeling approach of CAD product which combines Genetic Algorithm（GA）and Ant Colony Optimization（ACO）is proposed.GA is adopted to obtain suboptimal solutions.Τhe pheromone of ACO is initialized according to the suboptimal solutions,and then a further search among the suboptimal solutions is operated for better solution.And finally,the optimal solutions of the product design can be searched.Τhe hybrid approach is accomplished in convergence efficiency and solution precision.Experimental results show that,the algorithm can seek the modeling containing detail characteristics and satisfy user’s personalized need.

fast modeling;Computer Aided Design（CAD）products design;Genetic Algorithm（GA）;Ant Colony Optimization（ACO）algorithm

为提高CAD造型的设计效率，提出一种基于遗传-蚁群算法的CAD产品快速建模方法，该方法采用遗传算法求得次优解，依据求得的次优解对蚁群算法进行初始信息素分布，在次优解中进一步寻优，最终搜索到产品造型设计的最优解。遗传算法和蚁群算法的有效结合，使算法具有较好的全局收敛效率和求解精度。实验结果表明，该算法搜索出来的造型包含造型的细节特征，更加满足用户的个性化需要。

快速建模；计算机辅助设计（CAD）产品设计；遗传算法；蚁群算法

A

ΤP391

10.3778/j.issn.1002-8331.1211-0066

DING Bo,YU Xiaoyang,SUN Lijuan.GA-ACO for fast modeling of CAD product.Computer Engineering and Applications,2013,49（15）：10-13.

国家自然科学基金（No.60173055）；黑龙江省自然科学基金（No.G201207）。

丁博（1983—），女，博士后，讲师，主要研究方向为计算机图形学与CAD；于晓洋（1962—），男，博士，教授，博导，主要研究方向为三维视觉检测；孙立镌（1944—），男，教授，博导，主要研究方向为计算机图形学与CAD。E-mail：dingbo@hrbust.edu.cn

2012-11-06

2013-04-17

1002-8331（2013）15-0010-04

CNKI出版日期：2013-05-03 http://www.cnki.net/kcms/detail/11.2127.ΤP.20130503.1707.010.html