雙精英遺傳策略的基因聚類算法

賈瑞玉，宋飛豹,湯深偉

(安徽大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601)

1 引 言

隨著DNA微陣列技術(shù)的出現(xiàn)，為我們提供了很多的基因表達(dá)數(shù)據(jù).如何通過基因表達(dá)數(shù)據(jù)來分析出樣本的顯著性特點是當(dāng)前的主要研究內(nèi)容之一.聚類算法是數(shù)據(jù)挖掘的重要算法[1-3]，也是分析基因表達(dá)數(shù)據(jù)的一個有效方法.王文俊等人[4]提出了核類別保留投影法,將其用于數(shù)據(jù)特征提取，提高了聚類的效率；黃健恒等人[5]將聚類算法鑲嵌于MapReduce框架中，加快了算法的運行速度;劉展杰等人[6]為了提高算法的魯棒性,利用流形學(xué)習(xí)將基因表達(dá)數(shù)據(jù)映射到一個局部子空間.雖然聚類算法可以很好的對基因數(shù)據(jù)進(jìn)行分析，但傳統(tǒng)的聚類算法依然存在初始中心點敏感、局部收斂等問題，常用的解決方法就是使用遺傳算法與聚類結(jié)合[7].何宏等人[8]通過最大屬性劃分法來確定初始種群，通過兩階段的交叉變異來提高算法收斂速度.Mitchell M等人[9]通過添加擾動項和補(bǔ)類的策略增加了算法的多樣性.

雖然遺傳算法能夠在一定程度上改善聚類算法的不足，但是遺傳算法本身也存在著早熟、局部收斂等問題，為了解決這些問題，孟偉等人[10]通過為每次進(jìn)化種群引入固定比例的隨機(jī)個體來降低早熟影響.

近幾年來，利用精英策略來改進(jìn)遺傳算法的研究越來越多.慕彩紅等人[11]將精英個體的數(shù)目提升為M個，通過M個精英個體的協(xié)同遺傳操作來提高算法的全局求優(yōu)能力.劉全等人[12]將進(jìn)化種群以精英集為基礎(chǔ)劃分成兩個子種群,分別進(jìn)行不同的遺傳操作，從而提升了算法的效率.王福才等人[13]提出了一種混合精英策略，兼顧了算法的局部搜索能力和全局搜索能力，黃永青等人[14]提出了基于精英保留策略的蟻群遺傳算法,從而提升了算法的效率.

在此基礎(chǔ)上，本文提出一種雙精英遺傳聚類算法(DoubleEliteGeneticClusteringAlgorithm，簡稱DEGCA)，算法采用保優(yōu)進(jìn)化和兩個種群協(xié)同進(jìn)化策略，同時又加入了自適應(yīng)交叉變異率和差異度權(quán)重.首先，通過最大屬性范圍劃分得到初始聚類中心的初值，同時采用雙種群的遺傳算法操作,在兩個種群均各自獨立運行一定進(jìn)化代數(shù)后，將兩個種群進(jìn)行種群間的交叉操作，使得兩個種群能夠協(xié)同進(jìn)化，優(yōu)勢互補(bǔ)，完成種群的進(jìn)化.最后，通過實驗驗證了該算法的有效性.

2 數(shù)據(jù)預(yù)處理

根據(jù)基因表達(dá)數(shù)據(jù)本身的特點，我們在對基因表達(dá)數(shù)據(jù)進(jìn)行聚類分析的過程中，一般需要進(jìn)行一定的數(shù)據(jù)清洗，包括對缺失數(shù)據(jù)的處理，數(shù)據(jù)標(biāo)準(zhǔn)化，排除表達(dá)不明顯的基因數(shù)據(jù)及數(shù)據(jù)降維.

2.1 缺失值處理

由于基因表達(dá)數(shù)據(jù)是通過基因芯片技術(shù)獲取的，在獲取數(shù)據(jù)的過程中可能存在芯片缺陷，像素點不明顯等因素而出現(xiàn)部分缺失值.聚類算法是以距離為基礎(chǔ)的，由于缺失值的存在使得該基因無法進(jìn)行聚類分析.所以我們在求解過程中必須對這些缺失數(shù)據(jù)進(jìn)行處理.本文利用以下規(guī)則對缺失數(shù)據(jù)進(jìn)行了處理：

1.當(dāng)數(shù)據(jù)缺失太嚴(yán)重時，一般認(rèn)為超過總數(shù)的1/3，則刪除該條基因數(shù)據(jù)；

2.當(dāng)數(shù)據(jù)缺失數(shù)目在總數(shù)1/3之內(nèi)時，使用平均值填充法填充之.

2.2 數(shù)據(jù)標(biāo)準(zhǔn)化

在基因表達(dá)數(shù)據(jù)中，由于測量過程中存在系統(tǒng)偏差和標(biāo)簽差異，使得不同基因之間存在數(shù)值范圍差異.數(shù)值范圍的差異使得不同基因在聚類中的影響也會有明顯的差異.因此數(shù)據(jù)標(biāo)準(zhǔn)化也是必不可少的操作.本文將基因表達(dá)數(shù)據(jù)映射到0-1范圍內(nèi)，既能減少數(shù)值差異帶來的影響，又能降低計算復(fù)雜度.

2.3 方差分析

基因表達(dá)數(shù)據(jù)通常具有數(shù)以萬條的基因數(shù)據(jù)，但并不是每條基因都對基因數(shù)據(jù)分析做出了等同的貢獻(xiàn).實際上大多數(shù)基因在測量中的表達(dá)水平變化并不顯著，而這些基因的存在大大增加了數(shù)據(jù)分析的難度.方差分析作為測量數(shù)據(jù)變異程度的常用手段，我們可以通過方差分析來過濾掉基因數(shù)據(jù)中數(shù)據(jù)波動較小的基因.基因在測量中的數(shù)據(jù)波動越大，表明在實驗樣本中作用越大.過濾掉數(shù)據(jù)波動小的基因，一方面可以降低數(shù)據(jù)維度，減少計算復(fù)雜度，另一方面，也可以將富含信息的基因保留下來，使得分析更為準(zhǔn)確.

2.4 特征提取

主成分分析(Principal Component Analysis，簡稱PCA)算法[15]是一種無監(jiān)督的特征提取方法.利用數(shù)據(jù)映射把高維數(shù)據(jù)轉(zhuǎn)化成只含有少數(shù)幾個綜合屬性(即主成分)的數(shù)據(jù)，每個主成分都能夠反映出原始數(shù)據(jù)的大部分信息，并且所含信息互不重復(fù).通過PCA降維的方法既減少了基因表達(dá)數(shù)據(jù)中預(yù)測變量的個數(shù)，也使得每個主成分的屬性相互獨立，從而實現(xiàn)降噪的功能.

3 雙精英聚類算法

3.1 初始種群的產(chǎn)生

聚類初始中心點的選擇對聚類結(jié)果的影響是很大的，目前為止最常用的生成初始中心點的方法分別有基于K-means算法的隨機(jī)生成與基于K-means++算法的最遠(yuǎn)距離生成，但是兩種生成方式并不適用于包含大量冗余數(shù)據(jù)的數(shù)據(jù)集，而基因表達(dá)數(shù)據(jù)中含有大量的冗余基因，我們在聚類過程中需要降低這類基因?qū)垲惤Y(jié)果的影響，因此常用的兩種初始中心點生成方式并不適用于基因表達(dá)數(shù)據(jù)集.

為了一定程度上降低聚類初始中心點敏感以及冗余基因(即屬性)影響的問題，本文提出了一種基于波動最大屬性的劃分法.

1)根據(jù)實驗數(shù)據(jù)集中每個數(shù)據(jù)的每個屬性值建立一個矩陣Un*l，其中n為數(shù)據(jù)個數(shù)，l為屬性個數(shù)，uij為第i個數(shù)據(jù)在第j個屬性上的值.

2)按公式(1)計算數(shù)據(jù)集中每個屬性的方差.

(1)

3)根據(jù)每個屬性的方差降序排序,選取前m個屬性(m與n相關(guān))，使用自底而上的層次聚類算法對具有m個屬性的數(shù)據(jù)集進(jìn)行聚類；層次聚類過程如下：

①令每個數(shù)據(jù)為一個簇類.

②根據(jù)當(dāng)前數(shù)據(jù)集中簇群的個數(shù)k重新計算并建立一個距離矩陣Dk*k.

(2)

公式(2)中其中I，J分別為一個簇類集合，dis(I,J)為簇類I和J的歐式距離.

(3)

③尋找矩陣中距離最小且不為0的元素，即可得到距離最短的兩個不同簇類I和J.如果dIJ小于事先設(shè)定的閾值thre，則合并兩個簇類I和J，并返回步驟②；否則轉(zhuǎn)向4).

4)依次從層次聚類得到的k個簇類中隨機(jī)挑選一個數(shù)據(jù)點組成一個初始中心點.

5)重復(fù)4)過程N(yùn)次，由此得到初始種群，其中N為初始種群規(guī)模.

選取波動最大的m個屬性是為了降低冗余屬性對聚類結(jié)果的影響，同時也降低了算法過程中的計算量；我們使用層次聚類將數(shù)據(jù)集劃分為不同簇類，那是因為層次聚類算法不受初始中心的影響且不需要事先設(shè)定簇類個數(shù).

3.2 適應(yīng)度函數(shù)

設(shè)數(shù)據(jù)集D=(x1,x2,…,xn)共有k個數(shù)據(jù)中心，其k個中心點為C=(c1,c2,…,ck).則聚類所得的聚類總代價如下：

(4)

其中CLi是根據(jù)中心點ci劃分的簇，o是簇CLi中的元素，dist為歐式距離.E代表了數(shù)據(jù)集在中心點C=(c1,c2,…,ck)作用下所求出的聚類代價，其值越小，求得的簇內(nèi)距離越小.為了體現(xiàn)聚類代價E的作用，本文所采用的適應(yīng)度函數(shù)如下：

(5)

其中Exi代表數(shù)據(jù)集A在進(jìn)化個體Xi下的聚類代價.f(Xi)的值越大，聚類代價越小，則聚類的效果越好.f(Xi)的最大值即為本文需要求得的最優(yōu)聚類方案.

3.3 雙精英進(jìn)化機(jī)制

精英個體對于種群的進(jìn)化具有重要的引導(dǎo)作用，在精英策略下種群可以較快地收斂到全局最優(yōu).DEGCA是雙種群的進(jìn)化模式，為了充分發(fā)揮精英策略的作用，本文采用了精英庫策略.

精英庫共有兩個精英個體，開始是由兩個初始種群種群A和種群B中的最優(yōu)個體EliteA和EliteB組成的.EliteA和EliteB分別引導(dǎo)種群A和種群B各自進(jìn)化一定代數(shù)后，進(jìn)行種群間的交叉，同時在精英庫中更新EliteA和EliteB的值.然后，種群A和種群B重新從精英庫中選擇精英個體引導(dǎo)進(jìn)化，直至完成整個進(jìn)化過程.

3.3.1 種群A的進(jìn)化

種群A的精英個體EliteA初始值是從種群自身產(chǎn)生的，之后在種群內(nèi)的進(jìn)化過程中隨著遺傳進(jìn)化不斷地自我更新，在進(jìn)行種群間的交叉操作之后，再將EliteA與精英庫中適應(yīng)度較差的個體進(jìn)行對比，若EliteA較大，則將EliteA替換掉精英庫中適應(yīng)度較差的個體.然后在精英庫中挑選適應(yīng)度最高的個體作為ELiteA繼續(xù)引導(dǎo)種群A的進(jìn)化.

種群A的進(jìn)化目的是種群的收斂速度與多樣性的平衡.

3.3.1.1 自適應(yīng)交叉變異率調(diào)整

為了加快種群收斂速度，種族A在進(jìn)化中的交叉率和變異率將隨著進(jìn)化個體的適應(yīng)度而不斷調(diào)整，使得適應(yīng)度較高的個體具有較低的交叉變異率，從而可以保護(hù)種群中的優(yōu)秀個體.而種群中適應(yīng)度較低的個體具有更高的交叉變異率，從而使得適應(yīng)度低的個體產(chǎn)生更多的變化.其交叉率Pc及變異率Pm為：

(6)

(7)

其中，fmax為種群中的最優(yōu)個體的適應(yīng)度，favg是種群的平均適應(yīng)度，f′是交叉?zhèn)€體中適應(yīng)度較高的個體，f為將要變異個體的適應(yīng)度，k1,k2,k3,k4是種群進(jìn)化的可控參數(shù).由公式(6)、公式(7)可得，當(dāng)進(jìn)化個體適應(yīng)度越差時，交叉率變異率就越大，越容易產(chǎn)生優(yōu)秀的個體，而當(dāng)進(jìn)化個體的適應(yīng)度較高時，交叉率變異率較低，從而可以減少對優(yōu)秀個體的破壞.

傳統(tǒng)的遺傳算法常常會出現(xiàn)優(yōu)秀個體經(jīng)過交叉變異之后，得到的子代反而處于一個較低的水平.為了使進(jìn)化個體的交叉變異盡量朝著一個正確的方向進(jìn)行，同時使個體中優(yōu)秀基因能夠保留下來.本文提出一種保優(yōu)進(jìn)化的策略來保障優(yōu)秀個體的權(quán)益.

定義 1.(保優(yōu)進(jìn)化)：當(dāng)優(yōu)秀個體(適應(yīng)度高于種群的平均適應(yīng)度)經(jīng)過交叉變異后的子代個體，其適應(yīng)度低于種群平均適應(yīng)度時，保留父代個體作為新種群的成員，同時該父代個體將不再參與后續(xù)的進(jìn)化；若子代個體的適應(yīng)度高于種群平均值，則保留子代，父代個體依然可以參與后續(xù)的交叉變異中.

通過保優(yōu)進(jìn)化的策略可以最大程度的發(fā)揮優(yōu)秀個體中優(yōu)良基因的作用，而抑制了較差基因的作用，從而加快種群的收斂速度.

3.3.1.2 自適應(yīng)差異度調(diào)整

為了保證種群在加快收斂過程中的多樣性，本文提出了基于差異度的交叉?zhèn)€體選擇策略，即根據(jù)與目標(biāo)個體的差異度選擇交叉?zhèn)€體，算法過程中根據(jù)種群的不同進(jìn)化程度自適應(yīng)調(diào)整差異度權(quán)重kd.即當(dāng)種群中適應(yīng)度大于平均適應(yīng)度的個體超過2/3，說明該種群整體較優(yōu)，因此若個體xi的適應(yīng)度大于平均適應(yīng)度，我們應(yīng)該為其挑選差異度較大的個體；當(dāng)種群中適應(yīng)度大于平均值的個體少于1/3，說明該種群整體較差，因此對于適應(yīng)度大于平均值的個體xi，我們應(yīng)該為其挑選差異度較小的個體.根據(jù)這種思想，我們提出了差異度權(quán)重調(diào)整方式：

(8)

其中kd(j)為第j個個體的差異度權(quán)重，fj為已選擇的交叉?zhèn)€體(第j個)適應(yīng)度，favg為種群的平均適應(yīng)度，sumgood為適應(yīng)度大于平均值的個體數(shù)目，sum為種群規(guī)模.

得到差異度權(quán)重kd之后，我們就可以計算個體ai與aj之間的差異度D(i,j)：

(9)

L為遺傳算法中二進(jìn)制編碼長度，ail為個體ai在第l位的編碼，取值為0或1.

在交叉操作中，在選擇第一個交叉?zhèn)€體ai之后，第二個個體xj被選擇的概率為：

F(xj)=D(i,j)*f(xj)

(10)

其中f(xj)為個體xj的適應(yīng)度，F(xiàn)(xj)為個體xj被選擇的概率；適應(yīng)度越大，D(i,j)越大，個體被選擇的概率就越大，這有效地避免了無效交叉(即個體被交叉的基因完全相同).

3.3.2 種群B的進(jìn)化

種群B是以精英個體EliteB為主導(dǎo)的，EliteB的產(chǎn)生方式與ELiteA相似，只是每次從基因庫中要選擇與EliteA相異的個體.種群B的進(jìn)化目的是為了擴(kuò)大種群的多樣性，避免早熟現(xiàn)象，為了實現(xiàn)這一目的，DEGCA引入一定數(shù)目隨機(jī)個體來替換掉每次遺傳操作后種群B的進(jìn)化團(tuán)隊中適應(yīng)度較差的個體.為了使隨機(jī)個體的數(shù)目與種群整體優(yōu)秀程度相關(guān)，對引入隨機(jī)個體的數(shù)目rnum由公式(11)和公式(12)來確認(rèn)：

(11)

rnum=(τ0×PA+τ1)·N

(12)

其中，fbest是種群A經(jīng)歷過的最優(yōu)個體的適應(yīng)度，fmin是種群A當(dāng)前的最差個體的適應(yīng)度，N為種群個體數(shù)目.PA表征種群A的進(jìn)化程度，PA越大，種群A的整體適應(yīng)度則越小，也需要更多的隨機(jī)個體為種群產(chǎn)生更多的變化.公式(11)、(12)保證了隨機(jī)個體的數(shù)目將隨著種群的整體適應(yīng)度而不斷調(diào)整，且在一定范圍之內(nèi).

3.4 種群間的交叉

當(dāng)種群A和種群B各自獨立進(jìn)化r代后，分別從種群A和種群B中隨機(jī)選擇m個個體進(jìn)行交換，這一步驟相當(dāng)于交換種群A和種群B中的m個個體，使得種群A和種群B得以優(yōu)勢互補(bǔ)，協(xié)同進(jìn)化.交叉之后的兩個種群各自獨立的進(jìn)行進(jìn)化，直至滿足終止條件為止.

3.5 DEGCA算法描述

輸入：數(shù)據(jù)集A，中心點個數(shù)k，種群內(nèi)獨立進(jìn)化代數(shù)r

輸出：聚類中心點集合

算法步驟如下：

1)數(shù)據(jù)預(yù)處理

2)初始化，使用波動最大屬性劃分法產(chǎn)生數(shù)目相同的兩個初始種群.并根據(jù)初始種群來初始化精英庫

3)計算種群中每個個體的適應(yīng)度

①使用k-means方法更新質(zhì)心

②使用公式(5)計算個體的適應(yīng)度

③更新精英庫，若兩個種群中的最優(yōu)個體適應(yīng)度高于精英庫的最差個體，則替換之.更新精英庫后，將精英庫中的數(shù)據(jù)作為EliteA和EliteB

4)種群A的進(jìn)化

①使用輪盤賭選擇法挑選進(jìn)化個體

②使用公式(6)-公式(10)計算交叉變異率并選取交叉?zhèn)€體進(jìn)行交叉操作

③對交叉變異后的個體，采用保優(yōu)進(jìn)化的策略進(jìn)行篩選

5)種群B的進(jìn)化

①使用公式(12)獲取rnum個隨機(jī)個體并替換掉種群B中適應(yīng)度最差的rnum個個體，得到進(jìn)化團(tuán)隊TempB

②將TeamB與EliteB一同完成進(jìn)化

6)種群間的交互，當(dāng)種群A和種群B各自獨立進(jìn)化r代后，分別從種群A和種群B中隨機(jī)選擇m個個體進(jìn)行交換，同時更新精英庫

7)判斷是否滿足終止條件，滿足則輸出聚類結(jié)果，否則返回步驟3)繼續(xù)進(jìn)化

4 實驗仿真

4.1 評價標(biāo)準(zhǔn)

本文使用ARI(Adjust Rand index)指標(biāo)，NMI(Normalized Mutual Information)指標(biāo)和聚類純度來作為評判聚類效果的評價標(biāo)準(zhǔn).聚類純度(purity)能夠準(zhǔn)確反映聚類結(jié)果與真實劃分的符合程度[17].假設(shè)真實劃分為S={s1,s2,…,sk}，聚類得到的簇為Sc={Sc1,Sc2,…,Sck}，則聚簇Sci的純度可由公式(13)表示：

(13)

其中，|S′|為聚簇Sci中包含真實劃分類Si的個數(shù)，其最大值就是該聚簇占比最多的類.若聚類生成的某一簇與真實劃分的某一類純度較高，而與其它類的較低，說明其與該類的符合程度較高.所有聚簇劃分的總體純度為：

(14)

其中，k為劃分簇的個數(shù)，Pt的取值范圍在0和1之間.Pt值越大則表示聚類的結(jié)果越符合真實劃分.ARI和NMI為聚類中常用的評價標(biāo)準(zhǔn)，這里不作詳細(xì)介紹.

4.2 實驗結(jié)果

為了驗證DEGCA算法的有效性，本文將DEGCA與K-means，Kmeans++，以及標(biāo)準(zhǔn)遺傳聚類算法(Standard Genetic Clustering Algorithm，簡稱SGCA)進(jìn)行對比，從基因表達(dá)綜合數(shù)據(jù)庫(Gene Expression Omnibus，簡稱GEO)上選取兩個經(jīng)典數(shù)據(jù)集GDS5401和GDS5403進(jìn)行測試.其中GDS5401出版于2014年2月，是Woetzel等人[16]在柏林測量正常人(ormal)，類風(fēng)濕關(guān)節(jié)炎患者(Rheumatoid)和骨關(guān)節(jié)炎患者(Osteoarthritis)的滑膜組織基因數(shù)據(jù)，用以區(qū)分正常人，類風(fēng)濕關(guān)節(jié)炎患者和骨關(guān)節(jié)患者.2014年3月，Woetzel等人又發(fā)布了耶拿人群的正常，類風(fēng)濕關(guān)節(jié)炎患者和骨關(guān)節(jié)炎患者的滑膜組織基因數(shù)據(jù)，即GDS5403.具體數(shù)據(jù)如表1所示.

表1 數(shù)據(jù)集的描述

Table 1 Description of data set

數(shù)據(jù)集屬性值正常類風(fēng)濕骨關(guān)節(jié)炎GDS540122283101010GDS540322283101310

4種算法各自運行10次，得到的NMI和ARI如表2和表3所示.從表中可得，K-means++在兩個數(shù)據(jù)集的ARI和NMI均高于K-means，這說明K-means++在一定程度上解決了K-means初始中心點敏感的問題.SGCA聚類得到的ARI和NMI均優(yōu)于k-means，這說明了遺傳算法在一定程度上提高了聚類的精度，在GDS5401中SGCA的性能優(yōu)于K-means++，而在GDS5403中SGCA的ARI指標(biāo)高于K-means++，而NMI要略低K-means++，這說明SGCA相對于K-means++沒有明顯的優(yōu)勢.DEGCA在AMI和ARI指標(biāo)上均優(yōu)于其他三個聚類算法，這說明DEGCA聚類結(jié)果更為準(zhǔn)確.

表2 各個算法求得的ARI

Table 2 ARI obtained by each algorithm

數(shù)據(jù)集函數(shù)均值最大值最小值GDS5401k-means0.5230.6010.423k-means++0.5840.6670.553SGCA0.6370.8020.517DEGCA0.7830.8980.667GDS5403k-means0.5510.6010.462k-means++0.5810.6030.575SGCA0.5780.6010.545DEGCA0.6520.6670.601

表3 各個算法求得的NMI

Table 3 NMI obtained by each algorithm

數(shù)據(jù)集函數(shù)均值最大值最小值GDS5401k-means0.5930.6850.452k-means++0.6570.7460.632SGCA0.6830.7990.585DEGCA0.8220.8980.746GDS5403k-means0.5960.6350.534k-means++0.6130.6840.575SGCA0.6090.6350.604DEGCA0.7010.7190.634

4個算法在這10次實驗中的純度如表4所示，相對于k-means，在兩個數(shù)據(jù)集中k-means++的平均純度分別提升了0.064和0.067，SGCA分別提升了0.102和0.046，而DEGCA提升幅度最大，為0.159和0.121，這說明DEGCA的聚類結(jié)果最接近真實劃分的結(jié)果，性能提升也最為明顯.

表4 各個算法求得的純度

Table 4 Purity obtained by each algorithm

數(shù)據(jù)集函數(shù)均值最大值最小值GDS5401k-means0.7620.8330.700k-means++0.8260.8670.733SGCA0.8640.9330.767DEGCA0.9210.9670.867GDS5403k-means0.7360.8180.727k-means++0.8030.8480.788SGCA0.7820.8180.758DEGCA0.8570.8790.818

4.3 多樣性度量

文獻(xiàn)[12]提出了在以二進(jìn)制編碼為基礎(chǔ)的遺傳算法中，如何度量種群多樣性的計算公式.

(15)

其中L為個體的編碼長度，∑alj0表示所有個體在第l位為0的個數(shù)，∑alj1表示所有個體在第l位為1的個數(shù)，max(∑alj0,∑alj1)-min(∑alj0,∑alj1)代表了種群0和1的分布情況，其值越大則表示種群中0和1的分布越不均衡，從而種群的多樣性越低.

圖1 種群多樣性在GDS5401的變化

圖2 種群多樣性在GDS5403的變化

SGCA和DEGCA求得種群多樣性變化圖如圖1和圖2所示.從圖1和圖2可知SGCA運行到一定代數(shù)后，種群多樣性將會下降到一個較低水平，從而使算法陷入早熟收斂，而DEGCA由于種群B引入了部分隨機(jī)個體，種群多樣性一直維持在一定的水平，從而減少了早熟現(xiàn)象.

4.4 DEGCA與SGCA收斂速度對比

SGCA設(shè)置最大運行代數(shù)為100，種群數(shù)目為200，DEGCA種群內(nèi)進(jìn)化代數(shù)為5，種群間交叉最多20次.種群A和種群B的種群規(guī)模均為100.實驗結(jié)果見表5.

表5 兩種算法收斂的平均代數(shù)和運行時間

Table 5 Average algebra and running time of convergence of the two algorithms

數(shù)據(jù)集SGCADEGCA種群A種群B總種群 收斂代數(shù)46283430GDS5401每代耗時(s)252.18131.17127.25258.42 收斂耗時(s)115963672.84326.57752.6 收斂代數(shù)53323735GDS5403每代耗時(s)284.52148.96146.74295.7 收斂耗時(s)150804766.75429.410350

表5表明，在算法收斂代數(shù)上，DEGCA比SGCA縮短了將近1/3.在DEGCA的雙種群中，種群A的收斂速度較快，而在種群A的帶動下，種群B也能夠快速達(dá)到收斂.在算法效率上看，DEGCA在每代耗時上不如SGCA，但是在收斂耗時上，GDS5401提高了33.1%；GDS5403提高了31.4%.

5 結(jié) 論

本文提出一種基于雙精英遺傳策略的基因聚類算法，在傳統(tǒng)遺傳算法基礎(chǔ)上采用兩個種群協(xié)同保優(yōu)進(jìn)化策略，同時又提出了自適應(yīng)調(diào)整的交叉變異率和差異度選擇交叉，有效地提高了算法的收斂速度.相對于k-means,k-means++和SGCA，DEGCA聚類結(jié)果更接近真實劃分，聚類更加準(zhǔn)確.由于算法中加入太多進(jìn)化策略，導(dǎo)致運行時間也相對較長，因此我們下一步的工作旨在如何在保證聚類結(jié)果的同時降低算法的時間復(fù)雜度.