融合蝠鲼旋风式觅食策略的灰狼特征选择算法

杨舒云,刘宏志,李海生

(北京工商大学计算机学院,北京 100048)

1 引言

随着大数据时代的到来,越来越多高维数据集应用于数据挖掘中,并伴随着复杂噪声,给机器学习带来严峻的维度灾难问题。特征选择是从原始特征中选择出最有效特征,以降低数据集维度,提高模型性能的过程,因此近年来逐渐成为一个研究热点。

一般来说,特征选择的算法分为三类:嵌入式(embedded)、过滤式(filter)和封装式(wrapper)。在封装式方法中,使用学习算法来评估所选的特征子集,穷举法、顺序搜索、全局搜索等方法都可以用来搜索特征子集。但是在大部分情况下,穷举法因计算量太大而无法应用,顺序搜索法采用局部搜索可能导致局部最优,而全局搜索法主要采用随机搜索策略来探索解空间,因此有更大可能搜索到全局最优解。近年来,很多元启发式方法,如鲸鱼优化算法[1]、粒子群优化算法[2]等,由于其在全局搜索空间中强大的搜索能力,已经在函数优化[3]、参数优化[4]等领域显示出其有效性。其中,灰狼优化算法由于其较强的鲁棒性和参数少等优点,已经被证明了在特征选择领域的有效性,然而传统灰狼算法也存在易早熟等问题,从而导致次优解。

为了提高算法分类精度,一些学者开始对基本灰狼算法进行改进。Al-Tashi Q等人[5]提出了一种灰狼算法与粒子群算法结合的二进制版本进行特征选择,经对比实验表明取得了较高的性能。Attia等人[6]将灰狼优化与粗糙集理论结合,在维度各异的公开数据集上取得了较好的收敛速度和分类精度。Hu,Jiao等人[7]开发了一种通过协方差矩阵自适应进化策略、征税飞行机制和正交学习策略增强的 GWO 变体,增强算法的探索性能,在UCI数据集上都获得了优越的性能。徐明等[8]提出了基于正弦函数的非线性过渡参数、小孔成像学习等多种策略来提高寻优精度,在基准数据集上验证了其有效性。

上述研究从不同角度提高了灰狼算法的寻优性能,但勘探与开采能力的不平衡问题仍然存在,算法求解精度仍有待提高,如Hu,Jiao的GWO变体带来了更有效的勘探倾向,但是并未对算法的开采性能进行改进,徐明的非线性参数过渡等多种位置更新策略在一定程度上实现了全局勘探到局部开采的良好过渡,但忽略了种群初始化阶段的多样性。因此继续对其改进很有必要,本文提出一种融合蝠鲼旋风式螺旋觅食策略的混合灰狼算法(BWSGWO)用于特征选择,以达到更高的收敛精度。

2 基本GWO算法

灰狼优化算法(Grey Wolf Optimizer,GWO)模拟狼群严格的社会等级制度和狩猎行为[9],狼群中适应度最好的三匹灰狼依次记为α、β、δ,剩下的灰狼记为ω。其狩猎过程包括包围猎物和攻击猎物,重复以上步骤,直到达到终止条件,则停止迭代,获得最优解。

3 改进GWO算法

3.1 Tent混沌策略初始化种群

灰狼算法受种群初始状态的影响较大,低质量的初始种群在很大程度上影响了算法的收敛速度,导致算法的寻优效果较差。基本GWO算法采用随机方法初始化种群,没有任何先验知识,可能会导致种群分布不均匀,一些ω狼的位置距离最优值过远,从而容易陷入局部最优解。

混沌系统有随机性和遍历性等特点,通过其产生的灰狼群体具备较好的多样性。其基本思想是通过映射关系产生[0,1]之间的混沌序列,再将其逆映射到灰狼个体的搜索空间。常见的混沌映射有Logistic映射和Tent映射等,单梁等[10]证明 Tent 映射比 Logistic 映射的分布更均匀,因此,本文采取Tent混沌映射的方法初始化种群,有效避免基本GWO算法中随机函数初始化种群造成的局部最优风险,其数学表达式如下

(1)

式中,μ为混沌参数,不同μ值Tent映射的范围不同。μ取0.5时,系统呈现短周期状态,故不可取,本文经多次实验及文献分析,取最优μ值为为0.7,由图1(a)(b)可以看出,当迭代一定次数时,混沌参数为0.7的混沌系统会产生更加均匀的混沌序列。

图1 Tent混沌映射变化曲线

3.2 蝠鲼旋风式螺旋觅食策略

蝠鲼觅食优化(MRFO)[11]是 2020年提出的新型智能仿生群体算法。由于传统灰狼算法在位置更新时总是跟随三匹领导狼,导致局部开采能力强、全局勘探能力弱,针对这个问题,本文受MRFO启发,通过蝠鲼觅食会排成螺旋形捕捉高浓度浮游生物,引入新型旋风式螺旋觅食策略进行群体协作,其数学模型如下

(2)

式中,β为权重系数,r为[0,1]中的随机数,当t/T

图2 二维空间中的旋风觅食行为

如图所示,灰狼个体不仅跟随它前面的个体,而且只沿着螺旋形路径向猎物移动,形成长长的觅食链,从而大幅提高搜索效果。

本文结合灰狼算法自身优势,根据迭代次数的不同在旋风式螺旋觅食与传统觅食之间转换,以实现广泛的适应性搜索。对于传统觅食行为,结合个体对历史最优解的记忆进行改进,为每一匹狼建立历史仓库,解决了传统灰狼算法只盲目跟随领导狼,忽略个体与自身经验交流的问题,其位置更新方程定义为

(3)

(4)

式中,w为惯性权重,X1、X2、X3、X4分别为灰狼个体向着α、β、δ及自身历史最优解前进的步长和方向,A和C为系数向量。

3.3 自适应精英反向学习策略

(5)

式中,k可以取不同的实数,当k=1时称其为广义反向学习,lbj和ubj分别为第j维搜索空间的边界。虽然反向学习有大于一般的概率优更逼近最优解,但是并不能保证一定优于原解,因此,在反向学习后采用贪心策略选择其中的更优解进入下一次的迭代,其数学模型如下

(6)

同时,为适应种群复杂的非线性变化,加入变异因子Mp进行选择性反向学习,即随着迭代次数的增加,变异概率非线性递减,前期变异概率大,更有利于全局勘探,后期变异概率小,有利于局部开采迅速收敛,其数学模型如下:

(7)

式中,Mpmax为最大变异概率,Mpmin为最小变异概率。

4 BWSGWO特征选择算法组成

4.1 二进制离散编码

特征选择问题本质上是要找到一个合适的0/1串,0表示特征不被选择,1表示特征被选择,如图3所示为一个包含十个特征数据集的可能解决方案。

图3 解决方案表示

基本GWO算法在提出之初主要是为了解决解决连续优化问题,为了能让其解决离散空间问题,引入二进制思想来重新设计算法,使用转换函数来实现连续搜索空间到二进制空间的转换。但是代表性的S型转换函数sigmoid变化敏感,易于饱和,影响特征选择的精度,而tanh[13]函数克服了这一缺点。综上,本文采用V型函数tanh进行二进制转换,其数学模型如下

xsi=|tanh(x)|

(8)

(9)

4.2 适应度函数设计

特征选择问题被认为是一个多目标问题,因为它必须实现以下两点:最大化给定分类器的分类精度,最大限度地减少所选特征的数量。基于上述,本文将用于评估解决方案的适应度函数设计为实现两个目标之间的平衡,即

(10)

式中,error表示分类错误率,用KNN采用十折交叉验证法计算,F代表所选特征子集长度,dim代表原始数据集中所有特征,α和β是对应于分类精度和所选特征子集长度的权重参数,α∈[0,1]且β=1-α,本文算法意在保证较高精度的前提下减少特征数目,因此将α和β分别设置为 0.99 与 0.01[13]。

4.3 算法流程

综上所述,本文提出了融合蝠鲼旋风式觅食策略的灰狼特征选择算法,其执行步骤如下:

Step1:设置相关参数,种群规模N,最大迭代次数Tmax,搜索维度为d,搜索范围[lb,ub];

Step2:根据3.1节描述的Tent混沌策略初始化灰狼种群,并计算其适应度值,保存适应度最好的前三匹狼记为α、β、δ;

Step3:据3.2节描述的策略,由当前迭代次数与总迭代次数的比值,当t≤ 0.7T时,采用蝠鲼旋风式螺旋觅食策略进行灰狼位置更新,当t> 0.7T时,将灰狼等级捕猎制度与个体最优解记忆策略结合,进行围捕中的位置更新,以实现勘探到开采的良好过渡;

Step4:采用自适应精英反向学习策略,以一定的概率对当前最优解求其反向解,并进行两两评估,贪婪地选择较优解作为下一代个体精英个体;

Step5:重复上述步骤,若达到终止条件,则停止迭代,并输出结果。

5 仿真分析

5.1 仿真参数介绍

本文的仿真中,为保证仿真结果的公平性,各算法基本参数的选择相同,种群规模 N 为 10,最大迭代次数 Tmax为 100,取自参考文献中的经验值[14],其它对比算法的参数设置也与相应的参考文献保持一致。由于元启发式算法的特征选择具有一定的随机性,为避免偶然误差对实验结果产生影响,所有算法独立运行10次取平均值。

5.2 实验数据集介绍

本文从机器学习资料库UCI中收集的8个规模各异、特征数目不同的标准测试数据集进行特征选择,来验证所提算法的有效性。数据集的详细信息如表1所示。

表1 数据集信息

5.3 实验结果分析

为验证本文所提策略的有效性,本文将所提算法与经典离散粒子群算法、灰狼优化算法、鲸鱼优化算法作为对比,在表1的数据集上进行进行10次独立重复实验,比较算法的平均性能指标。

5.3.1 分类精度与所选特征数对比

表2从运行结果的平均分类精度及平均所选特征数对算法进行了对比。其中,加粗字体为所有算法中的最高平均分类精度和最小平均特征数。分析BWSGWO的实验结果可知,在所有的数据集中,BWSGWO都展示出了最高的分类精确。同时,在大部分数据集中,BWSGWO都展示出了较低的特征数,除了在ionosphere、Sonar、WaveformEW数据集中,本文所提算法虽然在特征选择数目上不是最佳,但与最优特征数差距不大,同时精度得到了非常显著的提升。

表2 测试数据集准确率对比

5.3.2 适应度对比

表3为四种算法的适应度函数值对比,其中Avg＿fit、Best＿fit分别为算法在不同数据集上的平均适应度和最佳适应度。由表4可知,除WaveformEW、Lymphography、Exactly数据集外都取得了最优的最佳适应度,尽管在在WaveformEW、Lymphography、Exactly数据集中表现不是最优,但是其上限接近最佳。此外,本文所提算法在8个数据集上都取得了最优的平均适应度,这在一定程度上表明了所提算法的稳定性。

表3 测试数据集适应度对比

5.3.3 收敛性分析

图4所示为8个数据集上BPSO、BGWO、BWOA、BWSGWO的适应度曲线对比结果。从图4中的收敛趋势可以看出,随着算法迭代次数的增加,各个算法在不同数据集上的适应度值均在降低,但相较于BPSO、BGWO、BWOA,本文提出的BWSGWO算法在总迭代次数相同的情况下,总能搜索到更优的解。图4(c)(e)分别为四种算法在Sonar和HeartEW数据集上的实验结果,表明BWSGWO算法在上述两个数据集上的收敛速度均大幅优于其它算法且搜索到的解都优于其它算法。图4(f)为四种算法在Lymphography数据集上的实验结果,表明BWSGWO算法在1次迭代后就搜索到了比其它算法更优的解,且前8次的迭代中收敛速度都优于其它算法,虽然在8-33次的迭代中暂时陷入局部最优,但是依然始终优于其它算法,且33次迭代之后迅速收敛得到全局最优解。图4(a)(d)(h)分别为四种算法在KrVsKpEW、WaveformEW、Exactly数据集上的实验结果,虽然在前期的迭代中表现并不是最优,但中后期快速收敛,搜索到的解均远由于其它算法。

图4 改进算法在8个数据集上的适应度曲线

综上可知,本文所提BWSGWO算法总能搜索到比其它算法都更优的解,体现出 BWSGWO算法具有更好的寻优性能。

因此,综合分类准确率、特征选择数量、鲁棒性、搜索性能和收敛性能方面对比四种算法,本文所提BWSGWO特征选择算法的总体性能优于其它四种算法。

5.4 时间复杂度分析

虽然特征选择算法需要取得较高的准确率,但是也需要较低的时间复杂度。在种群规模为N,优化维度为D,最大迭代次数为Tmax的情况下,基本GWO时间复杂度主要为种群初始化部分和灰狼位置更新部分,其时间复杂度为O(NDTmax)。

同理,改进灰狼的基本流程与基本GWO一样,此外,引入混沌策略O(ND),蝠鲼旋风式螺旋觅食策略与粒子群策略的新型捕猎行为O(NDTmax),自适应精英反向学习策略O(DTmax),因此总的时间复杂度与基本GWO算法相比没有增加,依然为O(NDTmax),都取决于种群规模、优化问题维度与最大迭代次数,因此可判定改进算法并未造成时间复杂度的增加,但是其性能却得到了显著的提升,证明了本文所提算法的有效性。

6 结束语

本文针对传统灰狼算法易陷入局部最优、寻优性能差的问题,提出了融合蝠鲼旋风式觅食策略的灰狼特征选择算法。创新性地引入蝠鲼旋风式螺旋觅食策略及时调整灰狼最佳位置,并为种群建立历史仓库,有效降低了传统灰狼算法中只跟随领导狼群进行捕猎的盲目性,大幅协调了灰狼种群的勘探和开采性能。此外,引入Tent混沌映射提高种群多样性,自适应精英反向学习策略提升抗局部极值能力。相较于其它经典元启法式算法,具有寻优策略良,算法不易早熟等优势。在8个规模各异、特征数目不同的UCI标准数据集上进行仿真,仿真结果表明,与经典算法BPSO、BGWO、BWOA对比,本文提算法能在最大程度提高分类精度的同时,保证较低的特征选择数,算法性能大大提升。在后续的研究中,主要考虑寻找更高效的特征表示方式,并进一步拓展该算法的应用领域。