Page 69 - 《软件学报》2020年第12期

张鑫 等:自然进化策略的特征选择算法研究 3735

确地控制种群的搜索范围和强度,这使得算法的鲁棒性不足;
• 其次,演化计算方法是通过个体在搜索空间进行探索来寻求最优解,当搜索空间比较大时,算法容易陷
入局部最优解,这导致演化计算方法对于高维数据的处理能力不足.
因此,特征选择算法上仍存在较多可改进和完善之处,特别是在处理高维数据的特征选择问题上.
作为进化算法的一种,进化策略(ES) [22,23] 在一些强化学习任务中的成功案例证明了进化策略能够有效适
用于评价学习 [24] .评价学习不同于监督学习和非监督学习,算法通常需要从一些离散的、有噪音的、延迟的标
量信息中学习.作为强化学习中一种重要的学习算法,策略迭代通常会使用神经网络作为决策机制 [25] ,并使用误
差反向传播来优化策略函数.文献[24]中替代了策略迭代中误差反向传播优化参数的方式,直接使用进化策略
对决策网络进行优化,最后达到了预期的目标效果.
包裹式的特征选择方法首先选取特征子集,然后使用学习算法对其进行评估,因此,特征选择也可以看作是
一种评价学习.受此启发,本文使用 ES 作为全局搜索算法进行特征选择,之后的工作证明了 ES 能够完成特征选
择任务,同时,与其他的特征选择方法相比也有一定的竞争力,并且能够有效地以分布式的方式进行多种群竞争
进化 [26] .
本文算法的具体实现过程为:在自然进化策略的基础上,通过采用一种新的编码方式使其能够适应于特征
选择问题;然后,结合模型分类准确率和特征维度缩减设计了一种新的适应度函数;同时,基于新的适应度函数
提出一种适应度塑造方法用于构造目标优化函数;之后,为了有效处理高维数据,在算法模型中引入亚种群合作
协同进化的思想;更进一步,以多种群分布式竞争进化的方式加速算法的收敛,并设计种群重启策略来防止种群
陷入局部最优解;最后,使用 GPU-Tensorflow 作为算法运行框架实现多种群分布式进化.我们将提出的算法记为
MCC-NES(multi-group cooperative coevolution feature selection algorithm based on natural evolution strategy).同
时,我们将本文提出的算法与近几年提出的其他比较高效的特征选择算法在 16 个 UCI [27] 的数据集中进行了对
比实验,验证了我们算法的有效性和优越性,尤其是在处理一些高维数据时有出色的表现.具体体现在:
首先,本文的方法可以高度并行化,通过引入特定的通信机制,可以使得多个工作线程在运行时并行加速;
其次,本文提出的方法表现出一种很好的探索能力,因为在已知均值和方差的情况下,正态分布是一种信息熵最
大、最不稳定的分布,算法在迭代中,通过正态分布生成搜索点能够保证算法对于搜索空间进行有效的探索;最
后,本文的方法有很好的鲁棒性,算法能够根据搜索情况自适应改变分布均值和方差来调整搜索的强度和范围.
1 相关工作

1.1 特征选择问题
特征选择问题可以描述为:用 S 表示 K 个样本 D 个特征的数据集,F 为 D 个特征的集合.特征选择任务就是
从集合 F 中选取 d 个特征,其中,d<=D,使得目标函数 f(⋅)取最大值,这里的目标函数一般表示为模型分类准确率.
也就是说,特征选择的目的是通过选取最少特征数的特征子集 X(X∈F)来使目标函数最大化.
我们采用如下二进制编码方式来表示选取的特征子集:
X = i ( ,...,x 1 i x i D ),x ∈ i j {0,1} (1)
其中, x = 表示第 i 个特征子集 X i 中第 j 个特征被选取;相应的, x = 0 表示这个特征不会被选取.那么,特征选
i
i
1
j
j
择问题就可以表示成如下的优化问题 [15] :
⎧ max ( )fX
i
⎨
x
⎪ s. t. X = i ( ,...,x i D ), x ∈ i j {0,1}, j = 1,2,...,D (2)
1
⎪
≤
⎩ 1| X ≤ | D
其中,|X|表示在特征子集 X 中所选取的特征数量.
1.2 进化策略
进化策略是一种黑盒优化算法,首次由 Ingo 等人提出 [28,29] ,并被设计用来处理高维连续性优化问题.如文献