改進(jìn)混合二進(jìn)制蝗蟲(chóng)優(yōu)化特征選擇算法

趙澤淵，代永強(qiáng)

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

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

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

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

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

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

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

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

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

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

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

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

2 改進(jìn)的混合二進(jìn)制蝗蟲(chóng)優(yōu)化特征選擇算法

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

2.1 基本二進(jìn)制蝗蟲(chóng)優(yōu)化特征選擇算法

2.1.1 基本二進(jìn)制蝗蟲(chóng)優(yōu)化算法

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

（1）種群初始化

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

（2）更新策略

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

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

最后，使用式（8）得出更新后蝗蟲(chóng)個(gè)體的位置[16]。

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

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

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

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

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

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

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

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

2.2 改進(jìn)二進(jìn)制蝗蟲(chóng)優(yōu)化特征選擇算法

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

2.2.1 改進(jìn)策略

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

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

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

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

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

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

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

2.2.2 改進(jìn)策略性能驗(yàn)證

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

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

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

（3）對(duì)于更新前后的三個(gè)蝗蟲(chóng)種群，分別計(jì)算其群體中兩兩蝗蟲(chóng)之間的距離，并計(jì)算所有蝗蟲(chóng)之間的平均距離dis。

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

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

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

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

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

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

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

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

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

2.3 混合二進(jìn)制蝗蟲(chóng)優(yōu)化特征選擇算法

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

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

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

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

2.3.2 改進(jìn)策略

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

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

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

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

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

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

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

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

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

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

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

2.4 特征子集評(píng)價(jià)函數(shù)

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

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

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

3 仿真實(shí)驗(yàn)和結(jié)果分析

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

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

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

從表3 BPSO 特征選擇算法、BGWO 特征選擇算法與SBGOA 特征選擇算法可以看出：對(duì)于8 個(gè)數(shù)據(jù)集，SBGOA 特征選擇算法的平均適應(yīng)度總是低于其他兩種算法，說(shuō)明SBGOA 特征選擇算法在降低特征數(shù)量與提高分類準(zhǔn)確率的性能優(yōu)于其他兩種算法。標(biāo)準(zhǔn)偏差反映了算法魯棒性的優(yōu)劣，即標(biāo)準(zhǔn)偏差的值越小，對(duì)應(yīng)算法的魯棒性越優(yōu)。表4 為5 種算法對(duì)應(yīng)8 個(gè)數(shù)據(jù)集的標(biāo)準(zhǔn)偏差排名與8 個(gè)數(shù)據(jù)集上的平均標(biāo)準(zhǔn)偏差，每個(gè)數(shù)據(jù)集對(duì)應(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 個(gè)數(shù)據(jù)集上的標(biāo)準(zhǔn)偏差排名參差不齊，但從平均標(biāo)準(zhǔn)偏差來(lái)看，兩者標(biāo)準(zhǔn)偏差整體相差很小。表明兩者的魯棒性并無(wú)較大的差別。說(shuō)明本文對(duì)BGOA 特征選擇算法的改進(jìn)并沒(méi)有提升算法的魯棒性。

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

從表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 個(gè)數(shù)據(jù)上，SBGOA 特征選擇算法的標(biāo)準(zhǔn)偏差排名均高于其余兩種算法，并且SBGOA 特征選擇算法的平均標(biāo)準(zhǔn)偏差明顯低于其余兩種算法。表明SBGOA 特征選擇算法的魯棒性優(yōu)于BPSO 特征選擇算法與BGWO 特征選擇算法。

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

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

綜合來(lái)說(shuō)，從提高分類準(zhǔn)確率和降低特征數(shù)量方面、魯棒性方面、搜索性能和收斂性能方面對(duì)比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é)束語(yǔ)

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