基于K-均值聚類的協同進化粒子群優化算法

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

1.江南大學 物聯網工程學院，江蘇 無錫 214122

2.國網濰坊供電公司，山東 濰坊 261021

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

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

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

1 粒子群優化算法

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

2 協同進化粒子群優化算法

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

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

其中，X是交互變量劃分到同一個子種群的次數；k是當前迭代次數；N是總迭代次數；r是當前迭代次數；的簡寫是從N個次數中取出r(r≤N)個次數的組合數。m是子種群數；v是交互變量總數。

由概率計算公式（3）可知，CCPOS2算法采用的動態分組策略提高了交互變量劃分到同一子種群的概率。

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

3 K-均值算法

近年來，數據挖掘成為一個很熱的研究方向，作為其主要方法之一的聚類也因此受到人們的關注。K-均值算法[15]是最早提出的較為經典的聚類算法之一，該算法魯棒性較強，能夠解決傳統上難以解決的問題，已在諸多領域上得到了廣泛的發展和應用。

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

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

圖1中黑色圓點代表隨機選取的聚類中心；灰色圓點代表更新后的聚類中心；弧線代表劃分成兩個區域。

圖1 k-means算法的計算過程

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

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

4KMS-CCPSO算法

4.1 算法思想

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

4.2 算法步驟

為解決高維的優化問題，優化算法需要保持很好的搜索性和收斂性。KMS-CCPSO算法使用柯西和高斯分布相結合的公式[14]對粒子的位置進行更新，其中選取全局最優解和局部最優解的差值作為兩大分布的標準差，公式為：

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

算法的步驟如下：

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

步驟2隨機初始化種群中粒子的初始位置，選取聚類中心的初始點。

步驟3在約束條件下求出粒子的適應度值，并分別記錄個體最優解和全局最優解。

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

步驟5比較新種群中粒子的適應度值，獲得個體最優解，通過環拓撲循環得到粒子的局部最優解。

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

步驟7判斷是否滿足終止條件，即是否已經達到設置的最大迭代次數，若滿足，執行步驟8，若不滿足，則返回執行步驟3。

步驟8終止優化運算，輸出粒子最優位置。

表1 12個測試函數說明

4.3 算法偽代碼

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

5 仿真實驗與結果分析

5.1 測試函數

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

5.2 實驗與結果分析

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

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

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

表2 五個算法的最優解平均值和方差比較

圖2 f1迭代進化曲線對比圖

圖3 f4迭代進化曲線對比圖

圖4 f5迭代進化曲線對比圖

圖5 f6迭代進化曲線對比圖

圖6 f7迭代進化曲線對比圖

圖7 f8迭代進化曲線對比圖

圖8 f1維數增加的最優解對比圖

圖9 f2維數增加的最優解對比圖

圖10 f7維數增加的最優解對比圖

6 結束語

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

[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]徐冰純，葛洪偉，王燕燕.基于多種群多模型協同進化的粒子群優化算法[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.