丁 博，于曉洋，孫立鐫

1.測控技術(shù)與儀器黑龍江省高校重點實驗室，哈爾濱 150080

2.哈爾濱理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

3.哈爾濱理工大學(xué) 測控技術(shù)與通信工程學(xué)院，哈爾濱 150080

基于遺傳-蟻群算法的CAD產(chǎn)品快速建模

丁 博1，2，3，于曉洋1，3，孫立鐫2

1.測控技術(shù)與儀器黑龍江省高校重點實驗室，哈爾濱 150080

2.哈爾濱理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

3.哈爾濱理工大學(xué) 測控技術(shù)與通信工程學(xué)院，哈爾濱 150080

1 引言

三維CAD（Computer Aided Design）造型的產(chǎn)品設(shè)計與制造已經(jīng)成為我國制造業(yè)的主流模式，由于三維CAD造型具有可視化、數(shù)字化和虛擬化等特點，使其成為產(chǎn)品開發(fā)各環(huán)節(jié)不可或缺的基礎(chǔ)載體。目前，基于參數(shù)化的特征造型技術(shù)已經(jīng)非常成熟[1]。大部分數(shù)字化造型設(shè)計軟件都采用了參數(shù)化造型方法，在這些軟件中設(shè)計人員通過修改特征參數(shù)來控制CAD產(chǎn)品的造型變化，每一步操作都需要設(shè)計人員的參與，顯然這種方法是非常低效的[2]。如何通過設(shè)計人員提供的少量特征參數(shù)就可以方便、準確、快速地獲取理想的三維CAD造型，并且造型的局部細節(jié)特征也能夠同時獲取是提高產(chǎn)品設(shè)計效率、縮短產(chǎn)品開發(fā)周期的關(guān)鍵。

智能化的產(chǎn)品設(shè)計方法主要用于優(yōu)化設(shè)計方案，通過多方案的比較，擇優(yōu)而產(chǎn)生設(shè)計方案的最優(yōu)解[3]。該方法可以使設(shè)計人員從復(fù)雜的局部美化設(shè)計當(dāng)中解脫出來，簡化建模過程。因此，采用智能化算法如遺傳算法、粒子群優(yōu)化算法和蟻群算法實現(xiàn)產(chǎn)品的快速建模成為一個全新的研究領(lǐng)域。國外開發(fā)的快速建模系統(tǒng)主要有：Kumiyo等人開發(fā)的IAM-eMMa系統(tǒng)和EVIDII系統(tǒng)[4]、Nishino等人開發(fā)的IEC系統(tǒng)[5]和美國普林斯頓大學(xué)形狀檢索與分析實驗室開發(fā)的三維模型搜索引擎[6]。國內(nèi)對快速建模技術(shù)也展開了研究，劉弘等人提出了一種支持外觀造型創(chuàng)新設(shè)計的進化計算方法，但該方法僅支持簡單產(chǎn)品的設(shè)計[7]。徐江等人提出了一種基于正交-交互式遺傳算法的產(chǎn)品造型設(shè)計方法，該方法可以初步滿足用戶對產(chǎn)品造型設(shè)計的需求[8]。王軍鋒提出了一種基于遺傳算法的產(chǎn)品造型設(shè)計階梯求解法，通過改進的遺傳算法搜索產(chǎn)品造型設(shè)計的最優(yōu)解，逐級完成造型設(shè)計的細化設(shè)計[9]。張開興提出了一種利用蟻群算法的三維CAD模型檢索算法[10]。以上研究僅采用單一的智能化算法搜索產(chǎn)品造型設(shè)計的最優(yōu)解，存在收斂效率和準確性不高的問題，同時，仍然需要設(shè)計人員的多次參與，容易造成設(shè)計人員的心理疲勞。

在此基礎(chǔ)上，本文在充分分析CAD特征造型的基礎(chǔ)上，采用特征依賴圖（Feature Dependency Graph，F(xiàn)DG）表示CAD造型，通過遺傳算法和蟻群算法相結(jié)合的方法檢測FDG的最大節(jié)點集合，從而將CAD產(chǎn)品造型快速構(gòu)模的問題轉(zhuǎn)換成檢測FDG的最大節(jié)點集合的問題。本文提出的CAD產(chǎn)品快速建模方法將遺傳算法和蟻群算法有效結(jié)合起來，搜索產(chǎn)品造型設(shè)計的最優(yōu)解。將遺傳算法求得的次優(yōu)解作為初始化信息素分布的依據(jù)，提高問題求解速度，通過蟻群算法提高問題求解精度，從而實現(xiàn)設(shè)計人員僅需提供的少量特征參數(shù)，就可以快速構(gòu)建出完整的造型，自動完成造型的細化設(shè)計，實現(xiàn)特征建模的智能化。

2 CAD造型的特征依賴圖表示

特征造型技術(shù)是CAD建模的主流技術(shù)，特征造型的體系結(jié)構(gòu)是一種三層結(jié)構(gòu)：底層是數(shù)據(jù)模型，這個數(shù)據(jù)模型用特征依賴圖（Feature Dependency Graph，F(xiàn)DG）表示，F(xiàn)DG包含了造型中的所有特征以及特征間的依賴關(guān)系，提供了造型的高層結(jié)構(gòu)[11]；中間層是細胞元幾何模型，它能夠完整地把特征顯示出來，但它不是面向用戶的，屬于過渡性幾何模型；最上層是視圖模型，視圖是根據(jù)用戶的需要，如面向生產(chǎn)，面向加工等，從細胞元幾何模型映射出來的模型，面向終端用戶，最接近真實效果。

FDG由節(jié)點和有向邊兩部分組成，是一個非循環(huán)的有向圖，其中節(jié)點表示特征，有向邊表示約束關(guān)系。有向邊的終點（即箭頭所指方向）是子特征，始點是父特征，有向邊表示特征之間存在直接特征依賴關(guān)系。直接特征依賴關(guān)系屬于一種單向的驅(qū)動關(guān)系，即父特征驅(qū)動子特征。處于特征依賴圖最頂端的節(jié)點所對應(yīng)的特征是祖先特征，最底端的節(jié)點所對應(yīng)的特征是葉子特征。特征依賴圖的形式化定義為：FDG=(V，E)，其中，V={1，2，…，n}是特征依賴圖的節(jié)點集合，E?V×V是特征依賴圖的邊集，特征依賴圖如圖1所示。

CAD造型把參數(shù)化、變量化的基本圖元作為特征，使用特征組合構(gòu)造零件的幾何形狀。一個CAD造型是由若干特征組成的，各特征之間相對獨立。每個特征又包含若干不同的特征水平Fij，例如一個長方體特征，它包含特征水平有不含附加特征長方體、帶圓角長方體和帶倒角長方體。造型特征矩陣如下所示：

圖1 特征依賴圖實例

其中，n為造型特征數(shù)，m為造型特征中最大的特征水平數(shù)，n，m，i，j均為正整數(shù)，且1≤i≤n，1≤j≤m。

如果一個模型由三個特征組成，分別用F1、F2、F3表示，F(xiàn)1有三個特征水平，F(xiàn)2和F3分別有兩個特征水平，那么造型特征矩陣為：

3 遺傳-蟻群算法

遺傳算法（Genetic Algorithm，GA）是一種產(chǎn)生最早、影響最大的隨機搜索與優(yōu)化算法。它采用達爾文進化論的適者生存、優(yōu)勝劣汰的進化思想[12]。作為一種全局搜索方法，具有自適應(yīng)性好、魯棒性和通用性等優(yōu)點[13]。目前，遺傳算法在機器學(xué)習(xí)、模式識別和圖像處理等領(lǐng)域都得到了廣泛應(yīng)用。

蟻群算法（Ant Colony Optimization，ACO）是從自然界螞蟻覓食行為中得到啟發(fā)而產(chǎn)生的，最初用來解決旅行商問題[14]。蟻群算法具有很強的魯棒性和搜索較好解的能力，并且易于并行實現(xiàn)[15]。目前，蟻群算法作為一種全新的模擬進化優(yōu)化方法得到了廣泛的應(yīng)用。

遺傳算法和蟻群算法從概念上都屬于隨機優(yōu)化算法，并且二者都具備全局搜索、概率隨機搜索和易于與其他算法相結(jié)合的優(yōu)點。但是，遺傳算法和蟻群算法都可能陷入局部最優(yōu)。同時，遺傳算法還具有計算量大和穩(wěn)定性差等缺點，導(dǎo)致求解精度和效率低。蟻群算法一般需要較長的搜索時間，而且該方法容易出現(xiàn)停滯現(xiàn)象。

3.1 算法基本思想

本文將遺傳算法和蟻群算法有效結(jié)合起來，將兩個算法的優(yōu)勢進行融合，提出了一種基于混合遺傳蟻群算法的CAD產(chǎn)品快速建模方法。遺傳-蟻群算法的互補優(yōu)勢在于：（1）蟻群算法可以彌補遺傳算法求解精度低的問題，提高求解精度；（2）遺傳算法可以適當(dāng)彌補蟻群算法求解速度慢的問題，提高求解速度。因為蟻群算法在缺乏初始信息素分布時，需要較長的搜索時間，有時甚至出現(xiàn)停滯現(xiàn)象，所以首先使用遺傳算法，利用遺傳算法的隨機性和快速收斂性，生成CAD造型的次優(yōu)解，再將求得的次優(yōu)解作為蟻群算法的初始信息素分布，利用蟻群算法的全局收斂能力和并行正反饋對次優(yōu)解進行優(yōu)化，最終生成CAD造型的最優(yōu)解，實現(xiàn)CAD產(chǎn)品造型的快速建模，并自動完成造型的細化設(shè)計。

3.2 次優(yōu)解和最優(yōu)解的生成算法

3.2.1 基于遺傳算法的次優(yōu)解的生成

（1）生成初始種群：根據(jù)設(shè)計人員提供的造型特征F= {F1，F(xiàn)2，…，F(xiàn)n}初始化種群。

（2）編碼：產(chǎn)品造型的染色體編碼采用由Holland提出的二進制法，即將特征水平Fij進行二進制編碼，建立特征水平集合與二進制編碼集的映射關(guān)系。若某產(chǎn)品含k個特征，且在特征Fi中某水平對應(yīng)編碼為0010，則該水平為Fi中第二個特征水平Fi2，圖2表示了由一組特征水平組成的一個模型。

圖2 染色體編碼示意圖

同理，當(dāng)遺傳結(jié)束獲得滿意解時，根據(jù)此編碼方式可以找到滿意解所相應(yīng)的造型特征水平組合，解碼對應(yīng)問題的解為：{F1j1，F(xiàn)2j2，…，F(xiàn)kjn}，1≤j1，j2，…，jn≤k，且j1，j2，jn，k為正整數(shù)。

（3）適應(yīng)度函數(shù)：CAD產(chǎn)品造型由若干特征組成，特征之間存在主客關(guān)系，主特征因素驅(qū)動客特征因素。實現(xiàn)快速建模的基礎(chǔ)就是：以主特征為主，綜合考慮所有的特征。這樣有利于算法收斂速度的提高，也是找到實際最優(yōu)解所必需的。因此，含有主特征的個體，適應(yīng)度值越大，越容易被選擇。按照特征之間的主客關(guān)系，設(shè)定特征的分值數(shù)列{Ti}(i=1，2，…，n)，令祖先特征的數(shù)值最大Tmax= {Tq;Tq≥Ti，i=1，2，…，n}，葉子特征的數(shù)值最小Tmin={Tp;Tp≤Ti，i=1，2，…，n}。設(shè)葉子特征的數(shù)值為1，其父特征的數(shù)值為2，以此類推，每高一個層次的特征數(shù)值加1。然后對特征分值進行[0，1]標準化：

其中i，n均為正整數(shù)，1≤i≤n。

（4）選擇：采用輪盤賭。

（5）交叉：對適應(yīng)值較高的染色體個體，隨機地選取一個截斷點，將母代（所選的兩個個體）編碼鏈截斷，互換從該截斷點起的末尾部分或其他部分生成后代。

（6）變異：隨機選取交叉產(chǎn)生個體中的某一位（或多位）進行一進制編碼翻轉(zhuǎn)操作。

3.2.2 基于蟻群算法的最優(yōu)解的生成

通過遺傳算法求得次優(yōu)解F′={F′1，F(xiàn)′2，…，F(xiàn)′n}，依據(jù)次優(yōu)解對蟻群算法進行初始信息素分布，進一步求得最優(yōu)解。本文以特征依賴圖為基礎(chǔ)，構(gòu)建了基于特征依賴圖的信息素模型，令信息素模型為Φ(τ1，τ2，…，τn)，其中n=||V，τi表示節(jié)點i上積累的信息素的數(shù)量，初始值依據(jù)遺傳算法求得的次優(yōu)解給出，其值越大意味著該節(jié)點被選擇的概率越大。某一節(jié)點被選中，也就是意味著該節(jié)點所對應(yīng)的特征被選中。被遺傳算法選中的節(jié)點的信息素初始值設(shè)為τ0，未被選中的節(jié)點的信息素初始值設(shè)為τ′0，且τ0＞τ′0。

定義1（極大節(jié)點集合）一個兩兩之間有邊的節(jié)點集合，如果該集合不被其他任一個集合所包含，即它不是其他任一集合的真子集，則該集合為特征依賴圖的極大節(jié)點集合。

定義2（最大節(jié)點集合）節(jié)點最多的極大節(jié)點集合稱為特征依賴圖的最大節(jié)點集合。

螞蟻k從當(dāng)前某一信息素濃度較高的節(jié)點開始搜索，每增加一個新的節(jié)點，相應(yīng)的當(dāng)前節(jié)點集合Sc進行擴展，直到成為一個極大節(jié)點集合。增加的節(jié)點是概率選擇的，每個節(jié)點被選擇的概率為：

其中，τi表示節(jié)點i上積累的信息素的數(shù)量，參數(shù)α決定了信息素對路徑選擇的影響力。

當(dāng)任意一個螞蟻k構(gòu)造完成一個極大節(jié)點集合Sc后進行局部信息素更新，信息素的數(shù)量按如下公式進行更新。

其中，Sb為初始化最大節(jié)點集合，該集合由遺傳算法的次優(yōu)解求得。局部信息素更新的目的在于增加算法在一次迭代過程中解的多樣性，從而間接地指導(dǎo)后繼螞蟻選擇那些尚未選擇的路徑，搜索尚未探索的解空間區(qū)域。

當(dāng)所有螞蟻都構(gòu)造完一個極大節(jié)點集合后，根據(jù)Sc計算本次迭代最優(yōu)解Sop，并根據(jù)Sop判斷Sb是否需要更新，如果需要更新，按如下公式進行全局信息素更新。

其中，ρ為信息素揮發(fā)系數(shù)，ω為固定常數(shù)，作用是對當(dāng)前為止最優(yōu)解上的信息素加強ω倍。全局信息素更新的目的是增加那些屬于本次最優(yōu)解節(jié)點上的信息素的數(shù)量，使得下一次迭代過程中螞蟻們能夠朝向本次迭代產(chǎn)生的最優(yōu)解的臨近區(qū)域進行搜索。全局信息素更新完成后繼續(xù)迭代，直到找到最優(yōu)解或算法達到最大迭代次數(shù)。通過遺傳-蟻群算法求得的最優(yōu)解得出若干個CAD造型，由用戶選擇最終造型。

4 算法驗證

采用Bespalov等人開發(fā)的CAD模型基準庫NDR（National Design Repository）[16]驗證本文提出的基于遺傳-蟻群算法的CAD產(chǎn)品的快速建模方法。NDR對典型CAD模型劃分類別，其中包含共700多個各類代表性CAD模型。在實驗過程中，遺傳-蟻群算法的參數(shù)設(shè)置為：α=1，ρ=0.90，ω=2，τ0=0.02，τ′0=0.01，最大迭代次數(shù)為2 000，蟻群中螞蟻數(shù)目為10。

通過對螺栓的設(shè)計，驗證本文提出的基于遺傳-蟻群算法的CAD產(chǎn)品快速建模方法。螺栓的類型有兩種：內(nèi)六角螺栓和外六角螺栓。螺栓由螺帽和螺桿兩個特征組成，螺帽的類型有圓形螺帽和六角螺帽，螺桿的類型有全螺紋螺桿和部分螺紋螺桿，同時定義一個螺栓要給出大徑和長度的數(shù)值。圖3為設(shè)計人員給定的特征水平和初始特征參數(shù)，作為該造型的大致設(shè)計意向，程序在此參數(shù)的基礎(chǔ)上通過遺傳-蟻群算法得到最優(yōu)方案群，圖4為自動生成的4個造型設(shè)計方案，最后由設(shè)計人員確定最終方案。

圖3 初始特征水平參數(shù)

圖4 基于遺傳-蟻群算法的造型設(shè)計方案

將本文的算法與文獻[7]中所提出的遺傳算法進行比較，如圖4和圖5所示，從檢索結(jié)果中可以看出，本文算法可以搜索出更多符合設(shè)計意圖的造型供用戶選擇，同時，搜索出的造型包含了造型的細節(jié)特征，因此造型更加滿足用戶的需求。為了充分對比兩種算法的性能，本文對基準庫中的CAD模型進行統(tǒng)計測試，獲得了一個平均查全率-查準率曲線，如圖6所示，可以看出，本文算法可以搜索到產(chǎn)品的最優(yōu)化造型設(shè)計，性能明顯高于普通的遺傳算法。

圖5 基于普通遺傳算法的造型設(shè)計方案

圖6 兩種算法的查全率-查準率曲線

5 結(jié)論

本文提出一種三維CAD模型的快速建模方法。首先將CAD模型用FDG表示，然后采用遺傳算法和蟻群算法相結(jié)合的混合算法，獲取完整的CAD模型。實驗結(jié)果表明，該算法具有良好的全局收斂效率和求解精度，快速構(gòu)建的模型符合用戶的需求。經(jīng)驗證，本文算法的綜合性能要明顯地高于單一采用遺傳算法的產(chǎn)品快速建模方法。

[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].計算機科學(xué)，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]劉弘，劉希玉.支持外觀造型創(chuàng)新設(shè)計的進化計算方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2006，18（1）：101-107.

[8]徐江，孫守遷.基于正交-交互式遺傳算法的產(chǎn)品造型設(shè)計[J].計算機集成制造系統(tǒng)，2007，13（8）：1470-1475.

[9]王軍鋒.基于遺傳算法的產(chǎn)品造型設(shè)計階梯求解法[J].工程圖學(xué)學(xué)報，2011（1）：5-9.

[10]張開興，張樹生，李亮.基于蟻群算法的三維CAD模型檢索[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2011，23（4）：633-639.

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

[12]劉全，王曉燕，傅啟明.雙精英協(xié)同進化遺傳算法[J].軟件學(xué)報，2012，23（4）：765-775.

[13]閆利軍，申清明，劉敏，等.產(chǎn)品設(shè)計規(guī)劃問題建模及遺傳算法求解[J].計算機工程與應(yīng)用，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造型的設(shè)計效率，提出一種基于遺傳-蟻群算法的CAD產(chǎn)品快速建模方法，該方法采用遺傳算法求得次優(yōu)解，依據(jù)求得的次優(yōu)解對蟻群算法進行初始信息素分布，在次優(yōu)解中進一步尋優(yōu)，最終搜索到產(chǎn)品造型設(shè)計的最優(yōu)解。遺傳算法和蟻群算法的有效結(jié)合，使算法具有較好的全局收斂效率和求解精度。實驗結(jié)果表明，該算法搜索出來的造型包含造型的細節(jié)特征，更加滿足用戶的個性化需要。

快速建模；計算機輔助設(shè)計（CAD）產(chǎn)品設(shè)計；遺傳算法；蟻群算法

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.

國家自然科學(xué)基金（No.60173055）；黑龍江省自然科學(xué)基金（No.G201207）。

丁博（1983—），女，博士后，講師，主要研究方向為計算機圖形學(xué)與CAD；于曉洋（1962—），男，博士，教授，博導(dǎo)，主要研究方向為三維視覺檢測；孫立鐫（1944—），男，教授，博導(dǎo)，主要研究方向為計算機圖形學(xué)與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