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

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 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)化過程中，蝙蝠個體通過調(diào)整對應(yīng)的響度與脈沖率，改變自身的位置，并且追隨最優(yōu)的蝙蝠個體，從而找到全局最優(yōu)解。該算法是搜索全局最優(yōu)解的有效方法并且收斂較快，但是也存在求解精度不高、易陷入局部最優(yōu)的缺陷。文獻(xiàn)[7]針對蝙蝠算法求解精度不高進(jìn)行了相關(guān)改進(jìn)，但是也存在容易陷入局部極值的問題。

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

1 蝙蝠算法介紹與分析

1.1 蝙蝠算法描述

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

1.1.1 蝙蝠算法的全局搜索

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

(1)

(2)

(3)

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

1.1.2 蝙蝠算法的局部搜索

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

Xnew=Xold+εAt

(4)

(5)

(6)

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

(7)

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

1.2 蝙蝠算法實現(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)生一個局部解Xnew

End if

ifrand

Xi=Xnew

fitness(i)=f(Xnew)

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

End if

End for

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

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

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

(8)

(9)

(10)

2.1.2 IDBA指引方向

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

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

(13)

(14)

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

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

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

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

Step 2 Whilet

Fori=1 toNp

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

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

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

End if

Ifrand>ri

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

End if

ifrand

GVi←Xnew-Xi

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

使GVi向中方向個數(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)勝劣汰策略，對蝙蝠個體按照適應(yīng)度值從小 到大排序。然后初始化一些蝙蝠個體，個體數(shù) 為蝙蝠個體總數(shù)的30 %，并且代替適應(yīng)度值較 小的30 %個蝙蝠個體

End

End While

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

4 實驗與結(jié)果分析

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

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

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

(15)

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

4.2 聚類評價指標(biāo)

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

(16)

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

4.3 聚類準(zhǔn)則

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

(17)

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

4.4 實驗參數(shù)設(shè)置

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

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

4.5.1 實驗結(jié)果

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

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

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

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

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

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

4.5.2 實驗分析

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