二進(jìn)制正交電魚優(yōu)化算法的特征選擇

王丹雨，劉 昊，丁桂艷

（遼寧科技大學(xué) 理學(xué)院，遼寧 鞍山 114051）

電魚優(yōu)化算法（Electric fish optimization algorithm，EFO）是由Yilmaz等［1］在2019年提出的元啟發(fā)式算法，其靈感來(lái)源于電魚的獵物位置和通信行為。該算法因簡(jiǎn)單且易于實(shí)現(xiàn)而受青睞。為了進(jìn)一步提升EFO算法的性能，一些改進(jìn)算法應(yīng)運(yùn)而生。例如，Kowdiki等［2］在2021年提出的EWOA算法，通過(guò)混合EFO和鯨魚優(yōu)化算法（Whale optimization algorithm，WOA）來(lái)增強(qiáng)手勢(shì)的分割 和 分類。Ibrahim等［3］在2021年提出 的

EFOAOA（Electric fish optimization algorithm arithmetic optimization algorithm，EFOAOA）算法能以高精度和高效率識(shí)別最重要的特征。

正交設(shè)計(jì)（Orthogonal design，OD）是一種實(shí)驗(yàn)性設(shè)計(jì)，其可以通過(guò)相對(duì)少量的實(shí)驗(yàn)找到不同因子的最佳組合水平［4］。Zhang等［5］于1996年提出正交交叉（Orthogonal crossover，OX），該方法將遺傳算法（Genetic algorithm，GA）的一些主要步驟視為“實(shí)驗(yàn)”，并且使用實(shí)驗(yàn)設(shè)計(jì)方法設(shè)計(jì)遺傳算子。OX運(yùn)算可以在方案定義的區(qū)域中執(zhí)行系統(tǒng)搜索。為了解決連續(xù)變量的全局?jǐn)?shù)值優(yōu)化問(wèn)題，Leung等［6］在2002年提出一種量化技術(shù)來(lái)補(bǔ)充正交設(shè)計(jì)。

特征選擇（Feature selection，F(xiàn)S）是模式識(shí)別中關(guān)鍵的數(shù)據(jù)預(yù)處理步驟，常用于解決高維數(shù)據(jù)集問(wèn)題。FS具有提高預(yù)測(cè)模型的計(jì)算效率、降低任務(wù)難度、減少特征數(shù)量等優(yōu)勢(shì)。因此，F(xiàn)S已經(jīng)成為機(jī)器學(xué)習(xí)的研究熱點(diǎn)，并廣泛應(yīng)用于不同領(lǐng)域，如人體動(dòng)作檢測(cè)［7］、文本分類［8］、COVID-19 CT圖像分類［9］、數(shù)據(jù)分析問(wèn)題［10］等。近年來(lái)，元啟發(fā)式算法被廣泛應(yīng)用于FS。例如，吳曉燕等［11］提出一種基于樽海鞘群與粒子群混合優(yōu)化算法的特征選擇方法；林煒星等［12］提出對(duì)稱不確定性和粒子群的高維特征選擇算法來(lái)解決特征選擇問(wèn)題。

針對(duì)現(xiàn)有的特征選擇方法存在計(jì)算效率低和收斂速度慢等不足，本文提出二進(jìn)制正交電魚優(yōu)化（Binary quantization orthogonal crossover electric fish optimization，BQOXEFO）特征選擇方法。首先，通過(guò)二進(jìn)制機(jī)制描述特征，并構(gòu)造基于分類精度和所選特征數(shù)量的適應(yīng)度函數(shù)，同時(shí)，采用K最近鄰分類器（K-nearest neighbor，KNN）對(duì)數(shù)據(jù)進(jìn)行分類。其次，通過(guò)在EFO中引入帶有量化的正交交叉策略提高算法的收斂速度和精度。第三，采用動(dòng)態(tài)邊界機(jī)制來(lái)提高算法的收斂速度。第四，使用基于正弦的主動(dòng)電定位更新策略，通過(guò)改變其移動(dòng)方向幫助個(gè)體跳出局部最優(yōu)。通過(guò)對(duì)比實(shí)驗(yàn)驗(yàn)證該算法的性能。

1 電魚優(yōu)化算法

1.1 種群初始化

首先，在dim維度搜索空間中隨機(jī)初始化N個(gè)個(gè)體構(gòu)成初始種群

個(gè)體在第t代的頻率值ft g是一個(gè)關(guān)于適應(yīng)度值的函數(shù)

式中：fmin和fmax分別表示最小和最大的頻率值；分別是個(gè)體在第t代的最差和最佳適應(yīng)度值；fitt

g則是第g個(gè)個(gè)體在第t代的適應(yīng)度值。

第g個(gè)個(gè)體的振幅值（Ag）計(jì)算式其中，α∈[0,1]是確定先前振幅值大小的常數(shù)，在本文中α=0.989。

1.2 主動(dòng)電定位

在EFO算法中，有效范圍的計(jì)算式

個(gè)體g和個(gè)體m之間的距離通過(guò)笛卡爾距離計(jì)算

在主動(dòng)電定位區(qū)域中，個(gè)體至少有一個(gè)鄰居的情況下，EFO算法位置更新方式否則（即S=?），EFO算法位置更新方式

式中：m表示從第g個(gè)個(gè)體的鄰居集合中隨機(jī)選擇的一個(gè)個(gè)體（即m∈S且Dgm≤rg）；φ∈[-1,1]為一個(gè)服從均勻分布的隨機(jī)數(shù)為第g個(gè)個(gè)體的侯選位置為第m個(gè)個(gè)體的位置；為第g個(gè)個(gè)體的當(dāng)前位置。

1.3 被動(dòng)電定位

計(jì)算第m個(gè)（即m∈NP）處于被動(dòng)模式個(gè)體感知到第g個(gè)（即m∈NA）處于主動(dòng)模式個(gè)體的概率

此處采用輪盤賭的方式，根據(jù)式（8）從NA中

選擇M個(gè)個(gè)體，確定其參考位置

并生成其新的位置

為了避免頻率較高的個(gè)體執(zhí)行被動(dòng)電定位的情況發(fā)生，該算法確定要修改的參數(shù)

其中，randd(0,1)是服從均勻分布的隨機(jī)數(shù)。

為了增加種群的多樣性，被動(dòng)電定位的最后一步是修改第g個(gè)個(gè)體的參數(shù)

其中，rand1(0,1)和rand2(0,1)均為服從均勻分布的隨機(jī)數(shù)。

如果個(gè)體超出搜索空間的邊界，則將會(huì)對(duì)其進(jìn)行越界處理

2 二進(jìn)制正交電魚優(yōu)化算法的特征選擇

2.1 特征選擇

2.1.1 特征初始化 BQOXEFO進(jìn)行初始化參數(shù)，并生成特征選擇問(wèn)題的初始種群。在計(jì)算目標(biāo)函數(shù)之前，將每個(gè)解向量轉(zhuǎn)換為僅包含0和1的二進(jìn)制形式

其中，1表示該特征被選擇，0表示不相關(guān)的特征而被忽略。

2.1.2 適應(yīng)度函數(shù) 計(jì)算每個(gè)解的適應(yīng)度函數(shù)，隨后執(zhí)行更新個(gè)體的過(guò)程，直到達(dá)到停止條件。適應(yīng)度函數(shù)由兩個(gè)客觀指標(biāo)所構(gòu)成，即分類的精度和所選特征的數(shù)量，并設(shè)置權(quán)重，計(jì)算式

式中：ACC是通過(guò)正確分類的實(shí)例數(shù)量除以實(shí)例總數(shù)計(jì)算得到的分類精度，ACCmax為m次重復(fù)實(shí)驗(yàn)中精度最高的一次；Lf為所選特征子集的長(zhǎng)度；Lt為特征總數(shù)；ωf為權(quán)重因子，其值在（0，1）之間。ωf是控制分類精度和選擇特征數(shù)量的重要權(quán)重，權(quán)重因子通常設(shè)置為接近1的值［13］，本文將ωf設(shè)置為0.8。

本文使用K分類器，其中k=3。KNN算法是數(shù)據(jù)挖掘分類技術(shù)中最簡(jiǎn)單的方法之一，每個(gè)樣本都用它最接近的k個(gè)鄰居來(lái)代表，而不是靠判別類域的方法確定所屬類別，對(duì)于類域交叉或重疊較多的待分樣本集來(lái)說(shuō)，KNN方法較其他方法更為適合。

2.2 基于量化技術(shù)的正交交叉策略

將量化技術(shù)和正交交叉設(shè)計(jì)應(yīng)用于EFO算法，從而提高EFO算法的搜索能力。在BQOXEFO的每一代中，只選擇一個(gè)個(gè)體執(zhí)行一次QOX（Quantization orthogonal crossover）策略，以節(jié)省計(jì)算成本。通過(guò)正交交叉操作，一個(gè)個(gè)體可以生成9個(gè)候選解，并且在整個(gè)種群中找出并替換比生成的9個(gè)候選解差的9個(gè)解，這不僅有助于增強(qiáng)種群的多樣性，還可以提高算法的收斂速度。將此策略分別添加在主動(dòng)電定位、被動(dòng)電定位和整體的更新式中，實(shí)驗(yàn)結(jié)果表明，添加到整體階段可以實(shí)現(xiàn)該策略的優(yōu)勢(shì)最大。

將此策略添加到算法的整體階段，位置更新公式

式中：rand表示（0，1）區(qū)間上服從均勻分布的隨機(jī)數(shù)；Xnew為新候選解的位置；s1,s2,s3分別為隨機(jī)選擇的三個(gè)個(gè)體，其中，s1,s2,s3∈(1,N)；Xs1,Xs2,Xs3分別為第s1,s2,s3個(gè)體對(duì)應(yīng)的當(dāng)前位置。

2.3 動(dòng)態(tài)邊界機(jī)制

為了提高算法的收斂速度，采用動(dòng)態(tài)邊界機(jī)制，分為主動(dòng)電定位的動(dòng)態(tài)邊界和被動(dòng)電定位的動(dòng)態(tài)邊界。首先，在主動(dòng)電定位中，將下邊界更改為總體的每個(gè)維度的最小值，上邊界更改為總體的每個(gè)維度的最大值

其次，在被動(dòng)電定位中，將下邊界更改為全局最優(yōu)解的最小值，上邊界更改為全局最優(yōu)解的最大值

2.4 基于正弦的主動(dòng)電定位更新策略

基于正弦的主動(dòng)電定位更新策略用于幫助個(gè)體通過(guò)改變其移動(dòng)方向而跳出局部最優(yōu)。在主動(dòng)電定位區(qū)域中至少存在一個(gè)鄰居的情況下，BQOXEFO算法使用公式（21）更新其位置；否則（即S=?），使用公式（22）。

其中，m表示從第g個(gè)個(gè)體的鄰居集合中隨機(jī)選擇的一個(gè)個(gè)體（即m∈S和Dgm≤rg）。

2.5 BQOXEFO算法的實(shí)現(xiàn)步驟

步驟1：初始化種群N并將每個(gè)搜索個(gè)體轉(zhuǎn)換為二進(jìn)制；計(jì)算出對(duì)應(yīng)的適應(yīng)度值。

步驟2：初始化頻率f和振幅A，并根據(jù)頻率值確定個(gè)體執(zhí)行主動(dòng)電定位或被動(dòng)電定位。

步驟3：主動(dòng)電定位階段：通過(guò)式（6）（7）（17）（18）（21）（22）等更新個(gè)體的位置信息并將其二進(jìn)制化。

步驟4：被動(dòng)電定位階段：通過(guò)式（9）（10）（19）（20）等更新個(gè)體的位置信息并將其二進(jìn)制化。

步驟5：計(jì)算所有個(gè)體的適應(yīng)度值。

步驟6：基于量化的正交交叉策略：執(zhí)行QOX策略。

步驟7：若不滿足終止條件，返回步驟3。否則終止算法，輸出最優(yōu)解。

3 實(shí)驗(yàn)結(jié)果與統(tǒng)計(jì)分析

3.1 數(shù)據(jù)集與對(duì)比算法

選用UCI機(jī)器學(xué)習(xí)庫(kù)［14］中的5個(gè)基準(zhǔn)數(shù)據(jù)集進(jìn)行測(cè)試，數(shù)據(jù)集信息見表1。所采用的數(shù)據(jù)集中都不存在缺失值。

表1 數(shù)據(jù)集信息Tab.1 Dataset information

為了驗(yàn)證BQOXEFO算法的性能，將其與4種算法進(jìn)行比較，其中包括原始的EFO算法和3種進(jìn)化算法：OSA（Owl search algorithm）［15］、PSO（Parti-cle swarm optimization）［16］和SOS（Symbiotic organisms search）［17］。所有算法采用相同的固定參數(shù)，種群規(guī)模設(shè)置為50，每種算法獨(dú)立運(yùn)行10次，最大計(jì)算次數(shù)設(shè)置為3 000次。

3.2 BQOXEFO與其他算法的比較

BQOXEFO與其他算法在數(shù)據(jù)集上的對(duì)比結(jié)果呈現(xiàn)在表2中。將算法多次運(yùn)行后的平均值（Mean）、標(biāo)準(zhǔn)差（Std）、最大值（Max）和平均特征選擇數(shù)（ASS）分別作對(duì)比。其中ASS的計(jì)算式

表2 BQOXEFO與其他算法的實(shí)驗(yàn)結(jié)果Tab.2 Experimental results of BQOXEFO and other algorithms

式中：length(X*)為所選的特征子集的長(zhǎng)度；R為算法在每個(gè)數(shù)據(jù)集上的重復(fù)運(yùn)行的次數(shù)。

算法按均值從最好到最差進(jìn)行排序。均值越大，排名越好。如果多個(gè)算法具有相同的性能，則這些算法的排名相同。

BQOXEFO在5個(gè)數(shù)據(jù)集中均排名第一，最終在整體上排名第一。從平均值和最大值分析，BQOXEFO在5個(gè)數(shù)據(jù)集中均為最優(yōu)秀的。從標(biāo)準(zhǔn)差分析，BQOXEFO在大部分的數(shù)據(jù)集中都表現(xiàn)出極好的穩(wěn)定性。BQOXEFO在每一個(gè)測(cè)試集上的ASS值都是1，這意味著BQOXEFO的降維能力很優(yōu)秀，還能保證精度。

5種算法對(duì)于D1和D2數(shù)據(jù)集的收斂曲線如圖1所示。BQOXEFO的收斂曲線均在其他算法上方，收斂速度最快。這表明BQOXEFO的收斂速度和收斂精度都有顯著優(yōu)勢(shì)。

3.3 統(tǒng)計(jì)分析

對(duì)算法進(jìn)行Wilcoxon符號(hào)秩檢驗(yàn)（Wilcoxon rank sum test，WRST），主要分析BQOXEFO與其他4種算法之間的顯著差異，結(jié)果見表3。其中‘H+’代表正的秩和，‘H-’代表負(fù)的秩和；P值（Probability value，P_value）用于檢測(cè)兩個(gè)算法是否有明顯差異，獲勝者（winner）用于記錄BQOXEFO與其他算法的差異。當(dāng)P_value≥0.05時(shí)，說(shuō)明兩個(gè)算法無(wú)明顯差異，將winner標(biāo)記為‘=’；當(dāng)P_value＜0.05、H+＞H-時(shí)，表示在5%的顯著性水平下BQOXEFO相比于其他算法的收斂性能有明顯優(yōu)勢(shì)，winner記為‘+’；當(dāng)P_value＜0.05、H+＜H-時(shí)，表示在5%的顯著性水平下BQOXEFO的收斂性能弱于對(duì)比算法，winner記為‘-’。計(jì)算結(jié)果表明，BQOXEFO比任何一種算法都要優(yōu)秀，有極大的優(yōu)勢(shì)。

表3 五種算法的WRST對(duì)比結(jié)果Tab.3 WRST comparison results of five algorithms

4 結(jié)論

本文提出二進(jìn)制正交電魚優(yōu)化BQOXEFO特征選擇方法。首先，通過(guò)二進(jìn)制機(jī)制來(lái)描述特征，并構(gòu)造基于分類精度和所選特征數(shù)量的適應(yīng)度函數(shù)，同時(shí)，采用KNN對(duì)數(shù)據(jù)進(jìn)行分類。其次，通過(guò)在EFO中引入帶有量化的正交交叉策略來(lái)提高算法的收斂速度和精度。第三，采用動(dòng)態(tài)邊界機(jī)制來(lái)提高算法的收斂速度。第四，使用基于正弦的主動(dòng)電定位更新策略，通過(guò)改變其移動(dòng)方向幫助個(gè)體跳出局部最優(yōu)。最后，通過(guò)UCI數(shù)據(jù)庫(kù)中的5個(gè)基準(zhǔn)數(shù)據(jù)集驗(yàn)證BQOXEFO算法的性能。BQOXEFO和4種對(duì)比算法的仿真實(shí)驗(yàn)和統(tǒng)計(jì)分析結(jié)果表明，BQOXEFO算法具有更好的收斂性能，能夠以更少的特征數(shù)量使分類精度最大化。