面向云制造的資源集群聚類方法研究＊

苑明海 李子晨 黃涵鈺 裴鳳雀 俞紅焱

（河海大學機電工程學院，江蘇 常州 213000）

在新興信息技術及先進制造技術的不斷發展下，云制造理念應運而生。云制造的關鍵是構建制造云，即通過構建云制造資源池，對制造資源進行統一封裝、發布、集中管理和智能化服務[1]。云服務池的建立意味著將存在海量的服務資源，資源分配的好壞直接影響云制造運營商資源管理的規范性及用戶按需索取的便捷度，因此對云制造資源進行有效的劃分，探索出適用于云制造資源集群的聚類方法顯得尤為重要。

對于云制造資源的分類已有大量研究，綜合來看，云制造資源可以分為硬資源和軟資源，二者資源還可繼續細分，如軟資源分為軟件、知識和人力等；硬資源分為制造設備、計算資源和物料等[2]。上述分類只是簡單地根據資源的某種屬性進行劃分，每一類的資源在一些屬性上既有相同點也有不同點，缺乏進一步細致有效地分類。為了滿足云制造用戶快速準確地對資源進行選擇的需求，有必要對云制造資源進行聚類分析。蔡安江等[3]針對資源組合優化問題，引入關聯規則挖掘策略及聚類分析，實現了資源的精準定位與匹配。Tong H 等[4]為了降低云制造平臺資源共享難度，根據聚類結果提出一種基于共識達成過程的子組間匹配方法。Cui J 等[5]結合粒子群算法(PSO)和k 均值聚類算法(k-means)解決了制造資源優化配置問題，但在資源利用率上存在不完善之處。

從已有的研究上來看，云制造的探索從資源服務的特點出發，對資源進行了表述、建模、配置、聚類、重構和調度等研究，各個部分相互影響，相輔相成，從而形成云制造一體化的服務體系。為了進一步規整云制造資源，探究能實現對云制造資源進行更為細致的聚類劃分的聚類算法成為眾多學者的研究突破點，如Huang M 等[6]采用k 均值聚類算法選擇最短完成時間來表示聚類目標，通過對車間機床、工件等資源的聚類形成分揀計劃，雖然在穩定性上有所改善，但是該算法運行時間較長。在不確定聚類方面，目前的研究大多按照分區或者基于密度進行聚類，Gullo F 等[7]致力于層次聚類，提出了一種基于原型的凝聚層次聚類方法(U-AHC)。為避免初始輸入參數對聚類結果的影響，Zhang R 等[8]提出一種無參數約束的自加權譜聚類。模糊聚類上，Bagherinia A 等[9]提出一種新的基于層次加權的模糊聚類集成框架，Xu S L 等[10]研究了基于極限學習機的模糊粒度鄰域聚類算法，這些算法對于一些模糊的數據聚類起到了很好的劃分作用，但對噪音數據的免疫性有所欠缺。對于目前應用廣泛的kmeans 聚類，Chunlei L 等[11]提出一種基于譜聚類思想和粒子群k-means聚類算法的工藝路線聚類模型，根據相似度實現工藝路線的聚類并挖掘高價值工藝路線以供復用。Wang T R 等[12]通過將k-means 算法與局部搜索策略結合提出一種改進的NSGA-II 以提高求解質量。

本文在分析云制造服務之間的關系的基礎上，結合云制造環境下制造資源聚集的類型建立云制造下混合式服務資源聚集模型。對云制造資源集群的聚類進行研究，通過優化蛙跳算法擴大了初始解的搜索范圍，提高了種群間信息共享的能力，并基于優化后的蛙跳算法提出了改進的k-means 聚類算法，在改善了聚類結果受初始參數及初始聚類中心的影響的同時，大大地提高了算法的穩定性并縮短了聚類的時間。

1 云制造資源間的關系及資源聚集描述

云制造下的資源并不是單獨存在的，其資源之間存在著一定的關聯性，通過分析之間的關系，有利于資源的分類與聚集，方便云制造系統的管理與運維，提高用戶按需索取的便捷度。研究資源的聚集過程將便于我們理解云制造資源的走向和云制造服務的流程，為探索出適用于云制造資源集群的聚類方法提供參考。

云制造下資源聚集需通過先進信息技術手段實現資源及能力的虛擬化，利用服務化技術進行封裝組合，其中服務化技術主要有兩種方式：資源及能力的聚合和資源及能力的拆分。聚合是集中所有資源與能力，為指定用戶提供服務；拆分是將聚集的資源及能力進行按需分組，為多用戶提供各類服務，如圖1 所示，云服務的形成過程即是云制造資源和能力服務化的過程。

圖1 服務化技術的兩種方式

針對不同的應用模式，服務資源聚集可以分為企業內聚集、行業內聚集和混合式聚集3 種，其中，混合式聚集融合了企業內聚集和行業內聚集兩種聚集方式，是最為普遍的聚集方式。本文建立的混合式服務資源模型圖如圖2 所示，實現了企業和行業間私有云和公有云的集成，圖中每一朵云代表一個大型企業或集團，資源提供方為企業內不同部門。

圖2 云制造下混合式資源服務聚集

該混合式聚集中，企業內部由資源提供方將元數據發布或映射到虛擬資源池中，通過云服務中間件對元數據統一封裝進行資源共享，最終將所需數據提供給用戶。數據層一方面根據用戶需求提供元數據，另一方面根據用戶需求特征，為用戶提供相關推送，滿足用戶個性化需求，同時，多企業間可以實現所有資源的共享?；旌鲜椒站奂瘜⑿袠I內的資源進行了整合，用戶只要通過云端就能獲取所需要的制造資源和能力服務，在滿足企業自身需求的同時，也促進整個行業的共同發展。

2 基于蛙跳算法改進的k-means 云制造資源聚類方法

云制造平臺中的資源量大、種類多、功能各異且分布較廣，合理有效地分配云制造資源有利于提高云制造系統服務化能力，從而提高整體系統互操性、開放性、敏捷性和集成能力。

2.1 k-means 聚類算法有效性評估

聚類的目標是實現類內樣品相似度最大，類間相似度最小[13-14]，即使聚類的簇內距離最小，簇間距離最大。通過對隨機數組兩兩比較復合相關系數，建立聚類有效性評估函數如下:

類內距離D內(intra-cluster distance)

類間距離D間(inter-cluster distance)

最終建立目標函數F(objective function)

式中：類內距離采用歐式距離，k為類的個數，X為聚簇Ri中的元素，Ci為第i個類的聚簇中心，pdist代表歐幾里得距離，類內距離計算的是所有類內元素到聚簇中心的歐幾里得距離平方之和；類間距離采用類平均距離，na、nb為兩個不同聚簇Ra、Rb中樣本的個數，Xi、Xj分別為Ra、Rb中的元素，類間距離與相異兩個聚簇內元素之間的歐幾里得距離平方總和成正比，λ為調節系數，λ＞0。為實現較大的類內聚合和類間分離，即對樣本進行聚類，實現目標函數F的最小化。

2.2 基于蛙跳算法改進的k-means 聚類

蛙跳算法(SFLA)結合了文化基因算法(MA)及粒子群算法(PSO)的優點，將局部搜索與全局尋優相結合，具有較強的魯棒性[15]。其原理是借鑒了生物之間信息分享的社會機制促進了種群的進化過程：為快速而準確地尋找食物，青蛙群體劃分成個數相同但模因信息不同的族群，組團搜索，形成局部范圍的小團體，局部精英個體影響著其所在族群的每一個青蛙個體；而隨著整個種群的進化，不同族群之間開始混合，進行信息交流，這個過程使得很多青蛙個體感受到不同族群之間（和自己不在一個族群內）的青蛙的模因，學習了新思想實現了全局的信息共享，使得整個種群沿著正確的方向搜索食物源。而為進一步增強蛙跳算法族群間的信息共享，使全局極值更快的接近最優解，對原始的蛙跳算法進行改進，主要是對族群中最差蛙向最優蛙學習過程的改進，由族群內部學習改為全局學習，擴大族群中最差蛙學習的搜索范圍，提高進化過程中的族群多樣性。

算法運行時，先產生D只青蛙，第j只青蛙可以表示為Cj=，為擴大解的搜索范圍，產生D只新蛙作為反向解，第j只新蛙可以表示為，其中，，計算這2D只青蛙個體的適應度，比較適應度的大小，選出適應度較高的D只青蛙，并標記全局最優的個體Uzbest，適應度為Fzbest。將這D只青蛙劃分為m個族群，每個族群包含n只青蛙，滿足D=m×n，計算每個族群的最優解Ugbest和最劣解Ugworst，其對應的適應度值為Fgbest和Fgworst，按照式（6）對每個族群的最劣解Ugworst進行改進，比較更新過的最劣解適應度值F*gworst是否優于原始的Fgworst，若不優于原始解則按照式（8）更新Ugworst，再次比較更新過的最劣解適應度值F**gworst是否優于Fgworst，若不優于則按照式（9）更新Ugworst，重復上述局部優化L次。

式中：i代表第i個蛙群，m為族群總數，Ugavg計算的是所有蛙群最優解的均值，rand1及rand2為[0,1]的隨機數，Gi和是第i個族群中最劣解移動的步長，及分別為第i個族群中最優解、最劣解及全局最優解，和是第i個族群中最劣解更新后新位置解，Umin和Umax代表族群計算過程中的最小值位置與最大值位置。

族群更新后將各蛙群進行混合，再次進行劃分，記錄全局最優的個體Uzbest，其適應度為Fzbest，循環族群局部更新、全局尋優及混合劃分操作，直至滿足終止條件。算法流程圖如圖3 所示。

圖3 基于蛙跳算法改進的k-means 聚類算法流程圖

基于蛙跳算法改進的k-means 聚類算法具體步驟可以描述為：

步驟1 輸入數據集Data={X1,X2, ···,XN}和聚簇數k。

步驟2 利用改進的蛙跳算法生成初始聚簇中心C={C1,C2, ···,Ck}，具體如下。

（1） 設置相關參數：設初始種群個體數為D，劃分族群數m，其中每個族群包含n個個體，即D=m×n，每個族群局部優化次數為L，全局最大進化代數Maxgen。

（2）初始化種群：在Data最大值與最小值之間隨機產生一群個體，第j個個體表示為Cj=，并生成相同數量的反向解，第j個新個體表示為C?j=，其中，j={1, 2, ···,D}，

（3） 按照式（3）計算上述2D個個體的適應度F，選取F值較小的D個個體作為最終初始種群。

（4） 種群劃分：將選取的D個個體按照F值大小進行排序，均勻地分配到m個族群內，即按照適應度排序將前m個個體分配到m個族群，緊接著的m個個體同樣分配到m個族群，以此類推，確保每個族群優劣解均衡。

（5） 族群進化：按照3.2 節所述，利用式（6）、式（8）和式（9）更新族群最差個體，重復局部搜索操作L次。

（6） 族群混合：將劃分進化后的族群進行混合，獲取全局最優個體。

（7） 檢驗是否滿足算法終止條件：根據全局最大進化代數Maxgen 判斷是否終止算法，當未達到算法終止條件時，轉到步驟（4），最終輸出全局進化Maxgen 次后的最優解Uzbest。

步驟3 以上述改進的蛙跳算法生成的Uzbest作為初始聚簇中心C，按最近鄰原則將Data 中數據進行聚類劃分，分為k個樣本集合R={R1,R2, ···,Rk}。

步驟4 更新聚簇中心C。取樣本集合Ri中所有樣本的均值作為新的聚簇中心Ci，Ri為R 中的一類樣本集。

步驟5 重新聚類劃分。按照最近鄰原則結合新的聚簇中心對Data 中數據重新進行聚類劃分，形成新的k個樣本集合R*=。

利用上述改進的蛙跳算法對聚簇中心先進行優化再進行迭代，循環迭代步驟直至算法結束，降低算法對聚簇中心的依賴性，改善傳統k-means 算法隨機選取初始聚簇中心不同而造成聚類結果波動的情況，同時改進后的蛙跳算法通過引入蛙群最優解均值，在一定程度上改善了算法優化過程中族群信息共享能力差等問題，提高了算法的收斂速度及解的穩定性。

3 實例分析

以兩種數據集及同類機床資源為例，利用本文所提出的算法對其進行聚類，數據集的點分布散亂且具有一定的相似性與交叉性，機床選擇同類型的機床，根據其能力屬性中的單位加工率、主軸最大轉速和加工等級這3 個性能屬性為特征進行聚類劃分，以驗證本文算法的可靠度。

3.1 改進的k-means 聚類有效性驗證

為驗證改進的k-means 聚類的有效性，利用本文算法對UCI 數據庫中的Iris 測試數據集和一個自構數據集Self-cd 進行聚類。Iris 數據集由150 個數據點構成，分為3 類，第一類與第二、第三類分界明顯，第二類與第三類存在數據交叉部分，每個數據點包含4 個特征；自構數據集Self-cd 內包含180個二維數據點，正態分布在6 組內，如圖4 所示。改進的k-means 算法在兩個數據集上的聚類收斂情況如圖5 所示。

圖4 自構數據集Self-cd

圖5 改進的k-means 算法聚類收斂情況

從圖5 可以看出由于Iris 數據集數據交叉部分較多，數據較自構數據集較為復雜些，因此最優的適應度值大些，算法在前5 次迭代收斂速度非常快，迭代50 次后算法幾乎接近全局最優解，說明改進的k-means 算法具有很好的收斂性且聚類結果比較穩定。

為進一步驗證該算法，同時采用模糊C均值聚類和GAk-means 聚類對這兩個測試數據集進行聚類比較，主要對這兩個數據集的聚類正確性進行比較，定義聚類準確度函數P=×100%，T與F分別為與已知正確聚類相比歸類相同與歸類不同的數據點個數，P越接近1 代表聚類結果越好，運行3 種算法各60 次，計算60 次運算中準確度最大值Pmax、均值Pmean、最小值Pmin（依次從上往下）如表1 所示。

表1 3 種算法聚類準確度P 比較

從圖5 和表1 可見，模糊C均值聚類算法因易陷入局部最小值的缺點，無論是在Iris 還是在Selfcd 數據集上，相比于后兩種算法，聚類的效果不佳，聚類準確度不高。GAk-means 聚類算法與模糊C均值聚類算法相比，聚類效果有所提升但不明顯，本文所提改進的k-means 聚類算法準確度較高，收斂性好且具有較快的收斂速度，算法在保證解穩定性的同時，相比于前兩種算法在聚類準確度方面也體現了較明顯的優勢，說明本文所提出的基于蛙跳算法改進的k-means 聚類算法可行有效。

3.2 云制造平臺某同類機床的聚類劃分

由于云制造資源具有海量性、多樣性、大規模性等特點，對云制造資源有效聚集的策略便成為資源初步處理的重要環節，本文在上述聚類算法得到有效性驗證的前提下，將該聚類算法運用于云平臺某銑床資源聚類上，以云平臺上1 000 個功能相似的銑床資源為例進行分類，以制造資源能力屬性中的單位加工率、主軸最大轉速和加工等級這3 個性能屬性為特征進行聚類劃分，即樣本數據集Data={X1,X2, ···,X1000}，每個樣本Xi具有3 個屬性指標，即Xi={xi1,xi2,xi3}。

為方便描述，將其具體參數描述如圖6 所示，單位加功率范圍為0.6～0.95，越大代表加功率越高，主軸最大轉速范圍為20～100，單位為 r/s，加工等級范圍0～10，越大代表加工精度越高，利用上述基于蛙跳算法改進的k-means 聚類算法對云制造平臺的資源進行進一步管理，其步驟如下：

圖6 1 000 種機床的性能參數

(1)初始聚簇中心的確定

利用上文所提出的改進的蛙跳算法確定初始的聚簇中心，選取k=4，蛙跳算法中取初始種群個體數為1 000，根據上述機床3 個特征參數的最大值與最小值隨機產生

1 000 個初始三維始個體，根據適應度排序劃分種群，族群數為50，每個族群包含20 個個體，組內迭代次數L設為30，種群總進化代數為100，局部優化與全局尋優混合進行，最終確定初始聚簇中心C={C1,C2,C3,C4}，其中Ci包含3 個參數，對應個體的3 個特征。

(2)聚類劃分

按照最近鄰原則將所有數據集分配給最近的聚簇中心，形成4 個聚簇，根據每個聚簇中的數據均值更新聚簇中心，再次進行數據的分配，直至非負代價函數收斂，最終輸出分類好的樣本集合，聚類結果如圖7 所示。

圖7 機床聚類結果圖

由圖7 可見，本聚類算法在1 000 個功能相似的銑床資源的聚類劃分上，能夠較為清晰地將1 000個銑床以單位加工率、主軸最大轉速和加工等級這3 個性能屬性劃分為合理的聚類，使相似資源聚集為一類，以便資源的實時分配及空缺資源的及時替補，以供云制造運營方進行管理與匹配用戶的個性化需求。

云制造系統對資源進行了高度的抽象，而用戶只關心資源的外部狀態，上述方式根據資源所具備的特征屬性實現了云制造資源的進一步劃分，該聚類方法同樣適用于特征值較多的海量樣本數據集，可對云制造平臺內不明數據資源進行歸類，剔除噪音數據，在減輕云制造運營方的管理壓力的同時，為用戶個性化的需求提供便捷的服務。

4 結語

本文對云制造環境下的服務進行研究，結合服務化技術聚合和拆分兩種方式建立了云制造下混合式服務聚集模型，基于k-means 聚類建立了聚類有效性評估函數，解決了傳統k-means 算法初始聚類中心隨機選取帶來的聚類結果不穩定問題，引入蛙跳算法對k-means 算法進行改進，又通過擴大初始蛙群和引入族群最優解均值改善蛙跳算法族群間學習能力弱的缺點，以改進后的蛙跳算法確定kmeans 初始聚簇中心，提出基于蛙跳算法改進的kmeans 聚類算法，通過實例驗證了該方法的有效性和可行性，為其他云制造資源的進一步劃分提供了參考與依據。