李郅琴，杜建强，聂 斌，熊旺平，徐国良，罗计根，李冰涛

1.江西中医药大学 计算机学院，南昌 330004

2.江西中医药大学 药学院，南昌 330004

特征选择本质上是组合优化问题，一般在数据挖掘、模式识别和机器学习中作为数据预处理过程。通过特征选择去除无关特征和冗余特征，可以解决维数灾难问题，降低问题的复杂度，提高学习算法的预测精度、鲁棒性和可解释性[1]。现如今，随着研究问题复杂度的增加，基于研究问题收集的数据集的维度也越来越高。很多特征是无关或冗余的，它们的存在对数据挖掘、机器学习等后续任务产生消极影响，如降低预测精度，增加结果的复杂性和不可理解性。因此，在数据挖掘之前，使用特征选择对数据集降维。

黑寡妇算法（black widow optimization algorithm，BWO）[2]是Hayyolalam 等人2020 年提出的一种元启发式算法，最初用于解决工程优化问题，具有收敛速度快、适应度值优化等方面的诸多优势。自黑寡妇算法提出短短不到一年时间，已有多篇相关论文发表，涉及多个领域；如Houssein 等[3]基于黑寡妇算法提出一种新的多层阈值图像分割算法，并将该方法与六种知名的元启发式算法进行比较，灰狼优化算法（gray wolf optimization，GWO）、飞蛾火焰优化算法（moth flame optimization，MFO）、鲸鱼优化算法（whale optimization algorithm，WOA）、正弦余弦算法（sine-cosine algorithm，SCA）、耳光群算法（slap swarm algorithm，SSA）、均衡优化算法（equilibrium optimization，EO），实验结果表明，该方法在适应度值和性能指标上优于其他方法，取得了高效可靠的结果，被认为是最有前途的多级图像分割方法；Katooli等[4]和Tightiz等[5]将黑寡妇算法应用在自适应神经模糊推理系统（adaptive neuro-fuzzy inference system，ANFIS）的训练过程中，提高了ANFIS的故障检测能力、鲁棒性和分类精度；Micev 等[6]提出自适应黑寡妇优化算法（adaptive black widow optimization algorithm，ABWO）取代提取发电机参数的标准图解方法，实验表明该方法的归一化误差平方和（normalized sum of squared errors，NSSE）最小，并且在同步发电机上验证了优化方法的适用性和准确性；Premkumar 等[7]采用黑寡妇算法对风力机仿真器的比例-积分（proportionalintegral，PI）控制器进行优化，通过仿真结果和硬件结果的吻合性验证了该方法的有效性。黑寡妇算法是有效果、有潜力的元启发式方法，可以预见它将来会在更多领域中发光发热，如特征选择。

本文的目标是解决黑寡妇算法不能进行特征选择的问题。本文的贡献有两点：第一，提出五种优化策略，包括二进制策略、“或门”策略、种群限制策略、快速生殖策略以及适应度优先策略，对黑寡妇算法进行改进；第二，将黑寡妇算法推广到特征选择问题，提出两种新的特征选择方法。前三种优化策略解决黑寡妇算法不能进行特征选择的问题，提出黑寡妇特征选择算法（black widow optimization feature selection algorithm，BWOFS）；综合五种优化策略提升算法性能，提出生殖调控黑寡妇特征选择算法（procreation controlled black widow optimization feature selection algorithm，PCBWOFS）。

1 相关工作

为解决特征选择问题，多年来，研究者们进行各种尝试，提出一系列特征选择方法。基于特征选择和学习算法的不同结合方式，可将特征选择方法分为过滤式（Filter）、封装式（Wrapper）、嵌入式（Embedded）以及集成式（Ensemble）四种类型。Filter是最早提出的一类特征选择方法[8-9]，它和学习算法相互独立，学习算法的效果不影响特征子集的生成，一般基于评价准则对特征排序来选择特征，包括对称不确定性SU、MIC[10]、mRMR[11]、马尔科夫毯等准则。Wrapper 将选用的学习算法封装成黑盒，根据它在特征子集上的预测性能评价特征子集，并结合搜索策略获取最优子集，搜索策略有完全搜索、序列前向搜索（sequential forward selection，SFS）、序列后向搜索（sequential backward selection，SBS）、序列前向浮动搜索（sequential forward floating selection，SFFS）、序列后向浮动搜索（sequential backward floating selection，SBFS）[12]，以及各种元启发式方法，如GA、PSO。一般而言，Wrapper比Filter效果更好，因为考虑了特征子集和学习算法的关系，但Wrapper时间复杂度比Filter 高。Embedded 取决于学习算法本身的特性，有些学习算法天然具有特征选择的功能，例如决策树、Lasso等。Ensemble通过引入集成思想，得到比单个特征选择方法更好的性能。尽管特征选择问题取得了一定的进展，但也需要根据不同原理，探索有潜力的特征选择方法，以解决不同的问题，为相关研究人员提供更多选择的可能。

特征选择使用某种评价准则从原始特征空间中选择特征子集[13-16]。很明显，特征选择问题是一个NP-hard问题[17]，评估所有特征子集时间复杂度为O( )2n[18]，这只能在低维搜索空间中实现完全搜索，高维空间中无法实现，因此高效的搜索策略是有效求解特征选择问题的关键。启发式的搜索策略的时间复杂度优于完全搜索、有序列前向搜索SFS、序列后向搜索SBS、序列前向浮动搜索SFFS、序列后向浮动搜索SBFS、双向搜索等。启发式的搜索策略的时间复杂度的优势是以降低学习算法的预测精度为代价，近年来，元启发式搜索由于其可接受的时间复杂度、较好的预测精度，在特征选择领域应用广泛。传统的元启发式搜索方法有遗传算法、粒子群等，它们在用于特征选择时效果良好，一些较新的元启发式特征选择方法，包括Emary等[19]提出的二元蚁狮优化器（binary ant lion optimizer，BALO），Zawbaa等[20]提出的花授粉算法（flower pollination algorithm，FPA），Mafarja 等[21]基于鲸鱼优化算法（WOA）提出的两个二进制变体算法，Ghaemi等[22]提出的森林优化特征选择算法（feature selection using forest optimization algorithm，FSFOA）。黑寡妇算法（BWO）[2]是受黑寡妇蜘蛛独特的交配行为启发而提出的，较于其他元启发式方法而言，具有更强大的全局搜索能力，可避免局部最优，且收敛速度快。若待求解的优化问题具有多个局部最优解，黑寡妇算法会是好的选择，但原生的黑寡妇算法并不能直接进行特征选择。

因此，本文针对黑寡妇算法不能进行特征选择的问题，设计五种优化策略改进黑寡妇算法，提出黑寡妇特征选择算法（BWOFS）和生殖调控黑寡妇特征选择算法（PCBWOFS），两种新方法都能提高学习算法的预测精度。

2 黑寡妇算法概述

黑寡妇算法（BWO）[2]是受黑寡妇蜘蛛独特的交配行为启发而提出的，该算法模拟了黑寡妇蜘蛛的生命周期，在51 个基准函数以及3 个具体工程问题上对BWO进行有效性验证，取得了良好的结果。

BWO的每一个解（潜在解决方案）是一只黑寡妇蜘蛛，黑寡妇蜘蛛的长度等于特征的维度。BWO 包括初始化种群、生殖、同类相食、突变、更新种群等5个阶段，除了初始种群阶段，其他4个阶段需迭代至满足结束条件，返回适应度最佳的黑寡妇。

2.1 初始化种群

BWO 算法中，待求解问题的一个解是一只黑寡妇蜘蛛，可以将黑寡妇蜘蛛视为一个一维数组：

其中，Nvar是特征的维度，初始化时，每个特征值都是随机的浮点数。每只黑寡妇都有适应度，使用某个适应度函数计算黑寡妇的适应度：

初始化种群时，需要生成Npop（种群大小）只黑寡妇，得到一个Npop×Nvar的黑寡妇矩阵。Npop需要预先定义，常用的有30、50等。

2.2 生殖

生殖阶段是全局搜索阶段。首先，根据适应度大小对种群排序，基于生殖率（procreating rate，PP）计算种群中参与生殖的黑寡妇，然后从中随机选择一对父母（雌雄黑寡妇）进行交配繁殖。在自然界中，每对黑寡妇都在自己的蜘蛛网上进行繁殖，与其他的黑寡妇是分开的，每次大约生成1 000 枚卵[2]，但只有适应度较高的小蜘蛛能存活下来。在黑寡妇算法中，每对父母借助α数组模拟生殖过程：

其中，W1和W2是父母，child1和child2是后代。这个过程要重复Nvar/2 次。

2.3 同类相食

同类相食指的是适应度高的蜘蛛吃掉适应度低的蜘蛛。黑寡妇蜘蛛的同类相食分为性同类相食、兄弟姐妹同类相食和子食母同类相食三种。性同类相食是指雌黑寡妇会在交配时或交配后吃掉雄黑寡妇，可以根据适应度分辨雌雄，适应度高的为雌性，适应度低的为雄性；兄弟姐妹同类相食发生在母蛛网上，幼蛛孵化后会在母蛛网上生活一周左右，期间会发生兄弟姐妹同类相食；子食母同类相食是指某些情况下会发生小蜘蛛吃掉母蛛的事件。黑寡妇算法中，模拟了性同类相食和兄弟姐妹同类相食，子食母同类相食暂未涉及。通过摧毁父亲实现性同类相食，根据同类相食率（cannibalism rate，CR）摧毁一部分孩子达到兄弟姐妹同类相食的目的。使用适应度值确定幼蛛的强弱。

2.4 突变

突变阶段是局部搜索阶段。黑寡妇算法在这一阶段根据突变率（mutation rate，PM）随机选择多个黑寡妇，每个黑寡妇随机交换数组中的两个特征值。

2.5 更新种群

一次迭代后，将同类相食阶段保留下来的黑寡妇以及突变阶段得到的黑寡妇作为下一次迭代的初始种群。

2.6 停止条件

可以考虑三种停止条件：（1）提前设置最大迭代次数。（2）最佳黑寡妇不再发生变化。（3）达到预设的精度水平。

黑寡妇算法伪代码如算法1所示。

算法1 黑寡妇算法（BWO）

3 模型构建

为将黑寡妇算法推广到特征选择问题以及提升算法性能，提出二进制策略、“或门”策略、种群限制策略、快速生殖策略以及适应度优先策略对黑寡妇算法进行改进。基于这些优化策略，提出两种新的特征选择方法：黑寡妇特征选择算法（BWOFS）和生殖调控黑寡妇特征选择算法（PCBWOFS）。

3.1 优化策略

3.1.1 二进制策略

传统的黑寡妇算法的目标是在连续搜索空间中寻找最优解，但特征选择是在离散的二进制空间中搜索最优解。所谓二进制策略是指引入二进制编码，随机使用“0”或“1”初始化黑寡妇的每个特征，“0”表示特征被选择，“1”代表特征未被选择，因此，特征选择问题中每只黑寡妇都是一个特征子集：

其中，Nvar是特征维度，每个特征值都是0或1。图1是特征选择问题中黑寡妇的一个示例。

图1 特征选择问题中的黑寡妇Fig.1 Black widows in feature selection problems

3.1.2 “或门”策略

特征选择时，参与计算的黑寡妇和α是0，1 数组，因此生殖方式有所变化，新的生殖方式称为“或门”策略：

其中，W1和W2是父母，child1和child2是后代，×代表对应位置相乘，||代表对应位置做或运算，例如[0，1，1，0]||[1，1，0，0]=[1，1，1，0]，这个过程要重复Nvar/2 次。算法的生殖过程是在搜索空间进行全局搜索。

3.1.3 种群限制策略

种群限制策略根据适应度对同类相食阶段保留下来的黑寡妇进行排序，将超过Npop（种群大小）的适应度低的黑寡妇删除。首先，黑寡妇算法种群过快增长以致算法较难收敛；其次，幼蛛孵化后会在母蛛网上生活一周左右，期间会发生兄弟姐妹同类相食，之后会被风带到其他的地方开始生活，许多幼蛛由于资源争夺、气候、天敌等原因并不能平安长大；此外，有许多进化算法都有种群限制的过程，如森林优化算法（forest optimization algorithm，FOA）[23-24]。因此，设计种群限制策略，让黑寡妇种群数量保持在一个较为稳定的范围内。种群限制策略可以防止黑寡妇种群的无限扩展，减小算法的时间复杂度，加快算法的收敛速度。

3.1.4 快速生殖策略

每次迭代时，生殖阶段控制一对蜘蛛只参与一次生殖，这便是快速生殖策略。算法1步骤5～11是实现生殖和同类相食的功能，容易发现步骤6会选择到重复的父母进行生殖。首先，这将导致重复的母亲保留在种群当中，这些适应度较高且相同的蜘蛛将被选中参与下一次繁殖，不利于全局搜索时产生多样化的孩子。其次，不符合自然界黑寡妇的繁殖规律，一对雌雄黑寡妇在单独的网上进行生殖，因为第一个进入网络的雄性通过网络缩减降低了雌性网络对竞争对手的吸引力[25]。最后，父亲（雄黑寡妇）在繁殖时或繁殖后会被母亲（雌黑寡妇）吃掉，母亲也可能被孩子吃掉，所以父亲只能参与一次生殖，母亲也一般参与一次生殖（如果母亲没有被吃掉，那么在下一次迭代时能再次生殖）。快速生殖策略不仅能解决以上问题，还意味着算法每次迭代时从nr对黑寡妇生殖产生nr×Nvar个孩子，变成nr/2 对黑寡妇进行生殖产生nr/2×Nvar个孩子，大大缩短了时间消耗，因此称为快速生殖策略。

3.1.5 适应度优先策略

适应度优先策略的思想是当孩子具有更好的适应度时，对应的母亲将会被取代。采用适应度优先策略能够避免耗费计算资源搜索低适应度的空间。该策略类似黑寡妇的子食母同类相食过程，自然界中，母亲在生殖后有几率被孩子吃掉。

3.2 黑寡妇特征选择算法

本文首次尝试将黑寡妇算法调整推广到用于特征选择的离散搜索空间问题，综合二进制策略、“或门”策略和种群限制策略，提出黑寡妇特征选择算法（BWOFS）。

假设原始特征集合X=(x1,x2,…,xNvar)M×Nvar，目标特征Y=(y1,y2,…,yM)T，初始种群Npop，生殖率PP，同类相食率CR，突变率PM，BWOFS 模型具体构建流程如下：

步骤1 二进制策略初始化黑寡妇种群：二进制策略初始化黑寡妇蜘蛛，生成含有Npop只蜘蛛的黑寡妇种群pop，每只黑寡妇都是一个特征子集，为每只黑寡妇计算适应度，若是分类任务，适应度函数可以选择KNN、决策树、SVM 等，适应度值可以是分类准确率等；对于回归任务，适应度函数可选PLS、Lasso 等回归方法，适应度值可以是RMSE、R2等。经过初始化种群阶段，生成Npop（种群大小）只黑寡妇，得到一个Npop×Nvar的黑寡妇矩阵。Npop需预先定义，可选30、50等。

步骤2“或门”策略生殖：首先根据适应度大小对种群排序，基于生殖率PP计算种群中参与生殖的黑寡妇，然后从中随机选择一对父母（雌雄黑寡妇），使用“或门”策略进行交配繁殖生成Nvar个孩子并计算适应度。

步骤3 同类相食：首先摧毁步骤2 中的父亲，然后根据适应度值对步骤2中的Nvar个孩子排序，基于同类相食率CR，摧毁适应度低的孩子，剩下的黑寡妇保存到种群pop2中。

步骤4 种群限制策略：种群pop2根据适应度排序，执行种群限制策略将超过Npop（种群大小）的适应度低的黑寡妇删除。

步骤5 突变：每个随机被选择进行突变的黑寡妇随机交换0，1 数组中的两个特征值，使用突变率PM 确定需要突变的黑寡妇的数量；

步骤6 更新种群：种群pop 更新为步骤4 保留下来的黑寡妇以及步骤5得到的黑寡妇。

步骤7 返回最优特征子集：循环步骤2～步骤6直到停止条件，返回种群pop 中适应度最好的最佳黑寡妇，得到最优特征子集Xbest。

该算法最终输出的最优特征子集是适应度最高的黑寡妇，黑寡妇特征选择算法（BWOFS）的伪代码如算法2所示。

算法2 黑寡妇特征选择算法（BWOFS）

3.3 生殖调控的黑寡妇特征选择算法

综合二进制策略、“或门”策略、种群限制策略、快速生殖策略以及适应度优先策略，提出生殖调控黑寡妇特征选择算法（PCBWOFS）。

假设原始特征集合X=(x1,x2,…,xNvar)M×Nvar，目标特征Y=(y1,y2,…,yM)T，初始种群Npop，生殖率PP，同类相食率CR，突变率PM，PCBWOFS 模型具体构建流程如下：

步骤1 二进制策略初始化黑寡妇种群：使用二进制策略初始化黑寡妇，产生含有Npop只黑寡妇种群pop，每只黑寡妇都是一个特征子集，为每只黑寡妇计算适应度。

步骤2 快速生殖策略和“或门”策略进行生殖：首先根据适应度大小对种群排序，基于生殖率PP 计算种群中参与生殖的黑寡妇，然后执行快速生殖策略不重复的随机选择一对父母，使用“或门”策略和快速生殖策略进行交配繁殖生成Nvar个孩子，并计算适应度。

步骤3 适应度优先策略的同类相食：首先摧毁步骤2中的父亲，然后根据适应度值对步骤2中的Nvar个孩子排序，基于同类相食率CR，摧毁适应度低的孩子，根据适应度优先策略若孩子出现比母亲更好的适应度，摧毁步骤2中的母亲，其余的黑寡妇保存到种群pop2中。

步骤4 种群限制策略：种群pop2根据适应度排序，执行种群限制策略，将超过Npop（种群大小）的适应度低的黑寡妇删除。

步骤5 突变：每个随机被选择进行突变的黑寡妇随机交换0，1 数组中的两个特征值，使用突变率PM 确定需要突变的黑寡妇的数量。

步骤6 更新种群：种群pop 更新为步骤4 保留下来的黑寡妇以及步骤5得到的黑寡妇。

步骤7 返回最优特征子集：循环步骤2～步骤6直到停止条件，返回种群pop 中适应度最好的最佳黑寡妇，得到最优特征子集Xbest。

PCBWOFS算法的伪代码如算法3所示。

算法3 生殖调控黑寡妇特征选择算法（PCBWOFS）

PCBWOFS 可以看作是BWOFS 的改进算法。PCBWOFS 在BWOFS 的基础上，增加快速生殖策略和适应度优先策略。对比算法2 步骤7～13（BWOFS 伪代码）和算法3 步骤7～16（PCBWOFS 伪代码）发现两个算法的不同之处，每次迭代时，BWOFS 有nr对黑寡妇进行生殖，可以产生nr×Nvar个孩子，而PCBWOFS 只有nr/2 对黑寡妇进行生殖，产生nr/2×Nvar个孩子。因此，BWOFS 较PCBWOFS 的明显优势在于每次迭代时全局搜索的特征子集的可能性更多，找到最优特征子集的可能性大；PCBWOFS 较BWOFS 的优势是每次迭代的计算量小，而且适应度优先策略能降低算法在低适应度空间计算资源的消耗。

4 实验结果与讨论

4.1 数据说明

本文将分别在分类、回归任务中验证提出的BWOFS和PCBWOFS。分类任务的10个数据集来自于UCI，分别是红酒数据集（wine），Ultrasonic Flowmeter Diagnostics数据集（有4 个数据集，分别简称为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）。由于获取的原始数据有些存在缺失值，需要通过数据预处理得到有效样本。经数据预处理，各分类数据集的信息描述见表1。

表1 分类数据集的信息描述Table 1 Information description of classification datasets

回归任务的7 个实验数据集分别来自于UCI 数据集上的Residential Building Data Set（简称为RBuild）、Student Performance Data Set（有数学成绩和葡萄牙语成绩，分别简称为SPMath和SPPortuguese）、Communities and Crime Data Set（简称为CCrime）、Superconductivity Data Set（简称为SConduct）、Blog Feedback Data Set的训练集（简称为BlogTr），以及Kaggle竞赛数据集House Prices Advanced Regression Techniques（简称为House）、Restaurant Revenue Prediction（简称为Restaurant）。同样地，对上述数据集进行预处理得到有效样本。经数据预处理，各回归数据集的信息描述见表2。

表2 回归数据集的信息描述Table 2 Information description of regression datasets

4.2 参数设置

实验中涉及到的3 个最优化算法FSFOA、BWOFS和PCBWOFS 的参数如表3 所示，为了确保实验的公平性，本文提出的两个算法BWOFS 和PCBWOFS 的参数设置保持一致。

表3 FSFOA、BWOFS、PCBWOFS的参数设置Table 3 Parameters setting of FSFOA，BWOFS and PCBWOFS

4.3 实验结果对比分析

在验证BWOFS、PCBWOFS 的同时，加入了全集、近似马尔科夫毯（AMB）、序列前向搜索（SFS）、序列前向浮动搜索（SFFS）、森林优化特征选择算法（FSFOA）的实验结果进行对比。分类任务使用KNN(k=3)作为适应度函数，分类准确率（CA）当作适应度值，实验结果见表4。回归任务的适应度函数为PLS，均方根误差（RMSE）作为适应度值，实验结果由表5 给出。表4 和表5中加粗显示的结果显示该数据集的最佳CA/RMSE或最好的维度缩减率（DR）。本文实验的硬件配置为Intel®CoreTMi5-3470 CPU@3.20 GHz，8.00 GB 内存，使用Python语言编写算法，IDE为PyCharm 2017.3.2。

由表4、表5 可知，相较其他对比方法（全集、AMB、SFS、SFFS、FSFOA），BWOFS 和PCBWOFS 各有优势。BWOFS 的优势在于全局搜索时产生的孩子数量比PCBWOFS 多，寻找最优特征子集有优势，虽然可能在低适应度空间耗费计算资源，但还是有比PCBWOFS表现更好的情况出现，如表4 的UltrasonicC 和表5 的SPPortuguese-y3；PCBWOFS 全局搜索时孩子数量少但更多地避免了低适应度空间计算资源的浪费，表现出较好的结果，如PCBWOFS 在表4 的UltrasonicD、BCWisconsin、Bench、Diabetic 和表5 的CCrime 中的指标（CA/RMSE）都是对比结果中唯一最好的。其他对比方法尤其是FSFOA 也展现了较好的结果，但本文方法BWOFS和PCBWOFS仍有优势，如RBuild-y1和RBuildy2 中，BWOFS 和PCBWOFS 选择的特征子集的RMSE值都低于FSFOA，且PCBWOFS、BWOFS分别在RBuildy1、RBuild-y2中的3个最优化特征选择方法中展现了最好的RMSE值。

表4 分类数据集实验结果（10-fold）Table 4 Experimental results of classification datasets（10-fold）

表5 回归数据集实验结果（10-fold）Table 5 Experimental results of regression datasets（10-fold）

综上，两个新方法BWOFS、PCBWOFS展现了其搜索优势，提高了模型精度，降低了特征维度，提高了分类准确率或减少了均方根误差。PCBWOFS因生殖调控，特征子集展现了比BWOFS 更好的分类准确率以及与BWOFS 相当的RMSE 值。总体来看，PCBWOFS 表现更好一些。

另外，对比维度缩减率，从表4、表5可以看出：BWOFS和PCBWOFS没有展现过多的优势，原因在于它们的搜索方向是更高的CA 或更低的RMSE，所以维度缩减率优势不大。这可以是新的研究方向，在尽可能降低特征维度的情况下寻找最优特征子集，尤其是分类问题中，如UltrasonicB和SCADI数据集上都出现了相同的分类准确率却不同维度缩减率的情况，因此这个研究方向具有可行性。

4.4 模型迭代过程

本节探讨最优化特征选择算法的迭代过程，将本文提出的两个方法BWOFS、PCBWOFS 与FSFOA 在分类和回归任务中进行比较。

由图2 不难发现，与FSFOA 相比，新方法BWOFS和PCBWOFS 可以在更少的迭代次数下找到最优特征子集，图3 上这一优势更加明显。原因在于BWOFS 和PCBWOFS强大的全局搜索能力，每次迭代搜索的解更多；然而FSFOA的局部播种和全局播种策略相对简单，需要更多的迭代次数寻找最优特征子集。此外，从图2、图3可以发现BWOFS和PCBWOFS有相似的收敛次数和最优适应度，证明PCBWOFS 对BWOFS 的改进是可接受的。

图2 分类数据集上三种最优化特征选择算法的迭代过程Fig.2 Iterative process of three optimal feature selection algorithms on classification datasets

图3 回归数据集上三种最优化特征选择算法的迭代过程Fig.3 Iterative process of three optimal feature selection algorithms on regression datasets

4.5 BWOFS和PCBWOFS的时间比较

对比本文提出的两个特征选择算法BWOFS 和PCBWOFS 的时间效率，表6、表7 分别是它们在分类、回归数据集上的时间比较。相较BWOFS，PCBWOFS时间消耗小，几乎只有BWOFS 的一半。因为BWOFS每次迭代产生nr×Nvar个孩子，而PCBWOFS 由于快速生殖策略每次迭代只产生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 结束语

本文提出五种优化策略：二进制策略、“或门”策略、种群限制策略、快速生殖策略以及适应度优先策略。使用前三种优化策略解决黑寡妇算法不能特征选择的问题，提出黑寡妇特征选择算法（BWOFS）；综合五种优化策略提升算法性能，提出生殖调控黑寡妇特征选择算法（PCBWOFS）。实验证明，将黑寡妇算法推广到特征选择问题是明智的，相较其他对比方法，BWOFS 和PCBWOFS可以找到预测精度更高的特征子集，有能力提供有竞争力和有前景的结果。特别地，若只对比两个新算法，发现PCBWOFS比BWOFS计算量小，时间消耗也少，但搜索最优特征子集的能力并未下降甚至有所提升。在接下来的研究中，将尝试使用本文提出的两个特征选择算法解决多目标任务特征选择问题，在提高预测性能的基础上尽可能减少特征数量，也即在预测性能和特征数量之间取得平衡。此外，还将尝试构建框架，让本不适合高维数据的黑寡妇特征选择算法在高维数据上发挥它的优势。