基于混合優化模糊C均值算法的網格資源聚類

摘 要:為了更好地解決目前網格資源查找效率低下的問題，結合網格環境中普遍存在的資源相似現象，提出了基于遺傳操作觸發的粒子群混合優化算法的網格資源模糊C均值聚類， 對網格資源進行最大相似性聚類，通過設置觸發條件，避免了潛在的局部迭代，一定程度上簡化了算法執行的復雜度。實驗表明，該方法能提高分類的運行速度及準確率，可以很好地應用到網格資源聚類中，優化網格資源調度前期工作。

關鍵詞:網格資源聚類; 遺傳操作; 觸發; PSO; FCM

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2010)06-2153-03

doi:10.3969/j.issn.1001-3695.2010.06.045

Hybrid FCM algorithm to grid resource clustering

XUE Shengjun， NIE Jing

(School of Computer Software， Nanjing University of Information Science Technology， Nanjing 210044， China)

Abstract:In order to better solve the grid resources discovering problem of low efficiency and exploit the generally existing characteristic of similarity between resources in grid environment， this paper proposed a hybrid FCM algorithm based on PSO and the trigger of GAto maximize the clustering of grid resources. By setting the trigger condition， avoided the potential local iteration， and simplified a certain extent， the complexity of the algorithm. Simulation results indicate that， the methodimproves the running speed and accuracy of clustering， and can be well applied to the grid resource clustering， thereby the preliminary work of grid resource scheduling will be optimized.

Key words:grid resources clustering; genetic operators; trigger; PSO; FCM

0 引言

為了滿足不斷提升的高性能應用的要求，將地理上分布、性能上異構的各種閑置資源通過互聯網有組織地連接，實現多種資源的全面共享，成為推動網格技術迅速發展的動力。網格中的資源以一系列的屬性所區別，如處理器類型、存儲性能、計算能力、通信帶寬等，而每一個應用都對執行該應用的網格資源節點有具體的要求，這樣就需要設計一種可擴展的、能適應資源動態變化、可滿足客戶多樣性，以及擁有好的定位性能的資源查找機制。

網格中的資源廣泛存在著相似現象，因此，聚類作為數據挖掘中的重要技術被應用在網格中。根據聚類分析對資源進行分類，將應用在滿足要求的一個或多個子集上運行，可以提高資源分配的準確性和定位性，降低資源選擇時的復雜度及響應時間。

目前相關的研究主要有:a)采用傳遞閉包求相似等價關系，并根據需要設置λ值進行截集得到資源聚類[1];b)根據用戶對所需資源性能需求，將網格資源聚類成不同性能比的資源集合[2];c)將資源按屬性分類，再以簇內外相似度為調整參數，用進化算法并行地在已分類集合中進行優化[3]。但以上方法有一定的隨機性，而且很難適應網格資源的大數據量要求，劃分的精確度很難保證。

本文嘗試利用基于遺傳操作觸發的粒子群算法優化模糊C均值聚類中心的選取，將PSO的全局搜索能力與FCM的局部搜索能力很好地結合起來，并通過遺傳操作，擴大了粒子群的搜索范圍，避免了早熟現象。并將此方法應用在網格資源聚類的問題求解中，解決了以往方法可能出現的問題，最后通過實驗說明了算法的有效性。

1 模糊C均值算法

設聚類樣本為X={x1，x2，…，xn}，xk=(xk1，xk2，…，xks)為樣本xk的s維特征矢量，xkj為樣本xk在第j維特征上的賦值。將該樣本集劃分為c(2≤c≤n)個子集，聚類中心的集合為V={v1，v2，…，vc}，模糊矩陣U=(μij)，μik是第k個樣本屬于第i類的隸屬度，m(m>1)為模糊指數。

FCM的目標函數[4]可描述為

Jm(U，V)=∑nk=1∑ci=1(μik)m(dik)2

s.t. ∑ci=1μik=1;μik∈[0，1];0<∑nk=1μik

其中:(dik)2=|xk-vi|2表示樣本xk與第i類的聚類中心vi的距離。

聚類的準則為min{Jm(U，V)}，應用拉格朗日乘法，結合約束條件∑ci=1μik=1，可得使Jm(U，V)為最小的μik的值為

μik=1∑cj=1dikdjk2/m-1(2)

同理可以獲得Jm(U，V)為最小時，聚類中心vi的值:

vi=1∑nk=1(μik)m∑nk=1(μik)mxk(3)

下面給出FCM算法的具體步驟:

a)初始化參數。給定聚類類別數c，設定迭代停止閾值ε，初始化聚類中心V，設置迭代計數器t。

b)根據式(2)計算隸屬度矩陣U。

c)根據式(3)更新聚類中心V，并計算Jm(U，V)。

d)如果Jmt(U，V)-Jit-1(U，V)<ε，則算法停止并輸出劃分矩陣U和聚類中心V;否則令t=t+1，轉向步驟a)。

2 基于GA操作的PSO混合算法

2.1 PSO簡介

粒子群算法(PSO)是一種典型的群體智能算法，可以在沒有集中控制、不提供全局模型的前提下，很好地解決復雜性問題。其基本思想是受到早期對鳥類群體行為研究結果的啟發，粒子可以根據它本身和同伴的飛行經驗來動態調整飛行速度，從而改變自己當前的位置，完成粒子在搜索空間的尋優過程。

假設在一個d維的搜索空間中，由m個代表潛在問題解的粒子組成一個粒子群。其中每個粒子表示一個d維的向量，記為xi=(xi1，xi2，…，xid)，i=1，2，…，m，即第i個粒子在d維的搜素空間中的位置是xi。將xi代入一個與求解問題相關的目標函數中，可計算出其適應度值，然后根據適應度值的大小評價xi的優劣。用pbest記錄第i個粒子自身搜索到的最好點(計算得到的適應值目前最優)。在整個粒子群中，至少有一個粒子的適應值是全局最優的，將其記錄為gbest。另外每個粒子還有個速度變量，也是一個d維向量，記為vi=(vi1，vi2，…，vid)，i=1，2，…，m。

PSO算法中粒子的位置、速度更新計算式如下:

vik+1=wvik+c1r1(pbest(i)-xi)+c2r2(gbest-xi)(4)

xik+1=xik+vik+1(5)

其中:i=1，2，…，m;學習因子c1、c2一般取值為2;r1、r2是均勻分布在[0，1]的兩個隨機數;w是慣性權重;k為迭代次數。

2.2 基于GA操作的PSO算法

眾所周知，PSO在尋找最優解的效率上好于遺傳算法[5，6]，但是PSO沒有遺傳操作(如選擇、交叉、變異)，而是根據自己的速度來決定搜索過程，這樣在算法收斂的情況下，所有的粒子都趨向同一最優解，約束了粒子的多樣性。因此，以粒子群算法為模板，在粒子群原始操作的基礎上增加遺傳操作[7]，可以融合GA與PSO兩者的優勢，達到更快的收斂速度及更高的搜索精度。下面介紹基于GA操作的PSO算法優化過程。

1)選擇 根據個體適應度，按照賭輪選擇法，從粒子群中選擇出M(偶數)個優良的個體。

2)交叉 對選出的M個個體，以交叉概率pc在隨機產生的編碼長度k處斷點進行交叉，產生M個更優良的新個體。

xi=xi1xi2…xikxik+1…xilxj=xj1xj2…xjkxjk+1…xjl交叉后xi^=xi1xi2…xikxjk+1…xjl

xi^=xj1xj2…xjkxik+1…xil

vi=vi1vi2…vikvik+1…vil

vj=vj1vj2…vjkvjk+1…vjl交叉后

vi^=vi1vi2…vikvjk+1…vjl

vj^=vj1vj2…vjkvik+1…vil

3)變異 變異操作是保持種群多樣性的有效手段，交叉結束后的全部個體的編碼位按變異概率pm隨機改變。pm過小、過大都會影響算法的收斂速度和搜索精度，不利于實現提高全局搜索能力的目的。

3 基于GAPSO混合優化的模糊C均值算法

經過以上介紹分析，可以知道FCM是通過梯度下降的方法來尋優的，這樣就存在局部最優問題。另外FCM的收斂速度對初始值的設定很敏感，尤其在聚類樣本集較大的情況下。基于遺傳操作的PSO優化算法有很強的全局搜索能力，收斂速度快，而且有很高的搜索精度，本文將兩者結合，提出了一種新的混合模糊聚類。

3.1 算法思想

FCM的核心就是確定聚類中心，所以基于GA操作的PSO算法對聚類中心進行編碼。粒子均由c個聚類中心組成，每個粒子對應一種聚類方法，即粒子xi={ai1，ai2，…，aic}。其中aij代表第i種聚類方式的第j個聚類中心，即如果樣本集有n個粒子，則有n種聚類方式。

方案的優劣用適應度函數來評判，這里的適應度函數即為FCM聚類準則函數公式加上常數的倒數。即

f(xi)=1Jm(U，V)+δ(6)

其中:δ為一給定的常數，一般取1。

如果聚類效果越好，適應度函數值就越高。

另外很重要的一點就是遺傳操作觸發的條件:當中止條件f t+1(xi)-f t(xi)<ε未滿足時，檢查一段時間內粒子的pbest和gbest，若這兩個向量沒有變化，則認為迭代陷入循環，此時遺傳操作觸發。

3.2 算法流程

下面給出算法詳細的流程:

a)初始化參數。給定模糊化程度常數m，閾值ε，粒子群規模N，迭代計數器t。

b)初始化粒子群。隨機選出c個樣本作為一個聚類中心集(一個粒子)，共進行N次，即形成規模為N的粒子群。隨機產生每個粒子的初始速度vi，給定學習因子c1、c2，權重w。

c)對粒子群進行編碼。采用實數編碼，一個編碼對應一個可行解。編碼結構如下:

x11…x1sx21…x2s…xc1…xcs

每個粒子的位置由c個聚類中心組成，其中s為樣本向量維數。

d)對每個聚類中心按式(2)計算隸屬度μij。其中i=1，2，…，j=1，2，…，n。

e)對每個粒子，根據適應度函數f求出每個粒子的適應度值，并由每個個體的適應值求出當前個體極值pbest和全局極值gbest。

f)用式(4)(5)對每個粒子的速度和位置進行更新，產生下一代粒子群。

g)若新一代粒子群的適應值f t+1(xi)-f t(xi)<ε，輸出最佳聚類中心個數c和聚類中心;否則檢查是否陷入迭代循環，若陷入循環，觸發遺傳操作，若沒有陷入轉向步驟e)。

h)將GAPSO混合算法得到的聚類中心個數c和聚類中心代入FCM算法中，得到所有樣本的聚類。

具體流程如圖1所示。

4 網格資源聚類實例及結果分析

為了驗證本文混合算法在網格資源聚類中的性能，將網格資源描述提取并量化為四個屬性，分別是計算能力、存儲能力、通信能力和穩定性，其中穩定性是以資源可使用的時間來衡量的。

在模擬實驗中，以考察聚類精度和迭代過程為目的，采用Iris數據集[8]分別在傳統FCM、基于PSO優化的FCM及基于GAPSO混合優化的FCM上進行網格資源聚類分析。

表1給出了實驗初始化參數。

表1 初始化參數表

初始化參數數據初始化參數數據

樣本向量維數s4交叉率pc0.7

學習因子c12變異率pm0.01

學習因子c22中止閾值ε0.000 001

慣性權重w0.9粒子數N40

數據集Iris中的四個特征分別模擬本文網格資源四維特征向量值，資源節點數為150。設置最大迭代次數為40，實驗結果如表2所示。

表2 實驗結果對比表格

算法正確聚類樣本錯誤聚類樣本錯誤率/%

FCM1351510

PSOFCM14374.67

GAPSOFCM14642.67

從表2的實驗結果對比中可以看到，傳統的FCM算法聚類精度不夠，這樣在網格大規模資源節點數目的環境下更難適應實際需求，降低了后續網格任務執行過程中的資源映射的效率，而基于GAPSO混合優化的FCM算法聚類精度有了明顯的提高。

圖2是傳統FCM算法對Iris數據集的聚類過程，MATLAB已經有專門的模擬工具箱。從圖2中可以看出，基于梯度下降的FCM算法隨著后期迭代次數的增加變化很不明顯，極易陷入局部最小。

圖3為PSOFCM、GAPSOFCM對Iris的聚類過程(適應值變化)。

從圖3中可以看出PSOFCM、GAPSOFCM都能較好地收斂到全局最優，但GAPSOFCM的收斂速度明顯優于PSOFCM，在迭代次數較少的時候就已經接近最優值。

5 結束語

本文提出了一種基于遺傳操作觸發的粒子群混合優化模糊C均值的網格資源聚類方法。將PSO全局查找能力與FCM局部尋優能力結合起來，保證了網格大規模資源的聚類精度。為改善粒子群優化聚類中心和聚類中心個數的過程，引入了遺傳選擇、交叉、變異操作，并設置了遺傳操作觸發的條件，通過監控一定迭代次數內粒子的pbest、gbest，避免了粒子群陷入迭代循環，同時加快了聚類速度。另外遺傳操作的調控也滿足了網格資源多樣性的要求。實驗證明，本算法在網格資源聚類中有較好的應用前景。

參考文獻:

[1]DU Xaoli， JIANG Changjun， XU Guorong， et al. Grid DAG scheduling algorithm based on fuzzy clustering[J]. Journal of Software，2006，17(11):2277-2288.

[2]GUO Dong， HU Liang， JIN Shilan ， et al. Applying preferencebased fuzzy clustering technology to improve grid resources selection performance[C]//Proc of the 4th International Conference on Fuzzy Systems and Knowledge Discovery. Washington DC: IEEE Computer Society，2007:214-218.

[3]童一飛，李東波.基于屬性的網格資源動態聚類研究[J].計算機集成制系統，2008，14(4):813-819.

[4]高新波.模糊聚類分析及應用[M]. 西安:西安電子工業出版社，2004:49-91.

[5]GANDELLI A， GRIMACCIA F， MUSSETTA M， et al. Development and validation of different hybridization strategies between GA and PSO[C]//Proc of IEEE Congress on Evolutionary Computation， 2007:2782-2787.

[6]PARSOPOULOS K E， VRAHATIS M N. On the computation of all global minimizers through particle swarm optimization[J]. IEEE Trans on Evolutionary Computation， 2004，8(3):211-224.

[7]PREMALATHA K， NATARAJAN Dr A M. Discrete PSO with GA operators for document clustering[J]. International Journal of Recent Trends in Engineering， 2009，1(1):20-24.

[8]UCI KDD archive[EB/OL]. http://kdd.ics.uci.edu/.