基于改進蚱蜢優(yōu)化算法的特征選擇機制

李雯婷，韓 迪，葉符明

(1.貴州商學院 計算機與信息工程學院，貴州 貴陽 550014；2.廣東金融學院 信用管理學院，廣東 廣州 510521)

0 引 言

特征選擇是數(shù)據(jù)處理、數(shù)據(jù)挖掘的預先步驟，主要目標是選擇相關性和信息化程度高的特征子集，消除非相關冗余特征，提高分類器學習效率[1]。目前，特征選擇主要有過濾法和封裝法[2]。過濾法主要利用數(shù)據(jù)關聯(lián)的統(tǒng)計手段決定特征關聯(lián)，方法與學習模型無關。例如信息增益、互信息、主成分分析等。此方法的冗余特征過多、選擇精度差。封裝法將機器學習的思想關聯(lián)至特征子集的選擇過程中，能夠降低特征子集的維度。而特征選擇的目標是同步實現(xiàn)數(shù)據(jù)集分類的準確率最高和特征選擇量最小，該問題可視為優(yōu)化問題。

近年來，群智能算法廣泛應用于特征選擇問題。如GWO算法[3]、ALO算法[4]、WOA算法[5]、BA算法[6]、SSA算法[7]均在特征選擇領域得到應用，并取得了不錯的性能表現(xiàn)。蚱蜢(也稱蝗蟲)優(yōu)化算法GOA[8]是近年來提出的一種新型群智能算法，它模擬了蚱蜢在不同成長階段的行為特征，具有較強的全局搜索能力，已廣泛應用在調度優(yōu)化[9]、機器人尋徑[10]、醫(yī)學細胞供應預測[11]等諸多領域。

然而，標準GOA依然存在尋優(yōu)精度差、收斂速度慢的不足。為此，文獻[12]引入正余弦機制協(xié)調算法全局搜索和局部開發(fā)，利用變異使算法能夠跳離局部最優(yōu)。文獻[13]提出結合模擬退火和曲線自適應的蝗蟲優(yōu)化算法，對算法全局尋優(yōu)能力和局部最優(yōu)跳離進行了優(yōu)化。文獻[14]提出融合變異和均勻分布的蝗蟲優(yōu)化算法，以分段思想作位置更新，使算法更好尋優(yōu)。文獻[15]設計對立學習蝗蟲優(yōu)化算法，文獻[16]利用混沌系統(tǒng)均衡全局搜索和局部開發(fā)，都實現(xiàn)了標準GOA算法的性能提升。

鑒于已有工作針對GOA算法在開發(fā)與搜索間的均衡、提升收斂速度及跳離局部最優(yōu)問題上的改進仍有片面性，本文具體工作為：設計一種融合完全隨機性的混沌Tent映射實現(xiàn)種群初始化，豐富種群多樣性和遍歷性；利用學習自動機對調整系數(shù)c更新，均衡全局搜索與局部開發(fā)；引入折射對立學習位置更新機制，避免陷入早熟收斂。將改進GOA算法應用于特征選擇問題，設計新的特征選擇算法LRGOAFS，實驗證明LRGOAFS可以同步降低特征選擇維度和提升數(shù)據(jù)分類準確率。

1 蚱蜢優(yōu)化算法GOA

蚱蜢優(yōu)化算法GOA是一種較新的自然啟發(fā)式算法，模擬了蚱蜢這類昆蟲的社會行為。蚱蜢這類害蟲會影響農作物產量，其整個生命周期由3個階段組成：蟲卵、幼蟲和成蟲。在幼蟲階段，蚱蜢的運動特征包括跳躍和柱狀旋轉式飛行，步長小，移動慢，捕食路徑上的植被；而成蟲階段，蚱蜢則以群體方式大范圍遷移，步長大，且具有突然性。GOA算法則通過幼蟲階段的局部開發(fā)和成蟲階段的全局搜索，促使種群向目標移動，實現(xiàn)目標搜索。蚱蜢個體位置的數(shù)學模型為

Xi=Si+Gi+Ai

(1)

式中：Xi為蚱蜢i的位置，Gi為蚱蜢i的重力，Ai為蚱蜢所受風力，Si為蚱蜢i與其它種群個體間的社群作用力，定義為

(2)

式中：dij=|xj-xi| 為蚱蜢i與j間的距離，d′ij=(xj-xi)/dij為個體i至個體j間的距離單元矢量。函數(shù)s可視為社群作用力的強度，定義為

s(r)=fe(-r/l)-e-r

(3)

式中：f為吸引力強度，l為吸引力步長。搜索食物過程中，蚱蜢會根據(jù)社群作用力建立3類區(qū)域：舒適區(qū)、吸引區(qū)和排斥區(qū)。當蚱蜢間的距離逐步增大時(大于10)，函數(shù)s趨近于無法產生社群作用力，即個體間沒有相互影響的作用力。一般做法是將個體位置限制于區(qū)間[1,4]。而處于舒適區(qū)個體的位置不進行更新。

Gi定義為

Gi=-ge′g

(4)

其中，g為引力常量，e′g為指向地心的單元矢量。Ai定義為

Ai=ue′w

(5)

其中，u為漂移常量，e′w為風向單元矢量。將相關參數(shù)代入式(1)，有

(6)

其中，N為種群中的蚱蜢數(shù)。

通常情況下，個體受到重力G和風力A的作用較弱，種群個體僅依據(jù)社群作用力S的影響進行位置更新。因此，可將位置更新方式定義為

(7)

(8)

其中，cmax為調整系數(shù)的最大值，cmin為最小值，l為當前迭代數(shù)，L為最大迭代數(shù)。

GOA算法偽代碼如算法1所示。

算法1：標準GOA算法

(1)initialize the value of the parameters such as population sizeN,cmax,cmin,L

(2)generate a random populationX

(3)set the current iterationl=1

(4)whilel

(5) compute the fitness functionf

(7) update the value ofc

(8) fori=1 toNdo

(9) normalize the distance between the solutions inXin the interval [1,4]

(10) updatexi∈X

(11) end for

(12)l=l+1

(13)end while

2 基于學習自動機和折射對立學習的改進蚱蜢優(yōu)化算法LRGOA

2.1 基于混沌映射的種群初始化

初始種群的分布對群智能算法的尋優(yōu)速度和精度有著關鍵影響。GOA算法通過隨機方式進行個體的初始化操作，這會導致種群多樣性缺乏，無法個體對空間的遍歷性。改進算法借助于混沌系統(tǒng)的隨機性、遍歷性特征，提升種群多樣性。目前，較為常用的混沌映射系統(tǒng)是Logistic和Tent混沌系統(tǒng)，如圖1所示(100次迭代生成的混沌值)?？梢?，Logistic映射比Tent映射遍歷性更差，在[0,0.1]、[0.9,1]兩個區(qū)間取值率較高(邊緣位置密度高)，中間密度較低，且對初始參數(shù)較為敏感。Tent映射均勻性好于Logistic映射，但Tent映射存在小周期、周期點不確定的不足。綜合考慮，改進算法在Tent映射中融入完全隨機化，添加隨機變量r/N改變混沌Tent原來的映射方式，具體方式為

(9)

式中：i為種群規(guī)模，j為混沌序號，對應個體空間維度，θ為隨機數(shù)，μ為混沌參數(shù)，且θ∈[0,1]，μ∈[0,2]。 確定混沌參數(shù)μ并對式(9)取相應初始值后，通過式(10)進行位置映射

xi,j=oi,min+yi,j×(hi,max-oi,min)

(10)

式中： [oi,min,hi,max] 為位置xi,j的上下限。

圖1 混沌映射

隨機生成種群無法保證初始個體均勻遍布完整搜索域，進而降低搜索精度。而根據(jù)式(9)，混沌序列的生成值取決于初始值，而初始值所發(fā)生的微小變化也會導致混沌序列值發(fā)生巨大變化，此時生成的初始種群將兼具隨機多樣和遍歷性等特征，這樣可以通過迭代均勻地遍歷到整個搜索區(qū)域。

2.2 基于學習自動機的調整系數(shù)c更新

根據(jù)式(7)可知，蚱蜢位置更新時需要兩次利用調整系數(shù)c1和c2，其中，c1類似粒子群優(yōu)化PSO的慣性權重，c1的作用是控制全局搜索與局部開發(fā)間的均衡。c2的作用則是減少個體間的吸引域、舒適域和排斥域，逐步減小吸引力和排斥力。然而，根據(jù)式(8)可知，調整系數(shù)是線性遞減的，導致全局搜索與局部開發(fā)切換、不同域內的個體所受吸引力和排斥力都以相同概率進行，這并不能滿足最優(yōu)的蚱蜢尋優(yōu)過程，搜索精度會受到影響。因此，兩個調整系數(shù)的更新必須以非線性形式進行更新。本文將引入以下的學習自動機對調整系數(shù)進行動態(tài)更新。

隨機環(huán)境中，可執(zhí)行的行動數(shù)通常是有限的。當執(zhí)行輸入行動集中的一個特定行動時，環(huán)境將給出一種反饋(獎勵或懲罰)。學習自動機的關鍵目標是通過分析過往行動及相應反饋選擇最優(yōu)行動，即：通過調整每個行動被選中的概率分布，并使概率值最終收斂到最佳行動上。學習自動化中，初始所有行動擁有相同概率，隨機選擇一種行動并觀察環(huán)境反饋。基于反饋結果，更新行動概率。通過若干次迭代學習，LA將選擇獲得環(huán)境獎勵的最優(yōu)行動集。一個可變結構的學習自動機可定義為六元組 (B,Φ,Ψ,P,G,T)， 其中，B為輸入行動集，Φ為內在狀態(tài)集，Ψ為環(huán)境反饋集，P為每個行動被選擇的概率矢量，G為概率更新策略，T為學習算法。

本文利用線性獎懲策略作為學習算法，兩個學習參數(shù)a、b用于更新學習自動機的行動選擇概率，其中，a為獎勵步長，b為懲罰步長。本文假設兩個學習參數(shù)a、b相等，以確保每次迭代擁有相同的概率更新。令αi為時刻t的行動選擇，p(t)為行動選擇概率分布函數(shù)，β為相應環(huán)境反饋。對于β∈{0,1} 的特定環(huán)境反饋，擁有r個行動(B中行動數(shù))線性獎懲策略可定義為式(11)，即β=0的獎勵反饋；和式(12)，即β=1的懲罰反饋。

當β=0時

(11)

當β=1時

(12)

其中，i為前一步驟中自動機的狀態(tài)，j為自動機更新后的狀態(tài)。i=j表明保持前一行動選擇，i≠j表明需要改變行動選擇。

結合以上分析，本文將利用學習自動機對調整系數(shù)c1和c2進行非線性自適應更新，具體定義為

c1=c1+k1δ

(13)

c2=c2+k2δ

(14)

其中，δ為較小正常量，k1、k2為決策參數(shù)，即行動集 {-1,0,1}。 初始時，3種行動取值概率相等。隨著迭代的進行，行動選擇概率將根據(jù)線性獎懲策略進行更新，即通過式(9)、式(10)的獎懲策略更新k1、k2在行動上的選擇概率。根據(jù)將選擇環(huán)境反饋β進行更新，β=0代表自動機將獲得獎勵，β=1代表自動機將獲得懲罰。通過比較個體適應度優(yōu)劣，確定環(huán)境反饋是獎勵或懲罰。若新個體的適應度優(yōu)于原始個體，則自動機獲得獎勵，β=0；否則，β=1。通過這種更新方式，算法所選擇的調整系數(shù)更新將是使得個體能從環(huán)境中獲得獎勵的最優(yōu)行動選擇帶來的結果。

2.3 基于折射對立學習的位置更新

對立學習是一種豐富候選種群個體質量的有效方式，它綜合利用了當前解的對立解的方式對候選種群的分布范圍進行了擴展，即同時在當前解和對立解的方向進行搜索，提高尋得較優(yōu)解的可能性。

定義個體i的位置為Xi=(xi,1,xi,2,…,xi,d)，xi∈[oi,hi]， 代表d維空間中問題的一個候選解， [oi,hi] 為個體i在維度上的搜索范圍。Xi的對立解為X′i=(x′i,1,x′i,2,…,x′i,d)，x′i,j為原解Xi中xi,j的對立數(shù)，i=1,2,…,N，j=1,2,…,d， 且對立數(shù)x′i=oi+hi-xi，xi∈[oi,hi]。 在計算個體位置適應度的同時，同步考慮其對立解的適應度，將候選解及其對立解同步考慮在種群中，并通過貪婪選擇策略擇優(yōu)保留個體至下一代種群，即為常規(guī)的對立學習機制。

然而，對立學習僅能在種群迭代早期提升算法的尋優(yōu)性能，在迭代晚期，對立解也可能陷入局部最優(yōu)。而折射對立學習則在對立學習基礎上，應用光線的折射原理來擴大搜索范圍，增加搜索全局最優(yōu)解的概率。光的折射定理指出：真空中的光線射入另一介質時，入射光線、折射光線及法線處于同一平面。折射角小于入射角，且隨入射角增加而增加，具體原理如圖2所示。

圖2 光線的折射原理

令原始解為x，折射解為x″，入射角為ρ1，折射角為ρ2，入射光線長度為m，折射光線長度為m′， [o,h] 為蚱蜢維度位置的搜索范圍，則

(15)

則光線的折射率φ為

(16)

令z=m/m′， 可得折射對立解為

(17)

若z=φ=1， 則折射對立解退化為對立解。

圖3是當前解、對立解及折射對立解的位置可能分布情況?？梢姡舭磳α⒔鈞′方向搜索，候選解將逐步遠離最優(yōu)解，即使個體適應度得到改善，也可能是局部最優(yōu)。然而，折射對立解的分布區(qū)域明顯與最優(yōu)解距離更近，更利于算法得到全局最解。為了使折射對立解逐步靠近最優(yōu)解的鄰近區(qū)域，可以調整入射解改變參數(shù)z、φ的取值使更靠近最優(yōu)解的折射對立解x″2或x″3進一步接近最優(yōu)解區(qū)域，如：減小入射角ρ1降低折射率φ使折射對立解x″2接近最優(yōu)，或增加折射光線長度m′減小z值使折射對立解x″3接近最優(yōu)。

圖3 當前解、對立解及折射對立解的分布

引入折射對立學習機制進行個體位置更新后，通過折射率φ或入射/折射光線長度比z的調整，有能力使LRGOA算法擴展搜索區(qū)域，提高種群多樣性，避免過早陷入局部最優(yōu)。

2.4 LRGOA算法實現(xiàn)

LRGOA算法步驟如下：

步驟1 對種群規(guī)模N，最大迭代數(shù)L，混沌參數(shù)μ，調整系數(shù)最大值cmax和最小值cmin、常量δ等參數(shù)進行初始化操作；

步驟2 利用修正的混沌Tent映射方法形成初始化種群；

步驟3 計算種群個體適應度，確定最優(yōu)解；

步驟4 利用學習自動機機制更新調整系數(shù)c；

步驟5 首先利用式(7)更新所有種群個體位置，再根據(jù)折射對立學習機制計算個體的折射對立解，通過貪婪選擇策略，保留原始解和其折射對立學習解中適應度較優(yōu)的解至種群中，且種群規(guī)模保持不變；

步驟6 重新計算種群個體適應度，更新最優(yōu)個體；

步驟7 迭代尋優(yōu)過程結束，轉到步驟8；否則，重復步驟4～步驟6；

步驟8 輸出最優(yōu)解。

3 基于LRGOA算法的特征選擇方法LRGOAFS

3.1 特征選擇模型

針對包含若干屬性的數(shù)據(jù)集而言，特征選擇是二值決策優(yōu)化問題，存在的理論解是指數(shù)級的。利用LRGOA算法進行特征選擇可以通過群智能算法獨有的啟發(fā)式搜索機制極大減小搜索空間和時間復雜度。然而，特征選擇解僅為取值0或1，1代表選擇該特征，0代表不選擇該特征。而LRGOA算法是針對連續(xù)優(yōu)化問題的算法，因此，需要將蚱蜢個體位置改變從連續(xù)變化轉化為二值變化。

表1代表一種特征選擇解，可將其視為蚱蜢個體在搜索空間中的位置矢量。矢量長度代表數(shù)據(jù)集的特征屬性總量，即8個原始屬性。矢量元素xi,2=xi,3=xi,5=xi,7=1， 代表2、3、5、7被LRGOA算法選擇在最優(yōu)特征子集，矢量元素xi,1=xi,4=xi,6=xi,8=0， 代表特征1、4、6、8未被選擇為最優(yōu)特征。分類器將根據(jù)特征2、3、5、7進行數(shù)據(jù)分類。

表1 特征選擇解

利用Sigmoidal函數(shù)(S型)實現(xiàn)LRGOA算法的二值轉換，將連續(xù)蚱蜢優(yōu)化算法轉換為二進制形式，定義為

(18)

式中：ΔXl表示迭代l時搜索個體的步長矢量，函數(shù)T表示特征子集中元素取值為1的概率。

個體位置將基于概率值T(ΔXl) 進行更新，具體為

(19)

其中，rand為隨機值。

對于封裝法下的特征選擇方法，需要結合學習算法評估所選特征子集優(yōu)劣。本文將采用k最近鄰分類器KNN獲取相應解的分類準確率。分類準確率越高，表明解的相關性越好。同時，由于特征選擇還需要盡可能減少選擇特征量，解中特征數(shù)量越少，也表明解的性能越優(yōu)。因此，需要綜合考慮這兩個沖突式目標設計特征選擇算法的適應度函數(shù)。本文通過式(20)定義平衡兼顧每個搜索個體的特征選擇量(最小化)和分類準確率(最大化)的適應度函數(shù)來評估所選特征子集的質量

(20)

式中：ErrRate表示利用所選特征的分類錯誤率，即分類器錯誤分類在總體分類中的占比，取值0到1之間，|SF|表示特征選擇量，|ALLF|表示原始數(shù)據(jù)集的屬性總量，ξ表示控制參數(shù)，用于控制算法對分類質量和特征子集長度的偏好，ξ∈[0,1]。

3.2 特征選擇算法設計

算法組成結構如下：首先，對數(shù)據(jù)集進行預處理，將其劃分為測試集和訓練集；其次，將數(shù)據(jù)集中的特征分布映射至種群個體位置的搜索空間中，使特征選擇問題與個體位置匹配；然后，進入LRGOA算法的尋優(yōu)過程，該過程主要通過折射對立學習機制對個體位置(對應特征選擇解)進行動態(tài)更新，其中的調整系數(shù)c將以學習自動機進行更新，從而更好提高搜索精度；通過不斷更新種群最優(yōu)解，最后，在到達算法終止條件時，輸出最優(yōu)個體即特征選擇最優(yōu)解。圖4是基于LRGOA算法的特征選擇過程。

圖4 LRGOAFS特征選擇算法流程

4 實驗分析

4.1 實驗配置

為了驗證基于LRGOAFS算法的特征選擇方法的有效性和穩(wěn)定性，選取UCI庫中(https://archive.icu.uci.edu/ml/index.php.)的10個數(shù)據(jù)集進行實驗測試分析，數(shù)據(jù)集描述見表2。實驗環(huán)境為操作系統(tǒng)win 10，CPU為i7 2.2 GHz，內存為8 GB。種群規(guī)模設置為30，最大迭代次數(shù)設置為100，混沌參數(shù)μ設為0.7，調整系數(shù)最大值cmax為1，最小值cmin為0.000 01、常量δ為0.1，控制參數(shù)ξ為0.99(通常分類準確率相對特征選擇量具有更大的重要性)。作為群智能算法，LRGOAFS算法下特征選擇過程具有一定隨機性，在數(shù)據(jù)集上執(zhí)行10次獨立實驗并取均值結果以降低偶然因素對算法計算結果的影響。實驗實施中，利用10-折交叉驗證(10-folds cross-validation)選擇訓練樣本和測試樣本。將每個數(shù)據(jù)隨機劃分為10個部分，9個部分作為訓練集，剩下1個部分作為測試集。分類器KNN中參數(shù)k=5。圖5是相應實驗過程圖解。

表2 數(shù)據(jù)集說明

圖5 實驗過程

選擇基于灰狼優(yōu)化的特征選擇算法BGWOFS[17]、蚱蜢優(yōu)化特征選擇算法BGOAFS[18]和改進蚱蜢優(yōu)化特征選擇算法IGOAFS[19]進行性能對比。本文基于LRGOA的特征選擇算法命名為LRGOAFS。BGWOFS采用了較新的同為群智能算法的灰狼優(yōu)化算法GWO對特征選擇進行求解，BGOAFS則采用標準GOA算法進行了特征選擇求解，IGOAFS則在改進標準GOA算法尋優(yōu)精度和效率的基礎上再求解特征選擇問題。BGWOFS算法中，收斂因子a的取值范圍為[0,2]。BGOAFS算法參數(shù)與本文相同，IGOAFS算法中l(wèi)imit閾值設為15，隨機個體選取量為種群規(guī)模的三分之一。3種算法的選擇使得后文的對比實驗中同時兼顧了橫向和縱向的比較。

4.2 評估指標

(1)平均分類準確率AAC

AAC代表得到特征子集后，在特定數(shù)據(jù)集上利用分類器計算的平均分類準確率。AAC取值越大，代表分類性能越好。具體定義為

(21)

其中，M為實驗重復次數(shù)，n為測試數(shù)據(jù)集的屬性總量，Cj為屬性j的正確分類標簽，Lj為分類器得到的預測標簽，函數(shù)Mat(x,y) 定義為

(22)

(2)平均特征子集降低比例AFSR

由于原始數(shù)據(jù)集中包含許多非相關性的冗余特征，若特征子集中特征關聯(lián)性不大，冗余特征過多，不僅會降低分類器的學習效率，還會降低數(shù)據(jù)集的分類準確率。因此，必須有效降低特征子集規(guī)模，最大程度提升特征間的相關性，在降低特征維度的同時，實現(xiàn)分類準確率的最大提升。

AFSR代表特征選擇算法得到的特征子集規(guī)模降低程度。AFSR取值越小，性能越好。將平均特征子集規(guī)模AFS定義為

(23)

則AFSR為

(24)

其中，M為實驗重復次數(shù)， |C| 為原始特征子集長度，g*,i為第i次算法運行的最優(yōu)特征子集， |*| 為集合*的基數(shù)。

(3)平均適應度AF及標準差SD

AF代表最優(yōu)特征子集對應的平均適應度值，取值越小，算法性能越好。SD則體現(xiàn)特征選擇算法的穩(wěn)定性，取值越小，說明算法穩(wěn)定性越強。具體定義為

(25)

(26)

4.3 實驗結果

圖6是4種算法在10個數(shù)據(jù)集上得到的平均分類準確率及相應標準方差值，柱狀圖對應左側縱坐標，折線圖對應右側縱坐標。本文的LRGOAFS算法在Flare、Hepatitis、Ionoshpere、Wine、Zoo、Vote等6個數(shù)據(jù)集上得到了最高平均分類準確率，是4種算法中最好的。同時，LRGOAFS算法可以在規(guī)模較大的Flare上得到最高分類準確率，證明算法不僅可以處理中小規(guī)模特征選擇問題，對較大規(guī)模特征選擇也是有效可行的。標準方差對應算法穩(wěn)定性，LRGOAFS算法在5個數(shù)據(jù)集上得到更小的標準方差，說明算法穩(wěn)定性也比較好，在處理不同規(guī)模特征選擇問題上適應度較強。另外3種算法雖然在個別數(shù)據(jù)集上可以得到比LRGOAFS算法更高的平均分類準確率，但穩(wěn)定性欠佳，求解成功率太低。

圖6 平均分類準確率

圖7是4種算法在10個數(shù)據(jù)集上得到的平均適應度及相應標準方差值，柱狀圖對應左側縱坐標，折線圖對應右側縱坐標。適應度函數(shù)(20)表明分類錯誤率越小，特征選擇量越少，算法性能越好，對應于適應度函數(shù)值越小越好?？梢钥吹?，LRGOAFS算法在Bands、Ionoshpere、Lung、Wine、Zoo等5個數(shù)據(jù)集上得到了更小的適應度，是4種算法中占比最高的，說明在綜合考慮分類準確率和特征選擇量方面，算法具有更好的綜合性能。也證實在LRGOAFS算法中采用針對標準GOA算法的改進措施是有效可行的，可以提升算法的尋優(yōu)精度。

圖7 平均適應度

圖8 平均特征子集降低比例

圖8是4種算法在10個數(shù)據(jù)集上得到的特征子集降維比例，比例越大，說明算法選擇的最優(yōu)特征子集規(guī)模越小，數(shù)據(jù)特征降維效果越好。LRGOAFS算法在6個數(shù)據(jù)集上得到最大降維比例，占比最高。結合圖6的結果可知，LRGOAFS算法在Ionoshpere、Wine、Zoo、Vote等4個數(shù)據(jù)集上同時實現(xiàn)了最高的分類準確率和最小的特征選擇比例，性能最好。另種3種算法并不能保證穩(wěn)定性。

圖9是4種算法在10個數(shù)據(jù)集上的平均計算時間對比結果。結果表明，LRGOAFS算法并不能保證在所有數(shù)據(jù)集上擁有最少的計算時間，甚至在部分數(shù)據(jù)集上計算時間花費更多(如Lung、Hepatitis數(shù)據(jù)集等)，但結合前文算法在分類準確率(圖6)、特征降維(圖8)和適應度(圖7)方面的表現(xiàn)，LRGOAFS算法依然實現(xiàn)了所有算法中的最佳綜合性能，算法在特征降維、提升分類準確率的同時，并未犧牲過多計算效率。

圖9 算法的平均計算時間

本文在第4節(jié)的實驗配置階段為LRGOAFS算法選用的分類器為KNN，這一部分進一步引用支持向量機SVM作為分類器對LRGOAFS算法的性能進行對比分析。KNN找到訓練集中離預測樣本點距離最近的k個值即可，在訓練集和測試集規(guī)模很大時，預測效率很可觀。且其參數(shù)只有一個k值，調參比較簡單。SVM具有相對復雜的訓練過程，訓練完后再對測試集進行分類，兩步獨立進行。同時SVM參數(shù)更多，訓練時間復雜性會略高。兩種分類器各有優(yōu)劣。將利用兩種分類器的特征選擇算法分別命名為LRGOAFS-KNN和LRGOAFS-SVM。測試了兩種算法在平均分類準確率和平均特征子集降低比例上的實驗結果，如圖10所示。圖中，柱狀圖對應左縱軸的平均分類準確率結果，折線圖對應右縱軸的平均特征子集降低比例結果。由結果可知，LRGOAFS-KNN算法在6個數(shù)據(jù)集上的平均分類準確率是占優(yōu)于LRGOAFS-SVM算法的，有一個數(shù)據(jù)集在這項指標上幾乎接近。此外，LRGOAFS-KNN算法在7個數(shù)據(jù)集上的平均特征子集降低比例是占優(yōu)于LRGOAFS-SVM算法的，LRGOAFS-SVM算法則有3個數(shù)據(jù)集。同時，結合兩種指標的結果可知，LRGOAFS-KNN算法總共在6個數(shù)據(jù)集上同步實現(xiàn)了更高的分類準確率和更高的平均特征子集降低比例，說明在近選10組數(shù)據(jù)集的測試上，LRGOAFS-KNN算法的性能略優(yōu)于LRGOAFS-SVM算法。

圖10 KNN與SVM分類器間的比較

為了測試算法跳出局部最優(yōu)的能力，利用一個多峰值基準函數(shù)Griewank進行尋優(yōu)測試，函數(shù)表示如式(27)所示，函數(shù)的搜索區(qū)間為[-600,600]，函數(shù)的理論極值為0。Griewank函數(shù)在整個搜索區(qū)間內存在多個極值點，因此可以測試算法是否具有跳離局部最優(yōu)解的能力。依然選取前文灰狼優(yōu)化算法BGWO[17]、蚱蜢優(yōu)化算法BGOA[18]和改進蚱蜢優(yōu)化算法IGOA[19]進行性能對比。結果如圖11所示。首先，從尋優(yōu)精度上看，在400次迭代過程中，LRGOA算法明顯比另外3個算法可以得到更接近于理論極值點的解，說明其尋優(yōu)精度更高。同時，曲線趨勢上看，LRGOA算法具有明顯的下墜趨勢，而另外3種算法走勢更平緩，說明尋優(yōu)精度已經無法進一步提高。尤其在100次迭代至150次迭代中，LRGOA算法在某處停留后，有一個加快下墜的趨勢，此處趨勢可解釋為：LRGOA在得到某局部最優(yōu)解后，仍然可以跳離局部極值，進一步擴展到其他搜索空間得到更優(yōu)解

(27)

圖11 算法的尋優(yōu)曲線

5 結束語

為了降維數(shù)據(jù)特征維度，提高數(shù)據(jù)分類準確率，提出了一種基于改進蚱蜢優(yōu)化算法的特征選擇算法。首先，利用融合完全隨機性的混沌映射機制優(yōu)化了蚱蜢初始種群，利用學習自動機對蚱蜢位置更新的調整系數(shù)進行改進，均衡全局搜索與局部開發(fā)；引入折射對立學習擴展搜索區(qū)域，避免算法過早陷入局部最優(yōu)解，實現(xiàn)了改進蚱蜢優(yōu)化算法。然后，將改進蚱蜢優(yōu)化算法應用于數(shù)據(jù)集的特征選擇求解，通過10種數(shù)據(jù)集測試驗證該算法不僅降低特征維度，還可以提高數(shù)據(jù)分類準確率，且具有更好的穩(wěn)定性。后續(xù)研究中，如何實現(xiàn)針對更高特征維度的特征選擇以及如何實現(xiàn)蚱蜢優(yōu)化算法的進一步優(yōu)化是下一步的主要研究內容。