基于精英個(gè)體劃分的變步長(zhǎng)螢火蟲算法的特征選擇方法

劉 磊，羅 蓉，尹 勝

(重慶郵電大學(xué) 先進(jìn)制造工程學(xué)院，重慶 400065)

0 引 言

特征選擇(feature selection)是機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘任務(wù)中，對(duì)于高維或冗余特征數(shù)據(jù)集采取的一種數(shù)據(jù)預(yù)處理方法[1]。特征選擇可以移除原數(shù)據(jù)集中冗余、不相關(guān)的噪音特征，從原數(shù)據(jù)集中獲取一個(gè)最優(yōu)的特征子集以提升機(jī)器學(xué)習(xí)模型的預(yù)測(cè)精度，同時(shí)最優(yōu)特征子集相較于原特征集具有更少的特征數(shù)據(jù)，利用其進(jìn)行機(jī)器學(xué)習(xí)模型的訓(xùn)練和預(yù)測(cè)可以極大地降低運(yùn)行時(shí)間與數(shù)據(jù)存儲(chǔ)方面的開銷[2]。機(jī)器學(xué)習(xí)領(lǐng)域中主要有2類特征選擇方式：過濾式(filter mode)和包裝式(wrapper mode)[3]。包裝式通常會(huì)取得比過濾式更好的特征選擇結(jié)果，包裝式比過濾式占用更長(zhǎng)運(yùn)算時(shí)間，在非海量數(shù)據(jù)規(guī)模且機(jī)器學(xué)習(xí)模型固定的情況下宜選用這種方式[4]。本文的特征選擇方法為包裝式的方法。特征選擇算法像基于貪心或完備思想的算法[5]雖可在原始數(shù)據(jù)集上找到最優(yōu)特征子集，但這些算法為找到全局最優(yōu)解需要付出高昂的計(jì)算代價(jià)[6]。特征選擇是一個(gè)0-1規(guī)劃的組合優(yōu)化問題[7]，被證明是NP(non-deterministic polynomial)難題[8]，而一些元啟發(fā)式或生物啟發(fā)式優(yōu)化算法已在求解此類NP難組合優(yōu)化問題中表現(xiàn)出了良好的性能[9]，其在解決特征選擇問題方面的研究[10-12]，近年來受到學(xué)術(shù)界越來越多的關(guān)注[13]，遺傳算法(simple genetic algorithm，SGA)[14-15]與離散粒子群優(yōu)化(binary particle swarm optimization，BPSO)[16-17]等傳統(tǒng)生物啟發(fā)式算法已成功用于特征選擇優(yōu)化。

螢火蟲算法(firefly algorithm，F(xiàn)A)是新型的生物啟發(fā)式群智能優(yōu)化算法[18]，F(xiàn)A因具有多目標(biāo)優(yōu)化能力[19]，使其被國(guó)內(nèi)外學(xué)者應(yīng)用于旅行商問題[20-21]、背包問題[22]、系統(tǒng)效能優(yōu)化[23]、特征選擇[24-27]等組合優(yōu)化問題的研究中。標(biāo)準(zhǔn)FA設(shè)置參數(shù)少，算法步驟和公式較簡(jiǎn)單，然而其步長(zhǎng)參數(shù)取值大小對(duì)其性能影響很大[22]，標(biāo)準(zhǔn)FA采用固定步長(zhǎng)設(shè)置，這使FA在優(yōu)化求解中全局最優(yōu)解發(fā)現(xiàn)率低、算法搜索易陷入局部最優(yōu)。對(duì)此，文獻(xiàn)[27]提出一種隨算法迭代次數(shù)增加而算法步長(zhǎng)逐漸減小的改進(jìn)策略，然而該步長(zhǎng)調(diào)整方式忽視了FA種群中螢火蟲個(gè)體在尋優(yōu)過程中的差異性，無(wú)法使個(gè)體自適應(yīng)調(diào)整尋優(yōu)步長(zhǎng)，且在算法迭代優(yōu)化的后期尋優(yōu)效率降低，這存在著尋優(yōu)局限性。因此，本文充分考慮了FA在尋優(yōu)過程中其種群內(nèi)個(gè)體的差異性，在遵循標(biāo)準(zhǔn)FA算法機(jī)理的基礎(chǔ)上，提出了基于精英個(gè)體劃分的變步長(zhǎng)FA(elite -individual -dipartition dynamic step firefly algorithm，EDSFA)，并將EDSFA進(jìn)行離散化實(shí)現(xiàn)，提出EDSFA的相應(yīng)離散化算法EDSBFA(elite -individual -dipartition dynamic step binary firefly algorithm，EDSBFA)用于機(jī)器學(xué)習(xí)任務(wù)中的特征選擇優(yōu)化，實(shí)驗(yàn)表明，在優(yōu)化特征選擇方面EDSBFA的總體性能優(yōu)于固定步長(zhǎng)BFA(binary firefly algorithm)、文獻(xiàn)[27]所提變步長(zhǎng)BFA以及傳統(tǒng)啟發(fā)式優(yōu)化算法SGA和BPSO。

1 精英個(gè)體劃分的變步長(zhǎng)FA

1.1 標(biāo)準(zhǔn)FA

標(biāo)準(zhǔn)FA算法原理：螢火蟲種群中的每只螢火蟲個(gè)體的位置代表待求解問題的一個(gè)可行解，即整個(gè)種群為原問題的解空間，螢火蟲自身亮度與待求解問題的目標(biāo)函數(shù)值相關(guān)，即螢火蟲亮度越強(qiáng)，對(duì)應(yīng)可行解的目標(biāo)函數(shù)值越佳。當(dāng)FA算法運(yùn)行時(shí)，熒光亮度較弱的螢火蟲被熒光亮度較強(qiáng)的螢火蟲吸引，并向其所處位置移動(dòng)，隨著算法的不斷迭代，種群中原先亮度較弱的螢火蟲持續(xù)不斷地移向亮度較強(qiáng)個(gè)體所處位置，最終種群中大多數(shù)螢火蟲將聚集在一個(gè)或多個(gè)亮度較強(qiáng)的螢火蟲周圍，當(dāng)螢火蟲間沒有亮度差異時(shí)算法收斂，而最亮螢火蟲所處位置代表問題的最優(yōu)解[19]。

在標(biāo)準(zhǔn)FA中，螢火蟲個(gè)體遵循以下3條規(guī)則：①所有個(gè)體無(wú)性別區(qū)分；②個(gè)體吸引力與自身亮度相關(guān)，較弱亮度的個(gè)體會(huì)被較強(qiáng)亮度的個(gè)體所吸引而向其移動(dòng)，最強(qiáng)亮度的個(gè)體將在解空間中隨機(jī)移動(dòng)；③待求問題的可行解的目標(biāo)函數(shù)值通常作為個(gè)體的亮度值。

1)螢火蟲的相對(duì)亮度為

Ι(γ)=Ι0e-γr2

(1)

(1)式中：r為螢火蟲之間的距離；γ為光強(qiáng)吸收系數(shù)，考慮了光在傳播過程中因空氣等介質(zhì)會(huì)有所損耗，可設(shè)為常數(shù)；I0為r=0時(shí)螢火蟲的熒光亮度，即自身熒光亮度，其值與目標(biāo)函數(shù)值有關(guān)，目標(biāo)函數(shù)值越優(yōu)，自身熒光亮度越強(qiáng)。

2)螢火蟲的吸引力為

β(r)=β0e-γr2

(2)

(2)式中，β0為r=0時(shí)螢火蟲的自身吸引力。

3)螢火蟲之間的距離為

(3)

(3)式中：若兩螢火蟲個(gè)體i和j分別位于xi和xj，它們之間的距離可用歐式距離rij表示；D為問題的解空間維度；xik，xjk分別表示第i與j只螢火蟲的位置向量xi,xj中第k維的分量。

螢火蟲的位置移動(dòng)為

xi(t+1)=xi(t)+β0*e-γrij2(xj(t)-

xi(t))+α*ε

(4)

發(fā)光亮度較弱的螢火蟲i將移向發(fā)光亮度較強(qiáng)的螢火蟲j，從而i的位置向量發(fā)生更新。

(4)式中，t指算法迭代計(jì)數(shù)。等號(hào)右端由3項(xiàng)因式構(gòu)成：第1項(xiàng)xi(t)表示螢火蟲i當(dāng)前所在解空間位置；第2項(xiàng)表示螢火蟲i向螢火蟲j移動(dòng)的距離；第3項(xiàng)α·ε為i向j移動(dòng)的過程中伴有的隨機(jī)擾動(dòng)，避免螢火蟲過早陷入局部最優(yōu)，其中，α為隨機(jī)移動(dòng)步長(zhǎng)，其取值為0～1，ε是由高斯分布、均勻分布或萊維飛行[28]所得到的隨機(jī)數(shù)向量。

1.2 基于精英個(gè)體劃分的變步長(zhǎng)策略

標(biāo)準(zhǔn)FA中螢火蟲位置移動(dòng)方式如(4)式，其中，移動(dòng)步長(zhǎng)α的引入是為了擴(kuò)大螢火蟲的移動(dòng)視野，提高螢火蟲種群的多樣性，避免算法早熟收斂。步長(zhǎng)參數(shù)α取值大小應(yīng)與具體解空間的搜索范圍相關(guān)，在較小搜索范圍內(nèi)α取值過大可能導(dǎo)致算法無(wú)法收斂；取值過小，隨機(jī)移動(dòng)距離極小，無(wú)法增加種群多樣性，不能起到擴(kuò)大搜索范圍或擴(kuò)大螢火蟲移動(dòng)視野、避免算法過早收斂的作用[22]。在標(biāo)準(zhǔn)FA中所有螢火蟲個(gè)體的步長(zhǎng)取統(tǒng)一固定值，不能根據(jù)實(shí)際搜索情況進(jìn)行調(diào)節(jié)，這具有很大的局限性。文獻(xiàn)[27]提出一種步長(zhǎng)α隨算法迭代次數(shù)增加而動(dòng)態(tài)減小的變步長(zhǎng)FA，相比標(biāo)準(zhǔn)FA擴(kuò)大了步長(zhǎng)α的調(diào)節(jié)范圍，在算法運(yùn)行初始階段能增強(qiáng)算法的隨機(jī)搜索能力，跳出局部最優(yōu)，算法迭代后期搜索的隨機(jī)性減弱，促使算法逐步收斂。該變步長(zhǎng)改進(jìn)策略沒有考慮螢火蟲個(gè)體在尋優(yōu)搜索中的差異性，在算法搜索中為所有個(gè)體設(shè)置一樣的步長(zhǎng)，在算法迭代后期由于步長(zhǎng)值被減到很小，難以使已處在局部最優(yōu)位置的大部分螢火蟲更進(jìn)一步擴(kuò)大尋優(yōu)視野，這極易使整個(gè)螢火蟲種群的搜索陷入局部最優(yōu)陷阱，另外算法跌代后期整個(gè)種群采取統(tǒng)一的小步長(zhǎng)值也降低了算法收斂的效率。對(duì)所有螢火蟲個(gè)體采取大步長(zhǎng)，能增強(qiáng)FA對(duì)解空間的全局搜索能力，但易跳過全局最優(yōu)而求解精度低；對(duì)所有個(gè)體采取小步長(zhǎng)，能增強(qiáng)FA在局部解空間的探索能力，但易使螢火蟲尋優(yōu)陷入局部最優(yōu)陷阱，且會(huì)降低算法求解效率。所以為每只螢火蟲個(gè)體的移動(dòng)單獨(dú)設(shè)置動(dòng)態(tài)變化的步長(zhǎng)是必要的。本文從螢火蟲種群的精英個(gè)體劃分角度出發(fā)，提出一種變步長(zhǎng)策略以提高FA的尋優(yōu)能力。

為了兼顧算法在解空間的全局搜索和局部探索能力，同時(shí)充分考慮每只螢火蟲的性能差異，本文提出如下的步長(zhǎng)調(diào)整策略：對(duì)每輪次算法迭代中種群里性能較好的精英個(gè)體增大其步長(zhǎng)，保持其全局移動(dòng)視野以搜索更大區(qū)域，提高了種群的多樣性，進(jìn)而降低搜索陷入局部最優(yōu)陷阱的風(fēng)險(xiǎn)；而對(duì)于當(dāng)前迭代輪次中的非精英個(gè)體減小其步長(zhǎng)，保持其在局部解空間的探索能力，小步長(zhǎng)值對(duì)精確搜索有利，能提高算法求解精度和促使種群逐步收斂?；诰€(gè)體劃分的變步長(zhǎng)設(shè)置具體表示為

αi(t+1)=

(5)

αi(t+1)=α0,αi(t)>1

(6)

(5)—(6)式中：αi(t+1)表示第i只螢火蟲個(gè)體在第t+1次算法迭代時(shí)的步長(zhǎng)；MaxGen指設(shè)置的算法最大迭代次數(shù)；α0表示初始統(tǒng)一步長(zhǎng)值；a為步長(zhǎng)增大的隨機(jī)加速度；a取值為[1,MaxGen/2]的隨機(jī)整數(shù)；Ii為個(gè)體i的熒光亮度；Ibest為當(dāng)前種群中最佳個(gè)體的熒光亮度；θ為用于劃分精英個(gè)體的閾值，θ為[0.85,0.95]的常數(shù)值，由(5)式知當(dāng)個(gè)體i的亮度大于當(dāng)前種群中最佳個(gè)體亮度值的θ倍時(shí)，便視其為精英螢火蟲個(gè)體，增大其步長(zhǎng)值，否則線性減小其步長(zhǎng)值，如果i的步長(zhǎng)經(jīng)過增大調(diào)整后已大于1，則按(6)式所示將其步長(zhǎng)重置為初始步長(zhǎng)值。對(duì)于(5)式中步長(zhǎng)增大的隨機(jī)加速度a的引入可使螢火蟲個(gè)體間步長(zhǎng)的擴(kuò)大趨于多樣化、隨機(jī)性，這也促進(jìn)了種群的多樣性變化，避免了種群的早熟收斂，另外a可結(jié)合具體解空間的搜索范圍進(jìn)行滑動(dòng)窗口取值，使步長(zhǎng)調(diào)節(jié)更具靈活性。

2 基于EDSBFA的特征選擇方法

2.1 螢火蟲位置向量編碼

特征選擇實(shí)際上是從原始數(shù)據(jù)集的M個(gè)數(shù)據(jù)特征中選擇N個(gè)特征后組成一個(gè)特征子集(M>N)，進(jìn)而用該特征子集中的特征優(yōu)化后續(xù)的數(shù)據(jù)分析處理，對(duì)于每個(gè)待選特征而言只存在“入選”或“落選”2種狀態(tài)，因此，可將螢火蟲個(gè)體的位置向量每一維的索引序號(hào)對(duì)應(yīng)于原數(shù)據(jù)集各維特征的索引序號(hào)，并將個(gè)體向量編碼為每一維元素僅為‘0’或‘1’的二元離散向量，其中，元素為0表示落選，元素為1表示入選，向量維度等于原數(shù)據(jù)集特征維度。例如螢火蟲i當(dāng)前位置向量為Xi=[0,1,0,1,0,1,0,1,1,0]，其向量維度為10，表示原數(shù)據(jù)集的10個(gè)數(shù)據(jù)特征中入選特征的索引序號(hào)分別為“2,4,6,8,9”，該索引序號(hào)所對(duì)應(yīng)特征即被選擇。

2.2 目標(biāo)函數(shù)定義

特征選擇的目標(biāo)是從原始數(shù)據(jù)集選擇一個(gè)特征數(shù)量較少的特征子集，利用該特征子集中的特征做數(shù)據(jù)挖掘，使機(jī)器學(xué)習(xí)模型獲取更好的預(yù)測(cè)準(zhǔn)確率。目標(biāo)函數(shù)應(yīng)考慮選擇的特征數(shù)量和預(yù)測(cè)準(zhǔn)確率這2個(gè)因素，當(dāng)所選特征數(shù)量越少和模型預(yù)測(cè)準(zhǔn)確率越高時(shí)，目標(biāo)函數(shù)值越優(yōu)，本文中螢火蟲的自身亮度等于螢火蟲位置向量的目標(biāo)函數(shù)值，所以目標(biāo)函數(shù)值越優(yōu)，螢火蟲的亮度越強(qiáng)。目標(biāo)函數(shù)定義為

f(accu,num|Xi)=

(7)

(7)式中：Xi為螢火蟲個(gè)體i的位置向量；accu為個(gè)體向量對(duì)應(yīng)特征子集的預(yù)測(cè)準(zhǔn)確率；num為該特征子集中入選特征的數(shù)量；k為特征數(shù)量num的權(quán)重，本文實(shí)驗(yàn)中k=0.5。

2.3 EDSFA離散化為EDSBFA

由于特征選擇問題是組合優(yōu)化問題，屬于離散優(yōu)化范疇，本文螢火蟲的位置向量編碼是0，1二元離散編碼，標(biāo)準(zhǔn)FA中對(duì)螢火蟲的距離、位置移動(dòng)的定義只適用于連續(xù)優(yōu)化領(lǐng)域而不適用于離散優(yōu)化，故須對(duì)螢火蟲的距離、位置移動(dòng)做適用于離散化操作的重新定義。對(duì)于提出的基于精英個(gè)體劃分的變步長(zhǎng)螢火蟲算法(EDSFA)，本文采用了與文獻(xiàn)[27]一樣的螢火蟲算法離散化方式，將EDSFA離散化為EDSBFA。

定義1 螢火蟲i與j之間的距離。由于本文螢火蟲位置向量被編碼為0，1二元離散向量，所以2個(gè)螢火蟲之間的距離或差距使用漢明距離描述比使用原FA中的歐式距離更適合，漢明距離準(zhǔn)確刻畫了2個(gè)向量的差異性，比歐式距離的計(jì)算開銷少，提高了算法運(yùn)行效率。兩螢火蟲個(gè)體間的歸一化漢明距離定義為

(8)

(8)式中：?指XOR異或操作；d為個(gè)體向量的維度。螢火蟲之間的吸引力β通過(2)式計(jì)算，其中距離r使用上述定義的歸一化漢明距離。

定義2 螢火蟲的離散化移動(dòng)。當(dāng)螢火蟲i向亮度更強(qiáng)更有吸引力的螢火蟲j移動(dòng)時(shí)，個(gè)體i的位置向量每一維元素值將做決策是否發(fā)生改變，本文將個(gè)體位置向量中每一維元素值的改變分2步進(jìn)行：①吸引移動(dòng)，如(9)式，對(duì)應(yīng)于(4)式右端第2項(xiàng)因式所作操作；②隨機(jī)游走，如(10)式，對(duì)應(yīng)于(4)式右端第3項(xiàng)因式所作操作。其中，rand(0,1)指0～1的隨機(jī)數(shù),αi為個(gè)體i的當(dāng)前步長(zhǎng),vik是個(gè)體i的位置向量的第k維分量在“吸引移動(dòng)”后的中間變量。

(9)

(10)

2.4 基于EDSBFA的包裝式特征選擇方法流程

包裝式特征選擇，使用優(yōu)化算法從原始數(shù)據(jù)集中選擇特征，產(chǎn)生一系列待評(píng)價(jià)特征子集，將各個(gè)特征子集對(duì)應(yīng)的特征數(shù)據(jù)送入機(jī)器學(xué)習(xí)分類器進(jìn)行分類器的訓(xùn)練，并用訓(xùn)練好的分類器做分類預(yù)測(cè)，經(jīng)過數(shù)次迭代優(yōu)化，最終將能使分類器獲得最好精度和泛化能力的特征子集輸出?；诰€(gè)體劃分的變步長(zhǎng)離散FA(EDSBFA)的包裝式特征選擇方法流程如圖1。

3 實(shí)驗(yàn)與分析

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

使用python3編程語(yǔ)言分別實(shí)現(xiàn)了本文提出的基于精英個(gè)體劃分的變步長(zhǎng)離散螢火蟲算法EDSBFA、固定步長(zhǎng)離散螢火蟲算法BFA、文獻(xiàn)[27]中所提變步長(zhǎng)離散螢火蟲算法IBFA，EDSBFA中除精英個(gè)體劃分閾值θ和步長(zhǎng)增大的隨機(jī)加速度a之外，初始步長(zhǎng)值α0、其他參數(shù)設(shè)置和BFA一樣均同IBFA[27]一致，如表1。表1中，所有算法的最大迭代次數(shù)MaxGen=100,t為當(dāng)前迭代計(jì)數(shù)，Randint表示隨機(jī)整數(shù)。

實(shí)驗(yàn)所用機(jī)器學(xué)習(xí)分類器與文獻(xiàn)[14，16]一致，為k-近鄰算法(k-nearest neighbor,KNN)分類器，其中，K=1,將python的Sklearn庫(kù)中KNN應(yīng)用接口與EDSBFA，BFA，IBFA的算法代碼進(jìn)行包裝融合，分別開發(fā)了基于EDSBFA，BFA，IBFA的包裝式特征選擇程序EDSBFA-KNN，BFA-KNN，IBFA-KNN，并使用文獻(xiàn)[14，16]中測(cè)試所用到的7個(gè)UCI分類數(shù)據(jù)集對(duì)所開發(fā)的特征選擇程序進(jìn)行了實(shí)驗(yàn)測(cè)試，為了保證測(cè)試結(jié)果的客觀準(zhǔn)確，由螢火蟲算法產(chǎn)生的特征子集使用KNN分類器的10折交叉驗(yàn)證方式進(jìn)行評(píng)價(jià)，且特征選擇程序在每個(gè)數(shù)據(jù)集上單獨(dú)運(yùn)行各30次，實(shí)驗(yàn)所得平均分類準(zhǔn)確率、選擇特征的平均數(shù)量與文獻(xiàn)[14]中基于遺傳算法(simple genetic algorithm,SGA)和文獻(xiàn)[16]中基于離散粒子群算法(binary particle swarm optimization,BPSO)優(yōu)化特征選擇所得KNN分類結(jié)果以及與單一KNN分類結(jié)果進(jìn)行了對(duì)比分析。此外，在UCI高維度數(shù)據(jù)集LSVT(LSVT為醫(yī)療語(yǔ)音數(shù)據(jù)集，共126個(gè)分類樣本，每個(gè)樣本多達(dá)309個(gè)特征)上進(jìn)一步測(cè)試了EDSBFA，BFA，IBFA的性能，每個(gè)算法程序單獨(dú)運(yùn)行20次。實(shí)驗(yàn)環(huán)境為Win10系統(tǒng) ，Inter (R) Core (TM) i3-3120 CPU 2.50 GHz, 8.0 GB內(nèi)存的PC機(jī)。

表1 參數(shù)設(shè)置Tab.1 Parameter setting

3.2 結(jié)果分析

在7個(gè)UCI分類數(shù)據(jù)集上，包裝式特征選擇方法EDSBFA-KNN，IBFA-KNN，BFA-KNN，SGA-KNN[14]，BPSO-KNN[16]和單一KNN取得的平均分類預(yù)測(cè)準(zhǔn)確率與特征數(shù)量如表2，其中，D為數(shù)據(jù)集特征維度；N為各方法選擇的平均特征數(shù)量；A為各方法獲得的平均分類準(zhǔn)確率，最少的特征數(shù)量與最高的分類準(zhǔn)確率為加粗顯示的數(shù)值。由表2可知，除SGA-KNN在數(shù)據(jù)集Segmentation，WDBC上取得的分類準(zhǔn)確率比使用單一KNN的分類結(jié)果差之外，SGA-KNN在其他5個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率比單一KNN要高，而BPSO-KNN，BFA-KNN，IBFA-KNN，EDSBFA-KNN在全部數(shù)據(jù)集上均取得了比單一KNN更高的分類準(zhǔn)確率，說明了基于優(yōu)化算法(SGA，BPSO，BFA，IBFA，EDSBFA)構(gòu)造最優(yōu)特征子集，KNN(K=1)利用最優(yōu)特征子集的特征數(shù)據(jù)進(jìn)行分類預(yù)測(cè)可以顯著改善其在數(shù)據(jù)集上的預(yù)測(cè)精度。Vowel數(shù)據(jù)集的特征維度較小(D=10)，數(shù)據(jù)集較簡(jiǎn)單，SGA-KNN，BPSO-KNN，BFA-KNN，IBFA-KNN，EDSBFA-KNN均取得了99%以上的分類精度，而IBFA-KNN，EDSBFA-KNN在Wine數(shù)據(jù)集上的分類準(zhǔn)確率和選擇的特征數(shù)量相同且比其他方法取得的結(jié)果要優(yōu)，此外EDSBFA-KNN在Vehicle，Segmentation，WDBC，Ionosphere，Sonar數(shù)據(jù)集上均取得了最高的分類準(zhǔn)確率，且其在大多數(shù)的數(shù)據(jù)集上選擇的特征數(shù)量偏少。綜合結(jié)果表明本文所提算法EDSBFA優(yōu)化特征選擇的能力要強(qiáng)于其他對(duì)比算法。

表2 各方法在數(shù)據(jù)集上的平均分類準(zhǔn)確率與平均選擇特征數(shù)量Tab.2 Average values of classification accuracy and number of selected features through each method

表3 EDSBFA，IBFA，BFA在 LSVT上的測(cè)試結(jié)果Tab.3 Test results of EDSBFA, IBFA, BFA for LSVT

在擁有高維度特征的LSVT數(shù)據(jù)集上進(jìn)一步測(cè)試了EDSBFA，IBFA，BFA的性能，實(shí)驗(yàn)結(jié)果如表3，其中，D，N，A的含義同表2，T指算法程序運(yùn)行時(shí)間，單位為s。由于LSVT的候選特征空間相比前7個(gè)測(cè)試數(shù)據(jù)集大得多，搜索算法早熟收斂的風(fēng)險(xiǎn)相對(duì)較小，故EDSBFA的步長(zhǎng)增大的幅度不宜過大，其隨機(jī)加速度a應(yīng)取偏小值，其取值為[1,10]的隨機(jī)整數(shù)。由表3中T列數(shù)據(jù)知，EDSBFA-KNN比BFA-KNN、IBFA-KNN要省分別近21%和58%的時(shí)間開銷，由表3中A列(括號(hào)內(nèi)為取得的最高分類準(zhǔn)確率)數(shù)據(jù)知，BFA-KNN的分類精度遠(yuǎn)不如IBFA-KNN，EDSBFA-KNN的分類精度，其最高分類準(zhǔn)確率沒有達(dá)到90%以上，而IBFA-KNN，EDSBFA-KNN的平均分類準(zhǔn)確率都已達(dá)到了95%以上，且IBFA-KNN的最高分類準(zhǔn)確率大于EDSBFA-KNN的最高分類準(zhǔn)確率，但EDSBFA-KNN的平均分類準(zhǔn)確率要高于IBFA-KNN的平均分類準(zhǔn)確率，且EDSBFA-KNN選擇的最優(yōu)特征數(shù)量最少，以上表明在高維度數(shù)據(jù)集上基于EDSBFA優(yōu)化特征選擇的精度要比基于BFA，IBFA的更優(yōu)、更穩(wěn)定，且EDSBFA算法運(yùn)行效率更高。圖2～圖7分別是LSVT測(cè)試中BFA，IBFA，EDSBFA的目標(biāo)函數(shù)值(熒光亮度)、分類準(zhǔn)確率、選擇的特征數(shù)量在100次算法迭代搜索過程中的變化情況。如圖2，BFA在迭代中步長(zhǎng)固定，無(wú)法自適應(yīng)調(diào)節(jié)，導(dǎo)致搜索趨于隨機(jī)化，整個(gè)種群難以持續(xù)獲得更好的解，而使算法陷入局部最優(yōu)或是無(wú)法收斂。圖3中，IBFA在迭代中整個(gè)種群雖能朝著優(yōu)化方向進(jìn)行搜索，可IBFA 未區(qū)分精英與非精英螢火蟲個(gè)體，這使螢火蟲個(gè)體在解空間中無(wú)法根據(jù)自身狀況進(jìn)行差異化搜索，這使找到更好解的效率變低。從圖4可知，EDSBFA在迭代過程中最佳螢火蟲個(gè)體的目標(biāo)函數(shù)值(熒光亮度)和整個(gè)螢火蟲種群的平均目標(biāo)函數(shù)值都在持續(xù)平穩(wěn)地獲得提升，在迭代25次左右就取得比BFA，IBFA迭代100次時(shí)更高的目標(biāo)值，且隨著迭代優(yōu)化的繼續(xù)呈現(xiàn)出算法收斂趨勢(shì)(最優(yōu)值等于平均值時(shí)算法收斂)，EDSBFA的收斂速度快于BFA，IBFA,且最終獲得更優(yōu)的解。

從圖5～圖7可知，BFA在迭代的后期由于算法陷入局部最優(yōu)或是搜索偏向隨機(jī)化導(dǎo)致難以取得更優(yōu)的分類準(zhǔn)確率和特征子集。IBFA在迭代中可持續(xù)獲得更高的分類準(zhǔn)確率，但過程較緩慢，且選擇的最優(yōu)特征數(shù)量波動(dòng)性大。EDSBFA隨著迭代能持續(xù)且快速地獲得更高的分類準(zhǔn)確率和含更少數(shù)量特征的特征子集，直至算法收斂，其總體性能明顯優(yōu)于BFA，IBFA。

4 結(jié)束語(yǔ)

本文提出一種新的改進(jìn)型螢火蟲算法EDSFA，并通過重新定義螢火蟲距離和移動(dòng)方式，給出了改進(jìn)算法的離散化實(shí)現(xiàn)EDSBFA，以適用解決特征選擇問題，將EDSBFA與KNN分類器結(jié)合以包裝式實(shí)現(xiàn)了特征選擇優(yōu)化，在UCI數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文所提算法EDSBFA在優(yōu)化特征選擇效果和運(yùn)行效率上性能優(yōu)越，所提改進(jìn)螢火蟲算法使用基于精英個(gè)體劃分的變步長(zhǎng)策略，考慮了螢火蟲個(gè)體差異性而進(jìn)行自適應(yīng)尋優(yōu)，算法兼顧了解空間的全局搜索和局部探索，降低算法陷入局部最優(yōu)的風(fēng)險(xiǎn)，同時(shí)使算法朝著種群優(yōu)化的方向搜索，保證了算法的快速收斂。本文算法改進(jìn)沒有使用交叉、變異等復(fù)雜手段，但取得了理想效果。螢火蟲算法的參數(shù)取值大小對(duì)算法的性能影響很大，不宜使用固定值，未來在本文變步長(zhǎng)改進(jìn)策略的基礎(chǔ)上，將對(duì)FA的光強(qiáng)吸收系數(shù)γ進(jìn)行自適應(yīng)改進(jìn)。另外基于啟發(fā)式算法的包裝式特征選擇優(yōu)化方法運(yùn)行效率低、耗時(shí)，未來可研究基于算法并行化的改進(jìn)方法以提升效率。