一種自適應(yīng)變異二進(jìn)制粒子群算法

姜磊，劉建華，張冬陽(yáng)，卜冠南

(1.福建工程學(xué)院 信息科學(xué)與工程學(xué)院，福建 福州 350118；2.福建省大數(shù)據(jù)挖掘與應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，福建 福州 350118)

引言

在數(shù)據(jù)分析中，特征選擇是一種重要的數(shù)據(jù)預(yù)處理技術(shù)。常見(jiàn)的特征選擇方法包括過(guò)濾式、包裹式、嵌入式[1]。特征選擇問(wèn)題屬于NP難問(wèn)題，其包裹式特征選擇方法通常是將智能算法用于特征選擇。在智能算法中，二進(jìn)制粒子群算法(BPSO)具有規(guī)則簡(jiǎn)單、參數(shù)設(shè)置較少等優(yōu)點(diǎn)，從而被用到特征選擇的問(wèn)題中。

文獻(xiàn)[2]提出了基于二進(jìn)制粒子群優(yōu)化的水下目標(biāo)特征選擇算法，并結(jié)合k近鄰分類(lèi)算法對(duì)3類(lèi)實(shí)測(cè)水下目標(biāo)數(shù)據(jù)進(jìn)行了最優(yōu)特征集的選擇及分類(lèi)實(shí)驗(yàn)。文獻(xiàn)[3]提出基于離散粒子群算法進(jìn)行織物疵點(diǎn)特征選擇的方法。文獻(xiàn)[4]提出了一種基于粒子群優(yōu)化的入侵特征選擇算法，通過(guò)分析網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)特征之間的相關(guān)性，可使粒子群優(yōu)化算法在所有特征空間中優(yōu)化搜索，自主選擇有效特征子集，降低數(shù)據(jù)維度。

特征選擇一般采用原始的BPSO算法，文獻(xiàn)[5]從算法的位置改變概率以及遺傳算法的模式定理方面對(duì)BPSO算法進(jìn)行了分析，發(fā)現(xiàn)BPSO算法存在搜索能力不足的缺點(diǎn)。文獻(xiàn)[6]針對(duì)BPSO算法提出了改進(jìn)方法，并驗(yàn)證了改進(jìn)方法的有效性。文獻(xiàn)[7]提出基于特征聚類(lèi)信息進(jìn)行種群的初始化策略提高初始化種群的質(zhì)量，并提出了一種基于決策空間相似性的自適應(yīng)局部搜索策略，避免算法早熟。文獻(xiàn)[8]提出一種鯰魚(yú)效應(yīng)引入新的粒子來(lái)提高BPSO算法性能，并用于特征選擇。文獻(xiàn)[9]提出一種新改進(jìn)的BPSO-SVM 算法用于特征選擇。

綜上所述，BPSO算法存在過(guò)早收斂問(wèn)題，其權(quán)重設(shè)置存在不合理的問(wèn)題。為了將BPSO算法更好地用于特征選擇，本文研究在粒子位置更新后提出了一種自適應(yīng)變異操作，同時(shí)對(duì)算法慣性權(quán)重參數(shù)采用一種遞增的設(shè)置方案，從而得到一種自適應(yīng)變異BPSO算法(AMBPSO)。

1 相關(guān)工作

群智能優(yōu)化算法源于模仿自然界中生物群體的行為模式，適用于解決大規(guī)模復(fù)雜性問(wèn)題。如今，要處理的數(shù)據(jù)規(guī)模越來(lái)越大，數(shù)據(jù)中冗余的特征數(shù)量也越來(lái)越多，特征選擇即成為大規(guī)模的NP難問(wèn)題。所以，群智能優(yōu)化算法適合特征選擇問(wèn)題的處理，尤其在包裹式的特征選擇方面，大量的群智能優(yōu)化算法被應(yīng)用，例如遺傳算法、蟻群算法、蝗蟲(chóng)優(yōu)化算法、蜻蜓算法等[10-13]。群智能優(yōu)化算法在處理特征選擇問(wèn)題時(shí)以生物個(gè)體作為特征選擇的一個(gè)候選解，以分類(lèi)準(zhǔn)確率或分類(lèi)錯(cuò)誤率作為評(píng)價(jià)函數(shù)來(lái)引導(dǎo)群體生物中生物個(gè)體向群體最優(yōu)位置移動(dòng)，從而得到最優(yōu)解。BPSO算法的原理、參數(shù)設(shè)置相對(duì)簡(jiǎn)單，理論成熟度上比較成熟。但是同其他群智能算法一樣，BPSO算法也易陷入局部最優(yōu)的求解問(wèn)題。一般的啟發(fā)式搜索算法要求前期要具有全局搜索能力，后期要具有局部搜索能力，對(duì)于BPSO算法的改進(jìn)也需要遵循這個(gè)原則，平衡算法的搜索能力。

2 基于自適應(yīng)變異BPSO的特征選擇

2.1 BPSO 算法

BPSO算法是Kennedy于1997年在連續(xù)性PSO算法基礎(chǔ)上提出的，用于解決離散的優(yōu)化問(wèn)題[14]。

任意粒子i(i=1,2,…,N)根據(jù)公式(1)更新速度:

(1)

式中，id、gd表示坐標(biāo)變量，vid表示粒子速度，c1、c2表示學(xué)習(xí)因子，rand()表示 0～1 之間的隨機(jī)數(shù)。pid表示個(gè)體最優(yōu)粒子位置，pgd表示群體最優(yōu)粒子位置。xid表示粒子位置，ω表示慣性權(quán)重，衡量粒子學(xué)習(xí)過(guò)程中上一代粒子對(duì)當(dāng)代粒子的影響權(quán)重，受PSO算法的影響，BPSO的權(quán)重通常采用隨機(jī)迭代遞減的方法。BPSO算法用于解決離散空間中的優(yōu)化問(wèn)題，基于二進(jìn)制編碼原則，算法中粒子位置向量每一維取值只能為0和1。Kennedy 提出利用 Sigmoid 函數(shù)作為轉(zhuǎn)換函數(shù)，將連續(xù)空間中的位置向量的每一維映射到二進(jìn)制編碼中的0或者1。通過(guò)公式(2)計(jì)算對(duì)應(yīng)的Sigmoid 函數(shù)值:

(2)

式中，vid表示粒子速度，s(vid)表示位置xid取1的概率，粒子通過(guò)(3)式改變它的位值：

(3)

其中，rand()是0～1 之間的隨機(jī)數(shù)。

2.2 BPSO算法的自適應(yīng)變異操作

BPSO由于在漢明空間中變化，存在容易預(yù)收斂等問(wèn)題。公式(2)特性造成當(dāng)速度vid很大時(shí)，s(vid)很接近1，且恒為1，致使xid不易改變，算法過(guò)早收斂；反之當(dāng)速度vid很小，也易收斂于0。綜上，BPSO易于過(guò)早收斂。為了提高BPSO算法的多樣性，克服過(guò)早收斂問(wèn)題，文獻(xiàn)[15]對(duì)BPSO算法提出了一種變異手段，粒子在(3)式更新位置后引入了變異操作如式(4)。

(4)

式中，rmut代表變異概率，且rmut=1/N，N為數(shù)據(jù)維度，也就是對(duì)每個(gè)粒子每位都會(huì)產(chǎn)生概率為rmut的變異可能。

但是式(4)的rmut在算法迭代過(guò)程中為定值，缺少對(duì)BPSO算法缺陷的針對(duì)性。一般啟發(fā)性算法前期需要較強(qiáng)的全局搜索能力，后期需要突出局部的搜索能力?；谏鲜鲈?，BPSO算法早期變異率要大，晚期變異要小。因此引進(jìn)如式(5)變異操作。

(5)

式中，R表示變異概率，但不是固定值，采用一種遞減策略，如式(6):

(6)

式中，t為當(dāng)前算法迭代的代數(shù)，T為算法迭代的最大代數(shù)。

算法采用式(3)更新后，執(zhí)行由式(5)(6)組合的變異操作，表示在產(chǎn)生新的粒子時(shí)，每一個(gè)粒子每位產(chǎn)生一定變異概率。根據(jù)分析，式(6)的變異概率R值是從1到0，即早期幾乎都會(huì)發(fā)生變異，而晚期幾乎不發(fā)生變異，變異概率隨著代數(shù)的增加自適應(yīng)從1到0變化，而式(4)中rmut固定值表示每次變異概率都只是為1/N(維度分之一)。

2.3 BPSO的慣性權(quán)重設(shè)置

受到PSO算法影響，BPSO算法也存在慣性權(quán)重w，其設(shè)置采用式(7)的線性遞減方案，

(7)

式中，wmax表示慣性權(quán)重最大值，wmin表示慣性權(quán)重最小值，t表示當(dāng)前的迭代次數(shù)，T表示最大的迭代次數(shù)。

文獻(xiàn)[16]通過(guò)理論分析研究了慣性權(quán)重w的設(shè)置對(duì)算法的影響，認(rèn)為算法應(yīng)當(dāng)在初期有很強(qiáng)的全局探測(cè)能力，逐步到后期的時(shí)候具有很強(qiáng)的局部探索能力。保持其他參數(shù)不變時(shí)，較小的慣性權(quán)重能夠增強(qiáng)全局探測(cè)能力較大的慣性權(quán)重能夠增強(qiáng)局部的探索能力。本研究采用慣性權(quán)重線性遞增的方案如式(8)。

(8)

式中，ρ取0.9，意味著權(quán)重變化迭代到最大代數(shù)的90%代就結(jié)束了。此后的迭代中，權(quán)重為固定的值。

PSO算法中，慣性權(quán)重w一般采用式(7)的遞減策略，w值從0.9遞減到0.4；傳統(tǒng)的BPSO采用類(lèi)似的方案。本研究將式(8)的遞增方案引入BPSO算法中，wmax和wmin的取值方法將在試驗(yàn)方法中確定。

2.4 kNN算法

將BPSO應(yīng)用于特征選擇，需要一個(gè)監(jiān)督學(xué)習(xí)器評(píng)價(jià)其特征選擇的適用度函數(shù)。最近鄰近算法(k-Nearest Neighbor algorithm，kNN)是一種常用的監(jiān)督學(xué)習(xí)方法[17]，其工作機(jī)制簡(jiǎn)單理論上比較成熟，易于快速實(shí)現(xiàn)。其基本原理是：給定測(cè)試樣本，基于某種距離度量找出訓(xùn)練集中與其最靠近的k個(gè)訓(xùn)練樣本，然后基于這些樣本的信息來(lái)預(yù)測(cè)，選擇k個(gè)樣本中出現(xiàn)最多的類(lèi)別標(biāo)記作為預(yù)測(cè)結(jié)果。本研究采用kNN算法對(duì)數(shù)據(jù)進(jìn)行分類(lèi)判別，作為選取數(shù)據(jù)特征子集的評(píng)價(jià)函數(shù)，k取5。

2.5 帶自適用變異操作BPSO的特征選擇算法流程

帶自適用變異操作的BPSO算法(AMBPSO)在原始BPSO算法執(zhí)行式(3)位置更新后，再采用式(5)(6)變異操作，并輔以式(8)的權(quán)重設(shè)置方案，最后將特征選擇結(jié)果應(yīng)用于kNN構(gòu)造分類(lèi)準(zhǔn)確率評(píng)價(jià)中，因此產(chǎn)生了AMBPSO特征選擇算法。其流程包括AMBPSO特征選擇算法流程和5-NN算法流程。

AMBPSO特征選擇算法流程

1 開(kāi)始2 初始化粒子群,粒子維度dim=樣本數(shù)據(jù)維度,種群數(shù)量popsize=203 popul=rand(popsize,dim)<0.54 記錄初始個(gè)體最優(yōu)bestpos=popul5 計(jì)算各粒子適應(yīng)度值fitvalue by 5-NN()6 記錄最佳適應(yīng)度值fbestpos,以及對(duì)應(yīng)粒子位置g7 While(停止準(zhǔn)則為最大迭代次數(shù))8 更新個(gè)體最優(yōu)9 利用(1)式更新粒子速度10 利用(2)和(3)式更新粒子的位值11 利用(5)和(6)式對(duì)粒子位值進(jìn)行變異12 計(jì)算新的各粒子適應(yīng)度值by 5-NN()13 與現(xiàn)有粒子適應(yīng)度值作比較,更新全局最優(yōu),記錄最佳適應(yīng)度值及更新對(duì)應(yīng)粒子位置g14 End (直到滿足最大迭代次數(shù))15 輸出最佳適應(yīng)度值即為分類(lèi)準(zhǔn)確率

5-NN算法流程

1 for i=1 to測(cè)試數(shù)據(jù)的樣本數(shù)量2 for j=1 to訓(xùn)練數(shù)據(jù)的樣本數(shù)量3 for m=1:popsize4 特征選擇方案:A(m)=popul(m,:)5 if A(1,dim)==0distij=06 else7 distij=distij+(dataik-datajk)28 end if9 next m10 next j11 對(duì)distij進(jìn)行從小到大排序記錄其對(duì)應(yīng)類(lèi)別12 取出前k(k=5)個(gè)distij及其對(duì)應(yīng)類(lèi)別13 對(duì)k個(gè)樣本所屬類(lèi)別個(gè)數(shù)進(jìn)行統(tǒng)計(jì)14 選出出現(xiàn)次數(shù)最多的類(lèi)別即為第i個(gè)測(cè)試樣本的類(lèi)別classi15 next i16 correct=017 for i=1 to分類(lèi)問(wèn)題的樣本數(shù)18 if classi=第i個(gè)測(cè)試樣本 then19 correct=correct+120 end if21 next i22 適應(yīng)度值=corret/測(cè)試數(shù)據(jù)樣本數(shù)量

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

3.1 相關(guān)參數(shù)設(shè)置與原始數(shù)據(jù)集

在PSO算法中學(xué)習(xí)因子c1、c2均取2，種群數(shù)量為20，最大迭代次數(shù)為1 000，kNN算法中的k值取5。用于測(cè)試數(shù)據(jù)為8種不同類(lèi)型的數(shù)據(jù)集，這些數(shù)據(jù)都是從從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)下載(https:∥archive.ics.uci.edu/ml/index.php)。數(shù)據(jù)集信息如表1。

表1 數(shù)據(jù)集信息

3.2 實(shí)驗(yàn)方案

從慣性權(quán)重和對(duì)更新粒子進(jìn)行變異兩個(gè)角度分析BPSO算法性能的變化。為了決定遞增慣性權(quán)重設(shè)置方案中的wmax和wmin的取值，對(duì)原始BPSO方案采用幾組不同權(quán)重取值方案，對(duì)每個(gè)數(shù)據(jù)集分別運(yùn)行30次，取其平均選擇特征數(shù)和平均分類(lèi)準(zhǔn)確率作為算法性能的評(píng)價(jià)標(biāo)準(zhǔn)，最終確定一個(gè)最優(yōu)的權(quán)重方案。

在選擇了最佳的權(quán)重方案條件下，通過(guò)實(shí)驗(yàn)，比較帶固定變異的BPSO和本文提出的帶自適應(yīng)變異BPSO分別應(yīng)用特征選擇的分類(lèi)準(zhǔn)確率性能。因?qū)嶒?yàn)方案分兩個(gè)內(nèi)容如下：

(1) 在慣性權(quán)重設(shè)置方面分別采用原始遞減區(qū)間0.9～0.4、遞增區(qū)間0.4～0.9、遞增區(qū)間0.4～1.0 這3種不同的設(shè)置方案分別對(duì)8組不同類(lèi)型數(shù)據(jù)進(jìn)行特征選擇實(shí)驗(yàn)對(duì)比。

(2) 在最佳慣性權(quán)重設(shè)置方案基礎(chǔ)上，分別用AMBPSO與文獻(xiàn)[15]提出固定變異MBPSO算法對(duì)8組數(shù)據(jù)進(jìn)行特征選擇后分類(lèi)準(zhǔn)確率對(duì)比。

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

3.3.1 基于權(quán)重設(shè)置不同方案BPSO特征選擇

在慣性權(quán)重設(shè)置方面分別采用原始遞減區(qū)間0.9～0.4、遞增區(qū)間0.4～0.9、遞增區(qū)間0.4～1.0等3種不同的設(shè)置方案，分別對(duì)8組不同類(lèi)型數(shù)據(jù)最優(yōu)的特征選擇，即尋找采用kNN分類(lèi)準(zhǔn)確率性能最優(yōu)的特征選擇方案。

表2給出了采用3種慣性權(quán)重設(shè)置方案的數(shù)據(jù)集分類(lèi)準(zhǔn)確率。從表2可以看出，在采用慣性權(quán)重遞增方案且遞增范圍與原始遞減范圍一致時(shí)，數(shù)據(jù)集WDBC分類(lèi)準(zhǔn)確率稍低于原始遞減方案，其他數(shù)據(jù)集分類(lèi)準(zhǔn)確率稍高于原始遞減方案，但變化較小，可見(jiàn)算法性能提升較小。把慣性權(quán)重遞增范圍上限提升到1.0時(shí)，分類(lèi)準(zhǔn)確率均高于前兩種方案，算法性能得到進(jìn)一步提升。因此，本研究的慣性權(quán)重設(shè)置方案為遞增且遞增區(qū)間為0.4～1.0。

3.3.2 AMBPSO算法與MBPSO算法性能的比較

AMBPSO算法的慣性權(quán)重設(shè)置方案為上節(jié)確定的0.4～1.0的遞增策略，實(shí)驗(yàn)分別用AMBPSO和MBPSO算法特征選擇的分類(lèi)準(zhǔn)確率。為了更對(duì)比性能，實(shí)驗(yàn)中也列出兩個(gè)特征選擇時(shí)，分別選擇出的特征數(shù)量。表3給出了研究所采用的AMBPSO算法跟文獻(xiàn)[15]所用MBPSO算法的比較結(jié)果。

從表3可見(jiàn)， AMBPSO算法性能在分類(lèi)準(zhǔn)確率和選擇特征數(shù)量上都要明顯優(yōu)于MBPSO算法，尤其是3個(gè)維度較高的數(shù)據(jù)集Ionosphere、SPECTF、Snoar效果更加明顯。

表2 不同慣性權(quán)重設(shè)置方案的分類(lèi)準(zhǔn)確率

表3 AMBPSO算法與MBPSO算法實(shí)驗(yàn)結(jié)果比較

3.3.3 選擇特征數(shù)量的實(shí)驗(yàn)比較

為了對(duì)算法性能做更好的對(duì)比，表4給出了數(shù)據(jù)集在3種慣性權(quán)重設(shè)置方案及變異后選擇特征的數(shù)量，從表4可以看出，采用區(qū)間在0.4～0.9的方案除數(shù)據(jù)集Vehicle、SPECT、Snoar選擇特征數(shù)量相較原始方案減少1至2個(gè)外，其他數(shù)據(jù)集選擇特征數(shù)量減少數(shù)量變化較小或有所增加。采用區(qū)間在0.4～1.0的方案相較前兩個(gè)均無(wú)明顯變化，以上分析采用3種慣性權(quán)重設(shè)置方案所選擇的特征數(shù)量總體上無(wú)明顯變化。但在采用AMBPSO算法之后的選擇特征數(shù)量明顯少于3種慣性權(quán)重設(shè)置方案，尤其是在高維數(shù)據(jù)的變化更為明顯，說(shuō)明從特征選擇數(shù)量性能指標(biāo)分析，自適應(yīng)變異BPSO的特征選擇數(shù)據(jù)不僅優(yōu)于固定變異操作，而且也提高了原始BPSO算法在不同權(quán)重方案下的性能。

表4 不同慣性權(quán)重設(shè)置方案選擇特征的數(shù)量

3.3.4 實(shí)驗(yàn)曲線對(duì)比圖

為了直觀地比較AMBPSO算法對(duì)特征選擇性能的影響，圖1給出了原始BPSO算法和AMBPSO算法在(a)～(h)8個(gè)數(shù)據(jù)集上的分類(lèi)準(zhǔn)確率隨迭代變化的對(duì)比曲線。從圖1可以看出，除了數(shù)據(jù)集Wine后期分類(lèi)準(zhǔn)確率AMBPSO算法稍低之外，其他7個(gè)數(shù)據(jù)集的AMBPSO算法分類(lèi)準(zhǔn)確率在實(shí)驗(yàn)前期低于原始BPSO算法，在實(shí)驗(yàn)后期隨著迭代次數(shù)增加都明顯高于原始BPSO算法，說(shuō)明在前期，AMBPSO算法的粒子的變異率較大，全局搜索能力較強(qiáng)，后期隨著迭代次數(shù)的增加，粒子變異率逐漸減小，算法的局部搜索能力得到增強(qiáng)，最終AMBPSO算法分類(lèi)準(zhǔn)確率比BPSO算法高。圖1曲線圖與2.2節(jié)所分析的理論完全吻合，并且算法性能得到明顯提高。

綜上分析，從分類(lèi)準(zhǔn)確率和選擇特征數(shù)量?jī)蓚€(gè)角度對(duì)比，結(jié)果證明本研究采用的新的慣性權(quán)重方案和自適應(yīng)變異操作相結(jié)合的AMBPSO算法具有明顯優(yōu)勢(shì)，從實(shí)驗(yàn)曲線圖上可以看出AMBPSO算法增強(qiáng)了原始算法前期的全局搜索能力和后期局部搜索能力，明顯提高了算法性能。

圖1 BPSO算法和AMBPSO算法在8個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)曲線對(duì)比圖Fig.1 Comparison of experimental curves of BPSO algorithm and AMBPSO algorithm on 8 data sets

4 結(jié)論

本研究提出的AMBPSO算法采用了線性遞增的慣性權(quán)重設(shè)置，并通過(guò)實(shí)驗(yàn)驗(yàn)證的方式確定了慣性權(quán)重的取值區(qū)間。另外在粒子更新后采用了一種變異操作，隨迭代次數(shù)變異概率遞減，使得粒子在前期的變異率大，后期變異率小。該算法在前期粒子的多樣性更強(qiáng)，具有較強(qiáng)的全局搜索能力，后期具有較強(qiáng)的局部搜索能力，算法性能明顯優(yōu)于原始的BPSO算法以及固定變異的二進(jìn)制粒子群算法(MBPSO)。