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

楊舒云,劉宏志,李海生

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

1 引言

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

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

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

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

2 基本GWO算法

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

3 改進GWO算法

3.1 Tent混沌策略初始化種群

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

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

(1)

式中,μ為混沌參數(shù),不同μ值Tent映射的范圍不同。μ取0.5時,系統(tǒng)呈現(xiàn)短周期狀態(tài),故不可取,本文經(jīng)多次實驗及文獻分析,取最優(yōu)μ值為為0.7,由圖1(a)(b)可以看出,當?shù)欢ù螖?shù)時,混沌參數(shù)為0.7的混沌系統(tǒng)會產(chǎn)生更加均勻的混沌序列。

圖1 Tent混沌映射變化曲線

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

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

(2)

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

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

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

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

(3)

(4)

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

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

(5)

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

(6)

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

(7)

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

4 BWSGWO特征選擇算法組成

4.1 二進制離散編碼

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

圖3 解決方案表示

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

xsi=|tanh(x)|

(8)

(9)

4.2 適應度函數(shù)設計

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

(10)

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

4.3 算法流程

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

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

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

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

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

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

5 仿真分析

5.1 仿真參數(shù)介紹

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

5.2 實驗數(shù)據(jù)集介紹

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

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

5.3 實驗結果分析

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

5.3.1 分類精度與所選特征數(shù)對比

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

表2 測試數(shù)據(jù)集準確率對比

5.3.2 適應度對比

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

表3 測試數(shù)據(jù)集適應度對比

5.3.3 收斂性分析

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

圖4 改進算法在8個數(shù)據(jù)集上的適應度曲線

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

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

5.4 時間復雜度分析

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

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

6 結束語

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