趙澤淵，代永強

甘肅農(nóng)業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院，蘭州 730070

特征選擇（feature selection）是從數(shù)據(jù)集已有的N個特征中去除冗余、無用的特征，并選出具有M個特征的特征子集的方法（M≤N），該方法能夠降低特征數(shù)目，提高分類算法的分類性能[1]。

常見的特征選擇方法分為過濾式（filter）、封裝式（wrapper）、嵌入式（embedded）[2-3]。過濾式方法與特定的學(xué)習(xí)算法無關(guān)，該方法從數(shù)據(jù)集本身的內(nèi)在性質(zhì)（如相關(guān)性）獲得評價標(biāo)準(zhǔn)，然后根據(jù)各子集的優(yōu)劣進行選擇[4]。封裝式方法是從數(shù)據(jù)集中不斷產(chǎn)生特征子集并將其用來訓(xùn)練分類器，最后根據(jù)分類器的性能來選擇最優(yōu)特征子集[5]。而在嵌入式方法中，特征選擇算法本身作為組成部分嵌入到分類算法里[4]。封裝式方法直接面向算法優(yōu)化，易于實現(xiàn)，并且精度與魯棒性優(yōu)于過濾式與嵌入式方法，因此本文采用封裝式的方法進行特征選擇。

假設(shè)數(shù)據(jù)集維度為n，窮舉搜索最優(yōu)特征子集的時間復(fù)雜度為O(2n)，對高維度數(shù)據(jù)進行特征選擇時使用窮舉搜索需要耗費大量時間以及計算資源[6-7]。啟發(fā)式搜索最優(yōu)特征子集是通過對比特征子集增減特征前后的優(yōu)劣程度來搜索最優(yōu)特征子集，其時間復(fù)雜度為O(n2)。雖然啟發(fā)式搜索方法在高維度條件下的性能優(yōu)于窮舉搜索方法，但其仍然需要花費大量時間成本。隨機搜索是指將特征選擇與隨機優(yōu)化算法相結(jié)合，使用隨機優(yōu)化算法的優(yōu)化策略生成子集，并使用特定的評價函數(shù)來評價子集的優(yōu)劣，最后依照自定義的結(jié)束條件來完成特征子集的選擇。對于高維度數(shù)據(jù)的特征選擇問題來說，隨機搜索方法的效率遠遠高于窮舉搜索方法和啟發(fā)式搜索方法。在隨機搜索方法中，隨機優(yōu)化算法的性能很大程度上決定了特征子集搜索方法的性能。

近年來，隨機優(yōu)化算法得到了科研工作者的廣泛關(guān)注[8-10]，相關(guān)學(xué)者對遺傳算法（genetic algorithm，GA）[11]、蟻群算法（ant colony optimization，ACO）[12]、人工蜂群算法（artificial bee colony，ABC）和粒子群優(yōu)化算法（particle swarm optimization，PSO）[13]等隨機優(yōu)化算法進行了深入和系統(tǒng)的研究，并將這些算法用于特征選擇問題的求解。

受蝗蟲種群行為啟發(fā)，Saremi等[14]于2017年提出了蝗蟲優(yōu)化算法（grasshopper optimization algorithm，GOA）。該算法原理簡單易懂，易于實現(xiàn)，并且能夠在小空間內(nèi)搜索時保持搜索個體均勻分布，限制個體重合，因此相較于其他群智能算法，該算法具有較好的局部搜索性能，有利于優(yōu)化特征選擇算法的局部搜索能力。近年來對GOA 的研究內(nèi)容包括改進與應(yīng)用兩方面。Tumuluru 等[15]提出了一種利用基因表達數(shù)據(jù)進行癌癥分級的方法，并利用GOA 優(yōu)化了該方法中深度置信神經(jīng)網(wǎng)絡(luò)的權(quán)值，實驗結(jié)果表明該方法的分級結(jié)果具有較高的準(zhǔn)確率；Mafarja 等[16]提出了一種基于GOA、選擇算子和進化種群動力學(xué)（evolutionary population dynamics，EPD）的特征選擇算法，并與其他同類方法進行了對比實驗，結(jié)果表明該算法的性能優(yōu)于文獻中的其他算法；Liao 等[17]提出了一種基于鄰域質(zhì)心的蝗蟲優(yōu)化算法，實驗結(jié)果表明改進算法具有更高的種群多樣性與收斂精度；Fathy[18]提出了一種基于GOA 的光伏陣列最優(yōu)重構(gòu)過程的求解方法，并通過實驗證實了該方法的可靠性和有效性；Lal 等[19]設(shè)計了一種混合動力系統(tǒng)的分?jǐn)?shù)階模糊PID（proportion integration differentiation）頻率控制器，利用GOA 優(yōu)化了該頻率控制器的參數(shù)，并通過實驗證實了該控制器的有效性；閆旭等[20]利用量子旋轉(zhuǎn)門操作改進了GOA，提出了一種基于量子計算思想的混合蝗蟲優(yōu)化算法，并利用作業(yè)車間標(biāo)準(zhǔn)測試問題進行了仿真實驗，結(jié)果表明該算法對比文獻中的其他四種算法具有更好的性能；李洋州等[21]通過引入曲線自適應(yīng)與模擬退火算法提高GOA 的收斂速度與精度，提出一種曲線自適應(yīng)和模擬退火蝗蟲優(yōu)化算法，實驗結(jié)果表明該算法比改進前的算法具有更好的求解質(zhì)量與收斂速度。上述文獻說明GOA 能夠在各類優(yōu)化問題中表現(xiàn)出較優(yōu)的性能，但其自身存在全局搜索性能弱與收斂精度低的不足，算法性能有較大的提升空間。

1 基本蝗蟲優(yōu)化算法

蝗蟲優(yōu)化算法[14]是受蝗蟲種群行為啟發(fā)而提出的群智能算法。經(jīng)過研究蝗蟲群體遷移、聚集、覓食的行為發(fā)現(xiàn)，蝗蟲個體在群體中會受到種群交互力、重力和風(fēng)力的影響?；谀M蝗蟲群體行為的數(shù)學(xué)模型如式（1）～（4）[14]：

其中，Xi表示第i只蝗蟲的位置，Si、Gi、Ai分別表示第i只蝗蟲受到的種群交互力、重力和風(fēng)力。

式（3）為s函數(shù)的表達式，用于計算蝗蟲個體間的吸引力與排斥力：s(r)>0，蝗蟲個體間相互吸引，則稱r的取值范圍為吸引域；s(r)<0，蝗蟲個體間相互排斥，則稱r的取值范圍為排斥域；s(r)=0，蝗蟲個體間既不吸引也不排斥，則稱r的取值為舒適距離（注意當(dāng)r的取值過大時，s(r)趨近于0，但這時r的取值并非是舒適距離。Saremi 等[14]指出，將蝗蟲個體間的距離限制在[1,4]上可以避免蝗蟲間距離過大對算法產(chǎn)生的不利影響）。式（3）中f為吸引強度參數(shù)，l為吸引尺度參數(shù)，通過改變兩者的取值情況可以控制蝗蟲之間的吸引域、排斥域和舒適距離的分布情況和吸引與排斥的強度。參考Saremi 等[14]對兩者的取值，本文取l=1.5，f=0.5。

結(jié)合上述公式，通常使用下式進行優(yōu)化問題的求解：

綜上可知，蝗蟲個體的位置不僅受到目標(biāo)位置的影響，還會受到其他所有個體位置的影響。在種群向目標(biāo)位置收斂的過程中，蝗蟲個體受到種群交互力的影響，搜索范圍、個體間的舒適距離不斷減小，但個體之間仍保持一定的間距，在一定范圍內(nèi)分散地搜索，最終所有蝗蟲個體會均勻分布到目標(biāo)位置附近。這種搜索個體之間的獨特交互方式，是蝗蟲優(yōu)化算法的顯著特征，使得蝗蟲優(yōu)化算法具備了較好的局部開發(fā)能力。

2 改進的混合二進制蝗蟲優(yōu)化特征選擇算法

本文通過改進二進制轉(zhuǎn)化策略并引入混合復(fù)雜進化方法，進一步提高了二進制蝗蟲優(yōu)化特征選擇算法的性能。通過對UCI數(shù)據(jù)集進行特征選擇，實驗結(jié)果表明，改進算法獲得了更好的特征子集，取得了更好的分類效果。

2.1 基本二進制蝗蟲優(yōu)化特征選擇算法

2.1.1 基本二進制蝗蟲優(yōu)化算法

蝗蟲優(yōu)化算法獨特的進化方式與較好的局部開發(fā)能力，使其在連續(xù)的優(yōu)化問題中擁有較好的性能。為了利用蝗蟲優(yōu)化算法產(chǎn)生特征子集，需要對其進行離散化處理。GOA 經(jīng)過對種群初始化和更新策略的修改后可得到二進制蝗蟲優(yōu)化算法（binary grasshopper optimization algorithm，BGOA）[16]，具體方法如下：

（1）種群初始化

在特征選擇算法中，每個蝗蟲個體代表一個解，其位置信息表示特征的選取情況。使用下式對初始蝗蟲種群進行二進制賦值[16]：

（2）更新策略

其中，本文引入了系數(shù)A來控制橫軸伸縮度，T(x)函數(shù)的返回結(jié)果為該個體d維位置變化概率。

Fig.1 Image of T(x) function圖1 T(x)函數(shù)圖像

最后，使用式（8）得出更新后蝗蟲個體的位置[16]。

其中，rand為(0,1)上的隨機數(shù)。

2.1.2 特征選擇實現(xiàn)流程

基于BGOA 的特征選擇算法偽代碼如下所示。

初始化BOGA 特征選擇算法參數(shù)cmax、cmin、最大迭代次數(shù)Tmax

初始化數(shù)據(jù)集、數(shù)據(jù)集參數(shù)

按照2.1.1 小節(jié)的方法進行種群初始化，同時使用特征子集評價函數(shù)（見2.4 節(jié)）計算所有個體的適應(yīng)度

首先利用BGOA 產(chǎn)生二進制個體，依照每個個體的編碼選取特征子集，之后使用特征子集評價函數(shù)對每個個體所對應(yīng)的特征子集進行評價，最后依據(jù)評價結(jié)果更新各個個體。依照上述流程不斷循環(huán)，直至達到最大迭代次數(shù)Tmax，此時將適應(yīng)度最低的個體作為結(jié)果返回。

時間復(fù)雜度分析：BGOA 中個體更新需要計算其他所有個體的位置，假設(shè)個體數(shù)量為N，則單個個體更新一次的時間復(fù)雜度為O(N)，群體更新一次的時間復(fù)雜度為O(N2)；假設(shè)最大迭代次數(shù)為Tmax，則可以得出BGOA特征選擇算法的時間復(fù)雜度為O(N2×Tmax)。

2.2 改進二進制蝗蟲優(yōu)化特征選擇算法

BGOA 特征選擇算法的二進制轉(zhuǎn)化方式具有過大的隨機性，導(dǎo)致蝗蟲個體更新較為盲目，在高維度條件下性能不佳。為了降低BGOA 特征選擇算法更新的盲目性，增強探索能力，提高維度條件下的性能，本文引入了步長引導(dǎo)個體位置變化的二進制轉(zhuǎn)化策略替代BGOA 特征選擇算法原有的轉(zhuǎn)化策略。將改進后的算法稱為改進二進制蝗蟲優(yōu)化算法（improved binary grasshopper optimization algorithm，IBGOA）特征選擇方法。

2.2.1 改進策略

本文提出了一種步長引導(dǎo)個體位置變化的二進制轉(zhuǎn)化策略，該策略如下所述：

首先，根據(jù)式（6），可以將式（4）改寫為：

為了使二進制化后的蝗蟲個體能夠根據(jù)步長大小控制更新后的位置與目標(biāo)位置之間的距離，本文基于Sigmoid 函數(shù)提出了新的函數(shù)S(x)對步長進行轉(zhuǎn)化，S(x)如式（10）所示。

其中，A為系數(shù)，用來控制橫軸伸縮度，S(x)函數(shù)的返回結(jié)果為個體d維位置變化概率。

Fig.2 Image of S(x) function圖2 S(x)函數(shù)圖像

根據(jù)轉(zhuǎn)換函數(shù)計算出當(dāng)前蝗蟲個體每一維度上的變化概率之后，使用式（11）對S(ΔXdi)進行轉(zhuǎn)化：

綜上可知，IBGOA 特征選擇算法中蝗蟲個體基于其受到的種群交互力得到位置變化概率，然后基于位置變化概率與目標(biāo)位置得出新的位置。相比于BGOA 特征選擇算法，IBGOA 特征選擇算法個體的更新方式具有更好的目的性和探索性能。

2.2.2 改進策略性能驗證

為驗證新的二進制轉(zhuǎn)化策略的性能，本文設(shè)計了一種驗證實驗方案，比較采用兩種改進更新策略后算法的性能，實驗步驟如下：

（1）按照2.1.1 小節(jié)的方法初始化一個蝗蟲種群，并將第一個蝗蟲個體作為目標(biāo)個體。

（2）分別采用改進前后的兩種二進制轉(zhuǎn)化策略對蝗蟲種群進行一次更新，得到更新后的兩個蝗蟲種群。

（3）對于更新前后的三個蝗蟲種群，分別計算其群體中兩兩蝗蟲之間的距離，并計算所有蝗蟲之間的平均距離dis。

本文按照上述的實驗方案分別在c=cmax=1 和c=cmin=0.000 01 兩個條件下進行了10 次獨立重復(fù)實驗，其中蝗蟲個體數(shù)量N=80，維度dim=10。10 次實驗中dis的平均值如表1 所示。

Table 1 Experimental results of average distance dis表1 平均距離dis 實驗結(jié)果

參數(shù)c用于平衡算法的全局探索能力與局部搜索能力。c=cmax=1 時，算法處于全局探索階段，觀察表1 可知，采用兩種策略更新后的蝗蟲群體中個體之間的平均距離相較于更新前均有所增加，但是采用新策略更新后的蝗蟲群體中個體之間的平均距離增加更為明顯，說明采用新策略的算法前期的探索能力更強。c=cmin=0.000 01 時，算法處于局部搜索階段，觀察表1 可知，采用新策略更新后的蝗蟲群體中蝗蟲個體之間的平均距離相較于更新前有明顯縮減，舊策略反而增加，說明采用舊策略的算法后期的局部搜索過程具有盲目性，而采用新策略的算法收斂性更強，更具有目的性。綜上所述，相較于基本算法的二進制轉(zhuǎn)化策略，本文提出的步長引導(dǎo)個體位置變化的二進制轉(zhuǎn)化策略對算法前期的探索能力與后期的收斂性能均有提升。

2.2.3 特征選擇實現(xiàn)流程

IBGOA 特征選擇算法的偽代碼如下所示。

初始化IBGOA 特征選擇算法參數(shù)cmax、cmin、最大迭代次數(shù)Tmax

初始化數(shù)據(jù)集、數(shù)據(jù)集參數(shù)

按照2.1.1 小節(jié)的方法進行種群初始化，同時使用特征子集評價函數(shù)（見2.4 節(jié)）計算所有個體的適應(yīng)度

相較于BGOA 特征選擇算法，該算法只對個體更新公式進行了調(diào)整，整體流程并無變化；由于IBGOA 特征選擇算法在個體更新時需要額外計算一個公式，因此該算法的時間復(fù)雜度可以表示為O(N×(N+1)×Tmax)=O(N2×Tmax)，而BGOA 特征選擇算法的時間復(fù)雜度也為O(N2×Tmax)，因此兩者差異可以忽略不計。

2.3 混合二進制蝗蟲優(yōu)化特征選擇算法

IBGOA 特征選擇算法在局部搜索中具有良好的性能，但其全局搜索能力較差，容易陷入局部最優(yōu)。本文在IBGOA 特征選擇算法中引入了混合復(fù)雜進化方法（shuffled complex evolution，SCE），以提高IBGOA特征選擇算法的全局搜索性能。將改進后的算法稱為混合二進制蝗蟲優(yōu)化算法（shuffled binary grasshopper optimization algorithm，SBGOA）特征選擇方法。

2.3.1 混合復(fù)雜進化方法

混合復(fù)雜進化方法是由美國亞利桑那州大學(xué)的Duan 博士等[22]于1992 年提出的一種模擬自然進化過程的混合進化方法。該方法的原理是將全局搜索作為自然進化的過程，將群體公平地劃分為幾個子群，每個子群都被允許獨立發(fā)展。在子群獨立發(fā)展的過程中不斷引入隨機生成的新成員來替代最差個體。經(jīng)過自定義次數(shù)的進化后，子群被迫重新混合，新的群體通過洗牌過程形成。這一策略有助于通過共享每個子群獨立獲得的信息和屬性來改進算法。

SCE 劃分子群獨立進化、競爭淘汰的獨特性質(zhì)能夠有效避免整個算法陷入局部最優(yōu)，其在子群獨立進化完成之后的強行混合可以使得大量搜索個體跳出其舒適圈，在更廣闊的解空間內(nèi)進行探索，從而使算法具有良好的全局搜索性能。

2.3.2 改進策略

SCE 優(yōu)秀的全局搜索性能恰好可以彌補IBGOA特征選擇算法全局搜索能力較差的缺陷，因此本文通過引入SCE 改進IBGOA 特征選擇算法，改進的具體方法如下：

（1）排序與劃分子群：在SBGOA 特征選擇算法中，種群在每次進行更新之前需要根據(jù)每個個體的適應(yīng)度對蝗蟲群體進行升序排序。排序完成后根據(jù)群體中個體的順序?qū)⒄麄€種群劃分為4 個子群S1、S2、S3、S4，每個子群含有M=N/4 個個體。為盡量減少每個子群中蝗蟲群體優(yōu)劣程度的差異，本文將X1劃分到S1，X2劃分到S2，X3劃分到S3，X4劃分到S4中，X5劃分到S1中……，依此類推，直到XN劃分到S4中后全部個體劃分完成。

（2）子群更新：劃分子群后獨立地更新各子群，對于單個子群，每個個體基于該子群中其他個體的位置和該子群中最優(yōu)個體的位置進行更新。為了保證算法的收斂能力，子群S1與S2按照基本方式進行更新；為了增強算法的全局搜索能力，子群S3與S4更新時的參數(shù)c=cmax，并且其不隨迭代次數(shù)變化。

（3）子群復(fù)合：當(dāng)所有子群經(jīng)過自定義次數(shù)tsub次的更新后，將所有子群拆分并將全部個體混合成為一個新的群體。

綜上可知，SBGOA 特征選擇算法中的整個蝗蟲種群被分為4 個子群，每個子群獨立進化，并且強制混合。算法在探索階段，各子群獨立的風(fēng)向（目標(biāo)位置）可以避免蝗蟲種群在同一方向進行探索，與IBGOA 比較，該策略有效提高了算法的探索能力；子群迭代完成后強制混合的策略可以提高蝗蟲個體跳出原先舒適圈（舒適距離）的能力，強制個體改變搜索路徑，提高了算法的跳出局部最優(yōu)的能力。在算法后期的局部搜索階段中，由于子群之間互不干擾，不同子群的個體間沒有吸引或排斥力，增加了個體重合的概率，弱化了算法的局部搜索能力，而各子群獨立的風(fēng)向可以確保個體不會聚集收斂到同一個極值點，進一步降低了算法的陷入局部最優(yōu)的可能，提高了算法的多樣性和魯棒性。

2.3.3 特征選擇實現(xiàn)流程

SBGOA 特征選擇算法的偽代碼如下所示。

初始化SBGOA 特征選擇算法參數(shù)cmax、cmin，最大迭代次數(shù)Tmax，子群迭代次數(shù)tsub

初始化數(shù)據(jù)集、數(shù)據(jù)集參數(shù)

按照2.1.1 小節(jié)的方法進行種群初始化，同時使用特征子集評價函數(shù)（見2.4 節(jié)）計算所有個體的適應(yīng)度

時間復(fù)雜度分析：SBGOA 中個體更新僅需計算所在子群的其余個體位置，假設(shè)每個子群所含個體數(shù)量為M=N/4，則單個個體更新一次的時間復(fù)雜度為O(M)，子群更新一次的時間復(fù)雜度為O(M2)；假設(shè)單個子群更新次數(shù)為tsub，則整個種群更新一次的時間復(fù)雜度為假設(shè)最大迭代次數(shù)為Tmax，則可以得出SBGOA 特征選擇算法的時間復(fù)雜度為由于子群迭代次數(shù)不會低于4（過低則無法正常收斂，沒有意義），因此該算法的時間復(fù)雜度高于BGOA 與IBGOA 特征選擇算法。值得一提的是，由于該算法采用分組更新且互不干擾的策略，可以并行實現(xiàn)，從而極大地縮短了算法的運行時間。

2.4 特征子集評價函數(shù)

為評價二進制蝗蟲優(yōu)化算法產(chǎn)生特征子集的優(yōu)劣程度，本文基于K-NN 分類器與十折交叉驗證法設(shè)計了一種特征子集評價函數(shù)（適應(yīng)度函數(shù)）。該函數(shù)的基本流程為：將初始數(shù)據(jù)集分為10 份，其中9 份作為訓(xùn)練集，其余1 份作為測試集；利用二進制蝗蟲優(yōu)化算法中蝗蟲個體的位置信息來截取特征子集；使用訓(xùn)練集訓(xùn)練K-NN 分類器并使用K-NN 分類器對測試集進行分類；采用十折交叉驗證法進行10 次驗證，得到該特征子集的分類錯誤率；將該特征子集的分類錯誤率與特征個數(shù)占總特征的比值按一定權(quán)重結(jié)合，按照式（13）計算該個體適應(yīng)度fitness。

其中,ErrorRate表示該子集的分類錯誤率，F(xiàn)eatureNum表示該子集的特征個數(shù)，dim表示數(shù)據(jù)集的特征總數(shù)。本文算法意在保證低分類錯誤率的基礎(chǔ)上降低特征數(shù)量，因此將分類錯誤率與特征數(shù)量的權(quán)重分別設(shè)置為0.99 與0.01。

由于特征子集為隨機選擇，那么可能會出現(xiàn)特征數(shù)量為0 的特征子集，但此時該特征子集無意義，因此需要對這種情況進行約束[23]。在特征子集評價函數(shù)中，本文將此類特征子集的適應(yīng)度設(shè)置為1，以消除無意義子集對算法的不利影響。

3 仿真實驗和結(jié)果分析

本文選擇在機器學(xué)習(xí)領(lǐng)域中常用的UCI 數(shù)據(jù)集中的Breast Cancer、Soybean-large 等8 個數(shù)據(jù)集作為測試算法性能的數(shù)據(jù)集。選用的數(shù)據(jù)集與其屬性如表2 所示。

Table 2 Selected UCI data sets表2 選用的UCI數(shù)據(jù)集

3.1 實驗參數(shù)設(shè)置

為了驗證IBGOA 與SBGOA 的改進效果，并客觀地評價SBGOA 的性能，本文使用BGOA 特征選擇算法、IBGOA 特征選擇算法、SBGOA 特征選擇算法、二進制粒子群優(yōu)化算法（binary particle swarm optimization，BPSO）[24]與二進制灰狼優(yōu)化算法（binary grey wolf optimization，BGWO）[25]在表2 中的8 個數(shù)據(jù)集上進行對比實驗。5 種算法的最大迭代次數(shù)均設(shè)置為20，種群大小均設(shè)置為80，其中SBGOA 特征選擇算法的子群迭代次數(shù)設(shè)置為10。

3.2 實驗結(jié)果分析

本文使用5 種算法分別對表2 中的數(shù)據(jù)集進行了10 次獨立重復(fù)實驗。實驗中5 種算法均使用本文設(shè)計的適應(yīng)度函數(shù)。實驗結(jié)果如表3 所示，其中avg_fit與std_fit分別是10 次重復(fù)實驗的平均適應(yīng)度與標(biāo)準(zhǔn)偏差，Average 是8 個數(shù)據(jù)集平均適應(yīng)度與標(biāo)準(zhǔn)偏差的平均指標(biāo)。表中每個數(shù)據(jù)集對應(yīng)的最低平均適應(yīng)度已用粗體標(biāo)出。

平均適應(yīng)度表示10 次測試結(jié)果的適應(yīng)度平均值，其值越低，則表示對應(yīng)算法提高分類準(zhǔn)確率和降維的性能越優(yōu)。從表3 BGOA 特征選擇算法與IBGOA特征選擇算法平均適應(yīng)度可以看出：對于Breast Cancer 數(shù)據(jù)集與Wine 數(shù)據(jù)集的測試結(jié)果，BGOA 特征選擇算法的性能略優(yōu)于IBGOA 特征選擇算法，但對于其余數(shù)據(jù)集的測試結(jié)果來說，后者的性能明顯優(yōu)于前者。Breast Cancer 數(shù)據(jù)集與Wine 數(shù)據(jù)集的特征數(shù)量分別為9 與13，低與其他數(shù)據(jù)集，因此可以得出BGOA 特征選擇算法在低維數(shù)據(jù)集的測試性能略優(yōu)于IBGOA 特征選擇算法，但對于高維數(shù)據(jù)集的處理性能來說，后者的表現(xiàn)更優(yōu)。說明本文對BGOA特征選擇算法的改進有效提升了算法在高維度下提高分類準(zhǔn)確率與降低特征數(shù)量的性能。

從表3 SBGOA 特征選擇算法、BGOA 特征選擇算法、IBGOA 特征選擇算法的平均適應(yīng)度可以看出：對于8 個數(shù)據(jù)集，SBGOA 特征選擇算法的平均適應(yīng)度總是低于其余兩種算法，表明SBGOA 特征選擇算法提高分類準(zhǔn)確率與降低特征數(shù)量的性能優(yōu)于其余兩種算法。說明本文對IBGOA 特征選擇算法的改進有效提升了算法的全局搜索能力。

從表3 BPSO 特征選擇算法、BGWO 特征選擇算法與SBGOA 特征選擇算法可以看出：對于8 個數(shù)據(jù)集，SBGOA 特征選擇算法的平均適應(yīng)度總是低于其他兩種算法，說明SBGOA 特征選擇算法在降低特征數(shù)量與提高分類準(zhǔn)確率的性能優(yōu)于其他兩種算法。標(biāo)準(zhǔn)偏差反映了算法魯棒性的優(yōu)劣，即標(biāo)準(zhǔn)偏差的值越小，對應(yīng)算法的魯棒性越優(yōu)。表4 為5 種算法對應(yīng)8 個數(shù)據(jù)集的標(biāo)準(zhǔn)偏差排名與8 個數(shù)據(jù)集上的平均標(biāo)準(zhǔn)偏差，每個數(shù)據(jù)集對應(yīng)的算法的標(biāo)準(zhǔn)偏差越小，則排名越靠前。

Table 3 Fitness and average index of 5 algorithms表3 5 種算法的適應(yīng)度與平均指標(biāo)

Table 4 Standard deviation ranking and average standard deviation of 5 algorithms表4 5 種算法的標(biāo)準(zhǔn)偏差排名與平均標(biāo)準(zhǔn)偏差

從表4 BGOA 特征選擇算法與IBGOA 特征選擇算法的排名情況可以看出：雖然兩者在8 個數(shù)據(jù)集上的標(biāo)準(zhǔn)偏差排名參差不齊，但從平均標(biāo)準(zhǔn)偏差來看，兩者標(biāo)準(zhǔn)偏差整體相差很小。表明兩者的魯棒性并無較大的差別。說明本文對BGOA 特征選擇算法的改進并沒有提升算法的魯棒性。

從表4 SBGOA 特征選擇算法與IBGOA 特征選擇算法的排名情況可以看出：在Arrhythmia 與Spectf數(shù)據(jù)集上前者的標(biāo)準(zhǔn)偏差排名低于后者，但對于其他6 個數(shù)據(jù)集，前者的標(biāo)準(zhǔn)偏差排名均高于后者，并且前者的平均標(biāo)準(zhǔn)偏差明顯低于后者，表明前者的魯棒性優(yōu)于后者。說明本文對IBGOA 特征選擇算法的改進有效提升了算法的魯棒性。

從表4 SBGOA 特征選擇算法、BPSO 特征選擇算法與BGWO 特征選擇算法的排名情況可以看出：在Arrhythmia 數(shù)據(jù)集上，SBGOA 特征選擇算法的排名低于其他兩種算法；在Clean1 數(shù)據(jù)集上，SBGOA特征選擇算法的標(biāo)準(zhǔn)偏差排名低于BPSO 特征選擇算法，高于GWO 特征選擇算法；在Spectf 數(shù)據(jù)集上，SBGOA 特征選擇算法的標(biāo)準(zhǔn)偏差排名低于BPSO 特征選擇算法，高于BGWO 特征選擇算法；在其他5 個數(shù)據(jù)上，SBGOA 特征選擇算法的標(biāo)準(zhǔn)偏差排名均高于其余兩種算法，并且SBGOA 特征選擇算法的平均標(biāo)準(zhǔn)偏差明顯低于其余兩種算法。表明SBGOA 特征選擇算法的魯棒性優(yōu)于BPSO 特征選擇算法與BGWO 特征選擇算法。

本文使用上述5 種算法分別對8 個數(shù)據(jù)集進行了特征選擇，并根據(jù)不同迭代次數(shù)下算法適應(yīng)度值的變化趨勢來評價算法的搜索性能與收斂性能。實驗結(jié)果如圖3 所示，其中X軸表示迭代次數(shù)t，Y軸表示最優(yōu)適應(yīng)度fitness。

圖3（a）、（e）和（f）分別為5 種算法在Breast Cancer、Wine 和Zoo 數(shù)據(jù)集上的實驗結(jié)果，從中可以看出：SBGOA 特征選擇算法在上述3 個數(shù)據(jù)集上的收斂速度均快于其他4 種算法，并且搜索到的解優(yōu)于其他4 種算法。圖3（b）和（g）分別為5 種算法在Soybean-large 和Ionosphere 數(shù)據(jù)集上的實驗結(jié)果，從中可以看出：SBGOA 特征選擇算法在上述兩個數(shù)據(jù)集上均于1 次迭代后便搜索到了適應(yīng)度比其他4 種算法更低的解，并且始終能夠在后續(xù)的迭代過程中搜索到比其他算法更優(yōu)的解。圖3（d）為5 種算法在Clean1 數(shù)據(jù)集上的實驗結(jié)果，從中可以看出：SBGOA特征選擇算法在前4 次迭代過程中均搜索到了比其他4 種算法更優(yōu)的解，雖然在第5 至13 次迭代的過程中搜索到的解劣于BGWO 特征選擇算法，但迭代14次以后搜索到了比其他4 種算法更優(yōu)的解。圖3（c）和（h）分別為5 種算法在Arrhythmia 和Spectf 數(shù)據(jù)集上的實驗結(jié)果，從中可以看出：SBGOA 特征選擇算法在上述兩個數(shù)據(jù)集上分別迭代5 次、8 次時便搜索到明顯優(yōu)于其他4 種算法的解，并且在之后的迭代過程中仍然能搜索到適應(yīng)度更低的解。綜上可知，除去Clean1 數(shù)據(jù)集上第5 至13 次迭代的結(jié)果，SBGOA特征選擇算法在各個數(shù)據(jù)集上每次迭代后搜索到的解均優(yōu)于其他4 種算法。這表明相比于其他4 種算法，SBGOA 具有更優(yōu)的搜索性能。SBGOA 特征選擇算法在Breast Cancer、Wine、Zoo 3 個數(shù)據(jù)集上的收斂速度均快于其他4 種算法，通過表2 可知，Breast Cancer、Wine、Zoo 3 個數(shù)據(jù)集均為低維度數(shù)據(jù)集，這表明相比于其他4種算法，SBGOA特征選擇算法在低維度數(shù)據(jù)集上具有更快的收斂速度。在Arrhythmia和Spectf 數(shù)據(jù)集上，SBGOA 特征選擇算法不僅能在較少迭代次數(shù)的情況下搜索到明顯優(yōu)于其他4 種算法的解，而且后續(xù)的迭代過程中仍然能夠繼續(xù)搜索到適應(yīng)度更低的解，表明SBGOA 特征選擇算法的收斂性能優(yōu)于其他兩種算法。

綜合來說，從提高分類準(zhǔn)確率和降低特征數(shù)量方面、魯棒性方面、搜索性能和收斂性能方面對比5種算法，SBGOA 特征選擇算法的總體性能優(yōu)于其他4 種算法。

Fig.3 Line graphs of fitness of 5 algorithms with changing of the number of iterations圖3 5 種算法適應(yīng)度隨迭代次數(shù)變化折線圖

4 結(jié)束語

IBGOA 特征選擇算法通過引入新的二進制轉(zhuǎn)化策略，有效降低了特征選擇算法二進制轉(zhuǎn)換的盲目性；對IBGOA 特征選擇算法引入混合復(fù)雜進化方法后提出的SBGOA，將蝗蟲群體劃分子群并獨立進化，提高了算法的多樣性，降低了早熟收斂的概率。仿真實驗結(jié)果表明：IBGOA 特征選擇算法有效提高了數(shù)據(jù)集的分類準(zhǔn)確率，SBGOA 特征選擇算法進一步提高了特征選擇的全局搜索能力；與BGOA、IBGOA、BPSO 和BGWO 特征選擇算法相比，SBGOA特征選擇算法具有更好的性能。