微分進化算法的優(yōu)化研究及其在聚類分析中的應用

摘 要： 為了使微分進化算法在進化過程中充分挖掘和利用歷史數據信息，提高它的全局搜索能力和收斂速度，提出了一種基于主成分的微分進化算法PCADE。該算法將種群空間映射到主成分空間從而得到一個由主成分構成的種群空間，在進化過程中前個主成分構成的個體可以直接進入下一代的進化，而剩余的個個體則從原種群和主成分種群空間中選擇出適應度值較高的個體進入下一代。實驗結果表明改進算法在聚類分析中取得了較好的結果。

關鍵詞： 微分進化算法； 粒子群算法； 主成分分析； 聚類分析； K?均值聚類算法

中圖分類號： TN710?34； TM417 文獻標識碼： A 文章編號： 1004?373X（2016）13?0103?05

Abstract： In order to make the differential evolution algorithm fully mine and use the historical data information in evolution process， and improve the global searching ability and convergence rate， a differential evolution algorithm based on principal component PCADE is proposed in this paper. The population space is mapped to the principal component space in this algorithm to obtain a population space composed of principal component. In evolution process， the first individuals composing of the principal component can access to the next generation evolution directly， and the individual with high fitness value in the residual N?m individuals is selected from the original population and principal component population space to access to the next generation. The experimental results show that the improved algorithm can obtain better result in cluster analysis.

Keywords： differential evolution algorithm； particle swarm optimization algorithm； principal component analysis； cluster analysis； K?means clustering algorithm

0 引 言

微分進化算法作為一種新興的演化計算方法，它不依賴具體問題的領域，有很強的魯棒性，是求解復雜系統(tǒng)優(yōu)化問題的有效方法，因此在很多領域都得到了廣泛的應用。微分進化算法雖然計算簡單，但是易限入局部最優(yōu)，存在早熟收斂現象。目前主要通過三個方面解決：一是調整控制參數改進算法；二是通過對搜索空間的改進提高算法性能；三是和其他算法結合產生新的混合算法。

本文主要對微分進化算法的收斂性及收斂速度進行深入分析，提出一種改進策略，提高算法的全局搜索能力和收斂速度，防止算法出現早熟的現象。并將改進的微分進化算法應用于聚類分析問題中，用于改善K?均值算法對初始聚類中心的敏感性。針對K?均值算法對噪聲數據、孤立點、初始聚類中心的敏感性，利用基于PCADE算法對K?均值聚類算法進行改進，并利用典型的測試數據集IRIS進行驗證，實驗結果表明該改進算法在聚類結果的精度方面有所提高。

1 基于主成分的微分進化算法PCADE

1.1 算法介紹

在群體的進化過程中如果子代能夠遺傳到父代較多的優(yōu)良信息，那么就越容易收斂到最優(yōu)解，子代個體的產生只是從種群中隨機挑選父代個體進行差分而得到的，而且并沒有遺傳到除了父代之外其他個體的任何信息。為了充分利用歷史數據信息，將主成分分析的方法引入到微分進化算法中。

主成分分析方法可以將數據中彼此相關的變量經過線性變換轉化為不相關的變量而且又能夠反應原始數據的大部分特征。那么在微分進化算法的迭代過程中，利用主成分分析方法，將種群pop經過線性變換映射到主成分構成的種群空間pca_pop中。在主成分構成的種群pca_pop中各個體之間互不相關，而且前m個主成分就能代表原始數據中80%以上的信息量。那么種群的更新將在這兩個空間中進行。

種群采取的進化策略如下：

假設迭代到第k代，種群pop（k）完成微分進化算法的交叉、變異，選擇時不立即進行下一代的進化，而是首先將該種群pop（k）映射到其主成分空間得到主成分種群pca_pop（k），然后將前個主成分作為下一代種群的前m個個體，即pca_pop（k）中前m個個體為pop（k+1）中前m個個體，種群pop（k+1）中剩余的N-m個個體從pca_pop（k），pop（k）中選出適應度值高的個體進入pop（k+1），直到種群個體數達到N。這樣就得到了下一代的種群pop（k+1），然后繼續(xù)進行下一步的迭代過程。

由于主成分構成的個體之間具有很小的相關性，當進化若干代之后，個體之間進行信息交流，提高種群多樣性，避免種群趨于一致性，極大地搜索出新的解空間，利于找到全局最優(yōu)解。

1.2 算法流程

Step5：計算種群pop的協(xié)方差矩陣，求解協(xié)方差矩陣的特征值和特征向量然后求主成分，得到一個由主成分構成的新的種群pca_pop；

Step6：種群pca_pop中主成分累積貢獻度達到90%的前個個體直接進入下一代，剩余個個體從種群pca_pop，pop中選出適應度值較高的個體進入下一代，直到種群規(guī)模達到

Step7：判斷是否滿足迭代條件，若不滿足則返回Step2。

算法流程圖如圖1所示。

2 微分進化算法在聚類分析中的應用

2.1 基于DE的K?均值聚類算法

K?均值算法對初始點的選取和樣本中的孤立點是敏感的，而且易陷入局部極小值，導致算法的聚類結果穩(wěn)定性較差。如果能采用一種快速有效的優(yōu)化算法對聚類中心進行優(yōu)化，找到質量較高的聚類中心，勢必會大大提高聚類的質量。目前針對這些問題處理的方法有很多，很多學者用模擬退火，遺傳算法，粒子群算法，蟻群算法等對K?均值算法進行改進，都取得了不錯的效果，和其他優(yōu)化算法相比，微分進化算法具有結構簡單，參數少，易于實現的優(yōu)良性能，因此將微分進化算法引入到K?均值算法中，將二者有機結合，彌補K?均值算法對孤立點的敏感性，發(fā)揮二者的優(yōu)勢，形成性能較優(yōu)的混合算法。

聚類問題的核心是求解各個聚類中心，因此利用DE算法進行聚類選取的時候，一個重要的問題是對聚類中心編碼。設在空間中，給定數據集該數據集共有個樣本，每個樣本點包含個屬性，即要將樣本數據分成類，在基于DE的聚類分析中，每個個體代表個聚類的中心，因此個體實際上就是維的向量。這樣每個個體采用如下的編碼結構：

2.2 基于PCADE的K?均值聚類算法

上述將微分進化算法引入到K?均值算法中，將二者有機結合，彌補K?均值算法對孤立點的敏感性，發(fā)揮二者的優(yōu)勢，形成性能較優(yōu)的混合算法。但是微分進化算法本身容易陷入局部最優(yōu)，尤其是算法進化后期收斂速度有所下降，因此將改進的微分進化算法PCADE與K?均值算法相結合，產生一種新的混合算法。

3 實驗結果及分析

為了驗證上述基于主成分分析方法的微分進化算法PCADE能否得到好的效果，利用測試函數對該改進算法進行數值實驗，并與原始微分進化算法（DE），粒子群算法（PSO）進行比較。首先DE算法中CR=0.5，最大迭代次數設置為1 000代；PSO算法慣性系數從0.9線性減少到0.1，最大迭代次數設置為1 000代；改進的微分進化算法PCADE中CR=0.5，主成分累積貢獻度為90%，最大迭代次數設置為1 000代。以上三種算法種群個數維數連續(xù)運行10次。

為了對算法性能進行評估，采用如下的評估辦法對測試函數1～4進行評價：

（1） 適應度值平均值：由于多次獨立運行結果存在數值上的差異，平均值表明其運行結果的平均性能；

（2） 最佳適應度值，最差適應度值：考慮在運行過程中的隨機性，增加10 次運行結果的最佳適應度和最差適應度值；

（3） 收斂曲線圖：從收斂曲線圖中可以直觀看出算法的收斂速度和收斂的精度。

測試函數1：的取值范圍為[-100，100]，最優(yōu)解為0；

測試函數2：的取值范圍為[-10，10]，最優(yōu)解為0；

測試函數3：的取值范圍為[-1.28，1.28]，最優(yōu)解為0；

測試函數4：的取值范圍為[-5.12，5.12]，最優(yōu)解為0。

利用上述測試函數對三種算法進行數值實驗，利用Matlab編程軟件進行編程，得出結果如表1～表3所示。

聚類算法仿真實驗的環(huán)境為：仿真軟件Matlab 7.0，采用的測試數據集為IRIS數據集。IRIS數據集被作為機器學習中分類問題的基準測試數據集，IRIS數據集一共包含150個樣本，3類花型（setosa，versicolor，vinginica）4個特征屬性（萼片長，萼片寬，花瓣長，花瓣寬），每類花一共有50個樣本。在進行聚類分析時，由于樣本數據受量綱和數量級的影響，因此在聚類分析處理過程中，應對原始數據矩陣進行變換處理，就是從數據矩陣的每個變量中找出其最大值和最小值，這兩者之差稱為極差，然后將每個原始數據減去該變量的最小值，再除以極差就得到規(guī)格化數據，進行規(guī)格化變化之后數據的特點是將數據轉化到[0，1]之間。將規(guī)格化后的數據集用來測試K?均值算法，基于微分進化的K?均值算法以及提出的基于PCADE的K?均值算法，從聚類結果分析聚類的效果。本文中算法參數設置如下：種群規(guī)模放縮因子交叉概率CR=0.5，累積貢獻度=90%，最大迭代次數50，獨立運行10次，實驗以10次運行結果取平均來分析聚類的好壞，如表4和圖8所示。

從表4結果可以看出在獨立運行10次之后，PCADE?Kmeans算法的正確識別率要高于其他兩種算法，最優(yōu)運行結果的正確率可以達到94.67%。從圖8也可以看出PCADE?Kmeans算法將IRIS數據進行了很好的聚類。因此改進的算法性能較好。

4 結 論

微分進化算法利用自然界優(yōu)勝劣汰的思想和簡單的差分操作使得其在一定程度上具有自組織、自適應、自學習的特征。但微分進化算法跟其他進化算法一樣存在早熟收斂等問題，因此對微分進化算法進行改進，提高其全局搜索能力和收斂速度，使之能夠適應各種復雜的工程問題，這是一個值得深入研究的領域。

本文通過研究國內外學者對微分進化算法的改進方法，提出了一種基于主成分的微分進化算法，該算法將種群空間映射到由主成分構成的種群空間，主成分空間中前個主成分構成的個體可以直接進入下一代的進化，而其余的個體則從主成分空間和原始種群空間中挑選出適應度值高的進入下一代，這樣的改進方法使得種群能夠更多地獲得父代的信息，增加了種群的多樣性。通過數值實驗證明該算法在收斂精度和收斂速度上都有很大的提高。該算法對聚類中心進行編碼構成進化種群，利用PCADE算法更新種群，最終得到較好的聚類中心，然后根據聚類中心對樣本進行聚類，利用IRIS數據集進行試驗，結果表明基于PCADE的K?均值聚類算法在聚類問題中得到了較好的結果。

從上述兩個方面來看，該改進的微分進化算法PCADE在性能方面有了很大的提升，值得進一步推廣。

參考文獻

[1] 李士勇，陳永強，李研.蟻群算法及其應用[M].哈爾濱：哈爾濱工業(yè)大學出版社，2004.

[2] 胡中波，熊盛武，胡付高.改進的差分演化算法及其在函數優(yōu)化中的應用[J].武漢理工大學學報，2007，29（4）：125?128.

[3] 蘇海軍，楊煜普，王宇嘉.微分進化算法的研究綜述[J].系統(tǒng)工程與電子技術，2008，30（9）：1793?1797.

[4] 歐陳委.K?均值聚類算法的研究與改進[D].長沙：長沙理工大學，2011.

[5] 孟凡軍，李天偉，徐冠雷，等.基于K?均值聚類算法的霧天識別方法研究[J].現代電子技術，2015，38（22）：56?58.

[6] VOSS M S. Principal component particle swarm optimization [C]// Proceedings of 2005 IEEE Swarm Intelligence Symposium. [S.l.]： IEEE， 2005： 401?404.

[7] EBERHART R， SHI Y. Comparing inertia weights and constriction factors in particle swarm optimization [C]// Proceedings of 2000 IEEE Congress on Evolutional Computation. La Jolla： IEEE， 2000： 84?88.

[8] TASGETIREN M F， SUGANTHAN P N. A multi?populated differential evolution algorithm for solving constrained optimization problem [C]// Proceedings of 2006 IEEE Congress on Evolutionary Computation. Vancouver： IEEE， 2006： 33?40.