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

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

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

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

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

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

1 云制造資源間的關(guān)系及資源聚集描述

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

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

圖1 服務(wù)化技術(shù)的兩種方式

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

圖2 云制造下混合式資源服務(wù)聚集

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

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

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

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

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

類內(nèi)距離D內(nèi)(intra-cluster distance)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（4） 種群劃分：將選取的D個個體按照F值大小進行排序，均勻地分配到m個族群內(nèi)，即按照適應度排序?qū)⑶癿個個體分配到m個族群，緊接著的m個個體同樣分配到m個族群，以此類推，確保每個族群優(yōu)劣解均衡。

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

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

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

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

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

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

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

3 實例分析

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

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

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

圖4 自構(gòu)數(shù)據(jù)集Self-cd

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

從圖5 可以看出由于Iris 數(shù)據(jù)集數(shù)據(jù)交叉部分較多，數(shù)據(jù)較自構(gòu)數(shù)據(jù)集較為復雜些，因此最優(yōu)的適應度值大些，算法在前5 次迭代收斂速度非?？欤?0 次后算法幾乎接近全局最優(yōu)解，說明改進的k-means 算法具有很好的收斂性且聚類結(jié)果比較穩(wěn)定。

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

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

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

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

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

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

圖6 1 000 種機床的性能參數(shù)

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

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

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

(2)聚類劃分

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

圖7 機床聚類結(jié)果圖

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

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

4 結(jié)語

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