徐 明， 龍 文

(1.貴州財(cái)經(jīng)大學(xué)， 貴州省大數(shù)據(jù)統(tǒng)計(jì)分析重點(diǎn)實(shí)驗(yàn)室， 貴陽(yáng) 550025； 2.貴州財(cái)經(jīng)大學(xué)數(shù)統(tǒng)學(xué)院， 貴陽(yáng) 550025； 3.貴州財(cái)經(jīng)大學(xué)， 貴州省經(jīng)濟(jì)系統(tǒng)仿真重點(diǎn)實(shí)驗(yàn)室， 貴陽(yáng) 550025)

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

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

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

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

1 灰狼優(yōu)化算法

GWO是一種模擬自然界中灰狼群攻擊獵物行為和分等級(jí)制度的元啟發(fā)式算法[17]。在GWO中，群體中最優(yōu)個(gè)體稱為α，第2最優(yōu)個(gè)體稱為β，第3最優(yōu)個(gè)體稱為δ，其他個(gè)體稱為ω?；依侨旱纳鐣?huì)等級(jí)制度如圖1所示。

圖1 灰狼群體的等級(jí)特性

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

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為迭代次數(shù)；I為元素均為1的常向量，其維數(shù)與X一致；A和C為系數(shù)向量；r1和r2為隨機(jī)數(shù)；a為過(guò)渡參數(shù)，其計(jì)算公式為

(4)

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

在GWO中，灰狼群攻擊獵物的數(shù)學(xué)表達(dá)式為

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δ的計(jì)算類似于A；Cα、Cβ和Cδ的計(jì)算類似于C。

GWO的偽代碼如下。

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

2 多策略融合灰狼優(yōu)化算法

與其他元啟發(fā)式算法相比，GWO在探索解空間未知區(qū)域具有較高的效率，但其在解決復(fù)雜高維優(yōu)化問(wèn)題時(shí)仍存在解質(zhì)量低、后期收斂速度慢、探索和開(kāi)發(fā)能力不平衡、容易陷入局部最優(yōu)等缺點(diǎn)[23]。提出一種新的改進(jìn)GWO算法，通過(guò)嵌入3種新的策略，即基于正弦函數(shù)的非線性過(guò)渡參數(shù)、基于個(gè)體歷史最佳指導(dǎo)的位置更新方程和小孔成像學(xué)習(xí)策略。

2.1 基于正弦函數(shù)的非線性過(guò)渡參數(shù)

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

由于GWO算法全局勘探和局部開(kāi)發(fā)過(guò)程是非線性變化和高度復(fù)雜，過(guò)渡參數(shù)a線性變化策略無(wú)法真正反映實(shí)際的優(yōu)化搜索過(guò)程，從而不能實(shí)現(xiàn)從全局勘探到局部開(kāi)采的良好過(guò)渡[23,29]。文獻(xiàn)[23]指出，GWO在搜索過(guò)程中具有局部開(kāi)采能力強(qiáng)而全局勘探能力弱的特點(diǎn)。因此，與局部開(kāi)采過(guò)程相比，所提算法的目標(biāo)是在全局勘探階段花費(fèi)更多的時(shí)間，提出一種新的非線性過(guò)渡參數(shù)a策略，可表示為

(9)

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

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

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

2.2 基于記憶指導(dǎo)的位置更新方程

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

受PSO啟發(fā)，結(jié)合當(dāng)前個(gè)體歷史最優(yōu)位置、當(dāng)前群體全局最優(yōu)α狼、β狼、δ狼和當(dāng)前灰狼個(gè)體的位置信息，所提出修改的位置更新方程可表示為

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表示當(dāng)前個(gè)體的歷史最佳位置，其他符號(hào)與基本GWO算法定義的符號(hào)相同。

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

2.3 小孔成像學(xué)習(xí)策略

在算法迭代尋優(yōu)過(guò)程中，由于群體中所有個(gè)體均向全局最優(yōu)區(qū)域逼近，在進(jìn)化搜索后期導(dǎo)致種群多樣性損失，從而出現(xiàn)迭代停滯現(xiàn)象，陷入局部最優(yōu)，這是基于種群迭代的元啟發(fā)式優(yōu)化算法的固有缺陷。GWO作為一種元啟發(fā)式優(yōu)化方法，自然也不例外。為了克服這些缺陷，研究學(xué)者提出了一些策略來(lái)增加群體多樣性，常用的有：變異策略、Lévy飛行算子、反向?qū)W習(xí)策略等。

小孔成像是一種常見(jiàn)的物理光學(xué)現(xiàn)象，它是指光源通過(guò)小孔從板的一側(cè)傾斜到另一側(cè)，在屏幕上形成其倒立的像。受反向?qū)W習(xí)策略啟發(fā)，提出一種基于小孔成像原理的反向?qū)W習(xí)策略。圖3給出了一維搜索空間上作用于當(dāng)前最優(yōu)個(gè)體的小孔成像學(xué)習(xí)策略示意圖。

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

根據(jù)小孔成像原理和圖3，可以得

(13)

令h/h′=k，通過(guò)變換可得像點(diǎn)P′在x軸上的投影為

(14)

顯然，當(dāng)k=1時(shí)，式(14)可化簡(jiǎn)為

X′1=l+u-X1

(15)

式(15)是一般反向?qū)W習(xí)策略公式，也就是說(shuō)，一般反向?qū)W習(xí)策略是小孔成像學(xué)習(xí)策略的一個(gè)特例。

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

(16)

式(16)中：Xj為當(dāng)前最優(yōu)解在第j個(gè)方向的投影；X′j為成像學(xué)習(xí)所得解的對(duì)應(yīng)投影；uj和lj分別為搜索空間在第j個(gè)方向的上下限，j=1,2,…,D。

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

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

3 實(shí)驗(yàn)結(jié)果及比較

為了驗(yàn)證多策略融合灰狼優(yōu)化(grey wolf optimizer algorithm integrated with multiple-strategies，MSGWO) 算法的有效性，選取6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)和10個(gè)UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，并與其他算法進(jìn)行比較。所有算法均采用MATLAB R2014a軟件實(shí)現(xiàn)，仿真實(shí)驗(yàn)環(huán)境為Intel(R) Core (TM) i5-5200U CPU 2.20 GHz 內(nèi)存4 GB Windows 8.1 (64位) 操作系統(tǒng)。

3.1 MSGWO算法性能測(cè)試

從文獻(xiàn)[23]中選取6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)測(cè)試MSGWO 算法的性能，6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)如表1所示。

表1中，f1～f3為單峰函數(shù)，f4～f6為多峰函數(shù)，單峰函數(shù)用來(lái)測(cè)試算法的局部搜索能力，而多峰函數(shù)則用于測(cè)試算法的全局搜索能力。每個(gè)函數(shù)的維數(shù)設(shè)置為30。

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

利用MSGWO對(duì)6個(gè)函數(shù)進(jìn)行求解，并與基本GWO[17]、mGWO(modified GWO)[27]和inspired GWO (IGWO)[29]算法比較。為了進(jìn)行公平的比較，4種算法采用相同的參數(shù)設(shè)置，即種群規(guī)模均設(shè)置為30、最大迭代次數(shù)設(shè)置為500。為了減少計(jì)算誤差，每種算法均獨(dú)立運(yùn)行30次實(shí)驗(yàn)。表2給出了4種算法對(duì)6個(gè)函數(shù)的平均值和標(biāo)準(zhǔn)差。

從表2結(jié)果可知，MSGWO在6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)上30次實(shí)驗(yàn)均能一致地獲得理論最優(yōu)解0，且標(biāo)準(zhǔn)差也為0，這充分說(shuō)明MSGWO具有較強(qiáng)的全局尋優(yōu)能力，且魯棒性也較強(qiáng)。與GWO、mGWO和IGWO算法相比，MSGWO獲得較好的平均值和標(biāo)準(zhǔn)差值。另外，根據(jù)Friedman’s排名檢驗(yàn)，MSGWO 排名第1，排名第2～4的依次是IGWO、mGWO和GWO。

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

3.2 基于MSGWO的特征選擇方法

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

表3 實(shí)驗(yàn)中使用的UCI數(shù)據(jù)集

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

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

表5 4種算法的所選特征個(gè)數(shù)比較

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

4 結(jié)論

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