李郅琴，杜建強，聶 斌，熊旺平，徐國良，羅計根，李冰濤

1.江西中醫(yī)藥大學 計算機學院，南昌 330004

2.江西中醫(yī)藥大學 藥學院，南昌 330004

特征選擇本質(zhì)上是組合優(yōu)化問題，一般在數(shù)據(jù)挖掘、模式識別和機器學習中作為數(shù)據(jù)預處理過程。通過特征選擇去除無關特征和冗余特征，可以解決維數(shù)災難問題，降低問題的復雜度，提高學習算法的預測精度、魯棒性和可解釋性[1]?，F(xiàn)如今，隨著研究問題復雜度的增加，基于研究問題收集的數(shù)據(jù)集的維度也越來越高。很多特征是無關或冗余的，它們的存在對數(shù)據(jù)挖掘、機器學習等后續(xù)任務產(chǎn)生消極影響，如降低預測精度，增加結(jié)果的復雜性和不可理解性。因此，在數(shù)據(jù)挖掘之前，使用特征選擇對數(shù)據(jù)集降維。

黑寡婦算法（black widow optimization algorithm，BWO）[2]是Hayyolalam 等人2020 年提出的一種元啟發(fā)式算法，最初用于解決工程優(yōu)化問題，具有收斂速度快、適應度值優(yōu)化等方面的諸多優(yōu)勢。自黑寡婦算法提出短短不到一年時間，已有多篇相關論文發(fā)表，涉及多個領域；如Houssein 等[3]基于黑寡婦算法提出一種新的多層閾值圖像分割算法，并將該方法與六種知名的元啟發(fā)式算法進行比較，灰狼優(yōu)化算法（gray wolf optimization，GWO）、飛蛾火焰優(yōu)化算法（moth flame optimization，MFO）、鯨魚優(yōu)化算法（whale optimization algorithm，WOA）、正弦余弦算法（sine-cosine algorithm，SCA）、耳光群算法（slap swarm algorithm，SSA）、均衡優(yōu)化算法（equilibrium optimization，EO），實驗結(jié)果表明，該方法在適應度值和性能指標上優(yōu)于其他方法，取得了高效可靠的結(jié)果，被認為是最有前途的多級圖像分割方法；Katooli等[4]和Tightiz等[5]將黑寡婦算法應用在自適應神經(jīng)模糊推理系統(tǒng)（adaptive neuro-fuzzy inference system，ANFIS）的訓練過程中，提高了ANFIS的故障檢測能力、魯棒性和分類精度；Micev 等[6]提出自適應黑寡婦優(yōu)化算法（adaptive black widow optimization algorithm，ABWO）取代提取發(fā)電機參數(shù)的標準圖解方法，實驗表明該方法的歸一化誤差平方和（normalized sum of squared errors，NSSE）最小，并且在同步發(fā)電機上驗證了優(yōu)化方法的適用性和準確性；Premkumar 等[7]采用黑寡婦算法對風力機仿真器的比例-積分（proportionalintegral，PI）控制器進行優(yōu)化，通過仿真結(jié)果和硬件結(jié)果的吻合性驗證了該方法的有效性。黑寡婦算法是有效果、有潛力的元啟發(fā)式方法，可以預見它將來會在更多領域中發(fā)光發(fā)熱，如特征選擇。

本文的目標是解決黑寡婦算法不能進行特征選擇的問題。本文的貢獻有兩點：第一，提出五種優(yōu)化策略，包括二進制策略、“或門”策略、種群限制策略、快速生殖策略以及適應度優(yōu)先策略，對黑寡婦算法進行改進；第二，將黑寡婦算法推廣到特征選擇問題，提出兩種新的特征選擇方法。前三種優(yōu)化策略解決黑寡婦算法不能進行特征選擇的問題，提出黑寡婦特征選擇算法（black widow optimization feature selection algorithm，BWOFS）；綜合五種優(yōu)化策略提升算法性能，提出生殖調(diào)控黑寡婦特征選擇算法（procreation controlled black widow optimization feature selection algorithm，PCBWOFS）。

1 相關工作

為解決特征選擇問題，多年來，研究者們進行各種嘗試，提出一系列特征選擇方法?；谔卣鬟x擇和學習算法的不同結(jié)合方式，可將特征選擇方法分為過濾式（Filter）、封裝式（Wrapper）、嵌入式（Embedded）以及集成式（Ensemble）四種類型。Filter是最早提出的一類特征選擇方法[8-9]，它和學習算法相互獨立，學習算法的效果不影響特征子集的生成，一般基于評價準則對特征排序來選擇特征，包括對稱不確定性SU、MIC[10]、mRMR[11]、馬爾科夫毯等準則。Wrapper 將選用的學習算法封裝成黑盒，根據(jù)它在特征子集上的預測性能評價特征子集，并結(jié)合搜索策略獲取最優(yōu)子集，搜索策略有完全搜索、序列前向搜索（sequential forward selection，SFS）、序列后向搜索（sequential backward selection，SBS）、序列前向浮動搜索（sequential forward floating selection，SFFS）、序列后向浮動搜索（sequential backward floating selection，SBFS）[12]，以及各種元啟發(fā)式方法，如GA、PSO。一般而言，Wrapper比Filter效果更好，因為考慮了特征子集和學習算法的關系，但Wrapper時間復雜度比Filter 高。Embedded 取決于學習算法本身的特性，有些學習算法天然具有特征選擇的功能，例如決策樹、Lasso等。Ensemble通過引入集成思想，得到比單個特征選擇方法更好的性能。盡管特征選擇問題取得了一定的進展，但也需要根據(jù)不同原理，探索有潛力的特征選擇方法，以解決不同的問題，為相關研究人員提供更多選擇的可能。

特征選擇使用某種評價準則從原始特征空間中選擇特征子集[13-16]。很明顯，特征選擇問題是一個NP-hard問題[17]，評估所有特征子集時間復雜度為O( )2n[18]，這只能在低維搜索空間中實現(xiàn)完全搜索，高維空間中無法實現(xiàn)，因此高效的搜索策略是有效求解特征選擇問題的關鍵。啟發(fā)式的搜索策略的時間復雜度優(yōu)于完全搜索、有序列前向搜索SFS、序列后向搜索SBS、序列前向浮動搜索SFFS、序列后向浮動搜索SBFS、雙向搜索等。啟發(fā)式的搜索策略的時間復雜度的優(yōu)勢是以降低學習算法的預測精度為代價，近年來，元啟發(fā)式搜索由于其可接受的時間復雜度、較好的預測精度，在特征選擇領域應用廣泛。傳統(tǒng)的元啟發(fā)式搜索方法有遺傳算法、粒子群等，它們在用于特征選擇時效果良好，一些較新的元啟發(fā)式特征選擇方法，包括Emary等[19]提出的二元蟻獅優(yōu)化器（binary ant lion optimizer，BALO），Zawbaa等[20]提出的花授粉算法（flower pollination algorithm，F(xiàn)PA），Mafarja 等[21]基于鯨魚優(yōu)化算法（WOA）提出的兩個二進制變體算法，Ghaemi等[22]提出的森林優(yōu)化特征選擇算法（feature selection using forest optimization algorithm，F(xiàn)SFOA）。黑寡婦算法（BWO）[2]是受黑寡婦蜘蛛獨特的交配行為啟發(fā)而提出的，較于其他元啟發(fā)式方法而言，具有更強大的全局搜索能力，可避免局部最優(yōu)，且收斂速度快。若待求解的優(yōu)化問題具有多個局部最優(yōu)解，黑寡婦算法會是好的選擇，但原生的黑寡婦算法并不能直接進行特征選擇。

因此，本文針對黑寡婦算法不能進行特征選擇的問題，設計五種優(yōu)化策略改進黑寡婦算法，提出黑寡婦特征選擇算法（BWOFS）和生殖調(diào)控黑寡婦特征選擇算法（PCBWOFS），兩種新方法都能提高學習算法的預測精度。

2 黑寡婦算法概述

黑寡婦算法（BWO）[2]是受黑寡婦蜘蛛獨特的交配行為啟發(fā)而提出的，該算法模擬了黑寡婦蜘蛛的生命周期，在51 個基準函數(shù)以及3 個具體工程問題上對BWO進行有效性驗證，取得了良好的結(jié)果。

BWO的每一個解（潛在解決方案）是一只黑寡婦蜘蛛，黑寡婦蜘蛛的長度等于特征的維度。BWO 包括初始化種群、生殖、同類相食、突變、更新種群等5個階段，除了初始種群階段，其他4個階段需迭代至滿足結(jié)束條件，返回適應度最佳的黑寡婦。

2.1 初始化種群

BWO 算法中，待求解問題的一個解是一只黑寡婦蜘蛛，可以將黑寡婦蜘蛛視為一個一維數(shù)組：

其中，Nvar是特征的維度，初始化時，每個特征值都是隨機的浮點數(shù)。每只黑寡婦都有適應度，使用某個適應度函數(shù)計算黑寡婦的適應度：

初始化種群時，需要生成Npop（種群大小）只黑寡婦，得到一個Npop×Nvar的黑寡婦矩陣。Npop需要預先定義，常用的有30、50等。

2.2 生殖

生殖階段是全局搜索階段。首先，根據(jù)適應度大小對種群排序，基于生殖率（procreating rate，PP）計算種群中參與生殖的黑寡婦，然后從中隨機選擇一對父母（雌雄黑寡婦）進行交配繁殖。在自然界中，每對黑寡婦都在自己的蜘蛛網(wǎng)上進行繁殖，與其他的黑寡婦是分開的，每次大約生成1 000 枚卵[2]，但只有適應度較高的小蜘蛛能存活下來。在黑寡婦算法中，每對父母借助α數(shù)組模擬生殖過程：

其中，W1和W2是父母，child1和child2是后代。這個過程要重復Nvar/2 次。

2.3 同類相食

同類相食指的是適應度高的蜘蛛吃掉適應度低的蜘蛛。黑寡婦蜘蛛的同類相食分為性同類相食、兄弟姐妹同類相食和子食母同類相食三種。性同類相食是指雌黑寡婦會在交配時或交配后吃掉雄黑寡婦，可以根據(jù)適應度分辨雌雄，適應度高的為雌性，適應度低的為雄性；兄弟姐妹同類相食發(fā)生在母蛛網(wǎng)上，幼蛛孵化后會在母蛛網(wǎng)上生活一周左右，期間會發(fā)生兄弟姐妹同類相食；子食母同類相食是指某些情況下會發(fā)生小蜘蛛吃掉母蛛的事件。黑寡婦算法中，模擬了性同類相食和兄弟姐妹同類相食，子食母同類相食暫未涉及。通過摧毀父親實現(xiàn)性同類相食，根據(jù)同類相食率（cannibalism rate，CR）摧毀一部分孩子達到兄弟姐妹同類相食的目的。使用適應度值確定幼蛛的強弱。

2.4 突變

突變階段是局部搜索階段。黑寡婦算法在這一階段根據(jù)突變率（mutation rate，PM）隨機選擇多個黑寡婦，每個黑寡婦隨機交換數(shù)組中的兩個特征值。

2.5 更新種群

一次迭代后，將同類相食階段保留下來的黑寡婦以及突變階段得到的黑寡婦作為下一次迭代的初始種群。

2.6 停止條件

可以考慮三種停止條件：（1）提前設置最大迭代次數(shù)。（2）最佳黑寡婦不再發(fā)生變化。（3）達到預設的精度水平。

黑寡婦算法偽代碼如算法1所示。

算法1 黑寡婦算法（BWO）

3 模型構(gòu)建

為將黑寡婦算法推廣到特征選擇問題以及提升算法性能，提出二進制策略、“或門”策略、種群限制策略、快速生殖策略以及適應度優(yōu)先策略對黑寡婦算法進行改進。基于這些優(yōu)化策略，提出兩種新的特征選擇方法：黑寡婦特征選擇算法（BWOFS）和生殖調(diào)控黑寡婦特征選擇算法（PCBWOFS）。

3.1 優(yōu)化策略

3.1.1 二進制策略

傳統(tǒng)的黑寡婦算法的目標是在連續(xù)搜索空間中尋找最優(yōu)解，但特征選擇是在離散的二進制空間中搜索最優(yōu)解。所謂二進制策略是指引入二進制編碼，隨機使用“0”或“1”初始化黑寡婦的每個特征，“0”表示特征被選擇，“1”代表特征未被選擇，因此，特征選擇問題中每只黑寡婦都是一個特征子集：

其中，Nvar是特征維度，每個特征值都是0或1。圖1是特征選擇問題中黑寡婦的一個示例。

圖1 特征選擇問題中的黑寡婦Fig.1 Black widows in feature selection problems

3.1.2 “或門”策略

特征選擇時，參與計算的黑寡婦和α是0，1 數(shù)組，因此生殖方式有所變化，新的生殖方式稱為“或門”策略：

其中，W1和W2是父母，child1和child2是后代，×代表對應位置相乘，||代表對應位置做或運算，例如[0，1，1，0]||[1，1，0，0]=[1，1，1，0]，這個過程要重復Nvar/2 次。算法的生殖過程是在搜索空間進行全局搜索。

3.1.3 種群限制策略

種群限制策略根據(jù)適應度對同類相食階段保留下來的黑寡婦進行排序，將超過Npop（種群大小）的適應度低的黑寡婦刪除。首先，黑寡婦算法種群過快增長以致算法較難收斂；其次，幼蛛孵化后會在母蛛網(wǎng)上生活一周左右，期間會發(fā)生兄弟姐妹同類相食，之后會被風帶到其他的地方開始生活，許多幼蛛由于資源爭奪、氣候、天敵等原因并不能平安長大；此外，有許多進化算法都有種群限制的過程，如森林優(yōu)化算法（forest optimization algorithm，F(xiàn)OA）[23-24]。因此，設計種群限制策略，讓黑寡婦種群數(shù)量保持在一個較為穩(wěn)定的范圍內(nèi)。種群限制策略可以防止黑寡婦種群的無限擴展，減小算法的時間復雜度，加快算法的收斂速度。

3.1.4 快速生殖策略

每次迭代時，生殖階段控制一對蜘蛛只參與一次生殖，這便是快速生殖策略。算法1步驟5～11是實現(xiàn)生殖和同類相食的功能，容易發(fā)現(xiàn)步驟6會選擇到重復的父母進行生殖。首先，這將導致重復的母親保留在種群當中，這些適應度較高且相同的蜘蛛將被選中參與下一次繁殖，不利于全局搜索時產(chǎn)生多樣化的孩子。其次，不符合自然界黑寡婦的繁殖規(guī)律，一對雌雄黑寡婦在單獨的網(wǎng)上進行生殖，因為第一個進入網(wǎng)絡的雄性通過網(wǎng)絡縮減降低了雌性網(wǎng)絡對競爭對手的吸引力[25]。最后，父親（雄黑寡婦）在繁殖時或繁殖后會被母親（雌黑寡婦）吃掉，母親也可能被孩子吃掉，所以父親只能參與一次生殖，母親也一般參與一次生殖（如果母親沒有被吃掉，那么在下一次迭代時能再次生殖）。快速生殖策略不僅能解決以上問題，還意味著算法每次迭代時從nr對黑寡婦生殖產(chǎn)生nr×Nvar個孩子，變成nr/2 對黑寡婦進行生殖產(chǎn)生nr/2×Nvar個孩子，大大縮短了時間消耗，因此稱為快速生殖策略。

3.1.5 適應度優(yōu)先策略

適應度優(yōu)先策略的思想是當孩子具有更好的適應度時，對應的母親將會被取代。采用適應度優(yōu)先策略能夠避免耗費計算資源搜索低適應度的空間。該策略類似黑寡婦的子食母同類相食過程，自然界中，母親在生殖后有幾率被孩子吃掉。

3.2 黑寡婦特征選擇算法

本文首次嘗試將黑寡婦算法調(diào)整推廣到用于特征選擇的離散搜索空間問題，綜合二進制策略、“或門”策略和種群限制策略，提出黑寡婦特征選擇算法（BWOFS）。

假設原始特征集合X=(x1,x2,…,xNvar)M×Nvar，目標特征Y=(y1,y2,…,yM)T，初始種群Npop，生殖率PP，同類相食率CR，突變率PM，BWOFS 模型具體構(gòu)建流程如下：

步驟1 二進制策略初始化黑寡婦種群：二進制策略初始化黑寡婦蜘蛛，生成含有Npop只蜘蛛的黑寡婦種群pop，每只黑寡婦都是一個特征子集，為每只黑寡婦計算適應度，若是分類任務，適應度函數(shù)可以選擇KNN、決策樹、SVM 等，適應度值可以是分類準確率等；對于回歸任務，適應度函數(shù)可選PLS、Lasso 等回歸方法，適應度值可以是RMSE、R2等。經(jīng)過初始化種群階段，生成Npop（種群大?。┲缓诠褘D，得到一個Npop×Nvar的黑寡婦矩陣。Npop需預先定義，可選30、50等。

步驟2“或門”策略生殖：首先根據(jù)適應度大小對種群排序，基于生殖率PP計算種群中參與生殖的黑寡婦，然后從中隨機選擇一對父母（雌雄黑寡婦），使用“或門”策略進行交配繁殖生成Nvar個孩子并計算適應度。

步驟3 同類相食：首先摧毀步驟2 中的父親，然后根據(jù)適應度值對步驟2中的Nvar個孩子排序，基于同類相食率CR，摧毀適應度低的孩子，剩下的黑寡婦保存到種群pop2中。

步驟4 種群限制策略：種群pop2根據(jù)適應度排序，執(zhí)行種群限制策略將超過Npop（種群大?。┑倪m應度低的黑寡婦刪除。

步驟5 突變：每個隨機被選擇進行突變的黑寡婦隨機交換0，1 數(shù)組中的兩個特征值，使用突變率PM 確定需要突變的黑寡婦的數(shù)量；

步驟6 更新種群：種群pop 更新為步驟4 保留下來的黑寡婦以及步驟5得到的黑寡婦。

步驟7 返回最優(yōu)特征子集：循環(huán)步驟2～步驟6直到停止條件，返回種群pop 中適應度最好的最佳黑寡婦，得到最優(yōu)特征子集Xbest。

該算法最終輸出的最優(yōu)特征子集是適應度最高的黑寡婦，黑寡婦特征選擇算法（BWOFS）的偽代碼如算法2所示。

算法2 黑寡婦特征選擇算法（BWOFS）

3.3 生殖調(diào)控的黑寡婦特征選擇算法

綜合二進制策略、“或門”策略、種群限制策略、快速生殖策略以及適應度優(yōu)先策略，提出生殖調(diào)控黑寡婦特征選擇算法（PCBWOFS）。

假設原始特征集合X=(x1,x2,…,xNvar)M×Nvar，目標特征Y=(y1,y2,…,yM)T，初始種群Npop，生殖率PP，同類相食率CR，突變率PM，PCBWOFS 模型具體構(gòu)建流程如下：

步驟1 二進制策略初始化黑寡婦種群：使用二進制策略初始化黑寡婦，產(chǎn)生含有Npop只黑寡婦種群pop，每只黑寡婦都是一個特征子集，為每只黑寡婦計算適應度。

步驟2 快速生殖策略和“或門”策略進行生殖：首先根據(jù)適應度大小對種群排序，基于生殖率PP 計算種群中參與生殖的黑寡婦，然后執(zhí)行快速生殖策略不重復的隨機選擇一對父母，使用“或門”策略和快速生殖策略進行交配繁殖生成Nvar個孩子，并計算適應度。

步驟3 適應度優(yōu)先策略的同類相食：首先摧毀步驟2中的父親，然后根據(jù)適應度值對步驟2中的Nvar個孩子排序，基于同類相食率CR，摧毀適應度低的孩子，根據(jù)適應度優(yōu)先策略若孩子出現(xiàn)比母親更好的適應度，摧毀步驟2中的母親，其余的黑寡婦保存到種群pop2中。

步驟4 種群限制策略：種群pop2根據(jù)適應度排序，執(zhí)行種群限制策略，將超過Npop（種群大?。┑倪m應度低的黑寡婦刪除。

步驟5 突變：每個隨機被選擇進行突變的黑寡婦隨機交換0，1 數(shù)組中的兩個特征值，使用突變率PM 確定需要突變的黑寡婦的數(shù)量。

步驟6 更新種群：種群pop 更新為步驟4 保留下來的黑寡婦以及步驟5得到的黑寡婦。

步驟7 返回最優(yōu)特征子集：循環(huán)步驟2～步驟6直到停止條件，返回種群pop 中適應度最好的最佳黑寡婦，得到最優(yōu)特征子集Xbest。

PCBWOFS算法的偽代碼如算法3所示。

算法3 生殖調(diào)控黑寡婦特征選擇算法（PCBWOFS）

PCBWOFS 可以看作是BWOFS 的改進算法。PCBWOFS 在BWOFS 的基礎上，增加快速生殖策略和適應度優(yōu)先策略。對比算法2 步驟7～13（BWOFS 偽代碼）和算法3 步驟7～16（PCBWOFS 偽代碼）發(fā)現(xiàn)兩個算法的不同之處，每次迭代時，BWOFS 有nr對黑寡婦進行生殖，可以產(chǎn)生nr×Nvar個孩子，而PCBWOFS 只有nr/2 對黑寡婦進行生殖，產(chǎn)生nr/2×Nvar個孩子。因此，BWOFS 較PCBWOFS 的明顯優(yōu)勢在于每次迭代時全局搜索的特征子集的可能性更多，找到最優(yōu)特征子集的可能性大；PCBWOFS 較BWOFS 的優(yōu)勢是每次迭代的計算量小，而且適應度優(yōu)先策略能降低算法在低適應度空間計算資源的消耗。

4 實驗結(jié)果與討論

4.1 數(shù)據(jù)說明

本文將分別在分類、回歸任務中驗證提出的BWOFS和PCBWOFS。分類任務的10個數(shù)據(jù)集來自于UCI，分別是紅酒數(shù)據(jù)集（wine），Ultrasonic Flowmeter Diagnostics數(shù)據(jù)集（有4 個數(shù)據(jù)集，分別簡稱為UltrasonicA、UltrasonicB、UltrasonicC和UltrasonicD），SCADI，Breast Cancer Coimbra（簡稱為BCCoimbra），Breast Cancer Wisconsin（Diagnostic）（簡稱為BCWisconsin），Connectionist Bench（Sonar，Mines vs. Rocks）（簡稱為Bench），以及Diabetic Retinopathy Debrecen（簡稱為Diabetic）。由于獲取的原始數(shù)據(jù)有些存在缺失值，需要通過數(shù)據(jù)預處理得到有效樣本。經(jīng)數(shù)據(jù)預處理，各分類數(shù)據(jù)集的信息描述見表1。

表1 分類數(shù)據(jù)集的信息描述Table 1 Information description of classification datasets

回歸任務的7 個實驗數(shù)據(jù)集分別來自于UCI 數(shù)據(jù)集上的Residential Building Data Set（簡稱為RBuild）、Student Performance Data Set（有數(shù)學成績和葡萄牙語成績，分別簡稱為SPMath和SPPortuguese）、Communities and Crime Data Set（簡稱為CCrime）、Superconductivity Data Set（簡稱為SConduct）、Blog Feedback Data Set的訓練集（簡稱為BlogTr），以及Kaggle競賽數(shù)據(jù)集House Prices Advanced Regression Techniques（簡稱為House）、Restaurant Revenue Prediction（簡稱為Restaurant）。同樣地，對上述數(shù)據(jù)集進行預處理得到有效樣本。經(jīng)數(shù)據(jù)預處理，各回歸數(shù)據(jù)集的信息描述見表2。

表2 回歸數(shù)據(jù)集的信息描述Table 2 Information description of regression datasets

4.2 參數(shù)設置

實驗中涉及到的3 個最優(yōu)化算法FSFOA、BWOFS和PCBWOFS 的參數(shù)如表3 所示，為了確保實驗的公平性，本文提出的兩個算法BWOFS 和PCBWOFS 的參數(shù)設置保持一致。

表3 FSFOA、BWOFS、PCBWOFS的參數(shù)設置Table 3 Parameters setting of FSFOA，BWOFS and PCBWOFS

4.3 實驗結(jié)果對比分析

在驗證BWOFS、PCBWOFS 的同時，加入了全集、近似馬爾科夫毯（AMB）、序列前向搜索（SFS）、序列前向浮動搜索（SFFS）、森林優(yōu)化特征選擇算法（FSFOA）的實驗結(jié)果進行對比。分類任務使用KNN(k=3)作為適應度函數(shù)，分類準確率（CA）當作適應度值，實驗結(jié)果見表4?；貧w任務的適應度函數(shù)為PLS，均方根誤差（RMSE）作為適應度值，實驗結(jié)果由表5 給出。表4 和表5中加粗顯示的結(jié)果顯示該數(shù)據(jù)集的最佳CA/RMSE或最好的維度縮減率（DR）。本文實驗的硬件配置為Intel?CoreTMi5-3470 CPU@3.20 GHz，8.00 GB 內(nèi)存，使用Python語言編寫算法，IDE為PyCharm 2017.3.2。

由表4、表5 可知，相較其他對比方法（全集、AMB、SFS、SFFS、FSFOA），BWOFS 和PCBWOFS 各有優(yōu)勢。BWOFS 的優(yōu)勢在于全局搜索時產(chǎn)生的孩子數(shù)量比PCBWOFS 多，尋找最優(yōu)特征子集有優(yōu)勢，雖然可能在低適應度空間耗費計算資源，但還是有比PCBWOFS表現(xiàn)更好的情況出現(xiàn)，如表4 的UltrasonicC 和表5 的SPPortuguese-y3；PCBWOFS 全局搜索時孩子數(shù)量少但更多地避免了低適應度空間計算資源的浪費，表現(xiàn)出較好的結(jié)果，如PCBWOFS 在表4 的UltrasonicD、BCWisconsin、Bench、Diabetic 和表5 的CCrime 中的指標（CA/RMSE）都是對比結(jié)果中唯一最好的。其他對比方法尤其是FSFOA 也展現(xiàn)了較好的結(jié)果，但本文方法BWOFS和PCBWOFS仍有優(yōu)勢，如RBuild-y1和RBuildy2 中，BWOFS 和PCBWOFS 選擇的特征子集的RMSE值都低于FSFOA，且PCBWOFS、BWOFS分別在RBuildy1、RBuild-y2中的3個最優(yōu)化特征選擇方法中展現(xiàn)了最好的RMSE值。

表4 分類數(shù)據(jù)集實驗結(jié)果（10-fold）Table 4 Experimental results of classification datasets（10-fold）

表5 回歸數(shù)據(jù)集實驗結(jié)果（10-fold）Table 5 Experimental results of regression datasets（10-fold）

綜上，兩個新方法BWOFS、PCBWOFS展現(xiàn)了其搜索優(yōu)勢，提高了模型精度，降低了特征維度，提高了分類準確率或減少了均方根誤差。PCBWOFS因生殖調(diào)控，特征子集展現(xiàn)了比BWOFS 更好的分類準確率以及與BWOFS 相當?shù)腞MSE 值。總體來看，PCBWOFS 表現(xiàn)更好一些。

另外，對比維度縮減率，從表4、表5可以看出：BWOFS和PCBWOFS沒有展現(xiàn)過多的優(yōu)勢，原因在于它們的搜索方向是更高的CA 或更低的RMSE，所以維度縮減率優(yōu)勢不大。這可以是新的研究方向，在盡可能降低特征維度的情況下尋找最優(yōu)特征子集，尤其是分類問題中，如UltrasonicB和SCADI數(shù)據(jù)集上都出現(xiàn)了相同的分類準確率卻不同維度縮減率的情況，因此這個研究方向具有可行性。

4.4 模型迭代過程

本節(jié)探討最優(yōu)化特征選擇算法的迭代過程，將本文提出的兩個方法BWOFS、PCBWOFS 與FSFOA 在分類和回歸任務中進行比較。

由圖2 不難發(fā)現(xiàn)，與FSFOA 相比，新方法BWOFS和PCBWOFS 可以在更少的迭代次數(shù)下找到最優(yōu)特征子集，圖3 上這一優(yōu)勢更加明顯。原因在于BWOFS 和PCBWOFS強大的全局搜索能力，每次迭代搜索的解更多；然而FSFOA的局部播種和全局播種策略相對簡單，需要更多的迭代次數(shù)尋找最優(yōu)特征子集。此外，從圖2、圖3可以發(fā)現(xiàn)BWOFS和PCBWOFS有相似的收斂次數(shù)和最優(yōu)適應度，證明PCBWOFS 對BWOFS 的改進是可接受的。

圖2 分類數(shù)據(jù)集上三種最優(yōu)化特征選擇算法的迭代過程Fig.2 Iterative process of three optimal feature selection algorithms on classification datasets

圖3 回歸數(shù)據(jù)集上三種最優(yōu)化特征選擇算法的迭代過程Fig.3 Iterative process of three optimal feature selection algorithms on regression datasets

4.5 BWOFS和PCBWOFS的時間比較

對比本文提出的兩個特征選擇算法BWOFS 和PCBWOFS 的時間效率，表6、表7 分別是它們在分類、回歸數(shù)據(jù)集上的時間比較。相較BWOFS，PCBWOFS時間消耗小，幾乎只有BWOFS 的一半。因為BWOFS每次迭代產(chǎn)生nr×Nvar個孩子，而PCBWOFS 由于快速生殖策略每次迭代只產(chǎn)生nr/2×Nvar個孩子，所以計算量小，時間消耗少。

表6 BWOFS和PCBWOFS在分類任務的時間比較Table 6 Comparison of time between BWOFS and PCBWOFS in classification tasks s

表7 BWOFS和PCBWOFS在回歸任務的時間比較Table 7 Comparison of time between BWOFS and PCBWOFS in regression tasks s

5 結(jié)束語

本文提出五種優(yōu)化策略：二進制策略、“或門”策略、種群限制策略、快速生殖策略以及適應度優(yōu)先策略。使用前三種優(yōu)化策略解決黑寡婦算法不能特征選擇的問題，提出黑寡婦特征選擇算法（BWOFS）；綜合五種優(yōu)化策略提升算法性能，提出生殖調(diào)控黑寡婦特征選擇算法（PCBWOFS）。實驗證明，將黑寡婦算法推廣到特征選擇問題是明智的，相較其他對比方法，BWOFS 和PCBWOFS可以找到預測精度更高的特征子集，有能力提供有競爭力和有前景的結(jié)果。特別地，若只對比兩個新算法，發(fā)現(xiàn)PCBWOFS比BWOFS計算量小，時間消耗也少，但搜索最優(yōu)特征子集的能力并未下降甚至有所提升。在接下來的研究中，將嘗試使用本文提出的兩個特征選擇算法解決多目標任務特征選擇問題，在提高預測性能的基礎上盡可能減少特征數(shù)量，也即在預測性能和特征數(shù)量之間取得平衡。此外，還將嘗試構(gòu)建框架，讓本不適合高維數(shù)據(jù)的黑寡婦特征選擇算法在高維數(shù)據(jù)上發(fā)揮它的優(yōu)勢。