鄭洪清

(廣西外國語學院 信息工程學院,南寧 530222)

聚類是將數(shù)據(jù)集中的樣本劃分為若干個通常不相交的子集,每個子集稱為“族”,同一族中的對象具有較高的相似度,不同族中的對象差別較大.聚類分析已成為數(shù)據(jù)挖掘領域的研究熱點問題,K 均值算法(K-means)是一種經(jīng)典的聚類算法,因其受初始聚類中心的影響容易陷入局部最優(yōu)等缺陷而限制了其應用范圍.許多學者提出一系列智能聚類算法,如蜜蜂交配優(yōu)化聚類算法[1]、螢火蟲聚類算法[2]、差分進化聚類算法[3]、布谷鳥聚類算法[4]、彈性網(wǎng)絡聚類算法[5]、花朵授粉聚類算法[6]、蝙蝠聚類算法[7]、灰狼與郊狼混合優(yōu)化算法[8]、自適應細菌覓食聚類優(yōu)化算法[9]、拓展差異度的高維數(shù)據(jù)聚類算法[10]、無人倉系統(tǒng)訂單分批問題及K-max 聚類算法[11]等.各種改進算法均取得了一定成效,但對于一些復雜問題仍存在精度不高和收斂速度慢等問題.

蝴蝶優(yōu)化算法[12](Butterfly Optimization Algorithm,BOA)是2018年Sankalap Arora 提出一種新的全局優(yōu)化算法,其靈感來自于蝴蝶的覓食行為.該行為由蝴蝶的合作向食物來源位置移動,蝴蝶接收并感知空氣中的氣味以確定食物來源或交配伙伴的潛在方向,但其本質(zhì)不同于文獻[13,14].由于提出時間短,國外可參考的文獻很少,國內(nèi)暫無相關(guān)論文報道.蝴蝶優(yōu)化算法與其他群智能算法一樣,也存在收斂速度和易陷入局部最優(yōu)等缺陷,因此本文嘗試提出了一種改進蝴蝶優(yōu)化算法(Improved Butterfly Optimization Algorithm,IBOA),首先描述了蝴蝶優(yōu)化算法的特點及實施步驟,重新定義蝴蝶優(yōu)化算法的局部迭代公式,再將遺傳算法的輪盤賭選擇、交叉操作和變異操作融入蝴蝶優(yōu)化算法中,通過標準的數(shù)據(jù)集測試驗證IBOA 算法的有效性.

1 基本的蝴蝶優(yōu)化算法

蝴蝶優(yōu)化算法是模擬蝴蝶的覓食行為,該思想的條件假設如下:

1)所有的蝴蝶都應該散發(fā)出某種香味,使蝴蝶能夠互相吸引.

2)每只蝴蝶都會隨機移動,或朝著散發(fā)出更多香味的最佳蝴蝶移動.

3)蝴蝶的刺激強度受目標函數(shù)值的影響或決定.

當蝴蝶能感覺到其他任何蝴蝶的香味時并朝它移動,在該算法中,該階段稱為全局搜索.在另一種情況下,當蝴蝶不能感覺周圍的香味時,然后它會隨機移動這個階段稱為局部搜索.利用轉(zhuǎn)換概率 控制全局和局部搜索過程,其迭代公式為:

式(1)中的f是香味感知量,c是感覺形式,I是刺激強度,a是香味,通常a和c的取值范圍為[0,1]之間;式(2)中的表示第i只蝴蝶在第t+1代的位置,r∈[0,1]的隨機數(shù),g?表示全局最優(yōu)解,fi表示第i只蝴蝶的香味感知量;式(3)中的,,分別表示第i,j,k只蝴蝶在第t代的位置;式(4)中的b為 常數(shù),ct,表示第t代的值,Ngen為最大迭代次數(shù).

基于上述描述,蝴蝶優(yōu)化算法的實施步驟如下:

Step 1.初始化種群規(guī)模n及轉(zhuǎn)換概率p等參數(shù).

Step 2.利用式(5)計算每只蝴蝶的適應度值,并求出當前最優(yōu)值fmin和最優(yōu)解Best.

Step 3.利用式(1)計算香味感知量,如果rand

Step 4.利用式(5)重新計算每只蝴蝶的適應度值Fnew,ifFnew

Step 5.利用式(4)更新c.

Step 6.判斷是否達到最大迭代次數(shù),如果是輸出最優(yōu)值和最優(yōu)解,否則跳至Step 3.

2 改進的蝴蝶優(yōu)化算法

由于基本的BOA 算法聚類效果差,本文對其進行改進,提出一種改進的蝴蝶優(yōu)化聚類算法.重新定義蝴蝶的局部搜索方式,同時結(jié)合輪盤賭選擇、交叉操作和變異操作,提高算法的尋優(yōu)能力,使聚類效果穩(wěn)定.

2.1 編碼方法

采用實數(shù)編碼,一只蝴蝶的位置表示一組聚類中心,假設有m個 聚類中心,數(shù)據(jù)集的屬性有d個,則每只蝴蝶的維數(shù)為nd=d×m.則第t代蝴蝶i的位置編碼為xi(t)=[c1(t),c2(t),···,cm(t),],其中cj(t)表示第t代蝴蝶的第j個聚類中心,j=1,2,···,m.

2.2 評價函數(shù)

本文采用如下的聚類準則作為適應度值:

其中,nc為聚類樣本數(shù),yi為第i個 樣本,f(xi(t))表示所有數(shù)據(jù)到聚類中心的最小值,值越小表示聚類效果越好.

2.3 重新定義迭代公式

鑒于基本的蝴蝶優(yōu)化算法局部尋優(yōu)能力較差,故結(jié)合精英策略將式(3)重新定義如下:

式(6)中g(shù)?為全局最優(yōu)解即為精英,其他蝴蝶在精英附近進行搜索,因此能提高算法的精度.

為了提高聚類效果和魯棒性,融合遺傳算法相關(guān)操作.

2.4 輪盤賭選擇

1)計算每只蝴蝶的適應度值Fitness;

2)計算每只蝴蝶被遺傳到下一代的概率p;

3)計算每只蝴蝶的累加概率q;

本研究中螺釘位置不良17例（共19枚），其中8例為開展該技術(shù)早期病例，可能與術(shù)者的技術(shù)水平密切相關(guān)；12例患者椎弓根狹小或無髓腔，術(shù)前研究患者影像學資料不充分，置釘路徑制定欠佳。

4)在蝴蝶種群中對每一個體產(chǎn)生一個隨機數(shù)r∈[0,1],執(zhí)行temp=find(r

2.5 交叉操作

2)若r

2.6 變異操作

設xi=(xi1,xi2,···,xid,xid+1,···,xie,···,xin),隨機選取兩個位置xid和xie,將兩個位置之間的元素進行逆轉(zhuǎn)操作,變換后的位置為=(xi1,xi2,···,xie,xie?1,···,xid,···,xin).

2.7 IBOA 實施步驟

Step 1.初始化種群規(guī)模、轉(zhuǎn)換概率、迭代次數(shù)N_iter和交叉概率pc等參數(shù).

Step 2.計算每只蝴蝶的適應度值,并求出當前最優(yōu)值fmin和最優(yōu)解Best.

Step 3.利用式(1)計算香味感知量,如果rand

Step 4.重新計算每只蝴蝶的適應度值Fnew,ifFnew

Step 5.執(zhí)行輪盤賭選擇、交叉操作和變異操作.重新計算每只蝴蝶的適應度值Fnew,ifFnew

Step 6.利用式(4)更新.

Step 7.判斷是否達到最大迭代次數(shù),如果是輸出最優(yōu)值和最優(yōu)解,否則跳至Step 3.

3 實驗分析

3.1 實驗環(huán)境與參數(shù)設置

為了測試IBOA 算法的正確性與有效性,選取6個基準測試函數(shù)來驗證算法,包括1 個人工數(shù)據(jù)集和5 個從UCI (http://archive.ics.uci.edu/ml/index.php)數(shù)據(jù)庫中選取了Iris、Wine、Glass、Cancer、Cintraceptive Method Choice (簡稱CMC)5 組實驗數(shù)據(jù),所有的實例均運行在處理器為Celeron(R)雙核CPU T3100,1.90 GHz、內(nèi)存為4G 的PC 上,以Matlab R2010a 編寫代碼.參數(shù)設置為:種群規(guī)模 ＝50、轉(zhuǎn)換概率 ＝0.1、c的初值為0.01,迭代次數(shù)N_iter＝200 和交叉概率pc＝0.85.在問題規(guī)模一致的情形下,這些算法的復雜度是相同的.

3.2 測試實例結(jié)果比較

(1)人工數(shù)據(jù)集1 (set_data=250,d=3,K=5):為了展示IBOA 的求解過程,分別計算第10 代、第50 代的求解結(jié)果如圖1和圖2中.并將算法獨立運行20 次的結(jié)果于表1中,Best 表示最優(yōu)解,Average 表示平均解,Worst 表示最差解,Std 表示標準差.表1中其他算法與數(shù)據(jù)來源于文獻[7],從表1中的計算結(jié)果可知IBOA的求解精度及魯棒性均優(yōu)于其他算法.

圖1 人工數(shù)據(jù)集1 第10 代的聚類結(jié)果

圖2 人工數(shù)據(jù)集1 第50 代的聚類結(jié)果

表1 人工數(shù)據(jù)集1 的20 次獨立運行結(jié)果比較

(2)UCI 數(shù)據(jù)集:將算法獨立運行20 次,與近幾年多種算法比較如表2–表7所示,其中表2–表6中的Kmeans、GA、ACO、PSO、HBMO、IDE 算法數(shù)據(jù)來源于文獻[3]且迭代次數(shù)為500 時的計算結(jié)果,IBA 算法數(shù)據(jù)來源于文獻[7],IGSO 算法數(shù)據(jù)來源于文獻[2],BPFPA 算法數(shù)據(jù)來源于文獻[6];表7中K-means、PSO、ABC、BA 和IBA 算法數(shù)據(jù)來源于文獻[7].從表2可知,IBOA 算法求解效果與IBA、BPFPA 相當,但比其余8 種算法效果較好;從表3可知,IBOA 算法與BPFPA 求解效果相當,但比其余7 種算法效果優(yōu)越許多;文中的“－”表示未有相關(guān)數(shù)據(jù).從表4可知,IBOA 的求結(jié)果在迭代次數(shù)為200 時優(yōu)于IDE 和其他算法;從表5可知,IBOA 算法的精度和方差均優(yōu)于其他算法;從表6可知,IBOA 算法的求解效果差于IDE,與IBA、BPFPA 效果相當,但優(yōu)于其他算法;從表7可知,IBOA 算法的求解效果與IBA、BPFPA 相當,但優(yōu)于其他算法.另外,圖3展示了IBOA 算法和BOA 算法在Survival 數(shù)據(jù)集的最優(yōu)解收斂曲線圖,從圖3易知,IBOA 算法的求解速度和精度較BOA 算法高.IBOA 求解Iris、Survival、CMC 數(shù)據(jù)集的聚類效果圖如圖4–圖6所示.

表2 11 種算法在Iris 數(shù)據(jù)集上聚類結(jié)果比較

表3 10 種算法在Wine 數(shù)據(jù)集上聚類結(jié)果比較

表4 9 種算法在Glass 數(shù)據(jù)集上聚類結(jié)果比較

表5 9 種算法在Cancer 數(shù)據(jù)集上聚類結(jié)果比較

表6 10 種算法在CMC 數(shù)據(jù)集上聚類結(jié)果比較

表7 8 種算法在Survival 數(shù)據(jù)集上聚類結(jié)果比較

圖3 IBOA 與BOA 求解Survival 數(shù)據(jù)集函數(shù)收斂曲線圖

4 結(jié)論

本文將精英策略的思想重新定義蝴蝶優(yōu)化算法的局部搜索迭代公式且遺傳算法相結(jié)合提出了一種改進的蝴蝶優(yōu)化聚類算法,通過求解1 個人工數(shù)據(jù)集和5 個UCI 數(shù)據(jù)庫中不同規(guī)模的數(shù)據(jù),統(tǒng)計分析結(jié)果表明IBOA 算法能夠避免陷入局部最優(yōu),具有較快的收斂速度和較強的魯棒性,能夠有效解決聚類問題且與其他聚類算法相比具有一定優(yōu)勢.

圖4 IBOA 求解Iris 數(shù)據(jù)集的聚類效果圖

圖5 IBOA 求解Survival 數(shù)據(jù)集的聚類效果圖

圖6 IBOA 求解CMC 數(shù)據(jù)集的聚類效果圖