基于云遺傳的混合粒子群聚類算法

武警工程大學(xué)研究生管理大隊 陳 思

武警工程大學(xué)理學(xué)院 劉建平

武警工程大學(xué)研究生管理大隊 劉方毅

基于云遺傳的混合粒子群聚類算法

武警工程大學(xué)研究生管理大隊 陳 思

武警工程大學(xué)理學(xué)院 劉建平

武警工程大學(xué)研究生管理大隊 劉方毅

針對K-means算法對初始聚類中心敏感、粒子群算法易陷入早熟收斂且易受初始值影響以及粒子群算法不能以概率1全局收斂的問題，提出一種基于仿射傳播和云遺傳的改進混合粒子群聚類算法，通過在初始化過程中引入仿射傳播聚類算法，克服初始值對算法的影響，通改進的Metropolis接受準(zhǔn)則和動態(tài)調(diào)整粒子集規(guī)模策略，實現(xiàn)了云遺傳算法和粒子群算法的協(xié)同聚類，并進行了全局收斂性證明、時間復(fù)雜度分析和實驗分析。

仿射傳播聚類算法；云遺傳算法；粒子群算法；K-means算法

1 引言

美國社會心理學(xué)家Kennedy和電器工程師Eberhart受到鳥群覓食行為的啟發(fā)，提出一種模仿鳥群覓食行為的多元搜索優(yōu)化算法，即粒子群（Particle Swarm Optimization，PSO）算法[1-2]。PSO算法模型簡潔，執(zhí)行效率高，控制參數(shù)少，被廣泛應(yīng)用于復(fù)雜優(yōu)化問題[3]。

為了提高傳統(tǒng)K-means聚類算法的收斂速度和效果，文獻[4]使用PSO算法進行初始聚類，將PSO算法得到的聚類結(jié)果作為K-means算法的初始聚類中心；文獻[5]通過引入變異操作，提高了PSO和K-means混合聚類算法的全局搜索能力。以上算法不能兼顧K-means算法對初始聚類中心的敏感性和PSO算法易陷入早熟收斂且易受初始值影響的問題，雖然算法的全局搜索能力有所提高，但是文獻[7]指出PSO算法不能以概率1收斂到全局最優(yōu)解，不一定能夠搜索到最佳的聚類結(jié)果。針對以上問題，本文提出一種基于云遺傳的混合粒子群聚類(Cloud Genetic Hybrid PSO Clustering, CGHPC)算法，通過在初始化階段引入仿射傳播聚類算法(Aff i nity propagation, AP)進行簡單初始聚類，以克服算法對初始聚類中心和初始值的敏感性，實現(xiàn)了云遺傳算法和PSO算法的協(xié)同聚類，并對算法進行了全局收斂性證明、時間復(fù)雜度分析和實驗分析。

2 算法介紹

2.1 粒子群算法

在一個涉及到h維解空間的問題中，假設(shè)粒子群的規(guī)模為m，第i個粒子為，粒子i的速度為。依據(jù)不同粒子的適應(yīng)度值來判定不同粒子的優(yōu)劣，粒子i適應(yīng)度最佳的個體最優(yōu)粒子為，而種群中具有最佳適應(yīng)度值的粒子為全局最優(yōu)粒子。粒子群算法在運算過程中，根據(jù)速度更新和位置更新公式來實現(xiàn)粒子的移動，速度更新和位置更新的公式如下：

其中，i表示粒子數(shù)，t為迭代次數(shù)，c1與c2為加速常數(shù)，r1和r2是兩個隨機數(shù)，ω為慣性權(quán)重。

2.2 仿射傳播聚類算法

AP算法將相似度矩陣 S=[s(i,k)]N×N作為輸入，其中s(i,k)的表達式如下：

相似度矩陣S的對角線上的數(shù)值為偏向參數(shù)P，其表明數(shù)據(jù)點被選為簇中心的可能性的大小，P越大則可能性越大。通常將矩陣S的均值作為初始P值，此時每個數(shù)據(jù)點均是候選聚類中心，通過調(diào)整P值的大小來得到不同個數(shù)的聚類中心。

3 CGHPC算法

在傳統(tǒng)的PSO算法中，隨著算法的進行和迭代次數(shù)的增加，粒子群種群多樣性不斷損失，直到算法陷入早熟收斂[8]。因此，定義種群密度（Population Density, PD）來衡量粒子群種群多樣性水平，作為判斷是否進入早熟收斂的依據(jù)。

云遺傳算法在傳統(tǒng)的遺傳算法思想中集合了云模型理論[9]，借助云模型的隨機性和穩(wěn)定傾向性的特點，采用云模型更新個體，保證了個體的多樣性和全局最佳定位，從而有效克服了傳統(tǒng)遺傳算法的早熟收斂和易陷入局部收斂等缺點。

為了解決PSO算法的早熟收斂問題，本文提出改進Metropolis接受準(zhǔn)則更新全局最優(yōu)解和動態(tài)減少PSO算法粒子集粒子數(shù)量兩種策略，實現(xiàn)PSO算法和云遺傳算法的協(xié)同。

改進的Metropolis接受準(zhǔn)則：若云遺傳算法種群全局最優(yōu)粒子的適應(yīng)度fc大于PSO算法的種群全局最優(yōu)粒子的適應(yīng)度fp，則將作為共同的全局最優(yōu)粒子存儲于全局最優(yōu)數(shù)據(jù)庫中，并令否則，若Er=exp[-(fc-fp)/A]大于隨機數(shù)R，則仍接受為共同全局最優(yōu)粒子存儲于全局最優(yōu)數(shù)據(jù)庫中，若Er小于R，則接受為共同全局最優(yōu)粒子存儲于全局最優(yōu)數(shù)據(jù)庫中，并令。其中A=a/log(t+T)，a為一個趨近于1的常數(shù)，T為協(xié)同算法最大迭代次數(shù)，t為算法當(dāng)前迭代次數(shù)，R=t(D1)/5，t(D1)為區(qū)間[0,5]上由t分布產(chǎn)生的隨機數(shù)，D1公式如下：

4 收斂性和時間復(fù)雜度分析

4.1 收斂性分析

設(shè)Sm={Z=(Z1,Z2,…,Zm)，Zi∈Z(i≤m}為CGHPC算法的種群（優(yōu)化解）空間，S2={(Z1,Z2),Z1,Z2∈S}被定義為母體空間，S被定義為個體空間，Zi被定義為個體，h為其維數(shù)，m為種群規(guī)模（優(yōu)化解），t為協(xié)同算法迭代次數(shù)，P為Sm上的概率分布。將CGHPC算法看做采用最優(yōu)保留策略的遺傳算法的拓展，則CGHPC算法由四部分組成：選擇算子Ts，交叉算子Tc，變異算子Tm，粒子移動算子Tp。

定義1 CGHPC算法的適應(yīng)度函數(shù)f為個體空間到正實數(shù)空間的映射，則CGHPC算法的全局最優(yōu)解集為：

定義2 CGHPC算法的選擇算子Ts是從一個種群中選擇一個個體的隨機映射。

定義3 CGHPC算法的交叉算子Tc是母體空間到個體空間的映射,其中 k表示可以生成Y的基因位置的個數(shù)，則CGHPC算法在執(zhí)行過程中單點雜交的概率為：

定義4 CGHPC算法的變異算子Tm是個體空間到個體空間的隨機映射。

引理1[9]當(dāng)PSO中加速度因子，粒子i由轉(zhuǎn)移到以為中心，任意ε為半徑的球狀區(qū)中的一步轉(zhuǎn)移概率為：

引理2[10]當(dāng)粒子t時刻的狀態(tài)時，其下一時刻的狀態(tài)的概率為：

引理3[11]采用最優(yōu)保留策略的遺傳算法種群序列{Zt;t≥0}是有限齊次馬爾科夫鏈。

引理4[12]帶有正態(tài)分布變異機制的粒子群優(yōu)化算法種群序列{Zt;t≥0}是有限齊次馬爾科夫鏈。

5 實驗分析

5.1 實驗環(huán)境

實驗的環(huán)境為: 操作系統(tǒng)Windows 7，CPU采用Intel Core Quad2 Q6600 2.4 GHz CPU、16 GB內(nèi)存，使用MATLAB2014a進行實驗。

5.2 實驗結(jié)果和分析

實驗數(shù)據(jù)為三組UCI數(shù)據(jù)，分別是Wine、Iris和Glass數(shù)據(jù)集。實驗中分別運行K-means算法、CAVPSO-K算法算法以及CGHPC算法。c1=c2=2, ωmax=0.9,ωmin=0.4, λ1=λ2=1.6。種群密度閾值0.05，三個數(shù)據(jù)集粒子群數(shù)目為50，最大迭代次數(shù)為50次。實驗獨立進行20次，對實驗結(jié)果求平均值。

表1 聚類準(zhǔn)確度結(jié)果對比

如表1為三種算法聚類準(zhǔn)確度結(jié)果對比，為便于對比分析，表中實驗結(jié)果均以“聚類準(zhǔn)確度+標(biāo)準(zhǔn)差”形式給出。從表1中可以看出，CGHPC算法的聚類精度結(jié)果和雙側(cè)t-檢驗結(jié)果要優(yōu)于其他兩種算法。其中，CAVPSO-K算法對Glass數(shù)據(jù)集進行聚類時，雙側(cè)t-檢驗的結(jié)果顯示與CGHPC算法的聚類精度相似，但其聚類精度平均值和標(biāo)準(zhǔn)差均劣于CGHPC算法，這也從側(cè)面表明CGHPC算法在聚類精度穩(wěn)定性相對CAVPSO-K算法具有優(yōu)勢。

表2 最優(yōu)適應(yīng)度結(jié)果對比

表3 最優(yōu)適應(yīng)度均值雙側(cè)t-檢驗結(jié)果符號及含義

表2和表3分別給出了三種算法的最有適應(yīng)度結(jié)果對比與雙側(cè)t-檢驗結(jié)果符號及含義。從表中可以看出CGHPC算法最有適應(yīng)度實驗結(jié)果均小于K-means算法和CGHPC算法，聚類效果較好，雙側(cè)t-檢驗結(jié)果也表明CGHPC算法最優(yōu)適應(yīng)度值相交于CAVPSO-K具有較好的穩(wěn)定性。

6 結(jié)論

為了解決K-means算法對初始聚類中心的敏感性、PSO算法易受初始值影響以及PSO算法不具全局收斂性且易陷入早熟收斂等問題，本文提出一種基于仿射傳播和云遺傳的混合粒子群聚類算法，通過引入仿射傳播聚類算法進行粒子群的初始化，克服K-means算法和PSO算法對初始化的敏感性，通過自適應(yīng)云算子、改進的Metropolis接受準(zhǔn)則以及動態(tài)調(diào)整粒子集規(guī)模等策略，實現(xiàn)了云遺傳算法和PSO算法的協(xié)同聚類，并進行了全局收斂性證明。實驗結(jié)果證明CGHPC算法可以有效提高聚類精度，跳出早熟收斂，算法性能得到有效提升。

[1]Poli R,Kennedy J,Blackwell T. Particle swarm optimization[J]. Swarm Intelligence,2007,1(1):33-57.

[2]Miyatake M,Veerachary M,Toriumi F,et al.Maximum power point tracking of multiple photovoltaic arrays:a PSO approach [J].IEEE Transactions onAerospace and Electronic Systems,2011,47(1):367-380.

[3]劉衍民,牛奔.新型粒子群算法理論與實踐[M].北京:科學(xué)出版社,2013:11-15.

[4]謝秀華,謝秀華,李陶深.一種基于改進 PSO的K-means 優(yōu)化聚類算法[J].計算機技術(shù)與發(fā)展,2014,24(2) :34-38.

[5]陶新民,徐晶,楊立標(biāo),等.一種改進的粒子群和K均值混合聚類算法[J].電子與信息學(xué)報,2010,32(1):92-97.

[6]王縱虎,劉志鏡,陳東輝.兩階段混合粒子群優(yōu)化算法[J].西南交通大學(xué)學(xué)報,2012,47(6):1034-1040.

[7]張慧斌,王鴻斌,胡志軍.PSO算法全局收斂性分析[J].計算機工程與應(yīng)用,2011,47(34):61-63

[8]陽春華,谷麗姍,桂衛(wèi)華.自適應(yīng)變異的粒子群優(yōu)化算法[J].計算機工程,2008,34(16):188-190.

[9]梁旭,黃明,寧濤等.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M].北京:電子工業(yè)出版社,2014:70-72.

[10]潘峰,周倩,李位星等.標(biāo)準(zhǔn)粒子群優(yōu)化算法的馬爾科夫鏈分析[J].自動化學(xué)報,2013, 39(4):381-388.

[11]丁建立,陳增強,袁著祉.遺傳算法與螞蟻算法融合的馬爾可夫收斂性分析[J].自動化學(xué)報,2004,30(4):629-634.

[12]陶新民,劉福榮,劉玉,等.一種多尺度協(xié)同變異的粒子群優(yōu)化算法[J].軟件學(xué)報,2012,23(7):1805-1815.

[13]張立昂,屈婉玲.Jon K,Eva T.算法設(shè)計[M].北京:清華大學(xué)出版社,2007:21-41.