基于K-均值聚類的協(xié)同進(jìn)化粒子群優(yōu)化算法

王燕燕 ，葛洪偉 ，楊金龍 ，王娟娟

1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122

2.國(guó)網(wǎng)濰坊供電公司，山東 濰坊 261021

粒子群優(yōu)化（P article Swarm Optimization，PSO）算法[1]是一種基于種群的智能優(yōu)化算法，該算法具有可變參數(shù)少，且簡(jiǎn)單易于實(shí)現(xiàn)的特點(diǎn)，得到了廣泛關(guān)注。為了避免粒子陷入局部最優(yōu)，提高粒子的全局搜索能力，增加算法的應(yīng)用領(lǐng)域，研究者常將其與其他的智能優(yōu)化算法相結(jié)合研究，以期達(dá)到更加好的優(yōu)化能力[2-3]。文獻(xiàn)[4]引入了慣性權(quán)重，加快了算法的收斂速度。文獻(xiàn)[5]通過(guò)引入時(shí)變加速因子和時(shí)變慣性權(quán)因子，有效地增強(qiáng)了算法的局部搜索能力。文獻(xiàn)[6]提出的多種群多模型協(xié)同進(jìn)化的粒子群優(yōu)化算法，有效地提高了種群的多樣性。

這些算法隨著維數(shù)增加會(huì)出現(xiàn)優(yōu)化性能迅速惡化的現(xiàn)象，而許多現(xiàn)實(shí)問(wèn)題中需要解決的往往都是高維（幾十維以上，本文在100維上進(jìn)行實(shí)驗(yàn)）優(yōu)化的情況[7-9]。為了解決高維優(yōu)化問(wèn)題，Potter和Jong[10]等提出協(xié)同進(jìn)化（cooperative co-evolutionary，CC）框架，將種群分解成多個(gè)單獨(dú)的子種群（每個(gè)子種群的搜索范圍較低），為解決高維問(wèn)題提供了一個(gè)很有前途的方法。文獻(xiàn)[11]將協(xié)同進(jìn)化框架[10]引入到PSO算法中，通過(guò)CC框架對(duì)粒子群進(jìn)行分組，提出協(xié)同粒子群優(yōu)化（Cooperative Particle Swarm Optimization，CPSO）算法：CPSO-SK和CPSO-HK算法，該算法通過(guò)降低種群的搜索范圍，增加函數(shù)評(píng)價(jià)次數(shù)的處理方法，有效地提高了PSO算法處理高維優(yōu)化問(wèn)題的收斂速度。文獻(xiàn)[12]在每一次迭代中對(duì)各分量進(jìn)行自適應(yīng)加權(quán)，避免了各分量相互依賴度很大而導(dǎo)致算法的性能惡化。文獻(xiàn)[13-14]提出的協(xié)同進(jìn)化粒子群優(yōu)化（CCPSO2）算法采用動(dòng)態(tài)分解和重組變量的方法，避免了交互粒子劃分到不同群中，提高了算法處理高維問(wèn)題的優(yōu)化性能?，F(xiàn)有的這些處理高維優(yōu)化問(wèn)題的算法[10-14]，在一定程度上提高了算法處理高維優(yōu)化問(wèn)題的性能，但是存在著收斂速度慢、優(yōu)化性能不佳的問(wèn)題。

針對(duì)上述算法解決高維優(yōu)化問(wèn)題的缺陷，本文提出了一種基于K-均值聚類的協(xié)同進(jìn)化粒子群優(yōu)化（Cooperative Coevolving Particle Swarm Optimization based onK-means Cluster，KMS-CCPSO）算法，該算法采用K-均值算法對(duì)粒子群進(jìn)行子種群劃分，在保證粒子群的局部搜索和全局搜索能力的同時(shí)，也有效避免了粒子群算法易陷入局部最優(yōu)的問(wèn)題。

1 粒子群優(yōu)化算法

PSO算法采用隨機(jī)初始種群位置和速度，并通過(guò)迭代更新找到最優(yōu)解。在迭代過(guò)程中，粒子通過(guò)兩個(gè)極值更新位置和速度。一個(gè)極值是粒子本身所遍歷得到的最優(yōu)解，稱之為個(gè)體最優(yōu)解；另一個(gè)極值是整個(gè)種群到當(dāng)前時(shí)刻所得到的最優(yōu)解，稱之為全局最優(yōu)解。PSO算法的速度和位置的更新公式為：

2 協(xié)同進(jìn)化粒子群優(yōu)化算法

CPSO算法[11]是由CPSO-SK算法[11]和CPSO-HK算法[11]相結(jié)合得到的，采用指定子種群維數(shù)的分組策略對(duì)種群進(jìn)行劃分子空間，降低函數(shù)的搜索空間，有效地提高了算法的收斂速度。

CCPSO2算法[14]借鑒了CPSO算法[11]對(duì)種群劃分子空間的思想，但不再預(yù)先指定子種群的規(guī)模，而是采用自適應(yīng)方案動(dòng)態(tài)決定子種群的規(guī)模的分組策略，提高了交互變量劃分到相同子種群的概率，提高了算法的優(yōu)化性能。交互變量劃分到同一子種群的概率計(jì)算公式[14]為：

其中，X是交互變量劃分到同一個(gè)子種群的次數(shù)；k是當(dāng)前迭代次數(shù)；N是總迭代次數(shù)；r是當(dāng)前迭代次數(shù)；的簡(jiǎn)寫(xiě)是從N個(gè)次數(shù)中取出r(r≤N)個(gè)次數(shù)的組合數(shù)。m是子種群數(shù)；v是交互變量總數(shù)。

由概率計(jì)算公式（3）可知，CCPOS2算法采用的動(dòng)態(tài)分組策略提高了交互變量劃分到同一子種群的概率。

分組策略[10]是處理高維問(wèn)題最有效的方法。通過(guò)分組策略，將種群劃分成多個(gè)子種群，各個(gè)子種群在不同的搜索范圍內(nèi)進(jìn)行優(yōu)化，整體上降低了種群的搜索范圍，有效地提高了算法的收斂速度和優(yōu)化性能。

3 K-均值算法

近年來(lái)，數(shù)據(jù)挖掘成為一個(gè)很熱的研究方向，作為其主要方法之一的聚類也因此受到人們的關(guān)注。K-均值算法[15]是最早提出的較為經(jīng)典的聚類算法之一，該算法魯棒性較強(qiáng)，能夠解決傳統(tǒng)上難以解決的問(wèn)題，已在諸多領(lǐng)域上得到了廣泛的發(fā)展和應(yīng)用。

K-均值算法[15]是一種基于劃分方法的聚類算法，考慮了樣本間的相似性度，該算法通過(guò)歐氏距離作為相似度測(cè)度，求對(duì)應(yīng)某一初始聚類中心向量V的最優(yōu)分類。樣本間的歐氏距離越小，說(shuō)明樣本間的相似度越大，反之同理。根據(jù)歐氏距離的大小將給定的n個(gè)粒子劃分成k個(gè)不同的簇，其簇內(nèi)粒子具有較高的相似度，簇間粒子具有較低的相似度。

其中，i表示第i個(gè)簇；xj表示第j個(gè)粒子，j∈[1,n]；μi表示第i個(gè)簇的聚類中心。K-均值算法[15]步驟：將給定的n個(gè)粒子劃分成k部分，每一部分稱為一個(gè)簇。首先，隨機(jī)地選取k個(gè)粒子，每個(gè)粒子作為一個(gè)簇的初始中心。對(duì)剩余的每個(gè)粒子，按照其與選定的各個(gè)簇的中心的距離，將它賦給與其距離最短的那個(gè)簇。然后計(jì)算每個(gè)簇內(nèi)粒子的距離平均值，再將粒子與新的聚類中心進(jìn)行距離比較，把粒子賦給與其最近的簇中。

圖1中黑色圓點(diǎn)代表隨機(jī)選取的聚類中心；灰色圓點(diǎn)代表更新后的聚類中心；弧線代表劃分成兩個(gè)區(qū)域。

圖1 k-means算法的計(jì)算過(guò)程

K-均值算法存在兩個(gè)缺點(diǎn)：（1）對(duì)聚類中心的選取依賴性較大；（2）對(duì)聚類所在的維數(shù)空間的要求很高。綜上可知，要想引入K-均值算法就必須解決K-均值算法的缺點(diǎn)。在本文中，k-均值的聚類中心是從粒子中隨機(jī)選取的，好壞粒子被取出的概率均為50%，且無(wú)法確定當(dāng)前好的粒子就一定能帶領(lǐng)種群找到最優(yōu)解，也不確定當(dāng)前不好的粒子就一定不能找到最優(yōu)解。所以這種隨機(jī)選取的聚類中心會(huì)增加種群的多樣性，避免種群陷入局部最優(yōu)。隨著進(jìn)化的進(jìn)行，所有粒子會(huì)向著一個(gè)地方運(yùn)動(dòng)，此時(shí)選出的聚類中心無(wú)論是否是隨機(jī)取得的都不會(huì)影響最終結(jié)果。因此，本文將K-均值算法的聚類中心點(diǎn)與種群最優(yōu)位置進(jìn)行結(jié)合，避免K-均值算法對(duì)聚類中心的過(guò)渡依賴。而且，為了保證K-均值算法的良好性能，將子種群的搜索范圍設(shè)定在二維空間中，有效地避免了K-均值算法隨著維數(shù)的增加，算法的性能會(huì)逐漸變差的情況。

通過(guò)公式和分析可知，引入K-均值算法的粒子群優(yōu)化算法后，在種群進(jìn)化的初期子種群間的相似度較小，使得種群的搜索范圍較大，保證種群的多樣性，具有較強(qiáng)的全局搜索能力；在種群進(jìn)化的后期，種群間的相似度較大，種群的搜索范圍縮小，粒子只在趨于不變的聚類中心點(diǎn)附近的范圍進(jìn)行優(yōu)化，具有較強(qiáng)的局部搜索能力，從而可以有效地避免了粒子群算法易陷入局部最優(yōu)的問(wèn)題。

4KMS-CCPSO算法

4.1 算法思想

由于分組策略可以有效地提高算法的收斂速度和優(yōu)化性能，而K-均值算法可以有效地避免粒子群算法易陷入局部最優(yōu)。因此，本文將分組策略和K-均值算法引入粒子群優(yōu)化算法中，綜合分組策略和K-均值算法優(yōu)勢(shì)，設(shè)定分組維數(shù)為二維，降低高維優(yōu)化問(wèn)題的搜索空間，提高算法的收斂速度，避免粒子陷入局部最優(yōu)，從而使粒子群優(yōu)化算法處理高維優(yōu)化問(wèn)題的性能得到提高。

4.2 算法步驟

為解決高維的優(yōu)化問(wèn)題，優(yōu)化算法需要保持很好的搜索性和收斂性。KMS-CCPSO算法使用柯西和高斯分布相結(jié)合的公式[14]對(duì)粒子的位置進(jìn)行更新，其中選取全局最優(yōu)解和局部最優(yōu)解的差值作為兩大分布的標(biāo)準(zhǔn)差，公式為：

其中，y?′i,d(t)和yi,d(t)分別表示粒子i的局部最優(yōu)解和個(gè)體最優(yōu)解，C(1)表示標(biāo)準(zhǔn)柯西分布，N(0,1)表示標(biāo)準(zhǔn)高斯分布。

算法的步驟如下：

步驟1設(shè)置粒子群數(shù)目、維數(shù)、最大迭代次數(shù)、子空間維數(shù)以及K-均值算法的聚類中心數(shù)目。

步驟2隨機(jī)初始化種群中粒子的初始位置，選取聚類中心的初始點(diǎn)。

步驟3在約束條件下求出粒子的適應(yīng)度值，并分別記錄個(gè)體最優(yōu)解和全局最優(yōu)解。

步驟4通過(guò)公式（4）的K-均值算法劃分子種群，獲得新聚類中心，并用來(lái)更新相鄰子種群的粒子位置。

步驟5比較新種群中粒子的適應(yīng)度值，獲得個(gè)體最優(yōu)解，通過(guò)環(huán)拓?fù)溲h(huán)得到粒子的局部最優(yōu)解。

步驟6利用公式（5）更新粒子的位置。

步驟7判斷是否滿足終止條件，即是否已經(jīng)達(dá)到設(shè)置的最大迭代次數(shù)，若滿足，執(zhí)行步驟8，若不滿足，則返回執(zhí)行步驟3。

步驟8終止優(yōu)化運(yùn)算，輸出粒子最優(yōu)位置。

表1 12個(gè)測(cè)試函數(shù)說(shuō)明

4.3 算法偽代碼

KMS-CCPSO算法偽代碼如下所示。其中，f表示劃分的簇的個(gè)數(shù)；s表示每個(gè)子空間的維數(shù)；K表示子種群的數(shù)目；cidk表示第k個(gè)簇的聚類中心；Pjxi表示第j個(gè)子種群的第i個(gè)粒子的位置；Pj.y?表示第j個(gè)子種群的全局最優(yōu)解；Pj.y?′i表示第j個(gè)子種群的第i個(gè)粒子的局部最優(yōu)解。

5 仿真實(shí)驗(yàn)與結(jié)果分析

5.1 測(cè)試函數(shù)

為了測(cè)試本文提出算法的性能，采用了12個(gè)測(cè)試函數(shù)。其中，f1-f5函數(shù)是單峰函數(shù)，f6-f12函數(shù)是多峰函數(shù)，函數(shù)的具體取值范圍和最優(yōu)解如表1所示。

5.2 實(shí)驗(yàn)與結(jié)果分析

將本文提出的KMS-CCPSO算法與兩個(gè)普通粒子群優(yōu)化算法：PSO算法[4]和MSM-PSO算法[6]及處理高維問(wèn)題的算法：CPSO-HK算法[11]和CCPSO2算法[14]進(jìn)行比較。本實(shí)驗(yàn)采用MATLAB7.8進(jìn)行仿真，系統(tǒng)軟硬件環(huán)境為：2.20 GHz，4.00 GB內(nèi)存，Windows7操作系統(tǒng)。實(shí)驗(yàn)中最大迭代次數(shù)為1 000次，粒子數(shù)目為36個(gè)，測(cè)試函數(shù)為100維，取30次運(yùn)行結(jié)果的平均值。具體實(shí)驗(yàn)結(jié)果如表2所示。其中均值表示算法的尋優(yōu)能力，方差表示算法的穩(wěn)定性。

KMS-CCPSO算法的運(yùn)行時(shí)間隨著問(wèn)題維數(shù)的增加會(huì)逐漸增加，仍與CCPSO2算法[14]的運(yùn)行時(shí)間相當(dāng)，優(yōu)化性能卻明顯高于CCPSO2算法[14]。時(shí)間復(fù)雜度可表示為O(N×D×maxiter)，其中，N為粒子群數(shù)目，D為粒子維數(shù)，maxiter表示粒子群優(yōu)化的最大迭代次數(shù)。

由表2可知，在均值指標(biāo)中，除了f8測(cè)試函數(shù)外，KMS-CCPSO算法的收斂精度都高于其他對(duì)比算法，尤其是在f4測(cè)試函數(shù)中，收斂精度和穩(wěn)定性明顯高于其他算法；在方差指標(biāo)中，本文算法穩(wěn)定性明顯高于對(duì)比算法。圖2~7給出了KMS-CCPSO算法與其他四個(gè)對(duì)比算法在不同函數(shù)中的迭代進(jìn)化曲線對(duì)比。從圖中可以看出，從迭代初期開(kāi)始，本文提出的KMS-CCPSO算法在收斂速度上就具有明顯優(yōu)勢(shì)，且隨著迭代次數(shù)的增加算法搜索到的解的精度也較高。圖8~10給出了KMS-CCPSO算法與其他四個(gè)對(duì)比算法在不同維數(shù)下的最優(yōu)解值。從圖中可以看出，對(duì)比算法在不同的測(cè)試函數(shù)中，找到最優(yōu)解的能力不同，如CPSO-HK算法[11]在f1和f2測(cè)試函數(shù)里隨著位數(shù)的增加，其尋優(yōu)能力依然較好，但是在f3測(cè)試函數(shù)里該算法的尋優(yōu)能力逐漸變差。從圖8-10中可以看出。KMS-CCPSO算法在不同的測(cè)試函數(shù)里隨著維數(shù)的增加，其尋優(yōu)能力保持平穩(wěn)不變。由于篇幅有限，本文只列舉了最具有代表性的6個(gè)測(cè)試函數(shù)在100維上的對(duì)比圖及3個(gè)測(cè)試函數(shù)的維數(shù)遞增曲線對(duì)比圖，在其他的測(cè)試函數(shù)中，KMS-CCPSO算法上也具有相似的性能。

表2 五個(gè)算法的最優(yōu)解平均值和方差比較

圖2 f1迭代進(jìn)化曲線對(duì)比圖

圖3 f4迭代進(jìn)化曲線對(duì)比圖

圖4 f5迭代進(jìn)化曲線對(duì)比圖

圖5 f6迭代進(jìn)化曲線對(duì)比圖

圖6 f7迭代進(jìn)化曲線對(duì)比圖

圖7 f8迭代進(jìn)化曲線對(duì)比圖

圖8 f1維數(shù)增加的最優(yōu)解對(duì)比圖

圖9 f2維數(shù)增加的最優(yōu)解對(duì)比圖

圖10 f7維數(shù)增加的最優(yōu)解對(duì)比圖

6 結(jié)束語(yǔ)

針對(duì)現(xiàn)有的粒子群優(yōu)化算法易陷入局部最優(yōu)和處理高維優(yōu)化問(wèn)題性能差的問(wèn)題，本文提出了基于K-均值的協(xié)同進(jìn)化粒子群優(yōu)化（KMS-CCPSO）算法，引入了分組策略、K-均值算法和高斯-柯西分布的位置更新公式，增加種群的多樣性，有助于種群跳出局部最優(yōu)。通過(guò)對(duì)12個(gè)測(cè)試函數(shù)的仿真實(shí)驗(yàn)驗(yàn)證了KMS-CCPSO算法具有較好的收斂精度和穩(wěn)定性，能夠較好地處理高維優(yōu)化問(wèn)題。

[1]Kennedy J，Eberhartr C.Particle swarm optimization[C]//Proc ofIEEE IntConfon NeuralNetworks.Perth：IEEE Piscataway，1995：1942-1948.

[2]Parsopoulos K E，Vrahatis M N.Recent approaches to global optimization problems through particle swarm optimization[J].Natural Computing，2002，1（2/3）：235-306.

[3]Poli R，Kennedy J，Blackwell T.Particle swarmoptimization an overview[J].Swarm Intelligence，2007，1（1）：33-57.

[4]Shi Y，Eberhart R.A modified particle swarm optimizer[C]//Proceedings of International Conference on Evolutionary Computation，Anchorage，Alaska，1998：69-73.

[5]Zhan Z H，Zhang J，Li Y，et al.Adaptive particle swarm optimization[J].IEEE Trans on Systems，Man，and Cybernetics-Part B：Cybernetics，2009，39（6）：1362-1381.

[6]徐冰純，葛洪偉，王燕燕.基于多種群多模型協(xié)同進(jìn)化的粒子群優(yōu)化算法[J].計(jì)算機(jī)工程，2013，39（5）：200-208.

[7]Gies D，Rahmat-Samii Y.Particle swarm optimization for reconfigurable phase-differentiated array design[J].Microwave and Optical Technology Letters，2003，38（3）：168-175.

[8]Ursem R K，Vadstrup P.Parameter identification of induction motors using differential evolution[C]//The 2003 Congress on Evolutionary Computation，IEEE，2003，2：790-796.

[9]Foli K，Okabe T，Olhofer M，et al.Optimization of micro heat exchanger：CFD，analytical results and multiobjective evolutionary algorithms[J].Int J Heat Mass Transfer，2006，49（5/6）：1090-1099.

[10]Potter M A，De Jong K A.A cooperative coevolutionary approach to function optimization[C]//Proceedings of the Third Internation Conference on Parallel Problem Solving from Nature，Jerusalem，Israel，1994：249-257.

[11]Bergh F V D，Engelbrecht A P.A cooperative approach to particle swarm optimization[J].IEEE Trans on Evolutionary Computation，2004，8（3）：225-239.

[12]Yang Z Y，Tang K，Yao X.Large scale evolutionary optimization using cooperative co-evolution[J].Information Sciences，2008，178（15）：2985-2999.

[13]Omidvar M N，Li X，Yang Z，et al.Cooperative co-evolution for large scale optimization through more frequent random grouping[C]//2010 IEEE Congress on Evolutionary Computation（CEC），IEEE，2010：1-8.

[14]LI X D，YAO X.Cooperatively coevolving particle swarms for large scale optimization[J].IEEE Trans on Evolutionary Computation，2012，16（2）：210-224.

[15]Krishna K，Murty M N.Genetic K-means algorithm[J].Systems，Man and Cybernetics，1999，29（3）：433-439.