王鳳領(lǐng) 梁海英 張 波

（賀州學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院 賀州 542899）

1 引言

差分進(jìn)化算法（DE）是由Storn.R和Price.K提出的一種基于群體進(jìn)化的啟發(fā)式算法，該算法從原始種群開始，通過變異、交叉和選擇操作來生成新種群，是一種隨機(jī)的并行全局搜索算法，具有記憶個體最優(yōu)解和種群內(nèi)信息共享的特點(diǎn)，即通過種群內(nèi)個體間的合作與競爭來實(shí)現(xiàn)對優(yōu)化問題的求解。差分進(jìn)化算法具有簡單高效、收斂速度快、魯棒性好等優(yōu)點(diǎn)。如劉明廣通過引入遷徙操作而提出一種改進(jìn)差分進(jìn)化算法，吳亮紅提出的基于群體適應(yīng)度二次變異的自適應(yīng)方差的差分進(jìn)化算法。

K-means算法是由Mac（lueen）提出的經(jīng)典聚類分析算法。它具有算法簡單，收斂快的優(yōu)點(diǎn)，但算法的聚類結(jié)果容易受到初始聚類中心的影響，易于陷入局部最優(yōu)。近年來，許多學(xué)者利用各種常用的智能優(yōu)化算法來改進(jìn)K-means算法，并取得了一些成果。基于差異進(jìn)化的K-means算法的改進(jìn)優(yōu)于基于傳統(tǒng)遺傳算法和微粒群優(yōu)化算法。但傳統(tǒng)的差分進(jìn)化算法也會造成全局尋優(yōu)能力下降，基于傳統(tǒng)差分進(jìn)化的K均值改進(jìn)算法的性能受到全局優(yōu)化能力的影響。本文提出基于改進(jìn)的差分進(jìn)化的K均值聚類算法。結(jié)合改進(jìn)的差分進(jìn)化算法和K均值，實(shí)驗(yàn)結(jié)果表明，該算法具有更好的全局優(yōu)化能力和更快的收斂性。

2 差分進(jìn)化算法

2.1 研究現(xiàn)狀

2013年，Liang Bai等提出一種快速全局K-means算法，有效提高算法的聚類速度。在2014年，Aristidis Likas和Grigorios Tzortzis提出一種基于權(quán)重的K-means算法。2015年，Li Ma等提出了一種改進(jìn)的K-mean算法。近幾年，國內(nèi)外許多研究人員將K-means和DE算法組合，取得一些成果。2015年Wan-li Xiang等使用動態(tài)攪亂差分進(jìn)化算法進(jìn)行聚類。2008年Swagatam Das等提出了基于差分進(jìn)化的自動聚類算法（ACDE）。喬艷霞等提出一種基于K-means的改進(jìn)差分進(jìn)化聚類算法，將差分進(jìn)化算法用于K-means聚類。劉莉莉等改進(jìn)自適應(yīng)調(diào)整的控制參數(shù)、將差分進(jìn)化算法用選擇結(jié)構(gòu)的多模式進(jìn)化方案，并將其與K-means聚類算法相結(jié)合，有效地解決初始聚類中心的優(yōu)化問題。高平，毛力等提出了一種基于改進(jìn)差分進(jìn)化的K-means聚類算法，通過Logistic變尺度混濁搜索，增強(qiáng)差分進(jìn)化算法的全局尋優(yōu)能力［1］。

2.2 差分進(jìn)化算法的關(guān)鍵操作

差分進(jìn)化算法（DE）是一種典型的實(shí)數(shù)編碼的進(jìn)化算法，采用變異、雜交、選擇等關(guān)鍵性操作從上一代種群到下一代種群的進(jìn)化，以實(shí)現(xiàn)群體優(yōu)化，下面將分析差分進(jìn)化算法中涉及的幾個操作［2］。

1）種群初始化

定義N×D的矩陣X用于存放當(dāng)前種群的數(shù)據(jù)，其中，D為種群中個體的維數(shù)，N為種群的規(guī)模，隨機(jī)產(chǎn)生N×D個服從均勻分布規(guī)律并滿足特定約束條件的數(shù)據(jù)，放入矩陣X中，構(gòu)成初始種群X(0)={X1(0)，X2(0)…XN(0)}。

2）變異操作

令種群大小為N，當(dāng)前進(jìn)化個體Xi(t)(i=1，2，…，N)表示，t為當(dāng)前進(jìn)化個數(shù)。隨機(jī)選擇三個不同的個體，從當(dāng)前進(jìn)化群體中，并滿足條件 r1，r2，r3∈{1，2，…，N}，r1≠r2≠r3≠i，個體Xr2(t)和 Xr3(t)差值(Xr2(t)-Xr3(t))被看作個體Xr1(t)的擾動因子［2］。將因子和個體 Xi(t)相加以獲得當(dāng)前突變，突變操作的演變的對應(yīng)個體Vi(t)，如式（1）所示:

其中F為控制擾動因子的縮放系數(shù)。群體中個體由D個分量組成，那么變體個體Vi(t)也由D個分量組成，即Vi(t)=vr1(t)，vr2(t)，…，viD(t))。

3）交叉操作

生成隨機(jī)整數(shù)r4，且 r4∈{1，2，…，N}，離散變異個體Vi(t)與當(dāng)前進(jìn)化個體Xi(t)交叉以獲得中間測試個體Ui(t)，其將與 Xi(t)選擇操作競爭，并且Ui(t)由D組分組成，即Ui(t)=(ui1(t)，ui2(t)，…，uiD(t))。其中第j個分量如式（2）所示:

r4是｛1，2，…，D｝中的隨機(jī)整數(shù)，randj（0，1）表示服從（0，1）上均勻分布的隨機(jī)數(shù)，并且r4可以保證在突變個體Vi(t)中存在至少一個維度分量，測試個體Ui(t)，確保突變操作的作用力。CR是交叉概率，并且CR∈［0，1］，CR概率越小，中間試驗(yàn)個體Ui(t)對當(dāng)前進(jìn)化個體Xi(t)的相似性越大。這可以幫助確保群體的多樣性和算法的全局優(yōu)化［3］。

4）選擇操作

在最小化問題的情況下，適應(yīng)度值越小越好［4］。如果Ui(t)的適應(yīng)度值小于的適應(yīng)度值，中間實(shí)驗(yàn)Ui(t)將替代新個體 Xi(t+1)中的當(dāng)前個體Xi(t)。否則，當(dāng)前進(jìn)化的個體 Xi(t)將直接到下一代。如果個體適合度值由 f(Xi(t))表示，則選擇操作可以式（3）表示如下:

5）參數(shù)設(shè)定

差分進(jìn)化算法的主要控制參數(shù)有縮放系數(shù)、交叉概率CR以及F種群規(guī)模N。對差分進(jìn)化算法的性能有著重要影響，尤其是縮放系數(shù)和交叉概率，在某種程度上決定算法的收斂速度和全局搜索能力［4］。

2.3 差分進(jìn)化算法的步驟和流程

1）步驟

種群中的每個體都是求解問題的可行解，種群規(guī)模為N，個體的適應(yīng)度表示為 f(Xi(t))函數(shù)，其中Xi(t)表示第t代種群的第i個個體，F(xiàn)是縮放系數(shù)，t是進(jìn)化代數(shù)。CR表示交叉概率。養(yǎng)分進(jìn)化算法的步驟描述為

步驟1:完成種群初始化，設(shè)群體大小N，縮放因子F∈［0，2］，交叉概率 CR∈［0，1］，進(jìn)化代數(shù)t=0，隨機(jī)生成初始種群 X(0)={X1(0)，X2(0)，…，XN(0)}，其中，對任一個體 Xi(0)都含D個分量的向量，即 Xi(0)={Xi1(0)，Xi2(0)，…，XiD(0)}；

步驟2:計(jì)算出每個體的適應(yīng)度值 f(Xi(t))，對種群中的每個體進(jìn)行評價；

步驟3:對種群個體 Xi(t)按式（1）完成變異操作，將得到變異個體Vi(t)；

步驟5:對于最小化求解問題，具有小適應(yīng)度函數(shù)值的個體進(jìn)入下一代種群中繼續(xù)進(jìn)化。采取貪心策略，在選擇操作過程中，擇優(yōu)選取，比較當(dāng)前進(jìn)化個體Xi(t)與相對應(yīng)中間試驗(yàn)個體的適應(yīng)度值。選擇方式按式 Xi(t+1)進(jìn)行；

步驟6:對種群X(t+1)中的個體進(jìn)行檢驗(yàn)，如果終止算法滿足條件，則輸出；否則t=t+1，轉(zhuǎn)到步驟2。

2）算法流程

根據(jù)上述差分進(jìn)化算法的描述，得到差分進(jìn)化算法的流程圖［5］，如圖1所示。

圖1 差分進(jìn)化算法的流程圖

3 基于差分進(jìn)化算法的K-均值聚類

差分進(jìn)化算法是基于選擇、交叉、變異操作的全局優(yōu)化算法，差分算法用于操作對多個個體組成的群體，該群體中的個體經(jīng)過優(yōu)化，逐漸接近最優(yōu)解，可通過K-均值聚類算法避免容易陷入局部最優(yōu)解的缺陷，提高算法收斂速度和算法的穩(wěn)定性［6］。

3.1 基于差分進(jìn)化的K-均值聚類算法描述

首先需要對從數(shù)據(jù)集中隨機(jī)選擇的聚類中心進(jìn)行編碼，構(gòu)建初始種群，然后進(jìn)行差分進(jìn)化算法的選擇、交叉、變異等，以獲得最佳個體，最后，最佳個體解碼，獲得最佳初始聚類中心并進(jìn)行聚類［7］。其步驟如下。

輸入:包含n個數(shù)據(jù)對象的數(shù)據(jù)集X、聚類數(shù)目K、縮放系數(shù)F、種群大小N、交叉概率CR。

輸出:輸出最佳聚類結(jié)果。

步驟1編碼:使用實(shí)數(shù)編碼從數(shù)據(jù)集中隨機(jī)選擇聚類中心，對與可行解對應(yīng)的編碼進(jìn)行編碼；每個個體由K個聚類中心向量串組成，因?yàn)闃颖鞠蛄烤S數(shù)d，所以每個個體應(yīng)該是K×d維向量［8］。具體編碼如下:

其中，Xi(t)為第t代種群的第i個個體，表示第i個個體的第j個聚類中心，迭代次數(shù)t的初始值為0。

步驟2種群初始化:從數(shù)據(jù)集K數(shù)據(jù)樣本中隨機(jī)選取個體作為初始種群，重復(fù)N次操作，構(gòu)建初始種群。

步驟3評價種群中每一個體；計(jì)算個體Xi(t)的適應(yīng)度值 f(Xi(t))。

步驟4變異操作:從種群中隨機(jī)選擇三個個體Xa，j(t)，Xb，j(t)，Xc，j(t)，并且 a≠b≠c≠i，并按如下式進(jìn)行計(jì)算得到變異個體Vi(t)，Vi(t)為縮放系數(shù)。

步驟5交叉操作:種群中的個體Xi(t)和變異個體Vi(t)進(jìn)行交叉操作，并按如下式進(jìn)行計(jì)算得到中間試驗(yàn)個體Ui(t):

其中，rand（0，1）是在（0，1）上均勻分布的隨機(jī)數(shù)，rand（i）是［1，K］上的隨機(jī)數(shù)。 CR是交叉概率，CR∈［0，1］。

步驟6選擇操作:在中間試驗(yàn)個體Ui(t)和當(dāng)前進(jìn)化個體Xi(t)之間，采用貪心算法計(jì)算和比較適應(yīng)度值，確定個體的最小適合度值，即最佳個體進(jìn)入下一代種群。

步驟7檢驗(yàn)種群X（t+1）中的個體，若滿足終止條件，則輸出最佳個體并終止算法；否則，迭代次數(shù)t將增加1，并返回步驟2繼續(xù)。

步驟8對輸出的最佳個體進(jìn)行解碼，得到相應(yīng)的最優(yōu)聚類中心集，并將種群中的所有數(shù)據(jù)對象劃分為相應(yīng)的簇中，根據(jù)最近鄰原則。

步驟9輸出聚類結(jié)果。

3.2 基于差分進(jìn)化的K-均值聚類算法流程

差分進(jìn)化算法是具有強(qiáng)大的全局搜索能力的進(jìn)化算法，應(yīng)用于優(yōu)化K-均值聚類算法的初始中心，有效克服K-均值聚類算法對初始中心值選擇敏感缺陷，大大提高初始聚類中心的質(zhì)量［9］。根據(jù)基于差分進(jìn)化的K-均值聚類算法的描述，得到基于差分進(jìn)化的K-均值聚類算法的流程圖，如圖2所示。

圖2 基于差分進(jìn)化的K-均值聚類算法的流程圖

4 改進(jìn)差分進(jìn)化的K-均值聚類算法

通過將差分進(jìn)化算法引入到K-均值聚類算法，可優(yōu)化初始聚類中心的選擇過程，簡便易行，提高聚類質(zhì)量和收斂速度。交叉和突變操作確保種群進(jìn)化的多樣性和算法的全局搜索能力［10］。然而，隨著差分進(jìn)化代數(shù)的增加，種群的多樣性將會變小，過早收斂到局部最小點(diǎn)，或者算法停滯不前［11］。因此，需要加強(qiáng)算法的局部搜索能力，特別是后期進(jìn)化算法收斂速度。在本文中，提出一種改進(jìn)的方案來提高算法的局部搜索能力［12］。

4.1 改進(jìn)方案

1）加強(qiáng)局部搜索能力

與標(biāo)準(zhǔn)差分進(jìn)化算法相比，全局優(yōu)化能力并沒有減弱，而且可以同時增強(qiáng)算法的局部搜索能力［13］。改進(jìn)方案的基本思想是記錄在算法變異操作中和個體Xi(t)對應(yīng)的兩個隨機(jī)個體之間的差，即 Xr2(t)-Xr3(t)，記為 Hi(t)，即 Hi(t)=Xr2(t)-Xr3(t)，在選擇操作之后獲到的個體Xi(t+1)為中心，Hi(t)為半徑，并在此范圍內(nèi)繼續(xù)搜索，產(chǎn)生新個體與 Xi(t+1)的適應(yīng)度值，如果在此范圍內(nèi)搜索新產(chǎn)生的個體適應(yīng)度值優(yōu)于Xi(t+1)，用個體(t+1)替代 Xi(t+1)將成為新的Xi(t+1)，從而加強(qiáng)原差分進(jìn)化算法的局部搜索功能［14］。

2）采用動態(tài)縮放系數(shù)

差分進(jìn)化算法中設(shè)置控制參數(shù)對算法的性能有重要的影響。在本文中，采用開口向上拋物線方式取值縮放系數(shù)F，F(xiàn)的值如式（6）:

其中，F(xiàn)min為最小縮放系數(shù)，且Fmin=0.4，F(xiàn)max為最大縮放系數(shù)，且Fmax=0.9。t為當(dāng)前進(jìn)化的代數(shù)，TMAX為算法設(shè)定的最大進(jìn)化代數(shù)。

3）采用動態(tài)交叉概率

在本文中，采取隨進(jìn)化代數(shù)線性增加的交叉概率取值策略，交叉概率CR對差分進(jìn)化算法的收斂速度有直接和重要的影響，方法如式（7）:

其中，CRmax為最大交叉概率，CRmax=0.9，CRmin為最小交叉概率，CRmin=0.3，t為當(dāng)前進(jìn)化代數(shù)，TMAX為算法設(shè)定的最大進(jìn)化代數(shù)。

4.2 算法描述

根據(jù)上述改進(jìn)方案，改進(jìn)了標(biāo)準(zhǔn)差分進(jìn)化算法，并將改進(jìn)的差分進(jìn)化算法應(yīng)用于K-均值聚類算法中初始聚類中心的優(yōu)化。對于一組聚類中心（c1，c2，…，cK），在K-均值聚類算法中，相應(yīng)的類內(nèi)距離定義為式（8）:

其中，mi為簇wi的中心，x是簇wi中的數(shù)據(jù)樣本，通過計(jì)算簇wi中所有數(shù)據(jù)樣本的均值來獲得，本文中的適應(yīng)度函數(shù)采用式（9）:

算法描述如下:

輸入:含有n個數(shù)據(jù)對象的數(shù)據(jù)集X、聚類數(shù)目K、種群規(guī)模N。

輸出:輸出最佳聚類結(jié)果。

步驟1:用于對聚類中心進(jìn)行編碼以完成種群初始化:對于使用實(shí)際編碼從數(shù)據(jù)中心對數(shù)據(jù)集進(jìn)行隨機(jī)選擇，進(jìn)化代數(shù)t=0，一組K個聚類中心對應(yīng)于一個個體，因?yàn)榫垲愔行拇砭垲?，種群N的大小，表明初始種群代表N種聚類，單個體由K個基因位向量串組成，基因位代表聚類中心，編碼如式（4）。

假設(shè)每個聚類中心的向量維數(shù)為d，數(shù)據(jù)樣本的維數(shù)為d維，種群中的每個個體為K×d維向量。從數(shù)據(jù)集K數(shù)據(jù)樣本中隨機(jī)選擇K個體的初始種群，重復(fù)N次操作，以構(gòu)建初始種群。

步驟2:個體評價，計(jì)算每個個體的適應(yīng)度值f(Xi(t))。

步驟3:變異操作，根據(jù)個體基因位進(jìn)行變異，個體 Xi(t)按式 vij(t)=xaj(t)+F(xbj(t)-xcj(t))(j=1，2，…，K)計(jì)算得到變異個體Vi(t)，記錄兩個隨機(jī)個體 的 差 值 Hi(t)=Xb(t)-Xc(t) ，Hi(t)=(hi1(t)，hi2(t)，…，hiK(t))為縮放系數(shù)，按照公式 F=(Fmax-Fmin)執(zhí)行動態(tài)遞減策略取值。

步驟4:交叉操作，按照式 uij(t)=計(jì)算得到中間試驗(yàn)個體Ui(t)，Ui(t)是由K維分量組成的，即Ui(t)=(ui1(t)，ui2(t)，…，uiK(t))。其中，CR為交叉概率，CR進(jìn)行取值策略。隨著進(jìn)化代數(shù)的增加，CR的值線性增加。

步驟5:選擇操作，中間試驗(yàn)個體Ui(t)和當(dāng)前進(jìn)化個體Xi(t)之間，哪個個體進(jìn)入下一代種群中使用貪心選擇策略來決定。擇優(yōu)選取當(dāng)前進(jìn)化個體Xi(t)與其對應(yīng)中間試驗(yàn)個體Ui(t)的適應(yīng)度值。對于最小化求解問題，具有較小適應(yīng)度值的個體可能繼續(xù)進(jìn)化成下一代種群。按式進(jìn)行選擇。

步驟6:檢驗(yàn)下一代種群中的個體，若滿足終止條件，則輸出最佳個體并終止算法；否則，迭代次數(shù)增加1，返回繼續(xù)步驟2操作。

步驟7:對輸出的最佳個體進(jìn)行解碼以獲得相應(yīng)的最優(yōu)聚類中心集，并根據(jù)最近鄰原則將種群中的所有數(shù)據(jù)對象劃分為相應(yīng)的簇。

步驟8:輸出聚類結(jié)果。

4.3 算法流程

改進(jìn)的差分進(jìn)化算法的重要特征是添加二次選擇和二次變異操作以增強(qiáng)局部搜索能力。同時，交叉概率和縮放因子不是固定值，是采用動態(tài)變化值策略［15］。

基于上述改進(jìn)差分進(jìn)化的K-均值聚類算法的描述，得到改進(jìn)差分進(jìn)化的K-均值聚類算法流程圖，如圖3所示。

圖3 基于改進(jìn)差分進(jìn)化的K-均值聚類算法流程圖

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

采用UCI數(shù)據(jù)庫中的三個數(shù)據(jù)集:IRIS數(shù)據(jù)集，Glass數(shù)據(jù)集和Vowel數(shù)據(jù)集被用作測試數(shù)據(jù)集。三個數(shù)據(jù)集用于測試K-均值聚類算法，基于差分進(jìn)化算法的K-均值聚類算法和提出的基于改進(jìn)差分進(jìn)化的K-均值聚類算法的聚類效果。

表1 測試數(shù)據(jù)集特征描述

在基于差分進(jìn)化K-均值聚類算法的仿真實(shí)驗(yàn)中，種群大小N占相應(yīng)數(shù)據(jù)集維數(shù)D的10倍，最大迭代次數(shù)T設(shè)置為1800。交叉概率CR為0.5?？s放系數(shù)為0.6。在基于改進(jìn)差分進(jìn)化的K均值聚類算法的仿真實(shí)驗(yàn)中，種群大小N也取相應(yīng)數(shù)據(jù)集的維數(shù)D的10倍，最大迭代次數(shù)T也被設(shè)置為1800，交叉概率CR和縮放系數(shù)F按公式自適應(yīng)取值。K-均值聚類算法、基于差分進(jìn)化的K-均值聚類算法和基于改進(jìn)差分進(jìn)化的K-均值聚類算法這三個測試數(shù)據(jù)集用于進(jìn)行35次仿真實(shí)驗(yàn)。結(jié)果如表2所示。

表2 IRIS數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

對于Glass數(shù)據(jù)集，其實(shí)驗(yàn)結(jié)果如表3所示。

表3 Glass數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

對Vowel數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果如表4所示。

表4 在Vowel數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

通過上述實(shí)驗(yàn)結(jié)果，我們可以發(fā)現(xiàn)隨機(jī)選擇初始聚類中心的K-均值聚類算法的聚類結(jié)果波動范圍較大，穩(wěn)定性差。因此，實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了基于差分進(jìn)化和改進(jìn)算法的K-均值聚類算法大大提高了聚類結(jié)果的穩(wěn)定性和有效性，并且聚類質(zhì)量得到了顯著提高。從結(jié)果分析可以看出，提出的算法的聚類結(jié)果和質(zhì)量優(yōu)于基于標(biāo)準(zhǔn)差分進(jìn)化的K均值聚類算法。改進(jìn)算法的收斂速度比基于差分進(jìn)化聚類算法的K-均值聚類算法的收斂速度快。

5 結(jié)語

針對基于差分進(jìn)化的K均值聚類算法的缺陷，提出基于改進(jìn)差分進(jìn)化的K均值聚類算法，介紹改進(jìn)算法的改進(jìn)方案，步驟和具體流程。并對K-均值聚類算法、基于差分進(jìn)化的K-均值聚類算法和改進(jìn)算法進(jìn)行仿真實(shí)驗(yàn)。結(jié)果表明，該算法具有收斂快的優(yōu)點(diǎn)，不僅具有差分進(jìn)化算法的全局優(yōu)化能力，而且具有K-均值聚類算法的優(yōu)點(diǎn)，搜索速度快，結(jié)果穩(wěn)定。