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

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

關(guān)鍵詞： 微分進(jìn)化算法； 粒子群算法； 主成分分析； 聚類分析； K?均值聚類算法

中圖分類號(hào)： TN710?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

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

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

1 基于主成分的微分進(jìn)化算法PCADE

1.1 算法介紹

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

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

種群采取的進(jìn)化策略如下：

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

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

1.2 算法流程

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

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

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

算法流程圖如圖1所示。

2 微分進(jìn)化算法在聚類分析中的應(yīng)用

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

為了對(duì)算法性能進(jìn)行評(píng)估，采用如下的評(píng)估辦法對(duì)測(cè)試函數(shù)1～4進(jìn)行評(píng)價(jià)：

（1） 適應(yīng)度值平均值：由于多次獨(dú)立運(yùn)行結(jié)果存在數(shù)值上的差異，平均值表明其運(yùn)行結(jié)果的平均性能；

（2） 最佳適應(yīng)度值，最差適應(yīng)度值：考慮在運(yùn)行過(guò)程中的隨機(jī)性，增加10 次運(yùn)行結(jié)果的最佳適應(yīng)度和最差適應(yīng)度值；

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

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

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

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

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

利用上述測(cè)試函數(shù)對(duì)三種算法進(jìn)行數(shù)值實(shí)驗(yàn)，利用Matlab編程軟件進(jìn)行編程，得出結(jié)果如表1～表3所示。

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

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

4 結(jié) 論

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

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

從上述兩個(gè)方面來(lái)看，該改進(jìn)的微分進(jìn)化算法PCADE在性能方面有了很大的提升，值得進(jìn)一步推廣。

參考文獻(xiàn)

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

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

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

[4] 歐陳委.K?均值聚類算法的研究與改進(jìn)[D].長(zhǎng)沙：長(zhǎng)沙理工大學(xué)，2011.

[5] 孟凡軍，李天偉，徐冠雷，等.基于K?均值聚類算法的霧天識(shí)別方法研究[J].現(xiàn)代電子技術(shù)，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.