基于特征的制造資源分類方法的研究*

趙昌龍，關雪松

(1.長春大學 機械與車輛工程學院，長春 130022;2. 吉林大學 機械科學與工程學院，長春130022)

0 引言

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

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

1 混合聚類算法的組成

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

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

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

圖1 加工設備向量

1.1 內(nèi)層迭代

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

1.1.1 染色體編碼方案

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

chr:

1.1.2 適應度函數(shù)構造

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

1.1.3 遺傳算子

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

選擇算子為雙點交叉算子，在個體編碼中采用隨機方式設置兩個交叉點，然后對基因進行部分交換，變異操作采用均勻遺傳算子來完成。

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

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

1.2 外層循環(huán)

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

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

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

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

2 實例分析

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

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

圖2 混合算法流程圖

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

表1 加工設備及其屬性

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

表2 分類結(jié)果

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

3 結(jié)束語

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

［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.