进化策略 Evolutionary Strategy

zt3ff3n · 发表于 2021-12-7 16:13

Evolutionary strategy是基于进化思想的一种优化算法，可以用于连续变量的函数优化问题，由于其不需要使用梯度更新、利用函数的内部知识，所以适用于无梯度优化、黑盒优化等场景。CMA-ES是其中最常用的算法。
本文首先介绍标准的ES算法，然后介绍CMA-ES，之后介绍CMA-ES的一些变种(对存储和计算代价进行了优化)，以及一些其他的ES算法，如open-ai es、guided es等。
1. 经典ES算法

ES算法的基本流程如下：

从正态分布中采样搜索方向 $\{\bold{\epsilon_1}, ..., \bold{\epsilon_P}\}$ 。
使用antithetic ES gradient estimator： $\hat{\nabla}f_{\sigma}^a(\theta) = \frac{1}{2\sigma P}\sum_{i=1}^P (f(\theta + \sigma \epsilon_i) - f(\theta - \sigma \epsilon_i)) \epsilon_i$ 评估梯度。
使用梯度更新当前参数 $\theta$ 。
重复。

其中，协方差矩阵是ES算法中最重要的部分，合适的协方差矩阵可以使得采样的大部分点为梯度下降的方向(作为exploitation)，少部分点为其他方向(作为exploration)，自动权衡探索和利用。
Vanilla ES使用的是 $N(0, I_n)$ ，所以会在不重要的方向上浪费很多的采样点。
CMA-ES则是使用自适应的协方差矩阵，期望在距离最优点距离较远时，扩大搜索范围(协方差矩阵为细长的椭圆形)，接近最优点时，缩小搜索范围(协方差矩阵呈现圆形)。
2. CMA-ES

推荐论文：The CMA Evolution Strategy: A Tutorial。

$(\mu/\mu_w, \lambda)$ -CMA-ES：

第一项的是种群大小， $\mu_w$ 是指求均值时采用加权和的方式， $\lambda$ 是通过在中采样获得的子代的数量。为步长。在搜索的过程中，自适应调整，，。CMA-ES可以看做是quasi-Newton法如BFGS的随机版本。
采样过程：不是直接在中采样，而是通过 $x_t^i = m_t + \sigma_tC_t^{1/2}z_t^i, z_t^i\sim N(0, I)$ 的方式计算，其中 $C_t^{1/2} = B_tD_tB_t^T$ ， $B_t$ 是的特征向量为列组成的矩阵， $D_t$ 是特征值开根号。计算特征值分解的过程的复杂度为 $O(n^3)$ ，但每 $O(n)$ 次评估计算一次，所以总复杂度为。
将子代解从好到坏排序： $f(x_t^{1:\lambda})\leq ...$ ，用前个计算新的均值，使用rank-one和rank-mu的规则更新协方差，cumulative step-size adaptation用于更新。

3. CMA-ES的变种

CMA-ES需要保存和更新协方差矩阵，其空间和时间代价都是，所以无法很好的用在高维空间。其变种都是对协方差矩阵进行改进，将协方差矩阵限定为某种特定形式，使得保存和更新更加高效。推荐可以看论文：A comparative study of large scale variants of CMA-ES。
1. Cholesky-CMA

该算法不是使用特征值分解，而是cholesky分解 $C_t = A_tA_t^T$ ，通过 $x_t^i = m_t+\sigma_tA_tz_t^i$ 的方式采样。
主要思想是，不是直接更新，而是使用rank-one的规则直接更新。
虽然时间和空间复杂度上没有减小，但在计算量上，减少了很多(是上三角或下三角)。

2. sep-CMA-ES

将协方差矩阵限制为 $C_t = diag(C_t)$ 的形式，更新时，只需要更新对角线元素，所以时间和空间复杂度降低为线性。
该算法的解释有两种：

找到从协方差矩阵原空间(即所有正定矩阵的集合)到对角矩阵空间(对角正定矩阵集合)的距离(通过F范数度量)最小的矩阵，该矩阵即为直接使用对角线上的元素作为对角矩阵的矩阵。
从自然梯度的角度解释(没有看懂)。

3. VkD-CMA-ES

将协方差矩阵限制为 $C_t = D_t(I + V_tV_t^T)D_t$ 的形式。其中 $V_t = [v_t^1, ..., v_t^k], 0\leq k \leq d-1$ 是由正交基组成的矩阵。当 $k=0$ 时， $C_t = D_tD_t$ ，为对角矩阵，即为sep-CMA-ES的形式；当 $k=d-1$ 时，与标准CMA-ES相同。
VkD-CMA-ES空间复杂度为 $O(nr)$ ，时间复杂度为 $O(nr\max(1, r/\lambda))$ ，其中 $r = k+\mu +1$ 。
具体计算 $D_t(I + V_tV_t^T)D_t$ 的方式是找到在所有该形式的矩阵组成的空间中的一个投影，即求解 $argmin _{(D, V)}||D(I+VV^T)D - C^{(t+1)}||_F$ 。
计算分为三步，通过比较复杂的特征值分解求解下面的问题：

求解 $argmin_{(\beta, V)}||(\beta I + VV^T) - (D^{(t)})^{-1}C^{(t+1)}(D^{(t)})^{-1}||_F$ ，得到 $\beta^*$ 和 $V^*$ 。
求解 $diag(D(\beta^* I + V^*(V^*)^T)D) = diag(C^{(t+1)})$ ，得到 $D^*$ 。
$V^{(t+1)} = (\beta^*)^{-1/2}V^*$ ， $D^{(t+1)} = (\beta^*)^{1/2}D^*$ 。

4. limited-memory CMA(LM-CMA)：

在cholesky CMA-ES中，如果 $A_0 = I, a = \sqrt{1-c_1}, b_t = \frac{\sqrt{1-c_1}}{||v_{t+1}||^2}(\sqrt{1+\frac{c+1}{1+c_1}||v_{t+1}||^2}-1)$ ，则更新公式为 $A_{t+1} = a^tI + \sum_{i=1}^ta^{t-i}b_{i-1}p_i^cv_i^T$ 。第二项对 $t$ 项的求和可以通过 $m$ 项的求和近似，则时间和空间复杂度变为 $O(mn)$ 。
5. RmES

RmES和LM-CMA思想类似，但是是对协方差矩阵的近似，假设 $C_0 = I$ ，并且只使用rank-one更新规则， $C_t = (1-c_1)^mI + c_1 \sum_{i=1}^m(1-c_1)^{m-i}p_i^c(p_i^c)^T$ 。
4. 其他ES算法

主要是总结一些AI的顶会上的ES方面的一些改进。OpenAI-ES讨论将ES算用于强化学习问题时的优势与不足，其他几篇的特点都是使用历史信息改进ES算法，并且如何平衡探索和利用，所以说如果想发ES相关的AI顶会，可以关注如何利用历史信息改进ES算法方面的内容。
1. OpenAI-ES

论文：Evolution Strategies as a Scalable Alternative to Reinforcement Learning，讨论了将ES用于RL任务的问题。
文中实际使用的ES比较简单，属于NES的一种(我目前理解的NES就是先通过差分的方式求梯度，然后使用梯度更新参数)，分为两步：

从标准正态分布中采样，乘以步长 $\sigma$ 后作为扰动。
通过差分的方式求平均梯度，更新参数。

OpenAI-ES最大的改进是：通过少量的改进，使得不同进程之间只需要传递标量，而不是传递梯度向量，使得并行加速比接近线性，从而提出了超大规模并行ES的方法。
2. Guided ES

论文：Guided evolutionary strategies: Augmenting random search with surrogate gradients。
主要是利用最近k次的surrogate gradient，计算低维(维)的subspace，将 $\epsilon_i$ 的采样限制在subspace中，减小搜索方向的方差。
具体来讲：使用k个标准正交基构成的矩阵 $U$ ，采样 $\epsilon_i\sim N(0, \sigma^2\Sigma)$ ， $\Sigma = \frac{\alpha}{n}I_n+\frac{1-\alpha}{k}UU^T$ ，第一项是从全空间中采样的协方差，对应exploration，有更大的variance和更小的bias，第二项是从之前的梯度subspace中采样的协方差，对应exploitation，有更小的variance和更大的bias。我们使用 $\alpha$ 控制探索和利用以及variance和bias。
3. ASEBO

论文：From Complexity to Simplicity: Adaptive ES-Active Subspace for Blackbox Optimization。
主要是使用PCA对历史的梯度信息矩阵进行降维，作为exploitation空间。
4. SGES

论文：Self-Guided Evolution Strategies with Historical Estimated Gradients。
之前的Guided ES中，没有具体说明如何获得surrogate gradient，SGES提出使用历史梯度信息作为surrogate gradient，并利用历史梯度信息计算用于exploitation空间。
5. ES求解强化学习问题

1. 函数benchmark和RL benchmark

在黑盒优化的问题中，通常会使用高维函数作为检验算法性能的标准(即benchmark)，但RL同样也可以看做是黑盒优化问题(输入为策略网络的参数，输出为reward)，那么函数benchmark和RL benchmark的区别是什么？

RL的函数更加复杂(局部最优点可能分布更加随机，变化更加剧烈等等)。
返回值存在随机性(给定同样的参数值，返回的累计奖赏可能是不同的)。
维度上一般是相当或更高(如果使用简单的线性策略，维度一般在几百到一千维，和函数benchmark维度差不多，如果使用更加复杂的神经网络，则很容易上千维)。

2. ES和RL算法的区别

ES相比RL的优势：

ES算法最大的优点是加速比近乎线性的并行化。
不需要backpropagation：使得单次训练时间减少，代码更加简单，不需要担心梯度消失或爆炸等问题，可以应用在更加general的情况(不可导函数)。
更加鲁邦：如果是通过ES求surrogate gradient，然后进行优化，因为求梯度的对象是通过gaussian smooth的函数，天然对扰动更加鲁邦。在基本相同的超参数设置下，可以完成所有任务。
ES探索能力更强，可以学到更具有diversity的表现。
ES参数少(不需要折扣因子gamma，值函数近似)，对于action frequency，延迟奖赏，长时效的动作影响。
其他来自黑盒优化的优点。

其他区别：

样本利用率问题：需要的样本相比RL更多(约3-10倍)，但由于RL需要反向传播更新策略，达到相同performance的计算量基本相当。需要样本过多可能是一个比较严重的问题，因为RL中样本利用率已经很低了。
RL通过从随机策略中采样动作探索，ES是通过参数的扰动探索。即RL对action空间扰动(返回随机策略)，ES对参数空间扰动(施加一个高斯噪声)，所以可以用确定性策略。

6. 总结

总体上来说，CMA-ES是最常用、也是效果十分好的ES算法。并且基本没有需要人为设定的超参数，很容易跑出很好的效果。可以作为求解复杂黑盒问题时第一个尝试的算法。
但由于其协方差矩阵的更新需要的时间复杂度，所以在问题维度较高时，运行速度会比较慢，所以问题维度较高(500维以上)时，可以尝试使用其改进算法，加速训练。
<hr/>欢迎关注我的公众号：炼丹攻略。

		自动登录	找回密码
密码			立即注册