粒子群優(yōu)化三維模型相似性評價

閆 潔 ，孫靜懿 ，韓文軍 ，2

（1.長春金融高等專科學(xué)校，吉林 長春 130028；2.電子科技大學(xué)中山學(xué)院，廣東 中山 528400）

1 引言

隨著CAD/CAM等數(shù)字化技術(shù)的發(fā)展，設(shè)計資源的重用在產(chǎn)品的創(chuàng)新設(shè)計中正變得越來越重要，日益增多的三維CAD模型為產(chǎn)品設(shè)計帶來了大量的可重用資源。CAD模型成果的累積成為核心競爭力的重要智力資源。研究和統(tǒng)計表明，產(chǎn)品的工藝結(jié)構(gòu)及其功能等方面存在較強(qiáng)的繼承特性，在產(chǎn)品設(shè)計過程中，約40%是重用過去的部件設(shè)計，約40%是對已有設(shè)計部件的微小修改，而只有約20%是完全新的設(shè)計[1]，因此，如何從海量產(chǎn)品的模型庫中有效挖掘典型結(jié)構(gòu)并合理重用，是提高開發(fā)效率的重要保障，基于三維模型檢索的設(shè)計重用技術(shù)近年來成為研究熱點(diǎn)之一。如何從海量產(chǎn)品模型中快速、有效地查找適合設(shè)計重用的局部結(jié)構(gòu)已成為產(chǎn)品開發(fā)各環(huán)節(jié)的一個迫切需求[2]。

目前，基于實(shí)例推理[3]、基于模塊化[4]和基于檢索[5]等多種設(shè)計重用算法已被廣泛使用，可有效提高產(chǎn)品設(shè)計效率和質(zhì)量，文獻(xiàn)[3]將設(shè)計知識融入到基于實(shí)例的推理中，實(shí)現(xiàn)知識的輔助決策。提高典型模具的設(shè)計效率和重用率；文獻(xiàn)[4]提出了基于模糊關(guān)聯(lián)分析與求解的復(fù)雜產(chǎn)品的模塊化設(shè)計，對產(chǎn)品設(shè)計中出現(xiàn)的不確定信息進(jìn)行轉(zhuǎn)化與傳遞。文獻(xiàn)[5]通過求解面屬性鄰接圖的頂點(diǎn)和邊的相容矩陣，實(shí)現(xiàn)對相似模型的檢索，提出基于模糊集的三維CAD模型相似性評價。由于機(jī)械產(chǎn)品CAD模型包含較多幾何及拓?fù)湫畔?，基于?shí)例推理和基于模塊化的設(shè)計重用方法可靠性不高，同時由于在現(xiàn)代設(shè)計中三維CAD模型設(shè)計信息的復(fù)雜化，傳統(tǒng)的基于檢索的數(shù)字化設(shè)計重用方法不再適用，基于內(nèi)容的模型典型結(jié)構(gòu)檢索方法提供了全新的技術(shù)方式，已成為近年研究熱點(diǎn)，其主要通過設(shè)計一套有效的匹配算法，在三維CAD模型庫中搜索含有與需求結(jié)構(gòu)具有最優(yōu)相似度的模型用以設(shè)計重用。文獻(xiàn)[7]基于模擬退火算法提出的相似模型檢索方法，利用屬性鄰接圖建立設(shè)計所需結(jié)構(gòu)與已有模型之間的關(guān)聯(lián)圖，通過模擬退火算法檢索關(guān)聯(lián)圖中的最大主團(tuán)完成相關(guān)所需結(jié)構(gòu)的挖掘和相似評價；文獻(xiàn)[8]使用蟻群算法搜索源模型與目標(biāo)模型之間的最優(yōu)面匹配序列，以最優(yōu)面匹配序列為基礎(chǔ)來計算兩個模型之間的相似性文獻(xiàn)[8]以自由草圖進(jìn)行建模，對模型進(jìn)行形狀分布比較來提高模型的形狀檢索精度；文獻(xiàn)[9]提出的基于形狀分布算法的檢索方法，通過比較模型隨機(jī)點(diǎn)之間距離（D2）統(tǒng)計特征的形狀分布曲線實(shí)現(xiàn)模型的相似性評價；文獻(xiàn)[10]基于遺傳算法對模型相似度計算時的權(quán)重進(jìn)行優(yōu)化，提出基于多特征加權(quán)融合的典型結(jié)構(gòu)檢索算法；文獻(xiàn)[11]通過構(gòu)造CAD模型屬性鄰接圖，借助神經(jīng)網(wǎng)絡(luò)進(jìn)行CAD模型的自動聚類；

三維CAD模型的相似性評價對模型重用至關(guān)重要，直接關(guān)系到模型中典型結(jié)構(gòu)檢索的效率和可靠性[12]，為此，在前人研究基礎(chǔ)上，文中利用模型面組成邊數(shù)差異，以此構(gòu)建模型的面相似性評價矩陣，然后以粒子群算法來搜索矩陣中的的最優(yōu)面匹配序列，通過最段匹配序列實(shí)現(xiàn)對源模型和目標(biāo)模型的相似性進(jìn)行評價，為三維CAD模型中主模型結(jié)構(gòu)的智能化檢索和有效重用提供依據(jù)。

2 模型相似矩陣構(gòu)建

三維CAD模型通常由面元素組成，面元素形狀的差異，形成了模型的千差萬別，在CAD模型檢索過程中，面的鄰接相似程度直接影響了模型檢索的精確性。因此通過累積兩個模型間的面相似情況，可以得到重用前模型的相似情況。如果組成兩個面的邊的數(shù)目相差較小，則兩模型存在較高的相似度；反之，則相似度較低。描述模型的面相似性使用的模型示例，圖中模型A包含u1，u2,…，u7七個面，模型 B 由 v1，v2，…，v7七個面組成，如圖 1 所示。

圖1 模型面相似計算示例Fig.1 Example of Similarity Calculation for Faces of Models

用A［x，y］表示面x與面y的鄰接關(guān)系，其計算過程為：

則圖1中兩個示例模型的相似度可以通過式（2）來計算

式中：N（u）—某模型的面含有的組成邊數(shù)；max（·）—取最大值。

式（1）說明當(dāng)S（ui，vj）值越大，說明兩個面的邊數(shù)N（ui）與N（vj）差異越小，兩個面的形狀越相似，使用S（ui，vj）可以構(gòu)造待評價兩模型的面相似度評價矩陣SAB，兩模型的面序列分別為矩陣的行和列。

式中：m和n—待評價的兩模型的面數(shù)，為便于后續(xù)相似性分析，如果兩模型面數(shù)不一致，則當(dāng)m>n時，將SAB進(jìn)行轉(zhuǎn)置處理。

組成兩模型的面的相似度影響著兩個模型的相似性，兩模型間的面相似度越高，兩模型之間的相似性越高[6]。而對于兩個待相似性評的模型，其對應(yīng)的組成面存在著不同的對應(yīng)方案，為此文中以面相似矩陣為參數(shù)，通過粒子群算法來匹配兩模型之間的面最優(yōu)匹序列，在此基礎(chǔ)上評價兩模型整體的相似情況?；诹Ｗ尤核惴ǖ淖顑?yōu)面匹配方法實(shí)現(xiàn)了局部典型結(jié)構(gòu)的的空間位置變換，使空間中處于不同位置和方向的典型模型結(jié)構(gòu)能夠重合。

3 改進(jìn)粒子群優(yōu)化模型相似評價

3.1 改進(jìn)粒子群算法最優(yōu)面匹配

粒子群算法以種群個體間的學(xué)習(xí)為核心，在搜索空間中粒子通過學(xué)習(xí)機(jī)制向最優(yōu)解區(qū)域飛行，調(diào)節(jié)參數(shù)少且收斂速度快，在很多領(lǐng)域得到了應(yīng)用。設(shè)d維空間種群規(guī)模為p，xt為粒子t所在的位置，其表示由粒子群算法得到的序列號向量，vt為粒子t的飛行速度表示算法經(jīng)過 k 次迭代后全局和粒子個體的最優(yōu)位置，相應(yīng)的適應(yīng)度函數(shù)分別表示為fGbest和fPbest。算法在實(shí)現(xiàn)過程中通過不斷迭代更新現(xiàn)最優(yōu)匹配序列的搜索，其過程為[8]：

式中：k—當(dāng)前迭代數(shù)；w—慣性因子；c1和c2—算法優(yōu)化的學(xué)習(xí)因子；r1和r2在迭代過程中在［0，1］內(nèi)隨機(jī)取值。

針對經(jīng)典粒子群算法在面匹配方面的不足，文中先采用基因表達(dá)式對粒子進(jìn)行編碼，并設(shè)計相應(yīng)飛行方法，同時通過環(huán)狀拓?fù)浜屯蛔兯阕樱岣咚惴ㄋ阉餍屎捅荛_局部最優(yōu)。

將語法樹節(jié)點(diǎn)自上而下、從左到右羅列，得到基因表達(dá)式的編碼區(qū)，并其追加非編碼區(qū)以消除葉節(jié)點(diǎn)出現(xiàn)運(yùn)算符，表達(dá)式首段由各種函數(shù)、運(yùn)算符以及終止符等構(gòu)成，而尾段僅有終止符號，基于基因表達(dá)式的粒子編碼，如表1所示。

表1 改進(jìn)算法粒子編碼Tab.1 Improved Algorithm Particle Coding

為使模型在預(yù)設(shè)精度達(dá)到最優(yōu)的簡潔性，約束表1中編碼的有效長度，當(dāng)實(shí)際編碼超過約束長度L時，設(shè)置罰因子對粒子進(jìn)行評價。

式中：f′—增加罰因子后的適應(yīng)度值；δ—罰因子；l≥1—實(shí)際長度，適應(yīng)度值會隨著編碼實(shí)際長度的增加而增大，使超長部分的粒子的適應(yīng)度變差，并在迭代中淘汰。

粒子向最優(yōu)個體學(xué)習(xí)即為向?qū)W習(xí)目標(biāo)飛行，當(dāng)前粒子為t，當(dāng)t向xkGbest，t學(xué)習(xí)時，先隨機(jī)選擇xkGbest，t的節(jié)點(diǎn)，然后以選中節(jié)點(diǎn)替代t節(jié)點(diǎn)，t向 xkPbest，t的學(xué)習(xí)方式與向 xkGbest，t相同，僅目標(biāo)不同。如圖 2所示為采用的R－鄰域環(huán)狀拓?fù)浣Y(jié)構(gòu)，圖中為種群規(guī)模，將粒子順序排列并首尾連接，每個粒子維護(hù)一個其自身與相鄰的2R個粒子共同組成的感知鄰域，粒子在飛行學(xué)習(xí)過程中會以其感知鄰域最佳粒子（rbest）進(jìn)行最優(yōu)信息傳遞，而當(dāng)與鄰域外粒子交互信息時，則以至少一個節(jié)點(diǎn)粒子為媒介，而此時媒介粒子可將自身的部分結(jié)構(gòu)信息融入優(yōu)化過程，從而增強(qiáng)粒子迭代學(xué)習(xí)的魯棒性。

圖2 R-鄰域環(huán)狀拓?fù)浣Y(jié)構(gòu)Fig.2 R-Neighbor Ring Topology

為避免協(xié)同搜索產(chǎn)生的局部最優(yōu)，根據(jù)變異思想先產(chǎn)生一個不大于編碼有效長度的隨機(jī)數(shù)作為待突變節(jié)點(diǎn)的個數(shù)，然后隨機(jī)生成編碼區(qū)內(nèi)突變位置，并對其節(jié)點(diǎn)進(jìn)行突變，當(dāng)隨機(jī)突變位于編碼首段，則從運(yùn)算、終止符等隨機(jī)選擇替換，而當(dāng)位于尾段，以終止符隨機(jī)替換。為緩解種群趨同影響，當(dāng)某位置出現(xiàn)多個相同粒子時，僅保留一個而其余粒子通過突變驅(qū)散原位置。相同粒子的檢測方法為先判斷適應(yīng)度值，適應(yīng)值不相等則編碼結(jié)構(gòu)必然不同；適應(yīng)度值相等時，再進(jìn)一步進(jìn)行編碼結(jié)構(gòu)判斷，當(dāng)兩粒子節(jié)點(diǎn)不同進(jìn)，則判定粒子編碼結(jié)構(gòu)不同。

根據(jù)以上描述，基于改進(jìn)粒子群優(yōu)化的模型最優(yōu)匹配面匹配過程哪圖3所示。圖中：PM—突變概率；MI—最大迭代次數(shù)；rand—（0～1）之間的隨機(jī)數(shù)。

3.2 基于最優(yōu)匹配面的模型相似評價

通過粒子群算法可以搜索得到兩個模型間的最優(yōu)位置xt=（j（1），j（2），…，j（m）），從而得到兩個模型之間的最優(yōu)面匹配序列（1，j（1）），（2，j（2）），…，（m，j（m）），根據(jù)最優(yōu)匹配序列提取SAB中元素，通過相似性累積可以得到兩個模型的整體最終相似性評價，即：

圖3 改進(jìn)粒子群優(yōu)化的最優(yōu)面匹配算法Fig.3 Improved Optimal Surface Matching Algorithm

4 實(shí)驗(yàn)驗(yàn)證分析

為驗(yàn)證提出算法的有效性，以O(shè)pen CASCADE為平臺構(gòu)造幾何模型，選取普渡大學(xué)ESB模型庫[12]中的部分模型，在Inte（R）CoreTMi7-7700HQ CPU，16G內(nèi)存的計算機(jī)硬件下進(jìn)行實(shí)驗(yàn)。

4.1 算法有效性實(shí)驗(yàn)

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

表2 算法有效性實(shí)驗(yàn)結(jié)果Tab.2 Experiment Result of Proposed Algorithm

4.2 算法性能比較實(shí)驗(yàn)

為充分驗(yàn)證文中算法的模型相似性評介性能，選取20個經(jīng)典重用模型結(jié)構(gòu)，以70%的相似度為評價閾值，以通用ESB模型庫中搜索存在經(jīng)典結(jié)構(gòu)的模型，每個經(jīng)典結(jié)構(gòu)進(jìn)行50次重復(fù)實(shí)驗(yàn)，取平均值，然后20個經(jīng)典結(jié)構(gòu)的實(shí)驗(yàn)結(jié)果再進(jìn)行平均，得到每個算法的平均查全率和平均查準(zhǔn)率，獲得PR曲線。所提算法與基于模擬退火算法（Wol-Sim）[10]和基于蟻群算法（Acs-Sim）[11]的模型相似性評價算法在ESB模型庫中進(jìn)行相似性模型搜索得到的PR曲線，如圖4所示。PR曲線的理想結(jié)果為查準(zhǔn)率等于的恒定直線，對于實(shí)驗(yàn)結(jié)果，曲線位置越靠近理想曲線，說明算法的相似性評價性能越好，對模型的檢索精度越高，從圖4曲線結(jié)果看出，所提算法的重用結(jié)構(gòu)檢索性能優(yōu)于Acs-Sim和Wol-Sim算法。

圖4 實(shí)驗(yàn)結(jié)果平均PR曲線Fig.4 Average PR Curve of Experimental Results

5 結(jié)束語

為實(shí)現(xiàn)典型模型結(jié)構(gòu)的高效重用，提出了基于粒子群算法優(yōu)化的CAD模型典型結(jié)構(gòu)相似性評價算法，算法首先由組成模型各面的邊的數(shù)目構(gòu)造相似性評價矩陣，然后以此為描述體，通過粒子群算法搜索兩模型的面最優(yōu)匹配序列，最后根據(jù)搜索到的面最優(yōu)序列提取并計算面相似度，進(jìn)而對模型整體的相似度進(jìn)行計算。通用ESB模型庫實(shí)驗(yàn)結(jié)果表明，與已有算法相比，所提算法可以更準(zhǔn)確地描述三維模型的典型結(jié)構(gòu)相似性，有助于典型結(jié)構(gòu)的準(zhǔn)確挖掘和設(shè)計重用。