二進制粒子群算法中V型轉換函數的應用分析

姜 磊 劉建華 張冬陽 卜冠南

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

0 引 言

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

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

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

1 經典BPSO

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

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

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

c2×rand()×(pgd-xid)

(1)

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

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

(2)

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

(3)

2 BPSO分析

2.1 性能分析

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

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

(4)

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

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

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

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

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

2.2 S型轉換函數分析

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

圖2 原始BPSO轉換函數曲線圖

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

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

3 V型轉換函數

3.1 函數提出

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

圖3 轉換函數曲線圖

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

(5)

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

(6)

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

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

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

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

3.2 函數分析

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

圖5 轉換函數曲線對比圖

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

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

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

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

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

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

算法1VBPSO特征選擇算法

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

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

3. 記錄初始個體最優bestpos=popul；

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

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

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

7. 更新個體最優；

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

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

10. 與現有粒子適應度值作比較，更新全局最優，記錄最佳適應度值及更新對應粒子位置g；

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

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

算法25-NN算法

1. fori=1 to測試數據的樣本數量

2. forj=1 to訓練數據的樣本數量

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個樣本所屬類別個數進行統計；

14. 選出出現次數最多的類別即為第i個測試樣本的類別classi；

15. nexti

16.correct=0；

17. fori=1 to分類問題的樣本數

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

19.correct=correct+1；

20. end if

21. nexti

22. 適應度值=corret/測試數據樣本數量。

5 實驗與結果分析

5.1 相關參數設置與原始數據集

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

表1 算法參數設置

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

表2 數據集信息

5.2 實驗方案

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

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

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

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

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

5.3 實驗結果分析

5.3.1S型轉換函數實驗結果分析

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

圖7 各粒子到全局最優粒子間平均距離曲線圖

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

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

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

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

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

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

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

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

5.3.3各數據集實驗曲線對比

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

圖9 BPSO和AMBPSO在6個數據集上的實驗曲線對比圖

6 結 語

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