張開興　杭晟煜　王金星　宋正河　劉賢喜,3

(1.山東農(nóng)業(yè)大學機械與電子工程學院， 泰安 271018； 2.中國農(nóng)業(yè)大學工學院， 北京 100083；3.山東省園藝機械與裝備重點實驗室， 泰安 271018)

0　引言

隨著產(chǎn)品數(shù)字化技術(shù)應用的不斷深入，企業(yè)已積累的大量CAD設(shè)計成果為新產(chǎn)品的研制提供了寶貴的可重用設(shè)計資源。雖然產(chǎn)品在不斷地更新?lián)Q代，但全新的功能、結(jié)構(gòu)和工藝設(shè)計只有約20%，其余80%的設(shè)計則可以通過直接重用或局部修改已有設(shè)計來完成，產(chǎn)品在功能、結(jié)構(gòu)和工藝等方面具有很強的相似性和繼承性。在企業(yè)的模型庫中，設(shè)計人員往往根據(jù)不同的應用背景通過人工交互方式定義一些典型結(jié)構(gòu)用于模型的設(shè)計重用。面對企業(yè)龐大的模型庫，這種方法效率低下，受主觀因素影響大，并且大量的典型結(jié)構(gòu)往往隱含在外形完全不同的CAD模型中，設(shè)計人員很難發(fā)現(xiàn)。因此，如何從海量的產(chǎn)品模型中快速、有效地挖掘出需要的典型結(jié)構(gòu)，并對其加以重用已成為產(chǎn)品開發(fā)各環(huán)節(jié)的一個迫切需求。

迄今為止，已有多種數(shù)字化設(shè)計重用方法在機械產(chǎn)品設(shè)計中得到廣泛應用，如基于實例推理的設(shè)計、基于模塊化的設(shè)計、基于檢索的設(shè)計等，可有效提高產(chǎn)品設(shè)計效率和質(zhì)量?；趯嵗评淼脑O(shè)計是通過訪問知識庫中過去同類問題的求解從而獲得當前問題解決方法的一種推理模式。張?zhí)飼萚1]提出基于規(guī)則和實例的推理方法，提高夾具設(shè)計知識重用率和設(shè)計效率；王儒等[2]將設(shè)計知識融入到基于實例推理活動中，實現(xiàn)知識的輔助決策?；谀K化的設(shè)計是對不同功能、性能和規(guī)格的產(chǎn)品進行劃分并設(shè)計出一系列的功能模塊，通過模塊的選擇和組合來構(gòu)成不同的產(chǎn)品。BRIERE等[3]采用基于結(jié)構(gòu)的模塊化設(shè)計方法對產(chǎn)品變體及特有部件進行系統(tǒng)性設(shè)計；郟維強等[4]提出了基于模糊關(guān)聯(lián)分析與求解的復雜產(chǎn)品模塊化設(shè)計方法處理產(chǎn)品設(shè)計過程中不確定信息的轉(zhuǎn)化與傳遞。基于檢索的設(shè)計主要通過建立三維零件CAD模型庫，設(shè)計一定的匹配算法，在模型庫中尋找與設(shè)計需求相似度最高的已有零部件進行設(shè)計重用。經(jīng)典方法有OSADA等[5]提出的基于形狀分布算法的檢索方法，通過比較模型隨機點之間距離(D2)統(tǒng)計特征的形狀分布曲線實現(xiàn)模型的相似性評價；陶松橋等[6]通過求解模型的面屬性化鄰接圖之間的頂點相容程度矩陣和邊相容程度矩陣，實現(xiàn)對不同近似程度的相似模型的檢索；TSAI等[7]將加工要求、質(zhì)量、材料等工程語義信息數(shù)字化，提出基于模糊集的三維CAD模型相似性評價。在農(nóng)業(yè)機械產(chǎn)品設(shè)計領(lǐng)域，基于實例推理、基于模塊化以及基于檢索的數(shù)字化設(shè)計重用方法引起眾多科研人員的日益重視，宋正河等[8]提出基于推理知識的聯(lián)合收獲機械快速設(shè)計方法；陸長明等[9]針對小型農(nóng)業(yè)作業(yè)機械，提出基于模塊化的快速設(shè)計和變異設(shè)計方法；張開興等[10]提出融合語義的三維CAD模型局部結(jié)構(gòu)檢索方法。

由于機械產(chǎn)品CAD模型包含較多幾何及拓撲信息，基于實例推理和基于模塊化的設(shè)計重用方法可靠性不高，同時由于在現(xiàn)代設(shè)計中三維CAD模型設(shè)計信息的復雜化，傳統(tǒng)的基于檢索的數(shù)字化設(shè)計重用方法不再適用，而啟發(fā)式算法由于具有能夠進行大量復雜信息快速準確處理的特點而在機械產(chǎn)品數(shù)字化設(shè)計領(lǐng)域有越來越多的應用。李海生等[11]采用遺傳算法進行多特征融合權(quán)重優(yōu)化，提出基于融合特征的非剛性三維模型檢索算法；高雪瑤等[12]使用蟻群算法搜索源模型與目標模型之間的最優(yōu)面匹配序列，以最優(yōu)面匹配序列為基礎(chǔ)來計算兩個模型之間的相似性；王玉等[13]通過構(gòu)造CAD模型屬性鄰接圖，借助神經(jīng)網(wǎng)絡(luò)進行CAD模型的自動聚類。

總體來說，現(xiàn)有的數(shù)字化設(shè)計重用技術(shù)主要針對產(chǎn)品零部件級，產(chǎn)品研制中大量的設(shè)計重用則是在更細觀的零部件內(nèi)部特征和典型結(jié)構(gòu)上，相似性判定以定性和文本屬性匹配為主，且可重用設(shè)計信息的確定也非常依賴于人的經(jīng)驗和知識，產(chǎn)品數(shù)字化設(shè)計重用的粒度粗、精度差、智能化水平低?；诖?，本文提出基于模擬退火算法的三維模型典型結(jié)構(gòu)挖掘與相似性評價方法。

1　模型表示與屬性鄰接圖構(gòu)建

1.1　CAD模型的B-rep表示

在CAD系統(tǒng)中，三維實體CAD模型的精確表示通常有2種方法[14]：①邊界表示法(Boundary representation，B-rep)。②構(gòu)造實體幾何表示法(Constructive solid geometry，CSG)。目前實際應用中的CAD系統(tǒng)零件的模型文件都保存有對應的B-rep信息，并且已成為國際標準的STEP文件格式也支持模型的B-rep表示。此外，不同CAD造型系統(tǒng)的零件模型都可方便地轉(zhuǎn)換為STEP中的B-rep格式。因此，本文算法中采用CAD模型的B-rep表示。

模型的B-rep表示是把模型定義為封閉的邊界表面圍成的有限空間，通過面、環(huán)、邊、點來定義模型的幾何及拓撲結(jié)構(gòu)。B-rep表示方法詳細記錄了構(gòu)成形體的所有元素的幾何信息及其拓撲信息，以便直接存取構(gòu)成形體的各個面、面的邊界以及各個頂點的定義參數(shù)，有利于面、邊、點為基礎(chǔ)的各種幾何運算和操作。其優(yōu)點在于：表示形體的點、邊、面等幾何元素是顯式表示的，比較容易確定幾何元素間的連接關(guān)系；且對模型的B-rep表示可以有多種操作和運算。

1.2　CAD模型的屬性鄰接圖構(gòu)建

屬性鄰接圖從圖的概念推廣而來，是一種用于描述零件幾何、拓撲信息的圖結(jié)構(gòu)，其定義如下：

定義1：屬性鄰接圖。G=(V,E,α,β)，其中，V是一個包含有限元素的非空集合，其元素稱為節(jié)點，且V≠?；E?{(u,v)|u,v∈V}，是一個以不同節(jié)點的無序?qū)ψ鳛樵氐挠邢藜希湓胤Q為邊(不考慮節(jié)點含有直接與自身相連的邊)；α：V→WV是一個從節(jié)點集合到其屬性集合的映射，WV是節(jié)點的屬性集合；β：E→WE是一個從邊集合到其屬性集合的映射，WE為邊的屬性集合。

對于CAD模型的屬性鄰接圖，模型中的每個面fi都有唯一的節(jié)點Vi與之相對應，模型中面的屬性集合WV包括面的類型、面的指向、面的相對面積等。E為面之間的鄰接關(guān)系，對于模型中任意2個面fi和fj，如2個面之間具有鄰接關(guān)系，則有唯一的一條邊Eij與之對應，模型中邊的屬性集合WE包括邊的類型、鄰接面之間的夾角、公共邊的凹凸性等。表1為面節(jié)點和邊的屬性[15]。

表1　CAD模型屬性及說明Tab.1　Attribute of CAD model and its instruction

(1)面的類型：本文中將CAD模型的面分為平面類、圓柱面類、圓環(huán)面類、圓錐面類、球面類和自由曲面類等。

(2)面的指向：在CAD模型中，面的指向?qū)?個曲面的方向性有較大影響。例如圓柱面和圓柱孔，凸臺和凹槽，雖然面的形狀相同，但在CAD模型中所要表達的形狀并不相同，因此有必要用面的指向加以區(qū)分。在幾何內(nèi)核中對CAD模型面的指向定義為面的方向和表面方向之間的關(guān)系，表面的方向總是從中心或軸向指向外的，而面的方向總是從模型實體指向外的。當面和曲面的方向相同時，面的指向為true，不同時為false。如圖1所示圓柱面f1的指向為true，圓柱孔f2的指向則為false，通過判斷面的指向可以有效地對這類相似的曲面進行區(qū)分。

圖1　CAD模型面的指向示意圖Fig.1　Graph of direction of surface in CAD model

(3)面的相對面積：一個面在CAD模型中所占面積的大小，對人的視覺認知及加工過程中有著重要的影響，因此面的相對面積也是面的一個重要屬性。在CAD模型中，某個面fi的面積為Si，其所有鄰接面集合為FA={f1,f2,…,fk}，則該面的相對面積Sei為

(4)邊的類型：本文中將CAD模型的邊分為直線、圓形曲線、橢圓形曲線、雙曲線、拋物線和其他曲線等。

(5)鄰接面夾角：面之間的夾角計算是一個較為復雜的問題，這里僅考慮3種情況：① 2個相鄰接面都為平面，面之間的夾角用2個面的法向夾角計算。② 一個面為平面，另一個面為二次曲面，平面取法向，二次曲面取軸向。③ 2個面都為二次曲面，面之間的夾角用兩曲面的夾角計算。對于不規(guī)則的曲面不予考慮，則邊的鄰接面夾角θ為

(6)邊的凹凸性：對于邊的凹凸性判斷，可利用文獻[16]計算。但是由于這些文獻一般將邊的凹凸性分為凹邊和凸邊，但對于2個相切鄰接面邊的凹凸性判別現(xiàn)有方法有時會存在判別錯誤，因此本文將邊的凹凸性分為凸邊、凹邊和平滑邊。如圖2所示對模型邊的凹凸性判斷結(jié)果為：邊l1為凸邊，l2為平滑邊，l3為凹邊。

圖2　CAD模型邊的凹凸性示意圖Fig.2　Graph of concavity and convexity of edge in CAD model

本文將STEP文件表達的B-rep模型讀入以O(shè)pen CASCADE[17]為幾何造型核心的原型系統(tǒng)，遍歷B-rep模型的每個面，將該面添加到模型的面集合FS={fi}，1≤i≤m，其中m為模型中面的數(shù)目；遍歷面集合FS中的每個面fi，同時在屬性鄰接圖中創(chuàng)建一個與該面對應的圖節(jié)點，并提取該面的屬性作為其對應節(jié)點的屬性；對于FS中的每2個面fi與fj，計算它們之間的連接關(guān)系，若兩面相鄰接，則在屬性鄰接圖中對應的兩節(jié)點間構(gòu)建一條邊，該邊的屬性由邊的類型、面之間的夾角及邊的凹凸性決定。圖3所示為CAD模型及其屬性鄰接圖，CAD模型的屬性圖記錄了模型幾何和拓撲信息，涵蓋的信息量大，與STEP文件記錄的B-rep模型的幾何拓撲信息相比，屬性鄰接圖記錄模型的信息形式簡潔，表達直觀，可讀性強。

圖3　CAD模型及其對應的屬性鄰接圖Fig.3　CAD model and its attribute adjacency graph

2　三維模型典型結(jié)構(gòu)挖掘與相似性評價

典型結(jié)構(gòu)是指模型中包含的具有重用價值的局部區(qū)域，這些局部區(qū)域主要是設(shè)計領(lǐng)域常見的凸臺類(Boss)、型腔類(Pocket)、臺階類(Step)、孔類(Hole)和槽類特征(Slot)，以及由這些基本特征組合、或按一定規(guī)律排布而成的復合特征，具有一定的復雜性。圖4所示為假定一個典型結(jié)構(gòu)以及含有該典型結(jié)構(gòu)的CAD模型屬性鄰接圖，圓、正方形和三角形分別表示屬性不同的節(jié)點，在圖4b屬性圖表示的CAD模型中挖掘圖4a屬性圖表示的典型結(jié)構(gòu)其實質(zhì)是在大圖中尋找子圖。

圖4　典型結(jié)構(gòu)及包含該典型結(jié)構(gòu)CAD模型屬性鄰接圖Fig.4　Attribute adjacency graphs of typical structure and its CAD model

那么，可以將CAD模型典型結(jié)構(gòu)的挖掘問題通過屬性鄰接圖轉(zhuǎn)換成檢測典型結(jié)構(gòu)與CAD模型的屬性鄰接圖之間公共子圖的問題來解決。在此，先給出公共子圖和最大公共子圖的定義：

定義2：公共子圖。給定圖G、Gα和Gβ，若圖G與圖Gα子圖同構(gòu)，同時，圖G也與圖Gβ子圖同構(gòu)，則稱圖G是圖Gα和圖Gβ的公共子圖，記作cs(Gα,Gβ)。

定義3：最大公共子圖。給定圖Gα和Gβ，若圖G是圖Gα和圖Gβ的公共子圖，且不存在圖G′，圖G′也是圖Gα和圖Gβ的公共子圖，圖G′的節(jié)點個數(shù)大于圖G，則稱圖G是圖Gα和圖Gβ的最大公共子圖，記作mcs(Gα,Gβ)。

2.1　關(guān)聯(lián)圖構(gòu)建

給定兩屬性鄰接圖G1、G2，節(jié)點集V1、V2，設(shè)二者的關(guān)聯(lián)圖為HV，則構(gòu)建關(guān)聯(lián)圖的具體算法步驟如下：

(1)對圖G1中的任意一個節(jié)點vi∈V1(1≤i≤n)，遍歷圖G2中每一個節(jié)點uj∈V2(1≤j≤m)，組成節(jié)點對(vi，uj)，若vi與uj具有相同的屬性值，則將(vi，uj)加入關(guān)聯(lián)圖HV的節(jié)點集VH作為其一個節(jié)點。

(2)任取關(guān)聯(lián)圖HV中的2個節(jié)點uH=(u1，u2)和vH=(v1，v2)，若u1≠v1，u2≠v2，且圖G1中的邊e1=(u1，v1)與圖G2中的邊e2=(u2，v2)具有相同的屬性值或圖G1中的節(jié)點u1和v1，圖G2中的節(jié)點u2和v2各不相鄰，則構(gòu)造一條邊eH=〈uH，vH〉，并加入到關(guān)聯(lián)圖HV的邊集EH中作為其一條邊，其中，第1種類型的邊稱為連通邊，第2種類型的邊稱為非連通邊。

圖5a所示為根據(jù)圖4中2個屬性鄰接圖構(gòu)建的關(guān)聯(lián)圖，圖中數(shù)字代表圖節(jié)點標號，根據(jù)步驟(1)，查找節(jié)點類型相同的頂點對集合，關(guān)聯(lián)圖由節(jié)點NaA、NaB、NaG、NbD、NbF、NdA、NdB、NdG、NcC和NcE組成；根據(jù)步驟(2)，根據(jù)各節(jié)點邊的屬性對關(guān)聯(lián)圖的10個頂點對進行連接，連通邊用實線表示，非連通邊用虛線表示。紅色圈內(nèi)的頂點集合即為關(guān)聯(lián)圖的最大團，局部結(jié)構(gòu)挖掘問題就轉(zhuǎn)換成檢測關(guān)聯(lián)圖中最大團問題。為了求解問題的方便，構(gòu)建關(guān)聯(lián)圖的鄰接矩陣，如圖5b所示，矩陣中數(shù)字0代表節(jié)點之間沒有連通關(guān)系，數(shù)字1代表節(jié)點之間是非連通關(guān)系，數(shù)字2代表兩者之間是連通關(guān)系。

圖5　關(guān)聯(lián)圖及其鄰接矩陣Fig.5　Association graph and its matrix

2.2　基于模擬退火算法的典型結(jié)構(gòu)挖掘方法

最大團問題是圖論中的一類經(jīng)典組合優(yōu)化問題，其求解算法目前主要分為精確算法和啟發(fā)式算法。精確算法最常用的是枚舉算法[18-19]；由于最大團問題的算法復雜度比較高，因此現(xiàn)在更多的研究均傾向采用高效率的啟發(fā)式算法。因此，本文將利用模擬退火算法來求解最大團問題，先給出極大團與最大團的定義：

定義4：極大團、最大團。對于給定圖G=(V，E)。其中，V={1，2，…，n}是圖G的頂點集，E?V×V是圖G的邊集。G的團就是一個兩兩之間有邊的頂點集合。如果一個團不被其他任一團所包含，即它不是其他任一團的真子集，則稱該團為G的極大團。頂點最多的極大團，稱之為G的最大團。

由最大團的定義可知，最大團問題的可行解是一個滿足一定約束條件的頂點集合，為了與解的表示相一致，提高算法效率，本文以能夠檢索CAD模型中典型相關(guān)結(jié)構(gòu)信息的關(guān)聯(lián)圖的矩陣G作為輸入(矩陣大小為n)；同時為了增強返回模型的多樣性以方便靈活地進行不同設(shè)計階段的設(shè)計重用工作，以挖掘出的子結(jié)構(gòu)矩陣即關(guān)聯(lián)圖矩陣中的極大團S為輸出(為保證所挖掘的子結(jié)構(gòu)具備一定工程意義，規(guī)定子結(jié)構(gòu)矩陣大小k最小值為3)。在本文模擬退火算法中，初始溫度T設(shè)定為1 000，終止溫度Tend設(shè)定為0.1，溫度變化系數(shù)r是0.99，目標函數(shù)為Fit(S)=k(k-1)-Mij以計算子圖的適應度f，函數(shù)中的Mij為求解某最大團中元素不為0個數(shù)之和，當尋找到目標最大團時，函數(shù)適應值是0。本文模擬退火算法的具體步驟如下：

(1)根據(jù)子圖大小k，利用Swap函數(shù)從容器中隨機選取節(jié)點構(gòu)成初始子圖Sinitial，同時利用目標函數(shù)函數(shù)Fit(S)=k(k-1)-Mij計算初始子圖的適應度finitial，剩余n-k節(jié)點構(gòu)成剩余子圖Sremainder。

(2)進入循環(huán)，結(jié)合Swap函數(shù)從當前初始子圖中任意選取節(jié)點u，利用Cald函數(shù)計算u在Sinitial中頂點的度du，從剩余子圖Sremainder中任意選取一個節(jié)點v，計算v替換u之后在Sinitial中頂點的度dv，如果dv值不小于du，就接受新結(jié)構(gòu)，而如果dv小于du，從剩余子圖Sremainder中重新任意選取節(jié)點，且若重復8n次后dv仍小于du，則新結(jié)構(gòu)度不滿足要求。

(3)計算新結(jié)構(gòu)的適應值fnew，如果finitial≤fnew，接受此結(jié)構(gòu)，如果finitial>fnew，則以一定概率接受此結(jié)構(gòu)。

(4)算法溫度T以一定速率r遞減，循環(huán)執(zhí)行步驟(2)，直至尋找到目標適應值f的結(jié)構(gòu)或者溫度達到終止點Tend之后，程序退出，完成此次典型結(jié)構(gòu)挖掘。

本文模擬退火算法的偽代碼如表2所示。

表2　模擬退火算法偽代碼Tab.2　Pseudo code of simulated annealing algorithm

2.3　相似性計算

在利用模擬退火算法查找關(guān)聯(lián)圖中最大團的過程中，只需要查找到極大團即可，查找出的極大團對應于典型結(jié)構(gòu)和CAD模型所共同包含的公共子圖，因此采用極大團的節(jié)點個數(shù)除以典型結(jié)構(gòu)面的個數(shù)來描述局部相似性，即

式中Sc——局部相似度

Nm——所有極大團節(jié)點的個數(shù)

N——典型結(jié)構(gòu)中面的個數(shù)

S越大表示2個模型局部相似性越高。

3　算法驗證與討論

為了驗證算法的有效性，以Microsoft Visual Studio 2010為集成開發(fā)環(huán)境，Open CASCADE為幾何造型平臺，實驗中所使用的模型主要來自于普渡大學的ESB[20]模型庫和項目組成員根據(jù)國家科技支撐計劃項目“農(nóng)機專業(yè)底盤數(shù)字化設(shè)計技術(shù)研究與示范”和國家重點研發(fā)計劃項目“丘陵山地拖拉機關(guān)鍵技術(shù)研究與整機開發(fā)”與“農(nóng)機裝備智能化設(shè)計技術(shù)研究”構(gòu)建的農(nóng)業(yè)機械裝備模型庫。

3.1　基于模擬退火算法的典型結(jié)構(gòu)挖掘?qū)嵗?/h3>

表3所示的是基于模擬退火算法在圖4b的CAD模型中挖掘圖4a的典型結(jié)構(gòu)的執(zhí)行過程。算法共執(zhí)行311次，以一定概率跳出當前可能局部解的次數(shù)為129次，由于新結(jié)構(gòu)度不滿足要求，執(zhí)行8n次后退出的次數(shù)是163次；適應度從最初10開始，有不斷減小且趨于穩(wěn)定的趨勢；從全局上講，由于算法以一定概率接受適應度變大的局部典型結(jié)構(gòu)，部分區(qū)域適應度波動較大；當適應度變成0，找到該典型結(jié)構(gòu)。

表4所示為從模型中選取紅色標記的典型結(jié)構(gòu)對其進行挖掘，并在模型庫中得到的返回模型?？梢园l(fā)現(xiàn)，本文算法可以將帶有該局部結(jié)構(gòu)的模型從模型庫中全部檢索出來，去掉了一些基本相同的模型，選取了15個具有代表性的模型進行了顯示。從返回模型中可以看出，典型相關(guān)結(jié)構(gòu)往往隱藏在外形各不相同的三維CAD模型中，而本文算法可以有效地將隱含典型結(jié)構(gòu)的CAD模型推送給設(shè)計人員，以供設(shè)計人員參考。

3.2　算法性能對比與評價

表5展示了本文算法與蟻群算法[21]和遺傳算法[22]在通用領(lǐng)域ESB模型庫中，以盤形結(jié)構(gòu)為測試對象的典型結(jié)構(gòu)挖掘能力比較，去掉無關(guān)模型后，將返回模型按相似度進行排序。從挖掘結(jié)果分析，相對于蟻群算法，本文算法以極大團作為輸出結(jié)果，而這種“模糊模式”的挖掘特性可以返回多層次相似度的模型，并且由于本文算法保證最大公共子圖是連通的，典型結(jié)構(gòu)的挖掘結(jié)果更符合人的相似性感知，例如表5蟻群算法第2及第6返回模型不符合視覺相似性；相對于遺傳算法，本文算法的返回模型數(shù)量多，并且具有較高的復雜度，便于設(shè)計人員進行深度挖掘。

表3　模擬退火算法執(zhí)行過程Tab.3　Process of simulated annealing algorithm

表4基于模擬退火算法典型相關(guān)結(jié)構(gòu)檢索結(jié)果
Tab.4Retrievalresultsoftypicalstructurebasedon
simulatedannealingalgorithm

表6和表7展示了本文算法與蟻群算法和遺傳算法在農(nóng)業(yè)機械裝備模型庫中，以稻麥收獲機械底盤紅色標記的轉(zhuǎn)向油缸和制動機構(gòu)典型結(jié)構(gòu)為測試對象的挖掘能力比較，去掉無關(guān)模型后，將返回模型按相似度大小進行排序。從返回模型中可以發(fā)現(xiàn)，對于農(nóng)業(yè)機械復雜零部件，本文算法相比蟻群算法和遺傳算法，其返回模型相似度與復雜度層次多樣，種類豐富全面，具有很大的靈活性，方便設(shè)計人員進行不同階段的設(shè)計工作。

表5盤形結(jié)構(gòu)挖掘的算法性能比較
Tab.5Comparisonofdisktypicalstructureminingabilitybasedonthreealgorithms

表6　轉(zhuǎn)向油缸典型結(jié)構(gòu)挖掘的算法性能比較Tab.6　Comparison of steering cylinder case typical structure mining ability based on three algorithms

表7　制動機構(gòu)典型結(jié)構(gòu)挖掘的算法性能比較Tab.7　Comparison of brake mechanism case typical structure mining ability based on three algorithms

為了充分對比3種算法的性能，本文分別對通用領(lǐng)域ESB模型庫和農(nóng)業(yè)機械裝備模型庫中的CAD模型進行統(tǒng)計測試，獲得了平均查全率-查準率(Precision-Recall，PR)曲線，理想檢索結(jié)果的曲線應該是一條查準率恒等于1的平行直線，位置靠上的曲線具有較高精度，代表著較好的檢索結(jié)果。從PR曲線顯然可以看出，本文算法的檢索性能明顯高于蟻群算法和遺傳算法，如圖6所示。

圖6　平均查全查準率曲線Fig.6　Precision-recall curves

本文算法的時間復雜度主要集中在利用模擬退火算法查找最大團。實驗所用測試機CPU為Intel Pentium 4 CPU 3.06 GHz，內(nèi)存4 GB。本文算法、蟻群算法和遺傳算法對單個模型的平均處理時間分別為0.136、0.251、0.303 s，由此可以看出，本文算法的時間效率高于其他2種算法。

4　結(jié)束語

提出了一種基于模擬退火算法實現(xiàn)三維CAD模型典型結(jié)構(gòu)挖掘與相似性評價的方法，即利用模擬退火算法檢測產(chǎn)品CAD模型屬性鄰接圖之間所構(gòu)造關(guān)聯(lián)圖的最大團，以有效挖掘模型中的典型結(jié)構(gòu)并完成相似性評價，解決了目前產(chǎn)品數(shù)字化設(shè)計中的面向產(chǎn)品特征級和局部結(jié)構(gòu)級的設(shè)計重用粒度粗、精度差、智能化水平低的問題。實驗結(jié)果表明，本文方法具備較優(yōu)的典型結(jié)構(gòu)挖掘能力，算法運行效率高，便于設(shè)計人員進行CAD模型設(shè)計重用工作。

1張?zhí)飼? 張發(fā)平, 閻艷, 等. 基于本體和知識組件的夾具結(jié)構(gòu)智能設(shè)計[J]. 計算機集成制造系統(tǒng), 2016, 22(5): 1165-1178.

ZHANG Tianhui, ZHANG Faping, YAN Yan, et al. Intelligent fixture configuration design based on ontology and knowledge components[J]. Computer Integrated Manufacturing Systems, 2016, 22(5): 1165-1178.(in Chinese)

2王儒, 王國新, 閻艷, 等. 支持產(chǎn)品智能化設(shè)計的知識服務方法研究[J]. 兵工學報, 2016, 37(11): 2101-2113.

WANG Ru, WANG Guoxin, YAN Yan, et al. Knowledge service method for supporting product intellectualized design[J]. Acta Armamentarii, 2016, 37(11): 2101-2113.(in Chinese)

3BRIERE C A, RIVEST L, DESPOCHERS A. Adaptive generic product structure modeling for design reuse in engineer-to-order products[J]. Computer in Industry, 2010, 61(1): 53-65.

4郟維強, 劉振宇, 劉達新，等. 基于模糊關(guān)聯(lián)的復雜產(chǎn)品模塊化設(shè)計方法及其應用[J]. 機械工程學報, 2015, 51(5): 130-142.

JIA Weiqiang, LIU Zhenyu, LIU Daxin, et al. Modular design method and application for complex product based on fuzzy correlation analysis[J]. Journal of Mechanical Engineering, 2015, 51(5): 130-142.(in Chinese)

5OSADA R, FUNKHOUSER T, CHAZELLE B, et al. Shape distributions[J].ACM Transactions on Graphics, 2002, 21(4): 807-832.

6陶松橋, 王書亭, 鄭壇光, 等. 基于非精確圖匹配的CAD模型搜索方法[J]. 計算機輔助設(shè)計與圖形學學報, 2010, 22(3): 545-552.

TAO Songqiao, WANG Shuting, ZHENG Tanguang, et al. CAD model retrieval based on inexact graph matching[J]. Journal of Computer-Aided Design & Computer Graphics, 2010, 22(3):545-552.(in Chinese)

7TSAI C Y, CHANG C A. A two-stage fuzzy approach to feature-based design retrieval[J]. Computers in Industry, 2005, 56(5): 493-505.

8宋正河, 畢淑琴, 金曉萍, 等. 履帶式收獲機械傳動系快速設(shè)計推理方法[J/OL]. 農(nóng)業(yè)機械學報, 2013, 44(增刊2): 268-272.http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=2013s250&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2013.S2.050.

SONG Zhenghe, BI Shuqin, JIN Xiaoping, et al. Rapid design reasoning method for crawler harvester transmission system[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2013, 44(Supp.2): 268-272.(in Chinese)

9陸長明, 張立彬, 蔣建東, 等. 基于模板重構(gòu)的小型農(nóng)業(yè)作業(yè)機變異設(shè)計方法[J]. 農(nóng)業(yè)工程學報, 2009, 25(10): 101-106.

LU Changming, ZHANG Libin, JIANG Jiandong, et al. Variantional design of small agricultural machinery based on templates reconfiguration[J]. Transactions of the CSAE, 2009,25(10):101-106.(in Chinese)

10張開興, 杭晟煜, 趙秀艷, 等. 面向設(shè)計重用的三維CAD模型局部結(jié)構(gòu)檢索方法[J/OL]. 農(nóng)業(yè)機械學報, 2017, 48(7): 405-412.http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20170752&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2017.07.052.

ZHANG Kaixing, HANG Shengyu, ZHAO Xiuyan, et al. Effective subpart retrieval method of 3D CAD models for design reuse[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2017, 48(7): 405-412.(in Chinese)

11李海生, 孫莉, 吳曉群, 等. 基于模型內(nèi)二面角分布直方圖的非剛性三維模型檢索[J]. 計算機輔助設(shè)計與圖形學學報, 2017, 29(6): 1128-1134.

LI Haisheng, SUN Li, WU Xiaoqun, et al.Non-rigid 3D shape retrieval based on inner dihedral angle histogram[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(6): 1128-1134.(in Chinese)

12高雪瑤, 李慧楠, 張春祥, 等. 基于蟻群搜索的三維CAD模型相似性計算[J]. 西南交通大學學報, 2017, 52(2): 416-423.

GAO Xueyao, LI Huinan, ZHANG Chunxiang, et al.Similarity calculation of 3D CAD model based on ant colony searching[J]. Journal of Southwest Jiaotong University, 2017, 52(2): 416-423.(in Chinese)

13王玉, 馬浩軍, 何瑋, 等. 機械三維CAD模型的聚類和檢索[J]. 計算機集成制造系統(tǒng), 2006, 12(6): 924-928.

WANG Yu, MA Haojun, HE Wei, et al.Clustering & retrieval of mechanical 3D CAD models[J].Computer Integrated Manufacturing Systems, 2006, 12(6): 924-928.(in Chinese)

14孫家廣. 計算機圖形學[M]. 3版. 北京: 清華大學出版社, 1998.

15王洪申，張樹生，白曉亮, 等. 三維CAD模型局部結(jié)構(gòu)檢索屬性圖算法[J]. 計算機輔助設(shè)計與圖形學學報, 2008, 20(3):316-320.

WANG Hongshen, ZHANG Shusheng, BAI Xiaoliang, et al.A partial retrieval algorithm of 3D CAD models based on attributed graphs[J]. Journal of Computer-Aided Design & Computer Graphics, 2008, 20(3):316-320.(in Chinese)

16劉雪梅, 張樹生, 崔衛(wèi)衛(wèi), 等. 逆向工程中基于屬性鄰接圖的加工特征識別[J]. 計算機集成制造系統(tǒng),2008,14(6):1162-1167.

LIU Xuemei, ZHANG Shusheng, CUI Weiwei, et al.Machined features recognition based on attributed adjacency graph in reverse engineering[J]. Computer Integrated Manufacturing Systems, 2008,14(6):1162-1167.(in Chinese)

17Open CASCAD technology [EB/OL]. (2006-5-10). http:∥www.epencascade.org.

18BORN C, KERBOSCH J. Algorithm 457: finding all cliques of an undirected graph [J]. Communications of the ACM, 1973, 16(9):575-579.

19KOCH I. Enumerating all connected maximal common subgraphs in two graphs [J]. Theoretical Computer Science, 2001, 250(1):1-30.

20JAYANTI S, KALYANARAMAN Y, IYER N, et al. Developing an engineering shape benchmark for CAD models [J]. Computer-Aided Design, 2006, 38(9): 939-953.

21FENET S, SOLNON C. Searching for maximum cliques with ant colony optimization[J].Application of Evolutionary Computing, LNCS,2003,26(11):236-245.

22李亮, 張樹生, 白曉亮, 等. 基于遺傳算法的三維CAD模型多特征融合和檢索[J]. 制造業(yè)自動化, 2013(3): 78-81.

LI Liang, ZHANG Shusheng, BAI Xiaoliang, et al. 3D CAD model retrieval using a genetic feature combination method[J]. Manufacturing Automation, 2013(3): 78-81.(in Chinese)