曹永春，紀(jì)金水，鄧 濤，蔡正琦

(西北民族大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院，甘肅 蘭州 730030)

0 引言

蜂群算法是受自然界蜜蜂群體行為啟發(fā)而產(chǎn)生的一種元啟發(fā)式優(yōu)化算法. 蜂群算法作為一種新興的群體智能優(yōu)化算法，近年來受到了相關(guān)學(xué)者的廣泛關(guān)注.根據(jù)受啟發(fā)的生物機理不同，蜂群算法可分為基于繁殖機理和基于采蜜機理兩類蜂群算法，并且各成體系.基于蜜蜂繁殖機理的蜂群算法(marriage in honey-bees optimization, MBO)最早由Abbass于2001年提出[1]，MBO算法將蜂后作為待求解優(yōu)化問題的最優(yōu)解，基于蜂群實際婚配行為建立算法模型，通過蜂后的婚飛過程，模擬蜂后與雄蜂的交配行為產(chǎn)生幼蜂，并通過工蜂(啟發(fā)式方法)優(yōu)化蜂后和幼蜂(潛在蜂后)的質(zhì)量，最終獲得問題的最優(yōu)解.目前蜂群算法已被成功應(yīng)用于解決可滿足行問題、動態(tài)規(guī)劃問題、多目標(biāo)配電網(wǎng)重構(gòu)問題、車輛路徑問題等[2].

聚類就是按照一組數(shù)據(jù)對象的特征屬性將其劃分為若干類(簇)，使得同類中的數(shù)據(jù)對象盡可能相似，不同類中的數(shù)據(jù)對象差別較大.聚類分析是一種廣泛應(yīng)用于機器學(xué)習(xí)、模式識別、數(shù)據(jù)挖掘及圖像處理等領(lǐng)域中的重要的無監(jiān)督的學(xué)習(xí)技術(shù)，是進一步分析和處理數(shù)據(jù)的數(shù)據(jù)預(yù)處理方法.按照不同標(biāo)準(zhǔn)，傳統(tǒng)的聚類分析方法大體可分為以下幾類：劃分聚類方法、層次聚類方法、基于密度的聚類方法、基于網(wǎng)格的聚類方法、基于模型的聚類方法及模糊聚類法等[3].

隨著智能優(yōu)化算法的快速發(fā)展及廣泛應(yīng)用，多種智能優(yōu)化算法被用于解決聚類問題并獲得較好的聚類效果.文獻[4]將多目標(biāo)粒子群優(yōu)化算法和K-means算法相結(jié)合生成隨機分布的初始化種群，最終采用maximin策略確定帕累托最優(yōu)解，算法表現(xiàn)出較好的聚類效果和穩(wěn)定性，但存在粒子編碼復(fù)雜，算法效率有待提高的問題.文獻[5]通過引入差分進化中的變異和交叉思想對基于人工蜂群的模糊C均值聚類算法進行了改進，改進后的算法在收斂速度及聚類穩(wěn)定性方面有明顯改善.文獻[6] 在現(xiàn)有K-means蟻群聚類算法的迭代過程隨機選擇一個或多個簇，并從中選擇含有信息素最小的節(jié)點進行變異操作，改進了原有算法易陷入局部最優(yōu)的問題，但算法耗時較長.文獻[7] 結(jié)合了K調(diào)和均值聚類算法(KHM)和遺傳算法的優(yōu)點，采用KHM計算每一代種群的聚類中心，并構(gòu)造適應(yīng)度函數(shù)，通過遺傳算法優(yōu)化操作獲得最優(yōu)聚類結(jié)果.算法在聚類精度和穩(wěn)定性方面表現(xiàn)較好，但該算法時間復(fù)雜度較高.

本文將MBO算法應(yīng)用于聚類問題，提出了一種基于MBO的蜂群聚類算法(MBOCA).該算法采用基于聚類中心的蜂后染色體編碼方式，通過模擬退火算法進一步優(yōu)化初始蜂后來提高初始解的質(zhì)量，從而加快算法的收斂速度；采用適合于聚類中心編碼方式的算術(shù)交叉操作產(chǎn)生幼蜂；充分利用蜂后良好基因信息的啟發(fā)式方法來模擬工蜂對幼蜂展開鄰域搜索，從而有效改進幼蜂質(zhì)量.

1 聚類評價標(biāo)準(zhǔn)

在解決聚類問題時首先要確定評價數(shù)據(jù)對象相似性的度量標(biāo)準(zhǔn).廣泛被使用的一個度量標(biāo)準(zhǔn)是數(shù)據(jù)對象之間的“距離”.本文采用Euclidean距離，以Kaufman等人提出的輪廓系數(shù)(silhouette coefficient)[8]作為衡量數(shù)據(jù)對象相似性的內(nèi)部評價指標(biāo).輪廓系數(shù)的數(shù)學(xué)模型及含義說明如下：

對含有n個數(shù)據(jù)對象的聚類問題，若聚類結(jié)果將n個數(shù)據(jù)對象聚類為k個類，則該聚類方案K的輪廓系數(shù)定義為：

(1)

其中，Sj為第j個類Cj的輪廓系數(shù)，具體定義如式(2)：

(2)

sj表示第j個數(shù)據(jù)對象xj的輪廓系數(shù)，其形式如式(3)：

(3)

式(3)中aj表示數(shù)據(jù)對象xj與同一類Cj中其他所有數(shù)據(jù)對象的平均距離，bj表示數(shù)據(jù)對象xj與其他類Ci(i∈[1,k]且i≠j)中數(shù)據(jù)對象平均距離的最小值，即若di為xj與類Ci中所有數(shù)據(jù)對象的平均距離，則bj=min(di).

由上述模型可見，輪廓系數(shù)S(K)作為衡量聚類結(jié)果的相似度，兼顧了類內(nèi)聚合度和類間分離度，即S(K)越小說明類間距離越大，類內(nèi)距離越小，類內(nèi)數(shù)據(jù)對象的相似度越高，聚類效果越好.本文將聚類結(jié)果的內(nèi)部評價指標(biāo)輪廓系數(shù)作為目標(biāo)函數(shù)，用于計算蜜蜂染色體的適應(yīng)度值從而指導(dǎo)蜂后的優(yōu)化過程.

對聚類結(jié)果的另一個度量標(biāo)準(zhǔn)是外部評價指標(biāo)，即用已知的正確聚類結(jié)果評判聚類算法的聚類效果.本文采用Rand index作為外部評價指標(biāo)衡量本文算法的聚類效果，其定義如下：

(4)

式(4)中，TP和FP分別表示算法的聚類結(jié)果，與已知正確聚類結(jié)果相比，被劃分到同一類中的正確和不正確的樣本對數(shù)；TN和FN分別表示被劃分到不同類中的正確和不正確樣本對數(shù).由上述Rand index定義可知，R(K) ∈[0，1]，R(K) 的值越趨近于 1 ,則算法聚類結(jié)果越接近正確結(jié)果，說明算法聚類結(jié)果越好.

2 基于繁殖機理的蜂群算法模型

MBO算法屬于一類群體智能算法，它是基于蜂群實際婚配行為而建立的算法模型.算法中每個蜂群是由蜂后、雄蜂、工蜂和幼蜂組成[9].蜂后的主要任務(wù)是通過產(chǎn)卵繁衍后代.在一個蜂群的生命周期中可能有一只或多只蜂后，只有一只蜂后的蜂群為單雌群，有多只蜂后的蜂群為多雌群.雄蜂的惟一任務(wù)是通過婚飛與蜂后交配，交配后雄蜂隨即死亡.工蜂的任務(wù)主要是照顧幼蜂，有時候也產(chǎn)卵.幼蜂來自受精卵或未受精卵.由受精卵產(chǎn)生的幼蜂表示潛在的蜂后或工蜂，而來自未受精卵的幼蜂會生長為雄蜂.

蜂后的婚飛在蜂群繁殖過程中起著關(guān)鍵作用.一次婚飛開始于蜂后的一段舞蹈，接著蜂后開始飛離蜂巢，大量雄蜂追隨其后試圖與之交配.在一次典型的婚飛過程中，每只蜂后會選擇7～20只雄蜂進行交配[1]，每次交配就是將雄蜂的精子收集在蜂后的受精囊中形成蜂群的遺傳池(genetic pool).當(dāng)蜂后的受精囊裝滿精子后，蜂后飛回蜂巢開始產(chǎn)卵(包括受精卵和未受精卵).蜂后通過從受精囊中隨機取出精子產(chǎn)生受精卵.新的蜂后和工蜂就是來自于受精卵，而雄蜂則來自于未受精卵.

婚飛可看作是在問題解空間中一系列狀態(tài)之間的轉(zhuǎn)移[2].在蜂后進行婚飛的開始階段，蜂后被初始化為一定的能量和速度，并以一定的概率與相遇的雄蜂進行交配.把這個過程可以看作算法在較大范圍的解空間中進行全局最優(yōu)解的探索.隨著婚飛的繼續(xù)進行，蜂后的能量和速度逐漸降低，蜂后開始低速飛行尋找待交配的雄蜂，即進行局部最優(yōu)解的開采.在蜂后的能量消耗至設(shè)定的閾值(如0)或受精囊裝滿精子后，蜂后停止飛行返回蜂巢.在算法處理過程中，工蜂的主要作用是照顧幼蜂，每個工蜂代表一種改進幼蜂質(zhì)量的啟發(fā)式方法.

MBO算法中雄蜂D被蜂后Q選擇交配的概率按式(5)計算

prob(Q,D)=exp[-Δ(f)/S(t) ]

(5)

其中，

prob(Q,D)表示雄蜂D被蜂后Q選擇交配的概率；

Δ(f)表示雄蜂D和蜂后Q之間適應(yīng)度的絕對差值；

S(t)表示蜂后Q在t時刻的飛行速度.

每次婚飛后，蜂后的速度和能量按式(6)和式(7)衰減，

S(t+1)=α(t)×S(t)

(6)

E(t+1)=E(t)-γ

(7)

式(6)中α是取值為[0,1]區(qū)間的表示每次婚飛后蜂后飛行速度的衰減因子，式(7)中γ為蜂后每次婚飛能量的遞減量.

由式(5)可見，在婚飛的開始階段，蜂后的速度較高，則雄蜂被選中交配的概率較大.在這一階段蜂后將與較多的雄蜂交配.種群的多樣性得到了很好的保留,算法在較大空間中進行了全局最優(yōu)解的探索.隨著婚飛的進行，在婚飛后期蜂后的飛行速度衰減到較低時，則雄蜂被選中交配的概率主要受蜂后和雄蜂適應(yīng)度絕對差值的影響.適應(yīng)度越接近蜂后，適應(yīng)度值的雄蜂被選中的概率就越大.在這一階段能更好地保留蜂群的良好基因.算法在局部較優(yōu)范圍內(nèi)進行更為精細的開采.

根據(jù)上述思想，MBO算法可分為如下4個主要階段：

1)構(gòu)建蜂后：根據(jù)問題解的編碼方式隨機產(chǎn)生指定數(shù)目的蜂后，并應(yīng)用啟發(fā)式方法優(yōu)化每個蜂后，得到較高質(zhì)量的蜂后.

2) 交配過程：在婚飛開始前，將每個蜂后的能量和速度初始化為[0.5, 1]區(qū)間的隨機值，在婚飛期間每個雄蜂依據(jù)式(5)計算的交配概率與相遇的蜂后進行交配，并以式(6)和式(7)更新蜂后的能量和速度，直到蜂后的能量小于設(shè)定的閾值或受精囊被裝滿.

3)產(chǎn)生幼蜂：通過單倍體交叉蜂后的染色體和受精囊中收集的雄蜂精子生成幼蜂，并通過工蜂照顧幼蜂(即使用啟發(fā)式方法執(zhí)行局部搜索優(yōu)化幼蜂).

4) 替換蜂后：若優(yōu)化后的最好(適應(yīng)度值最高)幼蜂優(yōu)于蜂后，則用該幼蜂替換蜂后，并殺死其他幼蜂.

3 基于繁殖機理的蜂群聚類算法

3.1 蜂后的染色體表示及選優(yōu)

結(jié)合聚類分析的問題特征及MBO算法的處理過程，本文蜂群聚類算法中蜂后的染色體以聚類中心表示，即蜂后的染色體可表示為向量：

Q=[X11,X12, …,X1d,X21,X22, …,X2d, …，Xk1,Xk2, …,Xkd]

即每個蜂后的染色體為k×d個實數(shù)組成的基因序列，k表示特定聚類問題的聚類數(shù)，d表示待聚類樣本的維數(shù).根據(jù)文獻[1]的實驗結(jié)果，本文算法采用1個蜂后.

初始蜂后是通過隨機生成蜂后染色體的每一位基因Xij獲得，每一位基因Xij須滿足Xij∈[jmin,jmax].jmin和jmax分別表示在數(shù)據(jù)集的所有樣本中第j維數(shù)據(jù)的最小值和第j維數(shù)據(jù)的最大值.

初始生成蜂后的基因質(zhì)量在一定程度上將會影響MBO算法的求解效率，應(yīng)該通過工蜂對其優(yōu)化.本文采用的方法是首先按照上述蜂后染色體表示的方法隨機產(chǎn)生一組初始解表示候選蜂后，按照每個蜂后的適應(yīng)度值排序，選出適應(yīng)度最高的候選蜂后作為蜂群的蜂后.然后采用模擬退火啟發(fā)式算法對初始蜂后進行鄰域搜索，進一步優(yōu)化蜂后質(zhì)量，加快算法的收斂速度.在鄰域搜索過程中發(fā)現(xiàn)候選蜂后Q′的適應(yīng)度值高于當(dāng)前蜂后Q的適應(yīng)度值，則以Q′取代當(dāng)前蜂后Q；否則以概率p(T,Q′，Q)決定Q′是否取代當(dāng)前蜂后Q，p(T,Q′，Q)的計算如下所示：

(8)

式中T表示當(dāng)前時刻的溫度，F(xiàn)(Q′)和F(Q)則分別表示候選蜂后Q′和當(dāng)前蜂后Q的適應(yīng)度值.

3.2 通過交叉產(chǎn)生幼蜂

本文算法隨機產(chǎn)生雄蜂，雄蜂的染色體與蜂后一樣以聚類中心表示.由于雄蜂是單倍體，其精子只有染色體的一半，即只有部分基因位的值.在算法交叉操作中本文通過以50%的概率選擇雄蜂染色體的基因位與蜂后染色體對應(yīng)基因位交叉.結(jié)合算法中蜂后染色體的表示方式，本文采用適合于蜂后編碼方式的算術(shù)交叉，具體交叉方法按下式進行.

Qki=αXki+(1-α)XPi

(9)

其中，α為(0，1)區(qū)間的隨機數(shù)，Xki表示蜂后Xk的第i位基因值，Xpi表示被蜂后選中進行交配的雄蜂Xp精子的第i位基因值，Qki表示交叉操作后蜂后第i位新基因值.

3.3 幼蜂優(yōu)化方法

工蜂照顧幼蜂，即使用啟發(fā)式方法優(yōu)化幼蜂的過程.本文充分利用蜂后良好的基因信息對幼蜂展開鄰域搜索來改進幼蜂質(zhì)量，具體操作方法按式(10)進行.

Vij=Xij+Rij(Xij-Xkj)

(10)

其中，Xi表示當(dāng)前幼蜂所代表的染色體，Xk表示蜂后所代表的染色體，j為在幼蜂(或蜂后)染色體所含基因數(shù)范圍內(nèi)的隨機數(shù)，而Rij則是用來控制幼蜂鄰域搜索范圍的隨機數(shù)，其取值范圍為[-1,1].本文利用蜂后良好的基因Xkj調(diào)整當(dāng)前幼蜂對應(yīng)基因Xij,從而將當(dāng)前幼蜂基因Xij改善為Vij.

3.4 蜂群聚類算法流程描述

綜上所述，蜂群聚類算法流程描述如下：

首先設(shè)置初始參數(shù)，MBO算法需要設(shè)置的參數(shù)包括總婚飛次數(shù)N，每個蜂后受精囊的大小M，雄蜂數(shù)量p，幼蜂數(shù)量y.設(shè)置初始參數(shù)后算法按下述步驟進行.

Step1：按3.1所述蜂后的染色體表示方法隨機生成m個候選蜂后，計算它們的適應(yīng)度值，選出最優(yōu)(適應(yīng)度值最高)的一個作為蜂后并用模擬退火算法進一步改進蜂后的質(zhì)量.

Step2：當(dāng)蜂后當(dāng)前婚飛次數(shù)t沒有達到指定的總婚飛次數(shù)N時.

初始化t時刻蜂后的能量E(t)和速度S(t)，并按式γ=(0.5×E(0))/M計算蜂后在t時刻能量遞減量.式中M表示蜂后受精囊的大小.

以蜂后生成的方法隨機生成p個雄蜂并計算它們的適應(yīng)度值，并按式(5)計算每個雄蜂被當(dāng)前蜂后選擇交配的概率prob(Q,D).

Step3：當(dāng)蜂后的能量E(t)>Emin,并且蜂后的受精囊未裝滿時，選擇一個交配概率prob(Q,D)最高的雄蜂，并將其精子裝入蜂后受精囊中，受精囊中精子數(shù)目增1.

根據(jù)式(6)和式(7)更新蜂后的速度和能量.

Step4：當(dāng)前產(chǎn)生的幼蜂數(shù)量未達到指定數(shù)量y時，蜂后染色體與從蜂后受精囊中隨機取出的一個精子按式(9)通過交叉操作產(chǎn)生一個幼蜂，并使用工蜂照顧幼蜂，即用式(10)進一步改進幼蜂質(zhì)量.

Step5：計算所有幼蜂的適應(yīng)度值，找出所有幼蜂中適應(yīng)度最高的幼蜂，如果該幼蜂的適應(yīng)度值高于當(dāng)前蜂后的適應(yīng)度值，則用該幼蜂替代蜂后Q作為新的蜂后.

殺死當(dāng)前所有幼蜂，轉(zhuǎn)Step2.

Step6：當(dāng)蜂后婚飛次數(shù)達到指定的總婚飛次數(shù)N后，則蜂后Q的染色體表示待求解問題的最優(yōu)解，輸出最優(yōu)解.

4 仿真實驗及結(jié)果分析

為驗證本文提出的基于MBO蜂群聚類算法的聚類效果和有效性，對1組自構(gòu)造數(shù)據(jù)集和3組取自UCI(http://archive.ics.uci.edu/ml)的真實數(shù)據(jù)集進行了對比實驗，比較了k-means聚類算法、遺傳聚類算法(GGA)[12]、基于采蜜機理的人工蜂群算法(ABC)及本文基于繁殖機理的蜂群聚類算法(MBOCA)的聚類效果.

自構(gòu)造數(shù)據(jù)集由以等概率生成的160個球形分布的二維數(shù)據(jù)點組成，并以高斯分布分配到8個類中.本文以SCDS表示自構(gòu)造數(shù)據(jù)集.2組真實數(shù)據(jù)集是來自UCI的Iris數(shù)據(jù)集、Wine數(shù)據(jù)集.Iris數(shù)據(jù)集中每個數(shù)據(jù)對象有4個屬性值，將150個這樣的數(shù)據(jù)對象分為3個類，每類50個數(shù)據(jù)對象.Wine數(shù)據(jù)集中每個數(shù)據(jù)對象有13個屬性值， 178個這樣的數(shù)據(jù)對象分布在3個類中.

根據(jù)文獻[1]的實驗結(jié)果，本文算法采用1個蜂后，設(shè)置幼蜂數(shù)目為100，蜂后的受精囊大小為21，隨機產(chǎn)生的雄蜂數(shù)目為150，婚飛最大次數(shù)為200.工蜂以兩種啟發(fā)式方法實現(xiàn)，一種是3.1所述的模擬退火方法，用來優(yōu)化初始蜂后的染色體；另一種是3.3所述的提高幼蜂質(zhì)量的啟發(fā)式方法.

4種聚類方法的聚類結(jié)果通過Rand index表示，在實驗中通過每種聚類算法分別在不同的數(shù)據(jù)集上運行30次，統(tǒng)計出Rand index的最大、最小及均值，并分別用max、min、mean表示，聚類結(jié)果如表1所示.

表1幾種算法聚類結(jié)果的比較

表1中數(shù)據(jù)說明，K-means算法雖然簡單高效，在各數(shù)據(jù)集上的Rand index最大值較高，均值也可接受，但由于算法易受初始聚類中心的影響，多次聚類結(jié)果的差異較大，表現(xiàn)出聚類結(jié)果的穩(wěn)定性較差.原始人工蜂群算法(ABC)在算法的各步驟未進行改進和優(yōu)化的情況下，聚類精度和算法的穩(wěn)定性都最低.文獻[12]的遺傳聚類算法和本文提出的基于MBO的蜂群算法，因結(jié)合聚類問題的具體特征及染色體的編碼方式，在算法的各步驟進行了有針對性的啟發(fā)式方法的處理，聚類精度均較高.由表中數(shù)據(jù)可以看出，本文算法在各數(shù)據(jù)集上的Rand index最大值和最小值的差值最小，說明本文算法在聚類效果的穩(wěn)定性方面有較大的優(yōu)勢，并且相對遺傳算法而言，MBO算法的復(fù)雜度較低.

基于以上分析，本文通過對初始蜂后的選優(yōu)和優(yōu)化，以及在幼蜂的優(yōu)化過程充分利用蜂后優(yōu)秀的基因信息進行啟發(fā)式搜索，有效提高了初始蜂后和幼蜂的質(zhì)量，這樣既加快了算法的收斂速度，相比其他幾種算法，也表現(xiàn)出較高的穩(wěn)定性.說明本文算法是一種可行的、有效的聚類方法.

5 結(jié)束語

本文將改進的MBO算法應(yīng)用于聚類分析，提出了一種基于MBO的蜂群聚類算法.算法中蜂后的染色體采用聚類中心表示.初始蜂后的產(chǎn)生首先在多個隨機生成的蜂后中選優(yōu)，再通過模擬退火啟發(fā)式方法進一步優(yōu)化，有效提高了蜂后的質(zhì)量，加快了算法的收斂速度，加強了算法的穩(wěn)定性.生成幼蜂的交叉操作采用適合蜂后染色體編碼方式的算術(shù)交叉，結(jié)合MBO算法中雄蜂精子單倍體這一特征，在算法交叉操作中對每個基因以50%的概率與蜂后對應(yīng)基因進行交叉操作產(chǎn)生幼蜂.對幼蜂的優(yōu)化算法充分利用蜂后良好的基因信息，對幼蜂展開鄰域搜索來改進幼蜂質(zhì)量.另外，本文采用兼顧類內(nèi)聚合度和類間分離度的輪廓系數(shù)計算蜜蜂的適應(yīng)度值，使算法的聚類結(jié)果更可靠.通過比較幾種聚類算法在3個數(shù)據(jù)集上的對比實驗，結(jié)果表明本文算法具有較高的聚類精度和較好的穩(wěn)定性.