一种自适应变异二进制粒子群算法

姜磊，刘建华，张冬阳，卜冠南

(1.福建工程学院 信息科学与工程学院，福建 福州 350118；2.福建省大数据挖掘与应用技术重点实验室，福建 福州 350118)

引言

在数据分析中，特征选择是一种重要的数据预处理技术。常见的特征选择方法包括过滤式、包裹式、嵌入式[1]。特征选择问题属于NP难问题，其包裹式特征选择方法通常是将智能算法用于特征选择。在智能算法中，二进制粒子群算法(BPSO)具有规则简单、参数设置较少等优点，从而被用到特征选择的问题中。

文献[2]提出了基于二进制粒子群优化的水下目标特征选择算法，并结合k近邻分类算法对3类实测水下目标数据进行了最优特征集的选择及分类实验。文献[3]提出基于离散粒子群算法进行织物疵点特征选择的方法。文献[4]提出了一种基于粒子群优化的入侵特征选择算法，通过分析网络入侵数据特征之间的相关性，可使粒子群优化算法在所有特征空间中优化搜索，自主选择有效特征子集，降低数据维度。

特征选择一般采用原始的BPSO算法，文献[5]从算法的位置改变概率以及遗传算法的模式定理方面对BPSO算法进行了分析，发现BPSO算法存在搜索能力不足的缺点。文献[6]针对BPSO算法提出了改进方法，并验证了改进方法的有效性。文献[7]提出基于特征聚类信息进行种群的初始化策略提高初始化种群的质量，并提出了一种基于决策空间相似性的自适应局部搜索策略，避免算法早熟。文献[8]提出一种鲶鱼效应引入新的粒子来提高BPSO算法性能，并用于特征选择。文献[9]提出一种新改进的BPSO-SVM 算法用于特征选择。

综上所述，BPSO算法存在过早收敛问题，其权重设置存在不合理的问题。为了将BPSO算法更好地用于特征选择，本文研究在粒子位置更新后提出了一种自适应变异操作，同时对算法惯性权重参数采用一种递增的设置方案，从而得到一种自适应变异BPSO算法(AMBPSO)。

1 相关工作

群智能优化算法源于模仿自然界中生物群体的行为模式，适用于解决大规模复杂性问题。如今，要处理的数据规模越来越大，数据中冗余的特征数量也越来越多，特征选择即成为大规模的NP难问题。所以，群智能优化算法适合特征选择问题的处理，尤其在包裹式的特征选择方面，大量的群智能优化算法被应用，例如遗传算法、蚁群算法、蝗虫优化算法、蜻蜓算法等[10-13]。群智能优化算法在处理特征选择问题时以生物个体作为特征选择的一个候选解，以分类准确率或分类错误率作为评价函数来引导群体生物中生物个体向群体最优位置移动，从而得到最优解。BPSO算法的原理、参数设置相对简单，理论成熟度上比较成熟。但是同其他群智能算法一样，BPSO算法也易陷入局部最优的求解问题。一般的启发式搜索算法要求前期要具有全局搜索能力，后期要具有局部搜索能力，对于BPSO算法的改进也需要遵循这个原则，平衡算法的搜索能力。

2 基于自适应变异BPSO的特征选择

2.1 BPSO 算法

BPSO算法是Kennedy于1997年在连续性PSO算法基础上提出的，用于解决离散的优化问题[14]。

任意粒子i(i=1,2,…,N)根据公式(1)更新速度:

(1)

式中，id、gd表示坐标变量，vid表示粒子速度，c1、c2表示学习因子，rand()表示 0～1 之间的随机数。pid表示个体最优粒子位置，pgd表示群体最优粒子位置。xid表示粒子位置，ω表示惯性权重，衡量粒子学习过程中上一代粒子对当代粒子的影响权重，受PSO算法的影响，BPSO的权重通常采用随机迭代递减的方法。BPSO算法用于解决离散空间中的优化问题，基于二进制编码原则，算法中粒子位置向量每一维取值只能为0和1。Kennedy 提出利用 Sigmoid 函数作为转换函数，将连续空间中的位置向量的每一维映射到二进制编码中的0或者1。通过公式(2)计算对应的Sigmoid 函数值:

(2)

式中，vid表示粒子速度，s(vid)表示位置xid取1的概率，粒子通过(3)式改变它的位值：

(3)

其中，rand()是0～1 之间的随机数。

2.2 BPSO算法的自适应变异操作

BPSO由于在汉明空间中变化，存在容易预收敛等问题。公式(2)特性造成当速度vid很大时，s(vid)很接近1，且恒为1，致使xid不易改变，算法过早收敛；反之当速度vid很小，也易收敛于0。综上，BPSO易于过早收敛。为了提高BPSO算法的多样性，克服过早收敛问题，文献[15]对BPSO算法提出了一种变异手段，粒子在(3)式更新位置后引入了变异操作如式(4)。

(4)

式中，rmut代表变异概率，且rmut=1/N，N为数据维度，也就是对每个粒子每位都会产生概率为rmut的变异可能。

但是式(4)的rmut在算法迭代过程中为定值，缺少对BPSO算法缺陷的针对性。一般启发性算法前期需要较强的全局搜索能力，后期需要突出局部的搜索能力。基于上述原理，BPSO算法早期变异率要大，晚期变异要小。因此引进如式(5)变异操作。

(5)

式中，R表示变异概率，但不是固定值，采用一种递减策略，如式(6):

(6)

式中，t为当前算法迭代的代数，T为算法迭代的最大代数。

算法采用式(3)更新后，执行由式(5)(6)组合的变异操作，表示在产生新的粒子时，每一个粒子每位产生一定变异概率。根据分析，式(6)的变异概率R值是从1到0，即早期几乎都会发生变异，而晚期几乎不发生变异，变异概率随着代数的增加自适应从1到0变化，而式(4)中rmut固定值表示每次变异概率都只是为1/N(维度分之一)。

2.3 BPSO的惯性权重设置

受到PSO算法影响，BPSO算法也存在惯性权重w，其设置采用式(7)的线性递减方案，

(7)

式中，wmax表示惯性权重最大值，wmin表示惯性权重最小值，t表示当前的迭代次数，T表示最大的迭代次数。

文献[16]通过理论分析研究了惯性权重w的设置对算法的影响，认为算法应当在初期有很强的全局探测能力，逐步到后期的时候具有很强的局部探索能力。保持其他参数不变时，较小的惯性权重能够增强全局探测能力较大的惯性权重能够增强局部的探索能力。本研究采用惯性权重线性递增的方案如式(8)。

(8)

式中，ρ取0.9，意味着权重变化迭代到最大代数的90%代就结束了。此后的迭代中，权重为固定的值。

PSO算法中，惯性权重w一般采用式(7)的递减策略，w值从0.9递减到0.4；传统的BPSO采用类似的方案。本研究将式(8)的递增方案引入BPSO算法中，wmax和wmin的取值方法将在试验方法中确定。

2.4 kNN算法

将BPSO应用于特征选择，需要一个监督学习器评价其特征选择的适用度函数。最近邻近算法(k-Nearest Neighbor algorithm，kNN)是一种常用的监督学习方法[17]，其工作机制简单理论上比较成熟，易于快速实现。其基本原理是：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这些样本的信息来预测，选择k个样本中出现最多的类别标记作为预测结果。本研究采用kNN算法对数据进行分类判别，作为选取数据特征子集的评价函数，k取5。

2.5 带自适用变异操作BPSO的特征选择算法流程

带自适用变异操作的BPSO算法(AMBPSO)在原始BPSO算法执行式(3)位置更新后，再采用式(5)(6)变异操作，并辅以式(8)的权重设置方案，最后将特征选择结果应用于kNN构造分类准确率评价中，因此产生了AMBPSO特征选择算法。其流程包括AMBPSO特征选择算法流程和5-NN算法流程。

AMBPSO特征选择算法流程

1 开始2 初始化粒子群,粒子维度dim=样本数据维度,种群数量popsize=203 popul=rand(popsize,dim)<0.54 记录初始个体最优bestpos=popul5 计算各粒子适应度值fitvalue by 5-NN()6 记录最佳适应度值fbestpos,以及对应粒子位置g7 While(停止准则为最大迭代次数)8 更新个体最优9 利用(1)式更新粒子速度10 利用(2)和(3)式更新粒子的位值11 利用(5)和(6)式对粒子位值进行变异12 计算新的各粒子适应度值by 5-NN()13 与现有粒子适应度值作比较,更新全局最优,记录最佳适应度值及更新对应粒子位置g14 End (直到满足最大迭代次数)15 输出最佳适应度值即为分类准确率

5-NN算法流程

1 for i=1 to测试数据的样本数量2 for j=1 to训练数据的样本数量3 for m=1:popsize4 特征选择方案:A(m)=popul(m,:)5 if A(1,dim)==0distij=06 else7 distij=distij+(dataik-datajk)28 end if9 next m10 next j11 对distij进行从小到大排序记录其对应类别12 取出前k(k=5)个distij及其对应类别13 对k个样本所属类别个数进行统计14 选出出现次数最多的类别即为第i个测试样本的类别classi15 next i16 correct=017 for i=1 to分类问题的样本数18 if classi=第i个测试样本 then19 correct=correct+120 end if21 next i22 适应度值=corret/测试数据样本数量

3 实验与结果分析

3.1 相关参数设置与原始数据集

在PSO算法中学习因子c1、c2均取2，种群数量为20，最大迭代次数为1 000，kNN算法中的k值取5。用于测试数据为8种不同类型的数据集，这些数据都是从从UCI机器学习数据库下载(https:∥archive.ics.uci.edu/ml/index.php)。数据集信息如表1。

表1 数据集信息

3.2 实验方案

从惯性权重和对更新粒子进行变异两个角度分析BPSO算法性能的变化。为了决定递增惯性权重设置方案中的wmax和wmin的取值，对原始BPSO方案采用几组不同权重取值方案，对每个数据集分别运行30次，取其平均选择特征数和平均分类准确率作为算法性能的评价标准，最终确定一个最优的权重方案。

在选择了最佳的权重方案条件下，通过实验，比较带固定变异的BPSO和本文提出的带自适应变异BPSO分别应用特征选择的分类准确率性能。因实验方案分两个内容如下：

(1) 在惯性权重设置方面分别采用原始递减区间0.9～0.4、递增区间0.4～0.9、递增区间0.4～1.0 这3种不同的设置方案分别对8组不同类型数据进行特征选择实验对比。

(2) 在最佳惯性权重设置方案基础上，分别用AMBPSO与文献[15]提出固定变异MBPSO算法对8组数据进行特征选择后分类准确率对比。

3.3 实验结果分析

3.3.1 基于权重设置不同方案BPSO特征选择

在惯性权重设置方面分别采用原始递减区间0.9～0.4、递增区间0.4～0.9、递增区间0.4～1.0等3种不同的设置方案，分别对8组不同类型数据最优的特征选择，即寻找采用kNN分类准确率性能最优的特征选择方案。

表2给出了采用3种惯性权重设置方案的数据集分类准确率。从表2可以看出，在采用惯性权重递增方案且递增范围与原始递减范围一致时，数据集WDBC分类准确率稍低于原始递减方案，其他数据集分类准确率稍高于原始递减方案，但变化较小，可见算法性能提升较小。把惯性权重递增范围上限提升到1.0时，分类准确率均高于前两种方案，算法性能得到进一步提升。因此，本研究的惯性权重设置方案为递增且递增区间为0.4～1.0。

3.3.2 AMBPSO算法与MBPSO算法性能的比较

AMBPSO算法的惯性权重设置方案为上节确定的0.4～1.0的递增策略，实验分别用AMBPSO和MBPSO算法特征选择的分类准确率。为了更对比性能，实验中也列出两个特征选择时，分别选择出的特征数量。表3给出了研究所采用的AMBPSO算法跟文献[15]所用MBPSO算法的比较结果。

从表3可见， AMBPSO算法性能在分类准确率和选择特征数量上都要明显优于MBPSO算法，尤其是3个维度较高的数据集Ionosphere、SPECTF、Snoar效果更加明显。

表2 不同惯性权重设置方案的分类准确率

表3 AMBPSO算法与MBPSO算法实验结果比较

3.3.3 选择特征数量的实验比较

为了对算法性能做更好的对比，表4给出了数据集在3种惯性权重设置方案及变异后选择特征的数量，从表4可以看出，采用区间在0.4～0.9的方案除数据集Vehicle、SPECT、Snoar选择特征数量相较原始方案减少1至2个外，其他数据集选择特征数量减少数量变化较小或有所增加。采用区间在0.4～1.0的方案相较前两个均无明显变化，以上分析采用3种惯性权重设置方案所选择的特征数量总体上无明显变化。但在采用AMBPSO算法之后的选择特征数量明显少于3种惯性权重设置方案，尤其是在高维数据的变化更为明显，说明从特征选择数量性能指标分析，自适应变异BPSO的特征选择数据不仅优于固定变异操作，而且也提高了原始BPSO算法在不同权重方案下的性能。

表4 不同惯性权重设置方案选择特征的数量

3.3.4 实验曲线对比图

为了直观地比较AMBPSO算法对特征选择性能的影响，图1给出了原始BPSO算法和AMBPSO算法在(a)～(h)8个数据集上的分类准确率随迭代变化的对比曲线。从图1可以看出，除了数据集Wine后期分类准确率AMBPSO算法稍低之外，其他7个数据集的AMBPSO算法分类准确率在实验前期低于原始BPSO算法，在实验后期随着迭代次数增加都明显高于原始BPSO算法，说明在前期，AMBPSO算法的粒子的变异率较大，全局搜索能力较强，后期随着迭代次数的增加，粒子变异率逐渐减小，算法的局部搜索能力得到增强，最终AMBPSO算法分类准确率比BPSO算法高。图1曲线图与2.2节所分析的理论完全吻合，并且算法性能得到明显提高。

综上分析，从分类准确率和选择特征数量两个角度对比，结果证明本研究采用的新的惯性权重方案和自适应变异操作相结合的AMBPSO算法具有明显优势，从实验曲线图上可以看出AMBPSO算法增强了原始算法前期的全局搜索能力和后期局部搜索能力，明显提高了算法性能。

图1 BPSO算法和AMBPSO算法在8个数据集上的实验曲线对比图Fig.1 Comparison of experimental curves of BPSO algorithm and AMBPSO algorithm on 8 data sets

4 结论

本研究提出的AMBPSO算法采用了线性递增的惯性权重设置，并通过实验验证的方式确定了惯性权重的取值区间。另外在粒子更新后采用了一种变异操作，随迭代次数变异概率递减，使得粒子在前期的变异率大，后期变异率小。该算法在前期粒子的多样性更强，具有较强的全局搜索能力，后期具有较强的局部搜索能力，算法性能明显优于原始的BPSO算法以及固定变异的二进制粒子群算法(MBPSO)。