启发式优化算法

启发式优化算法的一些调研

启发式优化算法的背景

1. 首先,我们需要有一个目标函数 f(\bold{x}), 其中的 \bold{x} \in \mathbb{R}^{n}n 是一个正整数。然后,目标函数 f(\bold{x}) 不一定需要是显式的(所谓显式指的是能够精确写出 f(\bold{x}) 的表达式,例如逻辑回归的目标函数,神经网络的目标函数,XGBoost 的目标函数等),隐式的目标函数使用启发式优化算法也是可以研究的(即无法写出 f(\bold{x}) 表达式)。

2. 其次,需要计算目标函数 f(\bold{x}) 的最大值 \max f(\bold{x}) 或者最小值 \min f(\bold{x})

3. 再次,如果存在多个函数 f_{i}(\bold{x}), 1\leq i\leq m, 并且每一个 f_{i}(\bold{x}) 的值域都在 [0,1] 内。如果目标函数是

\min_{x}(\max_{i}f_{i}(x)-\min_{i}f_{i}(x)),

希望求该目标函数的最小值,那么意思就是使得每一个 1\leq i\leq m, f_{i}(\bold{x})\bold{x} 的定义域内都相差得不多,也就是这 m 条曲线几乎重合。

4. 拥有目标函数的目的是寻找最优的 \bold{x} 使得它满足 argmin_{\bold{x}}f(x) 或者 argmax_{\bold{x}}f(x)

5. 在这里的 \bold{x}\in \mathbb{R}^{n} 一般都是连续的特征,而不是那种类别特征。如果是类别的特征,并不是所有的启发式优化算法都适用,但是遗传算法之类的算法在这种情况下有着一定的用武之地。

启发式优化算法的实验方法

1. 论文中的方法:找到一些形状怪异的函数作为目标函数,需要寻找这些函数的全局最大值或者全局最小值。除了全局的最大最小值点之外,这些函数也有很多局部极值点。例如 Rastrigin 函数(Chapter 6,Example 6.1,Search and Optimization by Metaheuristics)

\min_{\bold{x}}f(\bold{x}) = 10\cdot n +\sum_{i=1}^{n}(x_{i}^{2}-10\cos(2\pi x_{i})),

其中,\bold{x}\in[-5.12,5.12]^{n}. 或者 Easom 函数(Chapter 2,Example 2.1,Search and Optimization by Metaheuristics)

\min_{\bold{x}}f(\bold{x}) = - \cos(x_{1})\cos(x_{2})\exp(-(x_{1}-\pi)^{2}-(x_{2}-\pi)^{2}),

其中,\bold{x} \in [-100,100]^{2}.

2. 最朴素的算法:随机搜索法(Random Search)。也就是把 \bold{x} 的定义域切分成 m^{n} 份,其中 \bold{x}\in\mathbb{R}^{n}. 计算每一个交点的函数取值,然后统计出其最大值或者最小值就可以了。实际中不适用,因为当 n\geq 100 的时候,这个是指数级别的计算复杂度。

3. 启发式优化算法:针对某一个目标函数,使用某种启发式优化算法,然后与随机搜索法做对比,或者与其余的启发式优化算法做对比。

4. 在线调优:启发式优化算法大部分都可以做成实时调优的算法,调优的速度除了算法本身的收敛速度之外,还有给定一个 \bold{x} 之后,获取到 f(\vec{x}) 的时间。

注:可以尝试使用启发式优化算法在线调优推荐系统中的 AUC 或者 CTR。不过 CTR 一般具有波动性,需要几个小时甚至一天的数据才能够统计出一个相对靠谱的取值。同时,如果用户量不够多的话,如果切流量的话,可能会造成一些流量的 CTR 偏高,另外一些流量的 CTR 偏低。并且流量的条数会有上限,一般来说不会超过 100 左右,甚至只有 10 个不同的流量。因此,在其余场景下使用这类方法的时候,一定要注意获取目标函数 value 的时间长度。时间长度越短,能够进行的尝试(探索次数)就会越多,收敛的希望就会越大;反之,时间长度越长,能够进行的尝试(探索次数)就会受到限制,收敛的时间长度就会变长。

启发式优化算法的一些常见算法

以下的内容暂时只涉及最基本的算法,有很多算法的变种暂时不做过多的描述。

粒子群算法(Particle Swarm Optimization)

PSO 算法是有一个粒子群,根据群体粒子和单个粒子的最优效果,来调整每一个粒子的下一步行动方向。假设粒子的个数是 N_{p},每一个粒子 \bold{x}_{i}\in \mathbb{R}^{n} 都是 n 维欧几里德空间里面的点,同时需要假设粒子的速度 \bold{v}_{i}\in\mathbb{R}^{n}。在每一轮迭代中,需要更新两个最值,分别是每一个粒子在历史上的最优值和所有粒子在历史上的最优值,分别记为 \bold{x}_{i}^{*}1\leq i \leq N_{p})和 \bold{x}^{g}。在第 t+1 次迭代的时候,

\bold{v}_{i}(t+1) = \bold{v}_{i}(t) + c r_{1}[\bold{x}_{i}^{*}(t) - \bold{x}_{i}(t)] + c r_{2}[\bold{x}^{g}(t) - \bold{x}_{i}(t)],

\bold{x}_{i}(t+1) = \bold{x}_{i}(t)+\bold{v}_{i}(t+1), \text{ } 1\leq i\leq N_{p}.

在这里,c>0,并且 r_{1}, r_{2}[0,1] 中间的随机数。

注:需要解决的问题是如何设置这 N_{p} 个粒子,也就是构造粒子群的问题。在每次只能够设置调整一次 \bold{x} 的时候,可以把时间窗口按照连续的 N_{p} 段来进行切分,在一个时间段内的这 N_{p} 个时间点可以当成 N_{p} 个粒子,然后进行下一轮的迭代即可。

模拟退火(Simulated Annealing)

其核心思想是构造了温度 T 这个维度,当温度 T 高的时候,分子运动速度快,能够探索更多的区域;温度 T 低的时候,分子运动速度慢,能够探索的区域有限。随着时间的迁移,温度 T 会从一个较大的值逐渐降低到 0。

模拟退火的大体思路是这样的:先设置一个较大的温度值 T,随机初始化 \bold{x}(0)。假设目标函数是 E(\bold{x}),需要寻找 argmin_{\bold{x}}E(\bold{x}),然后执行以下的程序:

Repeat:

a. Repeat:

i. 进行一个随机扰动 \bold{x} = \bold{x} + \Delta \bold{x}

ii. 计算 \Delta E(\bold{x}) = E(\bold{x}+\Delta\bold{x}) - E(\bold{x})

如果 \Delta E(\bold{x}) <0,也就是 E(\bold{x} + \Delta\bold{x})<E(\bold{x}),选择 \bold{x}+\Delta\bold{x}

否则,按照 P = e^{-\Delta E/T} 的概率来接受 \bold{x} +\Delta\bold{x}

b. 令 T = T-\Delta T

直到 T 足够小。

遗传算法的个人理解:

  1. 如何选择合适的 \Delta \bold{x},可以选择 Gaussian 正态分布,并且可以同时修改 \bold{x}n 个维度,也可以每次只修改一个维度或者部分维度的值;
  2. 一开始在温度 T 很大的时候,即使 E(\bold{x}+\Delta\bold{x})\geq E(\bold{x}) 的时候,都会以极大概率接受 E(\bold{x}+\Delta\bold{x}),因为此时 \lim_{T\rightarrow\infty}e^{-\Delta E/T}=1。然后一开始都在四处游荡;
  3. 当温度 T 逐渐降低的时候,当时 \bold{x} 不一定在一个合适的位置,因此,需要记录历史上探索过的满足 E(\bold{x}) 最小的值,从历史上的值中选择出一个合适的值继续迭代。因此,在温度下降的时候,如何选择一个合适的值继续迭代可能是一个关键问题。
  4. 从遗传算法和 PSO 的对比效果来看,因为 PSO 算法会随时记录当前粒子和所有粒子的最优状态,然后在整个种群中,总会有少数粒子处于当前的最优状态,所以 PSO 的效果从实验效果上来看貌似比不记录状态的遗传算法会好一些。

进化策略(Evolutionary Strategies)

ES 和 GA 有一些方法论上面的不同,这个在书上有论述,等撰写了 GA 在一起看这一块的内容。

进化策略(Evolutionary Strategies)的大体流程与遗传算法(Genetic Algorithm) 相似,不同的是 ES 的步骤是交叉/变异(Crossover/Mutation)在前,选择(Selection)在后。

对于经典的进化策略而言,交叉算子(Crossover Operator)可以按照如下定义:两个父代(parents)\bold{x}_{1}\bold{x}_{2},那么子代(children)的交叉可以定义为:

\bold{x}'=(\bold{x}_{1}+\bold{x}_{2})/2,

这里的相加就是向量之间的相加。

对于经典的进化策略而言,变异算子(Mutation Operator)可以按照如下定义:对于一个向量 \bold{x} = (x_{1},\cdots,x_{n}),使用 Gaussian 正态分布可以构造出一个后代如下:

x_{i}'=x_{i}+N(0,\sigma_{i}),\text{ } i=1,\cdots,n,

这里的 \sigma_{i}, \text{ } i=1,\cdots,n 是基于具体问题的,很难给出一个通用的值。

就经验而谈,ES 算法一般来说比 GA 更加 Robust。在交叉(Crossover)或者变异(Mutation)之后,ES 算法就需要进行选择,通常来说,ES 算法有两种方式,分别是 (\lambda+\mu)(\lambda,\mu) 两种策略。这里的 \mu 表示人口数量(population size),\lambda 表示从人口中产生的后代的数量。

(1)在 (\lambda+\mu) 策略中,从 \mu 人口中通过变异或者交叉得到 \lambda 个人,然后从这 (\lambda+\mu) 个人中选择出 \mu 个最优的人。(\lambda+\mu) 是精英策略,每一次迭代都比上一次要好。

(2)在 (\lambda, \mu) 策略中,\mu 个最优的人是从 \lambda(\lambda\geq\mu) 中选择出来的。

传统的梯度搜索法,例如 Newton-Raphson 方法,需要能够计算目标函数 f(x) 的导数,也就是说目标函数必须可导。但是在 Evolutionary Gradient Search 中,不需要 f(x) 是可导的,而是使用导数的近似值来计算。

如果是 (1,\lambda)-ES 的方案,它整体来说其实只有一个人口。从当前的点 \bold{x} 开始,通过 Gaussian Mutation 的方法可以生成 \lambda 个后代,记为 \bold{t}_{1},\cdots,\bold{t}_{\lambda}。计算它们的函数取值 f(\bold{t}_{1}),\cdots,f(\bold{t}_{\lambda})。那么估算的梯度就可以计算出来:

\bold{g}=\sum_{i=1}^{\lambda}(f(\bold{t}_{i})-f(\bold{x}))(\bold{t}_{i}-\bold{x}),

归一化之后得到 \bold{e}=\bold{g}/||\bold{g}||.

Evolutionary gradient search 生成了两个点,分别是:

\bold{x}_{1}=\bold{x}+(\sigma \psi)\bold{e}, \bold{x}_{2}=\bold{x}+(\sigma/\psi)\bold{e},

这里的 \psi>1. 新的个体定义为: \bold{x}'=\bold{x}+\sigma'\bold{e}. 如果 f(\bold{x}_{1})>f(\bold{x}_{2}), 那么 \sigma' = \sigma\psi; 如果 f(\bold{x}_{1})\leq f(\bold{x}_{2}), 那么 \sigma'=\sigma/\psi.

进化策略(ES)包括 gradient search 和 gradient evolution,并且 covariance matrix adaptation(CMA)ES 在一定的限制条件下加速了搜索的效率。

参考资料:

  1. Search and Optimization by Metaheuristics,Kelin DU, M.N.S. SWAMY,2016年
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s