基于模擬退火的三維模型典型結(jié)構(gòu)挖掘與相似性評價(jià)

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

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

0　引言

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

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

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

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

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

1.1　CAD模型的B-rep表示

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

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

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

屬性鄰接圖從圖的概念推廣而來，是一種用于描述零件幾何、拓?fù)湫畔⒌膱D結(jié)構(gòu)，其定義如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

典型結(jié)構(gòu)是指模型中包含的具有重用價(jià)值的局部區(qū)域，這些局部區(qū)域主要是設(shè)計(jì)領(lǐng)域常見的凸臺類(Boss)、型腔類(Pocket)、臺階類(Step)、孔類(Hole)和槽類特征(Slot)，以及由這些基本特征組合、或按一定規(guī)律排布而成的復(fù)合特征，具有一定的復(fù)雜性。圖4所示為假定一個(gè)典型結(jié)構(gòu)以及含有該典型結(jié)構(gòu)的CAD模型屬性鄰接圖，圓、正方形和三角形分別表示屬性不同的節(jié)點(diǎn)，在圖4b屬性圖表示的CAD模型中挖掘圖4a屬性圖表示的典型結(jié)構(gòu)其實(shí)質(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)，同時(shí)，圖G也與圖Gβ子圖同構(gòu)，則稱圖G是圖Gα和圖Gβ的公共子圖，記作cs(Gα,Gβ)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3　相似性計(jì)算

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

式中Sc——局部相似度

Nm——所有極大團(tuán)節(jié)點(diǎn)的個(gè)數(shù)

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

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

3　算法驗(yàn)證與討論

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

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

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

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

3.2　算法性能對比與評價(jià)

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

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

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

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

表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　制動(dòng)機(jī)構(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è)機(jī)械裝備模型庫中的CAD模型進(jìn)行統(tǒng)計(jì)測試，獲得了平均查全率-查準(zhǔn)率(Precision-Recall，PR)曲線，理想檢索結(jié)果的曲線應(yīng)該是一條查準(zhǔn)率恒等于1的平行直線，位置靠上的曲線具有較高精度，代表著較好的檢索結(jié)果。從PR曲線顯然可以看出，本文算法的檢索性能明顯高于蟻群算法和遺傳算法，如圖6所示。

圖6　平均查全查準(zhǔn)率曲線Fig.6　Precision-recall curves

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

4　結(jié)束語

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

1張?zhí)飼?huì), 張發(fā)平, 閻艷, 等. 基于本體和知識組件的夾具結(jié)構(gòu)智能設(shè)計(jì)[J]. 計(jì)算機(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ì)的知識服務(wù)方法研究[J]. 兵工學(xué)報(bào), 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郟維強(qiáng), 劉振宇, 劉達(dá)新，等. 基于模糊關(guān)聯(lián)的復(fù)雜產(chǎn)品模塊化設(shè)計(jì)方法及其應(yīng)用[J]. 機(jī)械工程學(xué)報(bào), 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]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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宋正河, 畢淑琴, 金曉萍, 等. 履帶式收獲機(jī)械傳動(dòng)系快速設(shè)計(jì)推理方法[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報(bào), 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è)機(jī)變異設(shè)計(jì)方法[J]. 農(nóng)業(yè)工程學(xué)報(bào), 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è)計(jì)重用的三維CAD模型局部結(jié)構(gòu)檢索方法[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報(bào), 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]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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ì)算[J]. 西南交通大學(xué)學(xué)報(bào), 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王玉, 馬浩軍, 何瑋, 等. 機(jī)械三維CAD模型的聚類和檢索[J]. 計(jì)算機(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孫家廣. 計(jì)算機(jī)圖形學(xué)[M]. 3版. 北京: 清華大學(xué)出版社, 1998.

15王洪申，張樹生，白曉亮, 等. 三維CAD模型局部結(jié)構(gòu)檢索屬性圖算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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]. 計(jì)算機(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è)自動(dòng)化, 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)