三維CAD模型模塊劃分的蟻群聚類(lèi)圖分割方法
為了使三維CAD模型模塊劃分的結果保持較好的結構完整性，提出一種面向圖分割的蟻群聚類(lèi)算法。用屬性連接圖表示復雜的CAD模型并進(jìn)行簡(jiǎn)化;通過(guò)對模型連接方式和零件屬性的分析，獲得零件的結構、功能和材料相關(guān)性并建立綜合相關(guān)度矩陣;根據零件的連接層次系重構了蟻群聚類(lèi)的局部范圍界定和密度函數計算方法，實(shí)現了面向圖分割的的蟻群聚類(lèi)。采用上述方法對某型飛機襟翼模型進(jìn)行模塊劃分，驗證了所提方法的正確性和有效性。
引言
模塊劃分技術(shù)是模塊化設計和大規模定制生產(chǎn)的基礎，是滿(mǎn)足客戶(hù)多樣化需求的有效手段，同時(shí)也可應用于三維計算機輔助設計(Computer Aided Design，CAD)模型檢索領(lǐng)域。由于產(chǎn)品級CAD模型具有零件多、結構復雜的特點(diǎn)，檢索的計算量較大，以分而治之的思想將模型劃分為有一定結構和功能意義的模塊，并行地進(jìn)行對應模塊對比分析，能夠降低檢索的時(shí)間和空間復雜度。
目前，學(xué)者們已經(jīng)提出了多種模塊劃分方法。其中：文獻分析了零件之間的關(guān)聯(lián)度后采用Pmedian方法進(jìn)行模塊劃分;文獻提出了基于啟發(fā)式方法的圖解模塊劃分方法;文獻從零件交互角度進(jìn)行了產(chǎn)品全生命周期的模塊劃分;文獻利用模塊驅動(dòng)因素來(lái)定義設計需求和模塊構建之間的聯(lián)系;文獻從產(chǎn)品全生命周期的角度分析零件的交互關(guān)系，并采用模糊聚類(lèi)和模擬退火算法進(jìn)行模塊劃分;文獻以零件間物理和功能上的相關(guān)度為依據，基于蟻群聚類(lèi)算法進(jìn)行模塊劃分;文獻通過(guò)信息熵理論綜合衡量客戶(hù)需求、產(chǎn)品的裝配、成本和維修等因素，使用模糊聚類(lèi)進(jìn)行模塊劃分;文獻以產(chǎn)品全生命周期中的各因素對產(chǎn)品零部件交互的影響為依據進(jìn)行模塊劃分;文獻綜合模塊聚合度、耦合度和設計需求趨同度建立了劃分優(yōu)化模型，并用遺傳算法進(jìn)行求解。上述方法主要面向客戶(hù)定制生產(chǎn)和模塊化設計，從用戶(hù)需求和產(chǎn)品生命周期的角度出發(fā)分析零件的相關(guān)性，但只根據相關(guān)性還不足以完全表達復雜的拓撲連接結構，以此為依據劃分的模塊中還可能存在相互不連接的零件，從而造成模塊內部結構不完整。
為解決上述問(wèn)題，在模塊劃分時(shí)除了要分析零件相關(guān)性，還要考慮其拓撲連接關(guān)系，即在相關(guān)性和連接層次關(guān)系的共同影響下分析零件的耦合關(guān)系，以實(shí)現模塊內聚合關(guān)系的最大化，同時(shí)保持結構的完整性，這樣劃分出的模塊更有助于進(jìn)行模塊化設計，并能并行地進(jìn)行結構相似性分析。因此，本文提出一種面向圖分割的蟻群聚類(lèi)算法，通過(guò)將模型轉換為屬性連接圖，將模塊劃分問(wèn)題轉化為圖分割問(wèn)題;通過(guò)對零件功能、裝配連接和材料的相關(guān)性分析，建立綜合相關(guān)性矩陣并作為劃分基礎;面向圖分割問(wèn)題改進(jìn)蟻群聚類(lèi)算法，在保持子圖連通性的情況下進(jìn)行模塊劃分，最終使模塊具有較為完整的結構和相對獨立的功能。
1、零件相關(guān)性分析
CAD模型中存在模塊化的結構，即屬于同一模塊的零件有緊密的連接關(guān)系，能共同作用并實(shí)現某項子功能。因此在進(jìn)行模塊劃分時(shí)首先要對零件間的這種相關(guān)關(guān)系進(jìn)行分析。為了便于分析，需要將包含多種幾何、工程信息的CAD模型轉換為圖結構(如圖1)，圖中節點(diǎn)P 代表零件，邊L 表示零件間的連接裝配關(guān)系，然后附加劃分所需的屬性信息A(P)和A(L)，形成屬性連接圖G={P，L，A(P)，A(L)｝，如圖1b所示。在此基礎上分別從結構、功能和材料三個(gè)角度進(jìn)行模型中零件的相關(guān)性分析，作為模塊劃分的依據。
4、結束語(yǔ)
本文分析了現有的模塊劃分方法在模型拓撲結構分析上的局限性，提出了基于圖分割的模塊劃分方法，該方法將模型轉換為屬性連接圖的形式，通過(guò)在圖上進(jìn)行蟻群聚類(lèi)分析并進(jìn)行圖分割，最終達到將CAD模型劃分為模塊的目的。其中，通過(guò)分析零件的拓撲連接關(guān)系和功能、屬性相關(guān)性得到綜合相關(guān)性矩陣;根據圖結構的特點(diǎn)提出了局部范圍界定方法，避免了將空間距離遠、連接間隔大的零件劃分為同一模塊的問(wèn)題;改進(jìn)了密度函數的計算方法，對局部范圍中的零件按結構層次關(guān)系綜合相關(guān)性，使聚類(lèi)更有針對性。并以此建立了面向圖分割的蟻群聚類(lèi)算法。實(shí)例分析表明，所提方法能較好地對模型進(jìn)行劃分。由于模塊劃分的要求和目的不盡相同，后續研究中還需要對結構、功能和材料相關(guān)性的評價(jià)方法進(jìn)行優(yōu)化，使評價(jià)更加準確;并根據應用領(lǐng)域的不同，進(jìn)一步豐富相關(guān)性分析的角度，以適應不同的模塊劃分。
