趙昌龍，關(guān)雪松

(1.長(zhǎng)春大學(xué) 機(jī)械與車輛工程學(xué)院，長(zhǎng)春 130022;2. 吉林大學(xué) 機(jī)械科學(xué)與工程學(xué)院，長(zhǎng)春130022)

0 引言

針對(duì)目前市場(chǎng)需求的不可預(yù)測(cè)、持續(xù)發(fā)展和快速多變性，企業(yè)的各類生產(chǎn)活動(dòng)也必須相應(yīng)的具有高柔性，以便能夠?qū)κ袌?chǎng)需求的變化做出快速的反應(yīng)，并且及時(shí)對(duì)其自身的生產(chǎn)做出合理的調(diào)整甚至是重新規(guī)劃生產(chǎn)活動(dòng)。虛擬制造［1-2］則是解決這一問(wèn)題的有效途徑，利用虛擬制造技術(shù)在企業(yè)現(xiàn)有制造資源條件下，對(duì)產(chǎn)品模型的各個(gè)設(shè)計(jì)屬性滿足制造約束的程度進(jìn)行系統(tǒng)的分析，進(jìn)而得到設(shè)計(jì)模型中對(duì)產(chǎn)品制造和產(chǎn)品質(zhì)量不利的因素，從而及時(shí)地指導(dǎo)研發(fā)人員進(jìn)行該產(chǎn)品的設(shè)計(jì)。

企業(yè)的制造資源主要包括企業(yè)的各種加工設(shè)備，而一個(gè)加工設(shè)備則可能具備多個(gè)加工特征，不同加工設(shè)備的工藝能力差別也越來(lái)越小，因此，為了在可制造性評(píng)價(jià)過(guò)程中縮短搜索的時(shí)間、降低成本并且使這些設(shè)備便于管理，本文針對(duì)不同設(shè)備的加工特征，利用遺傳算法和模糊聚類算法對(duì)其進(jìn)行有效的分組。

1 混合聚類算法的組成

將遺傳算法與FCM 算法［6-8］相結(jié)合，不僅能夠發(fā)揮遺傳算法的全局尋優(yōu)能力，而且可以兼顧FCM 的局部尋優(yōu)能力，有效的克服FCM 對(duì)初始化的敏感度，提高收斂速度，解決聚類問(wèn)題具有更好的效果。基于遺傳算法和遺傳模糊聚類算法的混合聚類算法由外層迭代和內(nèi)層迭代兩大部分構(gòu)成［9-12］，外層迭代利用遺傳算法(GA)動(dòng)態(tài)來(lái)獲得最佳分類數(shù)，內(nèi)層迭代則利用遺傳模糊聚類算法(FGCM)進(jìn)一步確定與最佳分類數(shù)相對(duì)應(yīng)的最優(yōu)分類，將內(nèi)層迭代嵌入到外層迭代之中。

在加工過(guò)程中，由于零件及其被加工特征的尺寸與精度等制造標(biāo)準(zhǔn)的要求不同，即使是同一類型的特征往往也需要采用不同的加工設(shè)備進(jìn)行加工，因此在加工設(shè)備分組過(guò)程中，除了考慮加工設(shè)備所能夠完成的加工特征外(包括柱錐、平面、槽、孔、曲面和階梯)，將機(jī)床的加工能力(包括機(jī)床所能加工零件的尺寸大小及加工精度)也作為分組的依據(jù)，即將加工設(shè)備是否能加工大中型零件、是否能進(jìn)行精加工也作為加工設(shè)備的屬性在基于工藝的加工分組中，零件加工設(shè)備可用向量xi表示:

假如某立式銑床可以加工平面、曲面和槽等特征，而且可以進(jìn)行大中型零件的精加工，則它可以用特征向量(011010 01)來(lái)表示，如圖1 所示。

圖1 加工設(shè)備向量

1.1 內(nèi)層迭代

內(nèi)層循環(huán)主要是利用遺傳模糊聚類算法在對(duì)應(yīng)類別數(shù)c 下進(jìn)行的全局尋優(yōu)，以獲得最優(yōu)分類。解決聚類問(wèn)題的時(shí)候用到遺傳算法，應(yīng)該主要考慮到如何對(duì)聚類問(wèn)題進(jìn)行染色體編碼、如何構(gòu)造個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)，以及遺傳算子和遺傳參數(shù)設(shè)置等問(wèn)題。

1.1.1 染色體編碼方案

在這里，聚類中心矩陣V 采用實(shí)數(shù)編碼方案。我們可以假設(shè):將n 個(gè)加工設(shè)備分成c 類，也就是說(shuō)將一條染色體看成是由c 個(gè)聚類中心vi(i=1，2，…c)所組成的一個(gè)串，如果每個(gè)聚類中心有s 個(gè)特征，則這條染色體就是一個(gè)長(zhǎng)度為c×s 的實(shí)數(shù)碼串

chr:

1.1.2 適應(yīng)度函數(shù)構(gòu)造

聚類問(wèn)題實(shí)際上也可以看做是一個(gè)優(yōu)化問(wèn)題，也就是將待聚類數(shù)據(jù)集的損失函數(shù)達(dá)到最小化，即聚類效果越好，目標(biāo)函數(shù)越小，而對(duì)應(yīng)的適應(yīng)度函數(shù)應(yīng)該越大。利用FCM 算法目標(biāo)(損失)函數(shù)Jm定義適應(yīng)度函數(shù)為:

1.1.3 遺傳算子

選擇算子采用最優(yōu)個(gè)體保存策略與無(wú)回放余數(shù)隨機(jī)選擇相結(jié)合的混合遺傳算子。無(wú)回放余數(shù)隨機(jī)選擇的優(yōu)點(diǎn)在于能夠保證適應(yīng)度高的個(gè)體一定能夠遺傳到下一代的群體中，選擇誤差較小;最優(yōu)個(gè)體保存策略則可以保證遺傳算法的全局收斂性。

選擇算子為雙點(diǎn)交叉算子，在個(gè)體編碼中采用隨機(jī)方式設(shè)置兩個(gè)交叉點(diǎn)，然后對(duì)基因進(jìn)行部分交換，變異操作采用均勻遺傳算子來(lái)完成。

1.1.4 個(gè)體的FCM 優(yōu)化

根據(jù)每條染色體的聚類中心編碼，在每一代執(zhí)行完遺傳操作后對(duì)其進(jìn)行FCM 優(yōu)化，分別更新聚類中心V 和模糊矩陣U。將新的聚類中心矩陣編碼成為新的染色體，并且重新計(jì)算目標(biāo)函數(shù)值，采取最優(yōu)個(gè)體保存策略。

1.2 外層循環(huán)

FCM 算法在聚類分析前需要對(duì)分類數(shù)量進(jìn)行設(shè)定，不能對(duì)子類數(shù)量進(jìn)行優(yōu)化，在外層循環(huán)中可以利用遺傳算法動(dòng)態(tài)確定最佳分類數(shù)。效果好的聚類算法不僅要考慮模糊劃分同一類中的緊湊程度，而且要考慮不同類之間的分離程度。用類間距D 來(lái)表示各聚類中心之間的歐式距離的平均值，它表示出各聚類中心之間的離散程度，D 值越大說(shuō)明不同類之間的分離程度越大，由公式(2)可以計(jì)算得出D 值:

外層迭代的目標(biāo)就是將聚類損失函數(shù)Jm 最小化，而類間距離D 盡可能的大。定義外層迭代的目標(biāo)函數(shù)如下:

通過(guò)變換，可以將求最小值問(wèn)題轉(zhuǎn)化為求最大值的問(wèn)題，從而得到外層遺傳算法的適應(yīng)度函數(shù):

對(duì)分類數(shù)所進(jìn)行的二進(jìn)制編碼，采用最優(yōu)保存策略和無(wú)回放余數(shù)隨機(jī)選擇相結(jié)合的混合遺傳算子，利用單點(diǎn)交叉和基本位變異算子進(jìn)行遺傳操作，在對(duì)應(yīng)的分類數(shù)c 下，再利用內(nèi)層循環(huán)，得到與類別數(shù)c 對(duì)應(yīng)的最優(yōu)分組?；旌纤惴ǖ牧鞒虉D如圖2 所示。

2 實(shí)例分析

內(nèi)部循環(huán)群體個(gè)數(shù)為40，外部循環(huán)的群體個(gè)數(shù)20，交叉概率和變異概率分別為0.8 和0.1，將100次作為終止條件為。與不同的分類數(shù)對(duì)應(yīng)的模糊聚類的損失函數(shù)Jm 和類間距D 如圖3 所示，由圖3 可以看出分類數(shù)為6 時(shí)，Jm 與D 的和最小，此時(shí)外部循環(huán)的適應(yīng)度函數(shù)值最大，也就是說(shuō)6 為最佳分類數(shù)。當(dāng)分類數(shù)為6 時(shí)，分類結(jié)果如表2 所示。

為了驗(yàn)證混合模糊聚類算法的有效性，對(duì)22 個(gè)加工設(shè)備進(jìn)行分組，設(shè)備的屬性包括柱錐、平面、孔、槽、曲面、階梯、是否能加工大中型零件和是否能用于精加工等八個(gè)屬性，設(shè)備及其屬性如表1 所示。

圖2 混合算法流程圖

圖3 模糊聚類的目標(biāo)函數(shù)值圖

表1 加工設(shè)備及其屬性

表1 中:Z、P、C、K、Q、J、D 和R 分別表示柱錐、平面、槽、孔、曲面、階梯、是否能加工大中型零件和是否能用于精加工等設(shè)備特征。

表2 分類結(jié)果

第一組中的加工設(shè)備和第六組中的加工設(shè)備同樣都能加工柱錐、平面、槽和孔，但是第六組加工設(shè)備可以用于大中型零件的精加工，如果所加工的零件為大中型零件則可以直接搜索第六組加工設(shè)備，減少搜索時(shí)間和空間。在第二組、第一組和第六組中，設(shè)備的屬性中都有孔特征，但是在一個(gè)零件不僅需要加工一個(gè)孔特征，還需要加工其他的特征時(shí)，如平面、槽和曲面等特征時(shí)，選用第二組和第六組中的加工設(shè)備，使零件在一次裝夾中可以進(jìn)行多個(gè)特征的加工，這樣更有利于保證零件的加工質(zhì)量和減少裝夾的時(shí)間。

3 結(jié)束語(yǔ)

本文提出了一種基于模糊C-均值聚類算法和遺傳算法的混合算法，并應(yīng)用這一混合算法進(jìn)行加工設(shè)備的分類，利用這種方法可以動(dòng)態(tài)的確定分類數(shù)和分類。在實(shí)例分析中以22 種加工設(shè)備為例，根據(jù)不同加工設(shè)備的加工能力對(duì)加工設(shè)備進(jìn)行了分組，分組情況符合實(shí)際應(yīng)用，利用這種方法，可以有效地減少加工設(shè)備的搜索時(shí)間，提高加工效率。

［1］Mariella Consoni，F(xiàn)lorenzano Souza，Marco Sacco，Virtual manufacturing as a way for the factory of the future［J］.Journal Intelligent Manufacturing，2006，17:1－24.

［2］Kimura F，Product and Process Modeling as a Kernel for Virtual Manufacturing Environment［J］. Annals of the CIRP，1993，42(1):147－150.

［3］Onosato M，Iwata K，Development of a virtual manufacturing system by integrating product models and factory models［J］. Annals of the CIRP，1993，42(1):475－478.

［4］Zhang T，Ramakrishnan R，Livny M，Birch:a new data clustering algorithm and its applications［J］. Data Mining and Knowledge Discovery，1997，1(2):141－182.

［5］Wu K. L，Yang M. S. Alternative C-meansclustering algorithms［J］. Pattern recognition，2002，35:2267－2278.

［6］Zhang D.Q，Chen S.C. A novel kernelized fuzzy C-means algorithm with application in medical image segmentation［J］. Artificial Intelligence Med.，2004，32:37－50.

［7］Fan J L，Zhen W.Z.Suppressed fuzzy c-means clustering algorithm［J］.Pattern Recognition Lett.，2003，24:1607－1612.

［8］Karayiannis N B.Generalized fuzzy c-means algorithms［C］.In:Proc.Of the 5th IEEE Int’1 Conf.on Fuzzy Systems，2:1036－1042，New Orleans:IEEE，1996.

［9］Azzag H，Ventrini G，Oliver A，A hierarchical ant based clustering algorithm and its use in three real-world applications［J］. Eur. J. Oper. Res，2007，197(3):906－922.

［10］Azzag H，Monmarche N，Slimane M，A clustering algorithm based on the ants self-assembly behavior［C］. In:Advances in Artificial Life-Proceedings of the 7th European Conference on Artificial Life，Dortmund，Germany，2003，2801:564－571.

［11］Ngai E. W. T，Chan E. W. C. Evaluation of knowledge management tools using AHP［J］. Expert Systems with Application，2005，29:889－899.

［12］Soremekun G，Gürdal Z. Composite laminate design optimization by genetic algorithm with generalized elitist selection［J］. Computers and Structures，2001，79:131－143.