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

3736 Journal of Software 软件学报 Vol.31, No.12, December 2020

[30]所述,ES 是自然启发优化算法的一种,那么 ES 中同样包含基因突变、重组以及选取候选解的过程,并以迭
代的方式进化越来越好的解.进化策略中包含一个用于评估种群个体基因序列的适应度函数,每次选取候选解
的时候,最好的个体将会被保留,其他的个体直接舍去.然后,在保留下来的个体中,通过扰动基因序列来生成下
一代的个体,整个过程通过迭代就会找到较优的结果.
其中,公式(3)为给定优化问题的一般形式,那么进化策略可以应用于优化问题的所有领域,包括无约束和有
约束以及混合约束的搜索空间 Y 中:
*
y =argopt y∈Y f(y) (3)
进化策略又有两种候选解选取策略:(μ,λ)-ES 和(μ+λ)-ES.这两种策略的不同之处在于:前者每次迭代产生λ
个新解,选择较好的μ个成为下一次迭代的父代(μ≤λ),其他的直接舍去,其中,每个个体只存活一代,随即被新的
个体代替;而后者每次迭代产生λ个新解,通过和父代中的个体进行比较,选择较好的μ个成为下一次迭代的父
代,其他的直接舍去.本文采用第一种候选解选取策略,因为前者能够更有效地对搜索空间进行探索而不容易陷
入局部最优.ES 中每个个体 x 的一般形式为
ES individual x:=(y,θ,F(y)) (4)
其中,y∈Y 表示需要优化的目标序列;θ表示策略参数,并且θ中相关参数在 ES 算法中会自适应的进行调整;F(⋅)
为目标函数.使用这种表述形式,特征选择问题(2)也可以看作是进化策略的一种优化问题进行求解.
1.3 进化策略的框架
近年来,进化策略的框架已被广泛开发,包括使用完全协方差矩阵作为分布模型表示相关突变,这使得算法
框架在变异生成下一代个体时能够利用属性之间的协方差关系来捕获它们的相关性,因此,突变可以自适应局
部搜索情况,并且可以显著增加向最优解的收敛性能.协方差矩阵自适应进化策略(CMA-ES) [31] 已在多项研究
中证明是成功的 [32−34] .
我们的工作是基于自然进化策略(NES) [35,36] 展开的,NES 也是进化策略在框架上的一种扩展.NES 通过使
用样本的估计梯度来迭代地更新搜索分布.算法过程如下:搜索分布采样用于生成一批搜索点(即每代种群),然
后根据适应度函数评估每一个搜索点(种群中的每个个体),之后计算搜索点的搜索梯度并使用梯度上升的方
法,通过最大化种群适应度均值来自适应地调整模型中相关的参数.
NES 的核心就是使用搜索梯度 [37,38] 来更新搜索分布中的参数.我们将搜索梯度定义为样本预期适应度的
梯度,其中,搜索分布采用多元正态分布.如果用π(x|θ)表示参数为θ的分布策略,用 f(⋅)表示的样本适应度函数,我
们可以将搜索分布下的预期适应度表示如下:
[ ( )] =
( ) ( | )dxπ =
J () θ Ef x ∫ f x x θ (5)
θ
然后对公式(5)求导,并采用对数似然表示:
∇ θ J(θ)=E θ [f(x)]∇ θ logπ(x|θ) (6)
使用公式(6),我们可以从种群个体(x 1 ,x 2 ,…,x λ )得到搜索梯度的估计值:
( )∇ ∑
π
∇ θ J () θ ≈ 1 i= λ 1 f x i θ log ( | ) θ x i (7)
λ
公式(7)中,λ表示种群的大小,样本预期梯度在搜索分布空间中提供搜索方向,采用梯度上升来迭代更新搜
索分布:
θ←θ+η∇ θ J(θ) (8)
公式(8)中,η表示学习率.算法 1 表示在搜索分布上使用搜索梯度.
算法 1. Search-gradient-algorithm.
Initialize parent population p = { ,...,x 1 x μ }
0
μ
(0)
Initialize distribution parameters θ , fitness function f(⋅)
Repeat