改進(jìn)的蝴蝶優(yōu)化聚類算法①

鄭洪清

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 編碼方法

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

2.2 評價(jià)函數(shù)

本文采用如下的聚類準(zhǔn)則作為適應(yīng)度值:

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

2.3 重新定義迭代公式

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

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

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

2.4 輪盤賭選擇

1)計(jì)算每只蝴蝶的適應(yīng)度值Fitness;

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

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

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

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

2.5 交叉操作

2)若r

2.6 變異操作

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

2.7 IBOA 實(shí)施步驟

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

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

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

Step 4.重新計(jì)算每只蝴蝶的適應(yīng)度值Fnew,ifFnew

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

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

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

3 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

(2)UCI 數(shù)據(jù)集:將算法獨(dú)立運(yùn)行20 次,與近幾年多種算法比較如表2–表7所示,其中表2–表6中的Kmeans、GA、ACO、PSO、HBMO、IDE 算法數(shù)據(jù)來源于文獻(xiàn)[3]且迭代次數(shù)為500 時(shí)的計(jì)算結(jié)果,IBA 算法數(shù)據(jù)來源于文獻(xiàn)[7],IGSO 算法數(shù)據(jù)來源于文獻(xiàn)[2],BPFPA 算法數(shù)據(jù)來源于文獻(xiàn)[6];表7中K-means、PSO、ABC、BA 和IBA 算法數(shù)據(jù)來源于文獻(xiàn)[7].從表2可知,IBOA 算法求解效果與IBA、BPFPA 相當(dāng),但比其余8 種算法效果較好;從表3可知,IBOA 算法與BPFPA 求解效果相當(dāng),但比其余7 種算法效果優(yōu)越許多;文中的“－”表示未有相關(guān)數(shù)據(jù).從表4可知,IBOA 的求結(jié)果在迭代次數(shù)為200 時(shí)優(yōu)于IDE 和其他算法;從表5可知,IBOA 算法的精度和方差均優(yōu)于其他算法;從表6可知,IBOA 算法的求解效果差于IDE,與IBA、BPFPA 效果相當(dāng),但優(yōu)于其他算法;從表7可知,IBOA 算法的求解效果與IBA、BPFPA 相當(dāng),但優(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é)合提出了一種改進(jìn)的蝴蝶優(yōu)化聚類算法,通過求解1 個(gè)人工數(shù)據(jù)集和5 個(gè)UCI 數(shù)據(jù)庫中不同規(guī)模的數(shù)據(jù),統(tǒng)計(jì)分析結(jié)果表明IBOA 算法能夠避免陷入局部最優(yōu),具有較快的收斂速度和較強(qiáng)的魯棒性,能夠有效解決聚類問題且與其他聚類算法相比具有一定優(yōu)勢.

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

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

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