基于多策略融合灰狼優化算法的特征選擇方法

徐 明， 龍 文

(1.貴州財經大學， 貴州省大數據統計分析重點實驗室， 貴陽 550025； 2.貴州財經大學數統學院， 貴陽 550025； 3.貴州財經大學， 貴州省經濟系統仿真重點實驗室， 貴陽 550025)

特征選擇也稱為特征子集選擇或屬性選擇，它是機器學習中分類、回歸和數據挖掘中至關重要的預處理步驟。特征選擇的目的是利用一種選擇方法，刪除數據集中冗余和不相關的特征，找到最優特征子集。它不僅能降低數據維度、提高機器學習算法的效率，還能從原始數據集中選出對分類器分類性能最有用的特征，提高其分類精度[1-3]。假設數據集中有a個特征，則特征選擇問題的可能解決方案的總數是a，其搜索空間十分龐大。因此，特征選擇問題是一個NP-hard問題[4]。利用窮舉搜索法選擇一組最優特征子集將會耗費大量計算和時間成本，不適合用于求解特征選擇問題。

啟發式搜索算法是一類基于群體迭代搜索的方法，具有模型簡單、容易編程實現、需調整的參數少和強大的尋優能力等特點，較適合于解決特征選擇問題。近年來，基于啟發式搜索算法的特征選擇方法已被廣泛提出且獲得了滿意的結果，如遺傳算法(genetic algorithm, GA)[5]、蟻群優化算法(ant colony optimization, ACO)[6]、粒子群優化算法(particle swarm optimization, PSO)[7-8]、人工蜂群(artificial bee colony, ABC)算法[9]、頭腦風暴優化(brain storm optimization, BSO)算法[10]、鯨魚優化算法(whale optimization algorithm, WOA)[11]、引力搜索算法(gravitational search algorithm, GSA)[12]、蟻獅優化算法(ant lion optimizer, ALO)[13]、蝗蟲優化算法(grasshopper optim-ization algorithm, GOA)[1,14]、蝴蝶優化算法(butterfly optimization algorithm, BOA)[15]、教與學優化算法(teaching-learning-based optimization, TLBO)[16]等。

灰狼優化算法(grey wolf optimizer, GWO)是澳大利亞學者Mirjalili等[17]于2014年提出的一種元啟發式算法，它模擬自然界中灰狼群體的社會等級制度和捕食行為。研究表明，GWO算法在函數優化方面優于其他啟發式算法如GA、PSO、GSA和差分進化(differential evolution, DE)算法[17]。GWO具有原理簡單、參數設置少和較強的全局優化能力等特點，已被成功應用于解決實際應用問題如電力系統[18]、無人機目標跟蹤[19]、疾病診斷[20]、故障檢測[21]、圖像降噪[22]等。盡管GWO在許多領域得到了成功的應用，但其也存在解精度低、后期收斂速度慢、容易陷入局部最優等缺點[23]。因此，大量改進的GWO算法被提出用來改善基本GWO的性能。Long等[23]通過引入非線性控制參數a和修改的位置更新方程，提出了一種勘探能力增強的GWO算法(EEGWO)用于高維優化問題。EEGWO在高維經典測試函數上獲得了較好的結果，但在CEC2014測試集上性能降低。黃晨晨等[24]提出一種混合蛙跳灰狼優化算法(SFL-GWO)求解高維復雜函數。SFL-GWO使用三種策略即Logistic映射初始化、非線性距離控制參數和引入SFL算法改進位置方程，但其僅考慮經典測試問題。為了增強算法的全局搜索能力，Gupta等[25]提出了一種基于隨機行走機制的改進GWO算法(RW-GWO)，但其只限于考慮低維函數情況。Tu等[26]提出了一種多策略集成的GWO算法(MEGWO)，利用經典測試函數和CEC2014測試集對其性能進行驗證，結果表明，MEGWO獲得了較好的性能，但其只針對低維函數進行實驗。Mittal等[27]提出了一種基于非線性控制參數α策略的GWO算法求解全局和工程優化問題。

盡管已有的改進GWO算法通過使用一些有效修改策略或引入新的算子來提高性能[28]，但在面對復雜問題時也仍存在全局勘探和局部開發不平衡、后期收斂速度慢和易于早熟等不足。首先對此提出3種改進策略。策略1：利用基于三角函數的非線性過渡參數替代線性遞減參數，前期注重全局勘探而后期更注重局部開發，以期平衡算法的全局勘探和局部開發的能力；策略2：在迭代過程中，結合灰狼個體自身歷史最佳位置和決策層個體(α、β和δ)位置引導群體中其他灰狼個體位置更新，逐漸逼近最優解區域以加快算法收斂；策略3：為了幫助群體跳出局部最優，在當前群體最優個體(α狼)上執行基于小孔成像學習的策略以產生有潛力的候選個體。接著，為了檢驗改進算法的有效性，從文獻[23]中選取6個標準測試函數進行函數值尋優的仿真實驗，并與基本GWO和其他改進GWO算法進行比較；然后，將改進算法用于解決特征選擇問題，從UCI選取10個數據集進行尋找最優特征子集的仿真實驗，并與基本GWO和其他改進GWO算法進行比較。最后，將對所提改進算法的有效性和進一步研究進行討論。

1 灰狼優化算法

GWO是一種模擬自然界中灰狼群攻擊獵物行為和分等級制度的元啟發式算法[17]。在GWO中，群體中最優個體稱為α，第2最優個體稱為β，第3最優個體稱為δ，其他個體稱為ω。灰狼群的社會等級制度如圖1所示。

圖1 灰狼群體的等級特性

引灰狼群的狩獵行為由跟蹤靠近獵物、包圍獵物和攻擊獵物3個步驟完成。包圍獵物的表達式為

X(t+1)=Xp(t)-A(t)|C(t)Xp(t)-X(t)|

(1)

A(t)=2a(t)r1-a(t)I

(2)

C(t)=2r2I

(3)

式中：X和Xp分別為灰狼和獵物的位置向量；t為迭代次數；I為元素均為1的常向量，其維數與X一致；A和C為系數向量；r1和r2為隨機數；a為過渡參數，其計算公式為

(4)

式(4)中：T為最大迭代次數。

在GWO中，灰狼群攻擊獵物的數學表達式為

Y1=Xα(t)-Aα(t)|Cα(t)Xα(t)-X(t)|

(5)

Y2=Xβ(t)-Aβ(t)|Cβ(t)Xβ(t)-X(t)|

(6)

Y3=Xδ(t)-Aδ(t)|Cδ(t)Xδ(t)-X(t)|

(7)

X(t+1)=(Y1+Y2+Y3)/3

(8)

式中：Xα、Xβ和Xδ分別為α、β和δ狼的位置向量；Aα、Aβ和Aδ的計算類似于A；Cα、Cβ和Cδ的計算類似于C。

GWO的偽代碼如下。

算法1:GWO偽代碼1: 初始化參數A和G2: 隨機初始化N個灰狼位置3: 計算N個灰狼的適應度4: 定義Xα、Xβ和Xδ5: 令t=06: while t

2 多策略融合灰狼優化算法

與其他元啟發式算法相比，GWO在探索解空間未知區域具有較高的效率，但其在解決復雜高維優化問題時仍存在解質量低、后期收斂速度慢、探索和開發能力不平衡、容易陷入局部最優等缺點[23]。提出一種新的改進GWO算法，通過嵌入3種新的策略，即基于正弦函數的非線性過渡參數、基于個體歷史最佳指導的位置更新方程和小孔成像學習策略。

2.1 基于正弦函數的非線性過渡參數

對于元啟發式算法來說，它的搜索能力取決于在尋優過程中如何平衡算法的收斂速度和多樣性。在GWO中，過渡參數a在協調多樣性和收斂性之間起關鍵作用。較大的a值(a>1)有利于全局勘探能力，而較小的a值(a<1)則強調局部開采。適當選擇此參數對于平衡全局勘探和局部開采至關重要。在基本GWO算法中，由式(4)可知，過渡參數a的值隨迭代次數的增加線性遞減，而許多優化問題要求算法的全局勘探和局部開發搜索過程非線性變化以擺脫局部最優解。因此，改進GWO算法性能的一個活躍領域是如何設置過渡參數a的值。目前，已有幾種非線性過渡參數a策略[23, 27, 29]被提出。

由于GWO算法全局勘探和局部開發過程是非線性變化和高度復雜，過渡參數a線性變化策略無法真正反映實際的優化搜索過程，從而不能實現從全局勘探到局部開采的良好過渡[23,29]。文獻[23]指出，GWO在搜索過程中具有局部開采能力強而全局勘探能力弱的特點。因此，與局部開采過程相比，所提算法的目標是在全局勘探階段花費更多的時間，提出一種新的非線性過渡參數a策略，可表示為

(9)

式(9)中：astart和aend分別為過渡參數a的初始值和終止值。

圖2給出了過渡參數a線性遞減策略與所提出的非線性遞減策略的曲線比較。

從圖2可以清晰地看出，與原線性遞減策略相比，該非線性過渡參數在更多的迭代中比較著重于全局勘探。最初，所提出的非線性過渡參數的值較高，這表明與局部開發相比，它有助于長時間(約為最大迭代次數的67%)進行全局勘探。該圖還顯示，在搜索過程中，所提出的過渡參數策略僅在約33%的迭代中有利于局部開采。

2.2 基于記憶指導的位置更新方程

在GWO中使用非線性過渡參數后可知，由于使用非線性過渡參數時，當前最優候選解周圍的開采水平下降，最終迭代中獲得的解的準確性可能會受到損害。在基本GWO算法中，由式(5)～式(8)可知，群體中其他灰狼個體的位置更新僅受全局最優灰狼個體(α狼)、β狼、δ狼和當前灰狼個體的位置指導，從而導致個體之間缺乏多樣性以及從當前最優灰狼個體的過渡學習，GWO容易陷入局部最優。另外，個體歷史最佳位置信息在迭代搜索過程中有著不可替代的作用。然而，在基本GWO算法中尚未系統地利用灰狼個體歷史最佳位置信息，這說明它是一種缺乏記憶性的隨機優化技術。

受PSO啟發，結合當前個體歷史最優位置、當前群體全局最優α狼、β狼、δ狼和當前灰狼個體的位置信息，所提出修改的位置更新方程可表示為

Y1=Xpbest(t)-Aα(t)|Cα(t)Xα(t)-X(t)|

(10)

Y2=Xpbest(t)-Aβ(t)|Cβ(t)Xβ(t)-X(t)|

(11)

Y3=Xpbest(t)-Aδ(t)|Cδ(t)Xδ(t)-X(t)|

(12)

式中：Xpbest表示當前個體的歷史最佳位置，其他符號與基本GWO算法定義的符號相同。

與式(5)～式(7)相比，式(10)～式(12)的右邊第一部分改成當前灰狼個體歷史最佳位置Xpbest(t)。由個體歷史最佳位置和當前群體最優位置共同引導，在增加群體多樣性的同時也能加快算法的收斂。

2.3 小孔成像學習策略

在算法迭代尋優過程中，由于群體中所有個體均向全局最優區域逼近，在進化搜索后期導致種群多樣性損失，從而出現迭代停滯現象，陷入局部最優，這是基于種群迭代的元啟發式優化算法的固有缺陷。GWO作為一種元啟發式優化方法，自然也不例外。為了克服這些缺陷，研究學者提出了一些策略來增加群體多樣性，常用的有：變異策略、Lévy飛行算子、反向學習策略等。

小孔成像是一種常見的物理光學現象，它是指光源通過小孔從板的一側傾斜到另一側，在屏幕上形成其倒立的像。受反向學習策略啟發，提出一種基于小孔成像原理的反向學習策略。圖3給出了一維搜索空間上作用于當前最優個體的小孔成像學習策略示意圖。

圖3中，假設高度為h的光源P在x軸上的投影為X1(P為當前最優解)，P′為光源P的倒立像且高度為h′，P′為P的小孔成像學習點，X1為P′在x軸上的投影，O為基點，u和l分別為搜索空間在x軸方向的上下限。

根據小孔成像原理和圖3，可以得

(13)

令h/h′=k，通過變換可得像點P′在x軸上的投影為

(14)

顯然，當k=1時，式(14)可化簡為

X′1=l+u-X1

(15)

式(15)是一般反向學習策略公式，也就是說，一般反向學習策略是小孔成像學習策略的一個特例。

一般地，式(14)可擴展到D維空間，可表示為

(16)

式(16)中：Xj為當前最優解在第j個方向的投影；X′j為成像學習所得解的對應投影；uj和lj分別為搜索空間在第j個方向的上下限，j=1,2,…,D。

綜上所述，多策略融合GWO算法的流程圖如圖4所示。

圖4 多策略融合GWO算法流程圖

3 實驗結果及比較

為了驗證多策略融合灰狼優化(grey wolf optimizer algorithm integrated with multiple-strategies，MSGWO) 算法的有效性，選取6個標準測試函數和10個UCI數據集進行實驗，并與其他算法進行比較。所有算法均采用MATLAB R2014a軟件實現，仿真實驗環境為Intel(R) Core (TM) i5-5200U CPU 2.20 GHz 內存4 GB Windows 8.1 (64位) 操作系統。

3.1 MSGWO算法性能測試

從文獻[23]中選取6個標準測試函數測試MSGWO 算法的性能，6個標準測試函數如表1所示。

表1中，f1～f3為單峰函數，f4～f6為多峰函數，單峰函數用來測試算法的局部搜索能力，而多峰函數則用于測試算法的全局搜索能力。每個函數的維數設置為30。

表1 標準測試函數

利用MSGWO對6個函數進行求解，并與基本GWO[17]、mGWO(modified GWO)[27]和inspired GWO (IGWO)[29]算法比較。為了進行公平的比較，4種算法采用相同的參數設置，即種群規模均設置為30、最大迭代次數設置為500。為了減少計算誤差，每種算法均獨立運行30次實驗。表2給出了4種算法對6個函數的平均值和標準差。

從表2結果可知，MSGWO在6個標準測試函數上30次實驗均能一致地獲得理論最優解0，且標準差也為0，這充分說明MSGWO具有較強的全局尋優能力，且魯棒性也較強。與GWO、mGWO和IGWO算法相比，MSGWO獲得較好的平均值和標準差值。另外，根據Friedman’s排名檢驗，MSGWO 排名第1，排名第2～4的依次是IGWO、mGWO和GWO。

圖5給出了GWO、mGWO、IGWO和MSGWO算法對6個測試函數的收斂曲線比較。從圖5可以看出，與其他3種算法相比，MSGWO獲得較高的求解精度和較快的收斂速度。

3.2 基于MSGWO的特征選擇方法

為了驗證所提出的基于MSGWO算法的特征選擇方法的有效性，從UCI(University of California)中選取10個數據集進行測試，10個數據集的相關信息如表3所示。

表3 實驗中使用的UCI數據集

對于所有數據集，采用KNN分類器進行分類(k=5)。利用MSGWO對10個數據集進行特征選擇，并與基本GWO、EGWO(enhanced GWO)[30]和AGWO(augmented GWO)[31]算法進行比較。在MSGWO算法中，種群規模為10，迭代次數為100。為了減少誤差，每種算法獨立運行10次。表4給出了GWO、EGWO、AGWO和MSGWO算法對10個數據集的平均分類精度比較。表5給出了4種算法所選擇的最優特征子集所含特征數。

表4 4種算法的分類精度比較

表5 4種算法的所選特征個數比較

由表4可知，所提出的MSGWO算法在10個數據集上獲得的平均分類精度明顯優于基本GWO、EGWO和AGWO算法。另外，由表5中結果可以看出，與GWO和AGWO算法相比，MSGWO在10個數據集上均能找到最優的特征子集；與EGWO算法相比，除了Breastcancer數據集，MSGWO在其他數據集上獲得的特征子集更優。

4 結論

針對基本GWO算法存在的缺點，從3個方面進行改進，即設計基于正弦函數的非線性過渡參數策略、基于灰狼個體歷史最佳位置引導的位置更新方程和基于小孔成像原理的學習策略。6個標準測試函數的實驗結果表明，所提出的MSGWO算法無論在求解精度還是收斂速度指標上均要優于基本GWO、mGWO和IGWO算法。最后，提出一種基于MSGWO的特征選擇方法，10個UCI數據集的實驗結果表明，MSGWO算法能有效地進行特征選擇，提高分類器性能。如何改進MSGWO算法的性能，使其在更高維的特征選擇問題上具有較好的性能，以及將MSGWO算法用到其他工程問題上是下一步研究的內容。