為了使三維CAD模型模塊劃分的結(jié)果保持較好的結(jié)構(gòu)完整性，提出一種面向圖分割的蟻群聚類算法。用屬性連接圖表示復(fù)雜的CAD模型并進(jìn)行簡化;通過對模型連接方式和零件屬性的分析，獲得零件的結(jié)構(gòu)、功能和材料相關(guān)性并建立綜合相關(guān)度矩陣;根據(jù)零件的連接層次系重構(gòu)了蟻群聚類的局部范圍界定和密度函數(shù)計算方法，實現(xiàn)了面向圖分割的的蟻群聚類。采用上述方法對某型飛機襟翼模型進(jìn)行模塊劃分，驗證了所提方法的正確性和有效性。

　　引言

　　模塊劃分技術(shù)是模塊化設(shè)計和大規(guī)模定制生產(chǎn)的基礎(chǔ)，是滿足客戶多樣化需求的有效手段，同時也可應(yīng)用于三維計算機輔助設(shè)計(Computer　Aided Design，CAD)模型檢索領(lǐng)域。由于產(chǎn)品級CAD模型具有零件多、結(jié)構(gòu)復(fù)雜的特點，檢索的計算量較大，以分而治之的思想將模型劃分為有一定結(jié)構(gòu)和功能意義的模塊，并行地進(jìn)行對應(yīng)模塊對比分析，能夠降低檢索的時間和空間復(fù)雜度。

　　目前，學(xué)者們已經(jīng)提出了多種模塊劃分方法。其中：文獻(xiàn)分析了零件之間的關(guān)聯(lián)度后采用Pmedian方法進(jìn)行模塊劃分;文獻(xiàn)提出了基于啟發(fā)式方法的圖解模塊劃分方法;文獻(xiàn)從零件交互角度進(jìn)行了產(chǎn)品全生命周期的模塊劃分;文獻(xiàn)利用模塊驅(qū)動因素來定義設(shè)計需求和模塊構(gòu)建之間的聯(lián)系;文獻(xiàn)從產(chǎn)品全生命周期的角度分析零件的交互關(guān)系，并采用模糊聚類和模擬退火算法進(jìn)行模塊劃分;文獻(xiàn)以零件間物理和功能上的相關(guān)度為依據(jù)，基于蟻群聚類算法進(jìn)行模塊劃分;文獻(xiàn)通過信息熵理論綜合衡量客戶需求、產(chǎn)品的裝配、成本和維修等因素，使用模糊聚類進(jìn)行模塊劃分;文獻(xiàn)以產(chǎn)品全生命周期中的各因素對產(chǎn)品零部件交互的影響為依據(jù)進(jìn)行模塊劃分;文獻(xiàn)綜合模塊聚合度、耦合度和設(shè)計需求趨同度建立了劃分優(yōu)化模型，并用遺傳算法進(jìn)行求解。上述方法主要面向客戶定制生產(chǎn)和模塊化設(shè)計，從用戶需求和產(chǎn)品生命周期的角度出發(fā)分析零件的相關(guān)性，但只根據(jù)相關(guān)性還不足以完全表達(dá)復(fù)雜的拓?fù)溥B接結(jié)構(gòu)，以此為依據(jù)劃分的模塊中還可能存在相互不連接的零件，從而造成模塊內(nèi)部結(jié)構(gòu)不完整。

　　為解決上述問題，在模塊劃分時除了要分析零件相關(guān)性，還要考慮其拓?fù)溥B接關(guān)系，即在相關(guān)性和連接層次關(guān)系的共同影響下分析零件的耦合關(guān)系，以實現(xiàn)模塊內(nèi)聚合關(guān)系的最大化，同時保持結(jié)構(gòu)的完整性，這樣劃分出的模塊更有助于進(jìn)行模塊化設(shè)計，并能并行地進(jìn)行結(jié)構(gòu)相似性分析。因此，本文提出一種面向圖分割的蟻群聚類算法，通過將模型轉(zhuǎn)換為屬性連接圖，將模塊劃分問題轉(zhuǎn)化為圖分割問題;通過對零件功能、裝配連接和材料的相關(guān)性分析，建立綜合相關(guān)性矩陣并作為劃分基礎(chǔ);面向圖分割問題改進(jìn)蟻群聚類算法，在保持子圖連通性的情況下進(jìn)行模塊劃分，最終使模塊具有較為完整的結(jié)構(gòu)和相對獨立的功能。

　　1、零件相關(guān)性分析

　　CAD模型中存在模塊化的結(jié)構(gòu)，即屬于同一模塊的零件有緊密的連接關(guān)系，能共同作用并實現(xiàn)某項子功能。因此在進(jìn)行模塊劃分時首先要對零件間的這種相關(guān)關(guān)系進(jìn)行分析。為了便于分析，需要將包含多種幾何、工程信息的CAD模型轉(zhuǎn)換為圖結(jié)構(gòu)(如圖1)，圖中節(jié)點P 代表零件，邊L 表示零件間的連接裝配關(guān)系，然后附加劃分所需的屬性信息A(P)和A(L)，形成屬性連接圖G={P，L，A(P)，A(L)｝，如圖1b所示。在此基礎(chǔ)上分別從結(jié)構(gòu)、功能和材料三個角度進(jìn)行模型中零件的相關(guān)性分析，作為模塊劃分的依據(jù)。

　　4、結(jié)束語

　　本文分析了現(xiàn)有的模塊劃分方法在模型拓?fù)浣Y(jié)構(gòu)分析上的局限性，提出了基于圖分割的模塊劃分方法，該方法將模型轉(zhuǎn)換為屬性連接圖的形式，通過在圖上進(jìn)行蟻群聚類分析并進(jìn)行圖分割，最終達(dá)到將CAD模型劃分為模塊的目的。其中，通過分析零件的拓?fù)溥B接關(guān)系和功能、屬性相關(guān)性得到綜合相關(guān)性矩陣;根據(jù)圖結(jié)構(gòu)的特點提出了局部范圍界定方法，避免了將空間距離遠(yuǎn)、連接間隔大的零件劃分為同一模塊的問題;改進(jìn)了密度函數(shù)的計算方法，對局部范圍中的零件按結(jié)構(gòu)層次關(guān)系綜合相關(guān)性，使聚類更有針對性。并以此建立了面向圖分割的蟻群聚類算法。實例分析表明，所提方法能較好地對模型進(jìn)行劃分。由于模塊劃分的要求和目的不盡相同，后續(xù)研究中還需要對結(jié)構(gòu)、功能和材料相關(guān)性的評價方法進(jìn)行優(yōu)化，使評價更加準(zhǔn)確;并根據(jù)應(yīng)用領(lǐng)域的不同，進(jìn)一步豐富相關(guān)性分析的角度，以適應(yīng)不同的模塊劃分。