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

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

种自适应调整分布空间的方式,就是在每次迭代中,根据样本中最优的适应度值与最差的适应度值之间的差距
来调整分布空间的取值范围,这使得当种群中个体表现差异比较大的时候,能够增加参数调整的幅度;而当种群
中个体表现相似时,减小参数调整的步长:
⎧
⎪ ux ux + ( ) (i − 1)δ
() =
⎪ ⎪ i () − 1
( )
...
⎨ δ = fx λ fx 1 ,( f x 1:λ )≤≤ ( f x : λλ ) (11)
⎪ λ − 1
() −
⎪ fx f x
( )
() =−
⎪ ⎩ ux 1 λ 2 1
2.3 种群内的亚种群合作协同进化
我们使用 ES 算法解决特征选择问题最直接的想法就是基于数据集中所有的特征进行建模,但是这种建模
方式在处理一些高维数据时就会显现出弊端(因为搜索空间随数据维度呈指数级增长,由于计算资源的限制无
法完成矩阵建模).因此,我们在算法中引入了亚种群合作协同进化的思想 [41] .合作协同进化通过将原始特征集
划分成相对较小的子特征集,然后在每个子特征集中独立应用进化策略进行局部搜索,子特征集完成搜索后,将
通过合作协同进化来组合优化原特征选择问题的解决方案.
具体的,首先对数据集 D 按照特征随机划分成若干组 A={A 1 ,…,A n },各组包含的特征相互独立且唯一,然后
初始化 n 个对角协方差矩阵 C={C 1 ,…,C n }、n 个分布均值向量 M={m 1 ,…,m n }以及 n 个亚种群 S={S 1 ,…,S n },并
使每个亚种群 S i 对应一个子特征子集 A i 、一个均值向量 m i 以及一个对角协方差矩阵 C i (|A i |=|S i |=|m i |=rank(C i )).
初始化完成之后,让 n 个亚种群同步进行迭代更新.由于每个亚种群只维护一个子特征集的信息,而原特征选择
问题需要在原始特征集合中进行全局搜索,因此需要在每次迭代中,在 n 个亚种群间进行信息交互.具体的,每次
n
迭代时,每个亚种群随机产生 m 个搜索点,对于 n 个亚种群来讲,就会有 m 个子特征序列的组合,如果完整评估
所有特征序列的组合,当 n和 m增大时,很容易陷入组合爆炸.不失一般性,我们保留一定的历史信息,在组合的过
程中,我们保留种群历史表现最好的全局特征序列,每个亚种群的搜索就可以看成是对当前全局最优特征序列
的一次局部探索,每个亚种群产生的搜索点只改变当前亚种群在全局最优特征序列中所对应的这一部分特征,
同时对局部改动的全局最优特征序列进行评估,作为对当前亚种群采样的评估.如此,通过保留历史最优全局特
征序列,就会极大地降低算法搜索复杂度 O(m*n).进一步地,为了防止搜索过程中陷入局部最优解的情况,每次
迭代时选择保留表现排名前三的全局特征序列和一个随机产生的全局特征序列.这里,随机特征序列的产生是
由当前全局最优特征序列决定的,根据当前全局最优特征序列中特征的个数,随机地在原始特征集合中选取相
同数量的特征构成随机特征序列,然后,每次迭代时,每个亚种群同时在这 4 个特征序列上进行局部搜索.以上过
程是在一个种群中,通过亚种群协同进化的方式来实现种群优化的完整过程.
协同进化是一种进化算法,算法一般通过种群间相互激励来提升种群各自的性能.如在 IFS-CoCo [21] 算法
中,通过特征选择与实例选取协同进化来提升分类器准确率.我们所采用的方式与一般的协同进化方法不同:它
类似于分治法的思想,将原始集合划分为多个分组,通过分组与原始集合间协同进化来指导搜索.具体,算法在
迭代过程中,每个分组采用 ES 算法进行搜索,在分组进化过程中,我们会保留历史前三全局最优序列,同时使用
一个全局随机序列,每个分组在进化过程中都会和这 4 个全局序列进行交互,并更新全局最优序列.通过这种方
式,一方面为了防止算法陷入局部最优解,同时解决分组间组合爆炸的问题.
2.4 多种群间竞争进化及种群重启策略
第 2、3 节详细描述了一个种群使用合作协同进化解决特征选择问题的完整过程,进一步的,我们通过分布
式操作将这个过程扩展到多个种群实现多种群竞争进化.同时,为了防止种群陷入局部最优解,提出了一种种群
重启策略:
因为在算法初始阶段种群采用随机初始化,所以一个种群在迭代中的收敛速率和性能都很依赖于种群在
搜索空间中的初始化位置.引入一种种群重启机制,当一个种群的整体性能表现不好或者当种群性能上升停滞