一種改進(jìn)的蝙蝠算法*

周賢泉， 宋 威， 張士昱， 王晨妮

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

0 引 言

近來，群體智能算法作為一類優(yōu)化算法越來越為人所知[1～3],2010年Yang X S教授提出了蝙蝠算法(bat algorithm，BA)[4]，2011年Yang X S根據(jù)蝙蝠算法處理多目標(biāo)的優(yōu)化問題，取得了很好的效果[5,6]。在蝙蝠算法的優(yōu)化過程中，蝙蝠個(gè)體通過調(diào)整對(duì)應(yīng)的響度與脈沖率，改變自身的位置，并且追隨最優(yōu)的蝙蝠個(gè)體，從而找到全局最優(yōu)解。該算法是搜索全局最優(yōu)解的有效方法并且收斂較快，但是也存在求解精度不高、易陷入局部最優(yōu)的缺陷。文獻(xiàn)[7]針對(duì)蝙蝠算法求解精度不高進(jìn)行了相關(guān)改進(jìn)，但是也存在容易陷入局部極值的問題。

本文在文獻(xiàn)[7]基礎(chǔ)上提出4個(gè)方面的改進(jìn),并最終通過對(duì)UCI中的數(shù)據(jù)集進(jìn)行聚類測(cè)試，發(fā)現(xiàn)提出的改進(jìn)蝙蝠算法能夠有效的解決文獻(xiàn)[7]中存在的問題。

1 蝙蝠算法介紹與分析

1.1 蝙蝠算法描述

蝙蝠算法[8]原理：首先初始化每個(gè)蝙蝠個(gè)體的位置與速度，并且把這些蝙蝠個(gè)體所在的位置當(dāng)做求解問題空間的解，求出每個(gè)蝙蝠個(gè)體對(duì)應(yīng)的適應(yīng)度函數(shù)值。在迭代過程中，每個(gè)蝙蝠個(gè)體都會(huì)調(diào)整對(duì)應(yīng)的脈沖率與響度，向著最優(yōu)蝙蝠個(gè)體所在的位置移動(dòng)，最終可以尋找到全局最優(yōu)解。

1.1.1 蝙蝠算法的全局搜索

fi=fmin+(fmax-fmin)β,β∈[0,1]

(1)

(2)

(3)

式中β為[0 , 1]之間的一個(gè)隨機(jī)數(shù)，fi為第i只蝙蝠當(dāng)前的頻率，X*表示在當(dāng)前迭代過程中所有蝙蝠個(gè)體中最佳個(gè)體對(duì)應(yīng)的位置。在求解優(yōu)化問題中，fi的取值根據(jù)問題領(lǐng)域的大小確定，假設(shè)fmin=0，fmax=2，那么在蝙蝠算法尋優(yōu)過程中，每只蝙蝠都從[fmin，fmax]之間隨機(jī)獲得對(duì)應(yīng)的頻率。

1.1.2 蝙蝠算法的局部搜索

蝙蝠個(gè)體局部尋優(yōu)時(shí)，一旦搜尋到更優(yōu)解，蝙蝠個(gè)體就會(huì)在隨機(jī)游走中就近產(chǎn)生，其局部尋優(yōu)公式為

Xnew=Xold+εAt

(4)

(5)

(6)

式中α,γ都為常數(shù)，對(duì)于任意0<α<1和γ>0有

(7)

蝙蝠算法初始化時(shí)，每只蝙蝠個(gè)體的響度與脈沖率隨機(jī)設(shè)定，一般響度在[1 , 2]之間，脈沖率一般在[0 , 1]之間，在蝙蝠個(gè)體尋優(yōu)過程中，響度與脈沖率是不斷更新的。

1.2 蝙蝠算法實(shí)現(xiàn)步驟

假設(shè)求解目標(biāo)函數(shù)f(x)的極小值，其中，x=[x1,x2,…,xd]T，種群大小為Np，t=1，最大迭代次數(shù)為Tmax，響度為A，脈沖率為r，用以下偽代碼表示蝙蝠算法求解優(yōu)化問題的基本步驟：

Whilet

Fori=1 toNp

根據(jù)式(1)，式(2)，式(3)生成新的解Xnew

Ifrand>ri

根據(jù)式(4)產(chǎn)生一個(gè)局部解Xnew

End if

ifrand

Xi=Xnew

fitness(i)=f(Xnew)

根據(jù)式(5)，式(6)更新Ai和ri

End if

End for

蝙蝠個(gè)體按照對(duì)應(yīng)的適應(yīng)度值從小到大排序，找到最佳蝙蝠個(gè)體，更新X*

End While

2 改進(jìn)的蝙蝠算法

2.1 Improved-dBA算法

dBA[7]算法由Chakri A于2016提出，本文基于dBA基礎(chǔ)上提出一種改進(jìn)的BA(improved-DBA，IDBA)算法。

2.1.1 IDBA全局尋優(yōu)策略

在求解優(yōu)化問題時(shí)，往往存在多個(gè)極值，如果像文獻(xiàn)[7]中蝙蝠群體朝著最佳的蝙蝠個(gè)體位置移動(dòng)，那么蝙蝠個(gè)體不僅容易陷入局部極值，而且會(huì)使得種群多樣性急劇減少，所以,本文首先將蝙蝠個(gè)體按照對(duì)應(yīng)適應(yīng)度值從小到大排列，保存其中適應(yīng)度值較低的一些個(gè)體，然后在全局尋優(yōu)過程中，蝙蝠個(gè)體隨機(jī)從適應(yīng)度值較低的個(gè)體中選擇一個(gè)個(gè)體指導(dǎo)蝙蝠個(gè)體尋優(yōu)，這樣避免蝙蝠個(gè)體朝著單個(gè)最佳蝙蝠個(gè)體位置移動(dòng)，以防止蝙蝠個(gè)體陷入局部極值。

蝙蝠個(gè)體在迭代過程中存在個(gè)體歷史最優(yōu)位置，這些位置周圍也可能存在全局最優(yōu)解，所以,本文借鑒粒子群算法[2]中的尋優(yōu)策略，在蝙蝠個(gè)體全局尋優(yōu)策略中向著此個(gè)體迭代過程中的歷史最佳位置前進(jìn)以促進(jìn)蝙蝠個(gè)體尋優(yōu)。

蝙蝠發(fā)出的脈沖可以沿不同的方向發(fā)射，蝙蝠兩只耳朵可以接受回波，假設(shè)每只蝙蝠可以發(fā)射2個(gè)可能是有用的脈沖到2個(gè)方向，所以,提出兩種全局尋優(yōu)策略

(8)

(9)

(10)

2.1.2 IDBA指引方向

式(10)中的全局尋優(yōu)策略Xnew1示例圖如圖1(a)所示，表示出在Xnew1對(duì)應(yīng)的全局尋優(yōu)策略中，加上指引方向gdirection相比于不加指引方向離全局最優(yōu)解位置更近。

如圖1(b)可知，如果每次能夠得到較好的指引方向，那么就能夠在較少的迭代次數(shù)內(nèi)尋得全局最優(yōu)解。

圖1 蝙蝠全局尋優(yōu)策略

2.1.3 IDBA局部尋優(yōu)策略

提出的IDBA算法引用文獻(xiàn)[7]中的局部尋優(yōu)策略

(11)

(12)

式中w0=(Ubi-Lbi)/4，w∞=w0/4。

2.1.4 IDBA響度和脈沖率更新

2010年，Yang提出蝙蝠個(gè)體在迭代過程中根據(jù)式(5)和式(6)來更新響度和脈沖率，以此方法快速的搜尋到最優(yōu)解。脈沖率決定蝙蝠個(gè)體是否進(jìn)行局部尋優(yōu)，如果脈沖率在較少的迭代次數(shù)內(nèi)變得很大，那么如1.2節(jié)原始蝙蝠算法所示，蝙蝠個(gè)體就會(huì)有較低的概率進(jìn)行局部尋優(yōu)；同樣，如果響度A的值在較少的迭代次數(shù)內(nèi)變得很小，根據(jù)1.2節(jié)蝙蝠算法中可以看出這樣不利于全局尋優(yōu)得到的更優(yōu)解。

本文引用文獻(xiàn)[7]中脈沖率與響度的變化策略。脈沖率隨著迭代次數(shù)的增加而緩慢的變大，響度隨著迭代次數(shù)的增加而緩慢的變小。早期較小的脈沖率與較大的響度使得蝙蝠個(gè)體在全局搜索的過程中也能有很大的概率進(jìn)行局部尋優(yōu)；后期雖然脈沖率較大，但是也存在一定的概率進(jìn)行局部搜索，響度雖然較小，同樣存在一定的概率進(jìn)行解的更新，所以，設(shè)定IDBA算法中的脈沖率與響度如式(13)，式(14)所示變化

(13)

(14)

2.1.5 IDBA優(yōu)勝劣汰策略

在IDBA算法中，每只蝙蝠個(gè)體在迭代后對(duì)蝙蝠個(gè)體按照適應(yīng)度值從小到大進(jìn)行排序，并且隨機(jī)初始化蝙蝠個(gè)體總數(shù)的30 %的新個(gè)體代替適應(yīng)度值較大的蝙蝠個(gè)體。這樣增加蝙蝠個(gè)體的種群多樣性，增強(qiáng)所有蝙蝠個(gè)體的全局尋優(yōu)能力。

3 IDBA算法聚類應(yīng)用實(shí)現(xiàn)步驟

假設(shè)某數(shù)據(jù)集X存在m類樣本，對(duì)數(shù)據(jù)集X進(jìn)行聚類。將各中心點(diǎn)與對(duì)應(yīng)樣本的余弦距離和作為求解的適應(yīng)值函數(shù)。

Step 2 Whilet

Fori=1 toNp

IfGVi=Φ,設(shè)定GVi=零向量，否則從矩陣

GVi中隨機(jī)選擇一個(gè)向量作為gdirection，

根據(jù)式(8)、式(9)、式(10)生成新的解Xnew

End if

Ifrand>ri

產(chǎn)生一個(gè)局部解Xnew

End if

ifrand

GVi←Xnew-Xi

IfGVi方向數(shù)超過Np，隨機(jī)刪除一些方向向量，

使GVi向中方向個(gè)數(shù)不大于Np

End if

fitness(i)=f(Xnew)

End if

End if

End if

Step 3 設(shè)定參數(shù)C，算法每迭代C次設(shè)定GVi=Φ。

Step 4 優(yōu)勝劣汰策略，對(duì)蝙蝠個(gè)體按照適應(yīng)度值從小 到大排序。然后初始化一些蝙蝠個(gè)體，個(gè)體數(shù) 為蝙蝠個(gè)體總數(shù)的30 %，并且代替適應(yīng)度值較 小的30 %個(gè)蝙蝠個(gè)體

End

End While

蝙蝠個(gè)體按照適應(yīng)度值從小到大排序，找到最佳蝙蝠個(gè)體x*，可視化聚類結(jié)果

4 實(shí)驗(yàn)與結(jié)果分析

4.1 數(shù)據(jù)集

本文選擇UCI(http;//archive.ics.uci.edu/ml/)中的3個(gè)數(shù)據(jù)集作為各對(duì)比實(shí)驗(yàn)的聚類測(cè)試數(shù)據(jù)集。數(shù)據(jù)集1選擇Iris數(shù)據(jù)集，包含150個(gè)樣本，每個(gè)樣本包含4個(gè)屬性，分為3類，每類有50個(gè)樣本。數(shù)據(jù)集2選擇Wine數(shù)據(jù)集，包括了3種酒中13種不同成分的數(shù)量，數(shù)據(jù)集每行代表一種酒的樣本，共有178個(gè)樣本，其中,第1類有59個(gè)樣本，第2類有71個(gè)樣本，第3類有48個(gè)樣本；數(shù)據(jù)集3選擇Sonar數(shù)據(jù)集，包括了2類樣本，每類樣本有60個(gè)屬性，第一類有97個(gè)樣本，第二類有個(gè)樣本101個(gè)樣本。

為了避免各維度取值范圍不一致對(duì)聚類測(cè)試產(chǎn)生影響[9]，實(shí)驗(yàn)前采用極大值標(biāo)準(zhǔn)化對(duì)各數(shù)據(jù)集進(jìn)行歸一化處理

(15)

式中i為數(shù)據(jù)集中的樣本個(gè)數(shù)，j為樣本維數(shù)。

4.2 聚類評(píng)價(jià)指標(biāo)

準(zhǔn)確率(precision,P)[10]是指聚類正確的樣本與該類原有樣本數(shù)量之間的比值

(16)

式中Mi為第i類中的樣本數(shù)量，mi為正確聚類到第i類中的樣本數(shù)量，P越大說明聚類效果越好。

4.3 聚類準(zhǔn)則

本文選擇余弦相似度[11]對(duì)相似的樣本進(jìn)行歸類，通過計(jì)算2個(gè)向量的夾角余弦值來評(píng)估相似度

(17)

式中a與b分別為兩個(gè)樣本，cosθ越小說明兩個(gè)樣本之間相似性較低，cosθ越大說明兩個(gè)樣本之間相似性較高，兩個(gè)樣本可以歸為一類。

4.4 實(shí)驗(yàn)參數(shù)設(shè)置

本實(shí)驗(yàn)硬件環(huán)境:PC(CPU∶2.53 GHz,內(nèi)存∶2 GB),軟件環(huán)境Windows 7操作系統(tǒng)，在MATLAB R2014a編譯器上實(shí)現(xiàn)。

4.5 聚類測(cè)試結(jié)果與分析

4.5.1 實(shí)驗(yàn)結(jié)果

分別根據(jù)BA，DBA，IDBA，PSO，DE算法對(duì)數(shù)據(jù)集1、數(shù)據(jù)集2、數(shù)據(jù)集3進(jìn)行聚類測(cè)試。對(duì)每個(gè)算法獨(dú)立運(yùn)行 30次，最好的每類聚類正確的樣本個(gè)數(shù)如表1、表2、表3所示。

表1 各算法對(duì)應(yīng)的數(shù)據(jù)集1聚類正確的樣本個(gè)數(shù)

表2 各算法對(duì)應(yīng)的數(shù)據(jù)集2聚類正確的樣本個(gè)數(shù)

表3 各算法對(duì)應(yīng)的數(shù)據(jù)集3聚類正確的樣本個(gè)數(shù)

圖3為數(shù)據(jù)集1、數(shù)據(jù)集2、數(shù)據(jù)集3對(duì)應(yīng)的各智能算法運(yùn)行30次得到的聚類準(zhǔn)確率。

圖3 三個(gè)數(shù)據(jù)集對(duì)應(yīng)不同算法的聚類準(zhǔn)確率

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

由圖3(a)可知，對(duì)于數(shù)據(jù)集1，原始BA，PSO，DE算法容易陷入局部極值使得聚類準(zhǔn)確率較低只有66.67 %。文獻(xiàn)[7]中的改進(jìn)BA算法雖然能夠得到比較穩(wěn)定的聚類結(jié)果，但精度不是很高，本文算法，不僅能夠得到比較穩(wěn)定的聚類結(jié)果，而且測(cè)試精度達(dá)到98 %。由圖3(b)可知，對(duì)于數(shù)據(jù)集2，本文提出的改進(jìn)的蝙蝠算法IDBA相比于其他智能算法，聚類結(jié)果更穩(wěn)定并且能夠得到更好的聚類準(zhǔn)確率94.4 %。由圖3(c)可知，對(duì)于數(shù)據(jù)集3，本文提出的改進(jìn)的蝙蝠算法IDBA相比于其他智能算法，雖然聚類結(jié)果同樣不是很穩(wěn)定，但聚類準(zhǔn)確率最高，準(zhǔn)確率為69.23 %。

5 結(jié) 論

本文提出的IDBA算法相比于文中涉及到的其他智能算法收斂性更穩(wěn)定，魯棒性更強(qiáng)，并且求解精度較高，但該算法存在設(shè)置的參數(shù)較多的問題，參數(shù)設(shè)置不當(dāng)可能得不到更好的解，接下來該研究合適的參數(shù)，使得對(duì)于大部分優(yōu)化問題都可行。