姜 磊 劉建華 張冬陽 卜冠南

(福建工程學院信息科學與工程學院 福建 福州 350118) (福建省大數(shù)據(jù)挖掘與應用技術重點實驗室 福建 福州 350118)

0 引 言

二進制粒子群算法(BPSO)具有規(guī)則簡單、參數(shù)設置較少等優(yōu)點被廣泛應用到各領域的問題解決中。例如：文獻[1]提出了一種改進的BPSO用于生物組學特征選擇，文獻[2]將BPSO應用到刀具磨損狀態(tài)的識別中，文獻[3]將BPSO應用到電路優(yōu)化中，文獻[4]將BPSO應用到數(shù)據(jù)預處理的特征選擇問題等。

很多文獻都認為BPSO本身存在早熟、易陷入局部最優(yōu)等缺陷。針對這些缺陷文獻[5]將二進制黑洞算法與二進制粒子群算法相結合，實驗證明新的算法避免了局部極小值、收斂速度快，提高了分類準確率。文獻[6]提出了一種鯰魚效應的BPSO，通過引入鯰魚粒子來替換陷入局部最優(yōu)時最差的粒子。文獻[7]針對文本聚類中的特征選擇問題將BPSO與基于對立學習、混沌映射、基于適應度的動態(tài)慣性權重和變異相結合形成一種新的智能算法，實驗結果表明該算法具有較高的聚類精度，提升了BPSO的性能。文獻[8]針對BPSO的早熟收斂問題，利用速度和最優(yōu)群解之間的相似性來控制群變率，實驗結果表明該方法能夠正確選擇識別輸入特征，并具有較高的分類精度。而本文通過對粒子間距離變化曲線分析出原始BPSO具有過強的全局搜索能力，不收斂于全局最優(yōu)粒子，算法一直處于隨機全局探索中缺乏局部的搜索能力。以上提出的算法大都是與其他算法相結合或者引入新的粒子來改進原有的BPSO，本質(zhì)上都是增強算法后期的局部搜索能力。另外，較少有從轉換函數(shù)的角度來對算法進行改進，如:文獻[9]在原始的轉換函數(shù)基礎上提出了一種時變轉換函數(shù)，在背包問題的實驗上得到了較好的效果。文獻[10]直接給出了四種V型轉換函數(shù)并且選取了最優(yōu)的轉換函數(shù)。文獻[11]直接使用文獻[10]中選取的轉換函數(shù)來替換原始的轉換函數(shù)結合改進的適應度函數(shù)用于特征選擇。有關轉換函數(shù)分析的文獻較少，而且對原始算法轉換函數(shù)存在的缺點分析不夠深入，或是直接引用文獻[10]給出的轉換函數(shù)。

轉換函數(shù)在算法中占有非常重要的位置，本文從轉換函數(shù)的角度來對算法進行分析改進，針對原始BPSO轉換函數(shù)存在缺陷進行分析，提出一種更符合BPSO對轉換函數(shù)要求的V型轉換函數(shù)替換原始的S型轉換函數(shù)，形成VBPSO來克服原始算法過強搜索能力的缺陷，增強算法后期的局部搜索能力，提升原始BPSO的性能并應用到特征選擇問題中。

1 經(jīng)典BPSO

BPSO是Kennedy等[12]在連續(xù)性PSO基礎上提出的，用于解決離散的優(yōu)化問題。粒子速度與位置更新:

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

vid=w×vid+c1×rand()×(pid-xid)+

c2×rand()×(pgd-xid)

(1)

式中：w為慣性權重;c1、c2為學習因子;rand()為0到1之間的均勻隨機數(shù);pid為個體最優(yōu)粒子位置;xid為粒子位置;pgd為全局最優(yōu)粒子位置。

BPSO用于解決離散空間中的優(yōu)化問題，基于二進制編碼原則，算法中粒子位置向量每一維取值只能為0和1。Kennedy提出利用Sigmoid函數(shù)作為轉換函數(shù)，將連續(xù)空間中的位置向量的每一維映射到二進制編碼中的0或者1。計算對應的Sigmoid函數(shù)值:

(2)

式中：S(vid)為位置取1的概率，粒子通過式(3)改變它的位置。

(3)

2 BPSO分析

2.1 性能分析

對于BPSO的性能可以從算法的搜索能力進行實驗分析，粒子群算法在求解過程中，隨迭代次數(shù)增加各粒子自身位置會發(fā)生改變，向全局最優(yōu)粒子位置靠近，從而得到最優(yōu)解。這說明各粒子到全局最優(yōu)粒子間的距離會隨著迭代而發(fā)生變化，當各粒子靠近全局最優(yōu)解時距離會越來越小趨于0,為此本節(jié)定義一個距離L。

L代表各粒子到全局最優(yōu)粒子間的平均距離，如下：

(4)

式中：n為群體中粒子的數(shù)量，i取值為{1，2，…，n};d表示粒子的維度，取值為{1,2,…,D}。

式(4)表示一個粒子的每一位與全局最優(yōu)粒子的每一位對應求異或，再把對應每一位的異或值求和就得到了一個粒子與全局最優(yōu)粒子的距離。然后把求得的各個粒子間距離相加再除以粒子與全局最優(yōu)粒子間的間隔數(shù)就得出各粒子到全局最優(yōu)粒子間的平均距離L。若每個粒子的位置與全局最優(yōu)粒子位置趨于一致時，則粒子間的異或值的和趨于0，則L趨于0。若每個粒子的位置與全局最優(yōu)粒子位置都不同時，則粒子間的異或值的和為最大，此時L為最大。也可以認為，當L增大，此時各粒子的位置與全局最優(yōu)粒子的位置不同的數(shù)量越來越多，粒子的多樣性和隨機性越來越強，可以說明算法的全局搜索能力越來越強。反之L減小時，各粒子位置與全局最優(yōu)粒子位置趨于相同，各粒子向全局最優(yōu)粒子靠近，算法具有較強的局部搜索能力。

因此，L值可以用來定量分析算法的搜索能力。圖1為用數(shù)據(jù)集Snoar做BPSO特征選擇實驗的L的曲線圖。

圖1 粒子間平均距離L變化曲線圖

圖1給出了各粒子到全局最優(yōu)粒子間平均距離L的動態(tài)變化趨勢，隨著迭代次數(shù)增加各粒子到全局最優(yōu)粒子間平均距離越來越大，全局最優(yōu)粒子的位置不同的粒子的數(shù)量越來越多，差異性越來越大，粒子的多樣性和隨機性越來越強，不收斂于全局最優(yōu)粒子。說明原始BPSO隨著迭代次數(shù)增加全局搜索能力越來越強，缺乏局部搜索能力，算法一直處于隨機全局探索中，沒有啟發(fā)性搜索功能。

2.2 S型轉換函數(shù)分析

2.1節(jié)通過實驗曲線圖直觀說明了原始BPSO后期具有過強的全局搜索能力，本節(jié)從轉換函數(shù)的角度來分析算法存在問題的原因。BPSO轉換函數(shù)為S(vid),其表示粒子位置取1的概率，函數(shù)曲線如圖2所示。

圖2 原始BPSO轉換函數(shù)曲線圖

圖2說明原始BPSO的轉換函數(shù)曲線為S型，式(2)特性造成當速度vid很大時，S(vid)很接近1，而容易總為1，從而xid不易改變，過早收斂，反之當速度vid很小，也易收斂于0。因此，BPSO易于過早收斂。

有文獻也對粒子的速度和轉換函數(shù)的關系進行了分析。例如文獻[13]提出了位變化概率的思想，并對速度與位變化概率間的關系進行分析討論，認為當粒子速度為0時，位改變率達到最大的0.5，此時粒子的隨機性最大，算法具有較強的全局搜索能力。一般的啟發(fā)式算法開始需要全局的搜索能力，后期需要局部搜索能力，所以需要改變粒子速度與轉換函數(shù)之間的關系。另外文獻[14]認為轉換函數(shù)表示粒子位置的改變率，應該在[0,1]內(nèi)有界；粒子速度絕對值較大時粒子位置的改變率要高，相反在粒子速度絕對值較小時，粒子位置的改變率要低。綜上分析，原始的S型轉換函數(shù)使得算法的全局搜索能力越來越強而缺乏局部的搜索能力，需要對原始轉換函數(shù)改進以增強算法的局部搜索能力提高算法的性能。

3 V型轉換函數(shù)

3.1 函數(shù)提出

通過以上分析，改進的轉換函數(shù)值應表示粒子位置改變概率，并要符合以下要求：當粒子速度為0時，粒子的位置和最優(yōu)粒子位置一樣，粒子位置不用改變，轉換函數(shù)值為0；當粒子速度趨于正無窮或負無窮時，粒子可能不是最佳解，粒子的位置改變率要高，所以轉換函數(shù)值應趨于1。因此，轉換函數(shù)的函數(shù)曲線為關于y軸對稱的V型曲線，如圖3所示。

圖3 轉換函數(shù)曲線圖

根據(jù)上述分析對轉換函數(shù)的要求以及圖3所示的轉換函數(shù)曲線，改進的轉換函數(shù)為:

(5)

式中：S(vid)表示粒子位置改變的概率。當粒子速度vid為0時S(vid)為0,當vid趨于正負無窮時S(vid)趨于1，所以式(5)符合圖2所示的轉換函數(shù)曲線。為使得粒子位置在轉換函數(shù)值變化時符合以上分析，對粒子更新式(3)做如下改變：

(6)

式(6)表示在粒子速度較高時候當前粒子位置取反，粒子速度較低時當前粒子位置不變，對應了改進的轉換函數(shù)對粒子位置的要求。

在采用式(5)和式(6)后粒子速度絕對值較大時，粒子位置很大可能會改變而趨向最優(yōu)粒子。粒子速度絕對值較小時，粒子位置可能不變，所以粒子很快會收斂于全局最優(yōu)值。為直觀反映以上分析，同樣選擇數(shù)據(jù)集Snoar做特征選擇實驗，其L隨迭代次數(shù)的變化曲線如圖4所示。

圖4 采用新公式粒子間平均距離L變化曲線圖

可以看出L到迭代中期以后曲線急劇下降且趨于0，與圖1中的曲線趨勢完全不同。根據(jù)曲線趨勢結合2.1節(jié)L定義式可以得出，采用新公式到迭代中期以后，與全局最優(yōu)粒子位置不同的粒子的數(shù)量越來越少，粒子的多樣性趨于一致，粒子間距離越來越近，最終收斂于全局最優(yōu)粒子。與圖1對比分析說明采用新公式后各粒子會逐步靠近且最終收斂全局最優(yōu)粒子，具有較強的局部搜索能力。

3.2 函數(shù)分析

文獻[10]列出了四種轉換函數(shù)，并且選出了最優(yōu)的轉換函數(shù)，本節(jié)將對本文所提轉換函數(shù)與文獻[10]所提轉換函數(shù)進行函數(shù)曲線和算法性能對比，如圖5和圖6所示。

圖5 轉換函數(shù)曲線對比圖

圖6 粒子間平均距離曲線圖

圖5給出了兩種轉換函數(shù)曲線對比圖，y1為本文所提轉換函數(shù)，y2為文獻[10]所選最優(yōu)轉換函數(shù)。 y1、y2兩條曲線有兩個關于x=0對稱的交點，結合2.2節(jié)與3.1節(jié)可做以下分析，兩交點內(nèi)粒子速度的絕對值較小，此時的粒子位置與全局最優(yōu)粒子位置相同的概率較大，所以當前的粒子位置需要改變的概率應該要小，意味著轉換函數(shù)值要小，圖中兩交點內(nèi)y1的值小于y2，位置改變概率y1更小些。兩交點外粒子速度的絕對值較大，此時的粒子很可能不是最佳解，所以當前的粒子位置需要改變的概率應該要大，意味著轉換函數(shù)值要大，圖中兩交點外y1的值大于y2，位置改變概率y1更大些。根據(jù)以上分析，相比較y2，y1更符合轉換函數(shù)的要求，在圖6中也可以看出本文所提出的y1轉換函數(shù)的優(yōu)勢。

圖6中v1、v2、v3和v4分別為采用文獻[10]中所列出的轉換函數(shù)后所做特征選擇實驗曲線圖，v為采用本文所提出的轉換函數(shù)后的曲線。v1、v2的曲線大致相同，v3、v4的曲線大致相同，v1、v2曲線明顯低于v3、v4且一直呈遞減趨勢，說明采用v1、v2轉換函數(shù)后BPSO的局部搜索能力過強，前期缺乏全局搜索能力。曲線v在前期呈稍遞增趨勢，在中期后曲線快速遞減且低于v1、v2、v3、v4說明采用本文所提的轉換函數(shù)后算法前期具有全局搜索能力，后期具有較強的局部搜索能力，明顯強于文獻[10]選出的最優(yōu)轉換函數(shù)v4，更能接近全局最優(yōu)粒子，算法性能更高。為了驗證本文所涉及算法的性能分析，特別設計了特征選擇實驗。在此以V字型轉換函數(shù)為例來設計特征選擇實驗。

4 應用V字型轉換函數(shù)BPSO特征選擇流程

將BPSO應用于特征選擇，需要一個監(jiān)督學習器評價其特征選擇的適用度函數(shù)。KNN[15](K-Nearest Neighbor algorithm)是一種常用的監(jiān)督學習方法，其工作機制簡單,理論比較成熟，易于快速實現(xiàn)。本文采用KNN對數(shù)據(jù)進行分類判別，作為選取數(shù)據(jù)特征子集的評價函數(shù)。

綜合上述思想，本文提出的V型轉換函數(shù)BPSO(VBPSO)就是原始BPSO在迭代過程中采用轉換函數(shù)式(5)以及粒子改變式(6)再將其應用于KNN構造的特征選擇評價中，因此產(chǎn)生了特征選擇算法，用特征選擇算法來驗證本文算法的性能。

算法1VBPSO特征選擇算法

1. 初始化粒子群，粒子維度dim=樣本數(shù)據(jù)維度，種群數(shù)量popsize=20；

2.popul=rand(popsize,dim)<0.5；

3. 記錄初始個體最優(yōu)bestpos=popul；

4. 計算各粒子適應度值fitvalueby 5-NN()；

5. 記錄最佳適應度值fbestpos，以及對應粒子位置g；

6. While(停止準則為最大迭代次數(shù))

7. 更新個體最優(yōu)；

8. 利用式(1)更新粒子速度；

9. 利用式(5)和式(6)更新粒子的位置；計算新的各粒子適應度值by 5-NN()；

10. 與現(xiàn)有粒子適應度值作比較，更新全局最優(yōu)，記錄最佳適應度值及更新對應粒子位置g；

11. End(直到滿足最大迭代次數(shù))

12. 輸出最佳適應度值即為分類準確率。

算法25-NN算法

1. fori=1 to測試數(shù)據(jù)的樣本數(shù)量

2. forj=1 to訓練數(shù)據(jù)的樣本數(shù)量

3. form=1:popsize

4. 特征選擇方案：A(m)=popul(m,:)

5. IfA(1,dim)==0distij=0

6. else

7.distij=distij+(dataik-datajk)2

8. end if

9. nextm

10. Nextj

11. 對distij進行從小到大排序記錄其對應類別；

12. 取出前k(k=5)個distij及其對應類別；

13. 對k個樣本所屬類別個數(shù)進行統(tǒng)計；

14. 選出出現(xiàn)次數(shù)最多的類別即為第i個測試樣本的類別classi；

15. nexti

16.correct=0；

17. fori=1 to分類問題的樣本數(shù)

18. ifclassi=第i個測試樣本then

19.correct=correct+1；

20. end if

21. nexti

22. 適應度值=corret/測試數(shù)據(jù)樣本數(shù)量。

5 實驗與結果分析

5.1 相關參數(shù)設置與原始數(shù)據(jù)集

BPSO中學習因子c1和c2均取2，種群數(shù)量為20，最大迭代次數(shù)為1 000，KNN算法中k取5。算法主要參數(shù)設置如表1所示。

表1 算法參數(shù)設置

測試數(shù)據(jù)為6種不同類型的數(shù)據(jù)集，從UCI機器學習數(shù)據(jù)庫中下載，數(shù)據(jù)集信息如表2所示。

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

5.2 實驗方案

本文主要從轉換函數(shù)的角度分析BPSO的性能改變，主要針對原始BPSO的S型轉換函數(shù)、文獻[10]所列S型函數(shù)以及所選V型轉換函數(shù)、本文所提轉換函數(shù)對BPSO的性能影響以及對比，對每個數(shù)據(jù)集所采用的不同方案分別運行10次，取10次運行的平均分類準確率來作為算法性能的評價標準。為此本文將進行以下實驗設計：

(1) 采用原始BPSO對6組數(shù)據(jù)進行特征選擇實驗。

(2) 采用文獻[10]所列的其他S型轉換函數(shù)BPSO對6組數(shù)據(jù)進行特征選擇實驗。

(3) 采用文獻[10]所選轉換函數(shù)形成NBPSO以及本文所提出VBPSO對6組數(shù)據(jù)進行特征選擇實驗。

(4) 記錄下數(shù)據(jù)集實驗數(shù)據(jù)進行實驗對比分析。

5.3 實驗結果分析

5.3.1S型轉換函數(shù)實驗結果分析

圖7、圖8為采用不同S型轉換函數(shù)后L值和分類準確率的曲線圖，同樣采用數(shù)據(jù)集Snoar做特征選擇實驗。

圖7 各粒子到全局最優(yōu)粒子間平均距離曲線圖

圖8 不同S型轉換函數(shù)分類準確率變化曲線圖

由圖7可以看出，四條曲線基本上呈現(xiàn)遞增趨勢，說明隨著迭代次數(shù)增加各粒子到全局最優(yōu)粒子間平均距離越來越大，距離全局最優(yōu)粒子越來越遠。反映出分別采用s1-s4四種轉換函數(shù)后算法的全局搜索能力越來越強，缺乏局部搜索能力，算法一直處于隨機全局探索中，沒有啟發(fā)性搜索功能，不收斂于全局最優(yōu)粒子。

由圖8可以看出，四條曲線在迭代中后期基本處于水平狀態(tài)，說明分類準確率在迭代中后期基本不發(fā)生變化。根據(jù)以上分析，采用S型轉換函數(shù)后各粒子一直處于全局搜索狀態(tài)中，全局搜索能力越來越強不會收斂于全局最優(yōu)粒子，反映到分類準確率上就會過早的收斂，過了早期就基本不再變化，S型轉換函數(shù)使算法不能具有啟發(fā)性搜索，不能得到較高的分類準確率。

表3給出了采用不同S型轉換函數(shù)與文獻[10]所提供的V型轉換函數(shù)形成的NBPSO的分類準確率比較?？梢钥闯霾捎肗BPSO后的分類準確率都要比S1BPSO-S4BPSO要高，單從分類準確率上可以看出V型轉換函數(shù)能夠提升BPSO的性能。

表3 采用不同S型轉換函數(shù)分類準確率

5.3.2不同算法的分類準確率比較

表4給出了原始BPSO和根據(jù)文獻[10]所提供的轉換函數(shù)形成的NBPSO和本文所提的VBPSO所做特征選擇實驗的分類準確率，可以看出NBPSO、VBPSO的分類準確率都比原始BPSO的分類準確率要高，說明V字型的轉換函數(shù)以及新的粒子位置更新方式能使原始BPSO的性能得到提高，結果與3.1節(jié)理論分析對應。使用VBPSO的分類準確率高于NBPSO，綜合3.2節(jié)分析說明采用本文所提出的轉換函數(shù)優(yōu)于文獻[10]所選的轉換函數(shù)，更適合算法對V型轉換函數(shù)的要求，VBPSO在應用到特征選擇問題中的性能要優(yōu)于NBPSO和原始BPSO，結果與3.2節(jié)理論分析對應。

表4 不同轉換函數(shù)形成不同算法的分類準確率

5.3.3各數(shù)據(jù)集實驗曲線對比

圖9為6個數(shù)據(jù)集的實驗曲線對比圖，虛線為使用原始BPSO進行特征選擇的準確率變化曲線，實線為使用本文所提VBPSO進行特征選擇的準確率變化曲線?？梢钥闯觯摼€的變化趨勢在剛開始快速遞增，然后在迭代的200代后趨于直線，說明原始BPSO在迭代早期的時候分類準確率就不再變化，對應了2.1節(jié)分析的原始BPSO具有過強的全局搜索能力易早熟收斂且不收斂于全局最優(yōu)粒子。實線的變化趨勢一直呈遞增狀態(tài)且與虛線有交點最后都高于虛線，說明采用本文算法以后的分類準確率沒有出現(xiàn)早熟收斂現(xiàn)象且分類準確率都高于原始BPSO，VBPSO中的粒子最后都逐步靠近且收斂于最優(yōu)粒子，這與第3節(jié)理論分析相符。

圖9 BPSO和AMBPSO在6個數(shù)據(jù)集上的實驗曲線對比圖

6 結 語

本文從轉換函數(shù)的角度對算法進行改進，通過對各粒子到全局最優(yōu)粒子間平均距離變化曲線分析出原始BPSO具有過強的全局搜索能力，不收斂于全局最優(yōu)粒子的缺陷。然后從轉換函數(shù)層面分析，針對原始BPSO的缺陷，提出更合理的V型轉換函數(shù)替換原始BPSO的S型轉換函數(shù)形成VBPSO來增強算法后期的局部搜索能力，提升原始BPSO的性能并應用到特征選擇問題中。實驗結果表明,本文所提出的V字型BPSO(VBPSO)與原始BPSO相比能提高數(shù)據(jù)的分類準確率，明顯提升算法的性能。