融合蝠鲼旋風式覓食策略的灰狼特征選擇算法

楊舒云,劉宏志,李海生

(北京工商大學計算機學院,北京 100048)

1 引言

隨著大數據時代的到來,越來越多高維數據集應用于數據挖掘中,并伴隨著復雜噪聲,給機器學習帶來嚴峻的維度災難問題。特征選擇是從原始特征中選擇出最有效特征,以降低數據集維度,提高模型性能的過程,因此近年來逐漸成為一個研究熱點。

一般來說,特征選擇的算法分為三類:嵌入式(embedded)、過濾式(filter)和封裝式(wrapper)。在封裝式方法中,使用學習算法來評估所選的特征子集,窮舉法、順序搜索、全局搜索等方法都可以用來搜索特征子集。但是在大部分情況下,窮舉法因計算量太大而無法應用,順序搜索法采用局部搜索可能導致局部最優,而全局搜索法主要采用隨機搜索策略來探索解空間,因此有更大可能搜索到全局最優解。近年來,很多元啟發式方法,如鯨魚優化算法[1]、粒子群優化算法[2]等,由于其在全局搜索空間中強大的搜索能力,已經在函數優化[3]、參數優化[4]等領域顯示出其有效性。其中,灰狼優化算法由于其較強的魯棒性和參數少等優點,已經被證明了在特征選擇領域的有效性,然而傳統灰狼算法也存在易早熟等問題,從而導致次優解。

為了提高算法分類精度,一些學者開始對基本灰狼算法進行改進。Al-Tashi Q等人[5]提出了一種灰狼算法與粒子群算法結合的二進制版本進行特征選擇,經對比實驗表明取得了較高的性能。Attia等人[6]將灰狼優化與粗糙集理論結合,在維度各異的公開數據集上取得了較好的收斂速度和分類精度。Hu,Jiao等人[7]開發了一種通過協方差矩陣自適應進化策略、征稅飛行機制和正交學習策略增強的 GWO 變體,增強算法的探索性能,在UCI數據集上都獲得了優越的性能。徐明等[8]提出了基于正弦函數的非線性過渡參數、小孔成像學習等多種策略來提高尋優精度,在基準數據集上驗證了其有效性。

上述研究從不同角度提高了灰狼算法的尋優性能,但勘探與開采能力的不平衡問題仍然存在,算法求解精度仍有待提高,如Hu,Jiao的GWO變體帶來了更有效的勘探傾向,但是并未對算法的開采性能進行改進,徐明的非線性參數過渡等多種位置更新策略在一定程度上實現了全局勘探到局部開采的良好過渡,但忽略了種群初始化階段的多樣性。因此繼續對其改進很有必要,本文提出一種融合蝠鲼旋風式螺旋覓食策略的混合灰狼算法(BWSGWO)用于特征選擇,以達到更高的收斂精度。

2 基本GWO算法

灰狼優化算法(Grey Wolf Optimizer,GWO)模擬狼群嚴格的社會等級制度和狩獵行為[9],狼群中適應度最好的三匹灰狼依次記為α、β、δ,剩下的灰狼記為ω。其狩獵過程包括包圍獵物和攻擊獵物,重復以上步驟,直到達到終止條件,則停止迭代,獲得最優解。

3 改進GWO算法

3.1 Tent混沌策略初始化種群

灰狼算法受種群初始狀態的影響較大,低質量的初始種群在很大程度上影響了算法的收斂速度,導致算法的尋優效果較差?；綠WO算法采用隨機方法初始化種群,沒有任何先驗知識,可能會導致種群分布不均勻,一些ω狼的位置距離最優值過遠,從而容易陷入局部最優解。

混沌系統有隨機性和遍歷性等特點,通過其產生的灰狼群體具備較好的多樣性。其基本思想是通過映射關系產生[0,1]之間的混沌序列,再將其逆映射到灰狼個體的搜索空間。常見的混沌映射有Logistic映射和Tent映射等,單梁等[10]證明 Tent 映射比 Logistic 映射的分布更均勻,因此,本文采取Tent混沌映射的方法初始化種群,有效避免基本GWO算法中隨機函數初始化種群造成的局部最優風險,其數學表達式如下

(1)

式中,μ為混沌參數,不同μ值Tent映射的范圍不同。μ取0.5時,系統呈現短周期狀態,故不可取,本文經多次實驗及文獻分析,取最優μ值為為0.7,由圖1(a)(b)可以看出,當迭代一定次數時,混沌參數為0.7的混沌系統會產生更加均勻的混沌序列。

圖1 Tent混沌映射變化曲線

3.2 蝠鲼旋風式螺旋覓食策略

蝠鲼覓食優化(MRFO)[11]是 2020年提出的新型智能仿生群體算法。由于傳統灰狼算法在位置更新時總是跟隨三匹領導狼,導致局部開采能力強、全局勘探能力弱,針對這個問題,本文受MRFO啟發,通過蝠鲼覓食會排成螺旋形捕捉高濃度浮游生物,引入新型旋風式螺旋覓食策略進行群體協作,其數學模型如下

(2)

式中,β為權重系數,r為[0,1]中的隨機數,當t/T

圖2 二維空間中的旋風覓食行為

如圖所示,灰狼個體不僅跟隨它前面的個體,而且只沿著螺旋形路徑向獵物移動,形成長長的覓食鏈,從而大幅提高搜索效果。

本文結合灰狼算法自身優勢,根據迭代次數的不同在旋風式螺旋覓食與傳統覓食之間轉換,以實現廣泛的適應性搜索。對于傳統覓食行為,結合個體對歷史最優解的記憶進行改進,為每一匹狼建立歷史倉庫,解決了傳統灰狼算法只盲目跟隨領導狼,忽略個體與自身經驗交流的問題,其位置更新方程定義為

(3)

(4)

式中,w為慣性權重,X1、X2、X3、X4分別為灰狼個體向著α、β、δ及自身歷史最優解前進的步長和方向,A和C為系數向量。

3.3 自適應精英反向學習策略

(5)

式中,k可以取不同的實數,當k=1時稱其為廣義反向學習,lbj和ubj分別為第j維搜索空間的邊界。雖然反向學習有大于一般的概率優更逼近最優解,但是并不能保證一定優于原解,因此,在反向學習后采用貪心策略選擇其中的更優解進入下一次的迭代,其數學模型如下

(6)

同時,為適應種群復雜的非線性變化,加入變異因子Mp進行選擇性反向學習,即隨著迭代次數的增加,變異概率非線性遞減,前期變異概率大,更有利于全局勘探,后期變異概率小,有利于局部開采迅速收斂,其數學模型如下:

(7)

式中,Mpmax為最大變異概率,Mpmin為最小變異概率。

4 BWSGWO特征選擇算法組成

4.1 二進制離散編碼

特征選擇問題本質上是要找到一個合適的0/1串,0表示特征不被選擇,1表示特征被選擇,如圖3所示為一個包含十個特征數據集的可能解決方案。

圖3 解決方案表示

基本GWO算法在提出之初主要是為了解決解決連續優化問題,為了能讓其解決離散空間問題,引入二進制思想來重新設計算法,使用轉換函數來實現連續搜索空間到二進制空間的轉換。但是代表性的S型轉換函數sigmoid變化敏感,易于飽和,影響特征選擇的精度,而tanh[13]函數克服了這一缺點。綜上,本文采用V型函數tanh進行二進制轉換,其數學模型如下

xsi=|tanh(x)|

(8)

(9)

4.2 適應度函數設計

特征選擇問題被認為是一個多目標問題,因為它必須實現以下兩點:最大化給定分類器的分類精度,最大限度地減少所選特征的數量?；谏鲜?本文將用于評估解決方案的適應度函數設計為實現兩個目標之間的平衡,即

(10)

式中,error表示分類錯誤率,用KNN采用十折交叉驗證法計算,F代表所選特征子集長度,dim代表原始數據集中所有特征,α和β是對應于分類精度和所選特征子集長度的權重參數,α∈[0,1]且β=1-α,本文算法意在保證較高精度的前提下減少特征數目,因此將α和β分別設置為 0.99 與 0.01[13]。

4.3 算法流程

綜上所述,本文提出了融合蝠鲼旋風式覓食策略的灰狼特征選擇算法,其執行步驟如下:

Step1:設置相關參數,種群規模N,最大迭代次數Tmax,搜索維度為d,搜索范圍[lb,ub];

Step2:根據3.1節描述的Tent混沌策略初始化灰狼種群,并計算其適應度值,保存適應度最好的前三匹狼記為α、β、δ;

Step3:據3.2節描述的策略,由當前迭代次數與總迭代次數的比值,當t≤ 0.7T時,采用蝠鲼旋風式螺旋覓食策略進行灰狼位置更新,當t> 0.7T時,將灰狼等級捕獵制度與個體最優解記憶策略結合,進行圍捕中的位置更新,以實現勘探到開采的良好過渡;

Step4:采用自適應精英反向學習策略,以一定的概率對當前最優解求其反向解,并進行兩兩評估,貪婪地選擇較優解作為下一代個體精英個體;

Step5:重復上述步驟,若達到終止條件,則停止迭代,并輸出結果。

5 仿真分析

5.1 仿真參數介紹

本文的仿真中,為保證仿真結果的公平性,各算法基本參數的選擇相同,種群規模 N 為 10,最大迭代次數 Tmax為 100,取自參考文獻中的經驗值[14],其它對比算法的參數設置也與相應的參考文獻保持一致。由于元啟發式算法的特征選擇具有一定的隨機性,為避免偶然誤差對實驗結果產生影響,所有算法獨立運行10次取平均值。

5.2 實驗數據集介紹

本文從機器學習資料庫UCI中收集的8個規模各異、特征數目不同的標準測試數據集進行特征選擇,來驗證所提算法的有效性。數據集的詳細信息如表1所示。

表1 數據集信息

5.3 實驗結果分析

為驗證本文所提策略的有效性,本文將所提算法與經典離散粒子群算法、灰狼優化算法、鯨魚優化算法作為對比,在表1的數據集上進行進行10次獨立重復實驗,比較算法的平均性能指標。

5.3.1 分類精度與所選特征數對比

表2從運行結果的平均分類精度及平均所選特征數對算法進行了對比。其中,加粗字體為所有算法中的最高平均分類精度和最小平均特征數。分析BWSGWO的實驗結果可知,在所有的數據集中,BWSGWO都展示出了最高的分類精確。同時,在大部分數據集中,BWSGWO都展示出了較低的特征數,除了在ionosphere、Sonar、WaveformEW數據集中,本文所提算法雖然在特征選擇數目上不是最佳,但與最優特征數差距不大,同時精度得到了非常顯著的提升。

表2 測試數據集準確率對比

5.3.2 適應度對比

表3為四種算法的適應度函數值對比,其中Avg＿fit、Best＿fit分別為算法在不同數據集上的平均適應度和最佳適應度。由表4可知,除WaveformEW、Lymphography、Exactly數據集外都取得了最優的最佳適應度,盡管在在WaveformEW、Lymphography、Exactly數據集中表現不是最優,但是其上限接近最佳。此外,本文所提算法在8個數據集上都取得了最優的平均適應度,這在一定程度上表明了所提算法的穩定性。

表3 測試數據集適應度對比

5.3.3 收斂性分析

圖4所示為8個數據集上BPSO、BGWO、BWOA、BWSGWO的適應度曲線對比結果。從圖4中的收斂趨勢可以看出,隨著算法迭代次數的增加,各個算法在不同數據集上的適應度值均在降低,但相較于BPSO、BGWO、BWOA,本文提出的BWSGWO算法在總迭代次數相同的情況下,總能搜索到更優的解。圖4(c)(e)分別為四種算法在Sonar和HeartEW數據集上的實驗結果,表明BWSGWO算法在上述兩個數據集上的收斂速度均大幅優于其它算法且搜索到的解都優于其它算法。圖4(f)為四種算法在Lymphography數據集上的實驗結果,表明BWSGWO算法在1次迭代后就搜索到了比其它算法更優的解,且前8次的迭代中收斂速度都優于其它算法,雖然在8-33次的迭代中暫時陷入局部最優,但是依然始終優于其它算法,且33次迭代之后迅速收斂得到全局最優解。圖4(a)(d)(h)分別為四種算法在KrVsKpEW、WaveformEW、Exactly數據集上的實驗結果,雖然在前期的迭代中表現并不是最優,但中后期快速收斂,搜索到的解均遠由于其它算法。

圖4 改進算法在8個數據集上的適應度曲線

綜上可知,本文所提BWSGWO算法總能搜索到比其它算法都更優的解,體現出 BWSGWO算法具有更好的尋優性能。

因此,綜合分類準確率、特征選擇數量、魯棒性、搜索性能和收斂性能方面對比四種算法,本文所提BWSGWO特征選擇算法的總體性能優于其它四種算法。

5.4 時間復雜度分析

雖然特征選擇算法需要取得較高的準確率,但是也需要較低的時間復雜度。在種群規模為N,優化維度為D,最大迭代次數為Tmax的情況下,基本GWO時間復雜度主要為種群初始化部分和灰狼位置更新部分,其時間復雜度為O(NDTmax)。

同理,改進灰狼的基本流程與基本GWO一樣,此外,引入混沌策略O(ND),蝠鲼旋風式螺旋覓食策略與粒子群策略的新型捕獵行為O(NDTmax),自適應精英反向學習策略O(DTmax),因此總的時間復雜度與基本GWO算法相比沒有增加,依然為O(NDTmax),都取決于種群規模、優化問題維度與最大迭代次數,因此可判定改進算法并未造成時間復雜度的增加,但是其性能卻得到了顯著的提升,證明了本文所提算法的有效性。

6 結束語

本文針對傳統灰狼算法易陷入局部最優、尋優性能差的問題,提出了融合蝠鲼旋風式覓食策略的灰狼特征選擇算法。創新性地引入蝠鲼旋風式螺旋覓食策略及時調整灰狼最佳位置,并為種群建立歷史倉庫,有效降低了傳統灰狼算法中只跟隨領導狼群進行捕獵的盲目性,大幅協調了灰狼種群的勘探和開采性能。此外,引入Tent混沌映射提高種群多樣性,自適應精英反向學習策略提升抗局部極值能力。相較于其它經典元啟法式算法,具有尋優策略良,算法不易早熟等優勢。在8個規模各異、特征數目不同的UCI標準數據集上進行仿真,仿真結果表明,與經典算法BPSO、BGWO、BWOA對比,本文提算法能在最大程度提高分類精度的同時,保證較低的特征選擇數,算法性能大大提升。在后續的研究中,主要考慮尋找更高效的特征表示方式,并進一步拓展該算法的應用領域。