进化策略 Evolutionary Strategy
Evolutionary strategy是基于进化思想的一种优化算法，可以用于连续变量的函数优化问题，由于其不需要使用梯度更新、利用函数的内部知识，所以适用于无梯度优化、黑盒优化等场景。CMA-ES是其中最常用的算法。本文首先介绍标准的ES算法，然后介绍CMA-ES，之后介绍CMA-ES的一些变种(对存储和计算代价进行了优化)，以及一些其他的ES算法，如open-ai es、guided es等。
1. 经典ES算法
ES算法的基本流程如下：
[*]从正态分布中采样搜索方向https://www.zhihu.com/equation?tex=%5C%7B%5Cbold%7B%5Cepsilon_1%7D%2C+...%2C+%5Cbold%7B%5Cepsilon_P%7D%5C%7D。
[*]使用antithetic ES gradient estimator：https://www.zhihu.com/equation?tex=%5Chat%7B%5Cnabla%7Df_%7B%5Csigma%7D%5Ea%28%5Ctheta%29+%3D+%5Cfrac%7B1%7D%7B2%5Csigma+P%7D%5Csum_%7Bi%3D1%7D%5EP+%28f%28%5Ctheta+%2B+%5Csigma+%5Cepsilon_i%29+-+f%28%5Ctheta+-+%5Csigma+%5Cepsilon_i%29%29+%5Cepsilon_i评估梯度。
[*]使用梯度更新当前参数https://www.zhihu.com/equation?tex=%5Ctheta。
[*]重复。
其中，协方差矩阵是ES算法中最重要的部分，合适的协方差矩阵可以使得采样的大部分点为梯度下降的方向(作为exploitation)，少部分点为其他方向(作为exploration)，自动权衡探索和利用。
Vanilla ES使用的是https://www.zhihu.com/equation?tex=N%280%2C+I_n%29，所以会在不重要的方向上浪费很多的采样点。
CMA-ES则是使用自适应的协方差矩阵，期望在距离最优点距离较远时，扩大搜索范围(协方差矩阵为细长的椭圆形)，接近最优点时，缩小搜索范围(协方差矩阵呈现圆形)。
2. CMA-ES
推荐论文：The CMA Evolution Strategy: A Tutorial。
https://www.zhihu.com/equation?tex=%28%5Cmu%2F%5Cmu_w%2C+%5Clambda%29-CMA-ES：
[*]第一项的是种群大小，https://www.zhihu.com/equation?tex=%5Cmu_w是指求均值时采用加权和的方式，https://www.zhihu.com/equation?tex=%5Clambda是通过在中采样获得的子代的数量。为步长。在搜索的过程中，自适应调整，，。CMA-ES可以看做是quasi-Newton法如BFGS的随机版本。
[*]采样过程：不是直接在中采样，而是通过https://www.zhihu.com/equation?tex=x_t%5Ei+%3D+m_t+%2B+%5Csigma_tC_t%5E%7B1%2F2%7Dz_t%5Ei%2C+z_t%5Ei%5Csim+N%280%2C+I%29的方式计算，其中https://www.zhihu.com/equation?tex=C_t%5E%7B1%2F2%7D+%3D+B_tD_tB_t%5ET，https://www.zhihu.com/equation?tex=B_t是的特征向量为列组成的矩阵，https://www.zhihu.com/equation?tex=D_t是特征值开根号。计算特征值分解的过程的复杂度为https://www.zhihu.com/equation?tex=O%28n%5E3%29，但每https://www.zhihu.com/equation?tex=O%28n%29次评估计算一次，所以总复杂度为。
[*]将子代解从好到坏排序：https://www.zhihu.com/equation?tex=f%28x_t%5E%7B1%3A%5Clambda%7D%29%5Cleq+...，用前个计算新的均值，使用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分解https://www.zhihu.com/equation?tex=C_t+%3D+A_tA_t%5ET，通过https://www.zhihu.com/equation?tex=x_t%5Ei+%3D+m_t%2B%5Csigma_tA_tz_t%5Ei的方式采样。
[*]主要思想是，不是直接更新，而是使用rank-one的规则直接更新。
[*]虽然时间和空间复杂度上没有减小，但在计算量上，减少了很多(是上三角或下三角)。
2. sep-CMA-ES
将协方差矩阵限制为https://www.zhihu.com/equation?tex=C_t+%3D+diag%28C_t%29的形式，更新时，只需要更新对角线元素，所以时间和空间复杂度降低为线性。
该算法的解释有两种：
[*]找到从协方差矩阵原空间(即所有正定矩阵的集合)到对角矩阵空间(对角正定矩阵集合)的距离(通过F范数度量)最小的矩阵，该矩阵即为直接使用对角线上的元素作为对角矩阵的矩阵。
[*]从自然梯度的角度解释(没有看懂)。
3. VkD-CMA-ES
将协方差矩阵限制为https://www.zhihu.com/equation?tex=C_t+%3D+D_t%28I+%2B+V_tV_t%5ET%29D_t的形式。其中https://www.zhihu.com/equation?tex=V_t+%3D+%5Bv_t%5E1%2C+...%2C+v_t%5Ek%5D%2C+0%5Cleq+k+%5Cleq+d-1是由正交基组成的矩阵。当https://www.zhihu.com/equation?tex=k%3D0时，https://www.zhihu.com/equation?tex=C_t+%3D+D_tD_t，为对角矩阵，即为sep-CMA-ES的形式；当https://www.zhihu.com/equation?tex=k%3Dd-1时，与标准CMA-ES相同。
VkD-CMA-ES空间复杂度为https://www.zhihu.com/equation?tex=O%28nr%29，时间复杂度为https://www.zhihu.com/equation?tex=O%28nr%5Cmax%281%2C+r%2F%5Clambda%29%29，其中https://www.zhihu.com/equation?tex=r+%3D+k%2B%5Cmu+%2B1。
具体计算https://www.zhihu.com/equation?tex=D_t%28I+%2B+V_tV_t%5ET%29D_t的方式是找到在所有该形式的矩阵组成的空间中的一个投影，即求解https://www.zhihu.com/equation?tex=argmin+_%7B%28D%2C+V%29%7D%7C%7CD%28I%2BVV%5ET%29D+-+C%5E%7B%28t%2B1%29%7D%7C%7C_F。
计算分为三步，通过比较复杂的特征值分解求解下面的问题：
[*]求解https://www.zhihu.com/equation?tex=argmin_%7B%28%5Cbeta%2C+V%29%7D%7C%7C%28%5Cbeta+I+%2B+VV%5ET%29+-+%28D%5E%7B%28t%29%7D%29%5E%7B-1%7DC%5E%7B%28t%2B1%29%7D%28D%5E%7B%28t%29%7D%29%5E%7B-1%7D%7C%7C_F，得到https://www.zhihu.com/equation?tex=%5Cbeta%5E%2A和https://www.zhihu.com/equation?tex=V%5E%2A。
[*]求解https://www.zhihu.com/equation?tex=diag%28D%28%5Cbeta%5E%2A+I+%2B+V%5E%2A%28V%5E%2A%29%5ET%29D%29+%3D+diag%28C%5E%7B%28t%2B1%29%7D%29，得到https://www.zhihu.com/equation?tex=D%5E%2A。
[*]https://www.zhihu.com/equation?tex=V%5E%7B%28t%2B1%29%7D+%3D+%28%5Cbeta%5E%2A%29%5E%7B-1%2F2%7DV%5E%2A，https://www.zhihu.com/equation?tex=D%5E%7B%28t%2B1%29%7D+%3D+%28%5Cbeta%5E%2A%29%5E%7B1%2F2%7DD%5E%2A。
4. limited-memory CMA(LM-CMA)：
在cholesky CMA-ES中，如果https://www.zhihu.com/equation?tex=A_0+%3D+I%2C+a+%3D+%5Csqrt%7B1-c_1%7D%2C+b_t+%3D+%5Cfrac%7B%5Csqrt%7B1-c_1%7D%7D%7B%7C%7Cv_%7Bt%2B1%7D%7C%7C%5E2%7D%28%5Csqrt%7B1%2B%5Cfrac%7Bc%2B1%7D%7B1%2Bc_1%7D%7C%7Cv_%7Bt%2B1%7D%7C%7C%5E2%7D-1%29，则更新公式为https://www.zhihu.com/equation?tex=A_%7Bt%2B1%7D+%3D+a%5EtI+%2B+%5Csum_%7Bi%3D1%7D%5Eta%5E%7Bt-i%7Db_%7Bi-1%7Dp_i%5Ecv_i%5ET。第二项对https://www.zhihu.com/equation?tex=t项的求和可以通过https://www.zhihu.com/equation?tex=m项的求和近似，则时间和空间复杂度变为https://www.zhihu.com/equation?tex=O%28mn%29。
5. RmES
RmES和LM-CMA思想类似，但是是对协方差矩阵的近似，假设https://www.zhihu.com/equation?tex=C_0+%3D+I，并且只使用rank-one更新规则，https://www.zhihu.com/equation?tex=C_t+%3D+%281-c_1%29%5EmI+%2B+c_1+%5Csum_%7Bi%3D1%7D%5Em%281-c_1%29%5E%7Bm-i%7Dp_i%5Ec%28p_i%5Ec%29%5ET。
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就是先通过差分的方式求梯度，然后使用梯度更新参数)，分为两步：
[*]从标准正态分布中采样，乘以步长https://www.zhihu.com/equation?tex=%5Csigma后作为扰动。
[*]通过差分的方式求平均梯度，更新参数。
OpenAI-ES最大的改进是：通过少量的改进，使得不同进程之间只需要传递标量，而不是传递梯度向量，使得并行加速比接近线性，从而提出了超大规模并行ES的方法。
2. Guided ES
论文：Guided evolutionary strategies: Augmenting random search with surrogate gradients。
主要是利用最近k次的surrogate gradient，计算低维(维)的subspace，将https://www.zhihu.com/equation?tex=%5Cepsilon_i的采样限制在subspace中，减小搜索方向的方差。
具体来讲：使用k个标准正交基构成的矩阵https://www.zhihu.com/equation?tex=U，采样https://www.zhihu.com/equation?tex=%5Cepsilon_i%5Csim+N%280%2C+%5Csigma%5E2%5CSigma%29，https://www.zhihu.com/equation?tex=%5CSigma+%3D+%5Cfrac%7B%5Calpha%7D%7Bn%7DI_n%2B%5Cfrac%7B1-%5Calpha%7D%7Bk%7DUU%5ET，第一项是从全空间中采样的协方差，对应exploration，有更大的variance和更小的bias，第二项是从之前的梯度subspace中采样的协方差，对应exploitation，有更小的variance和更大的bias。我们使用https://www.zhihu.com/equation?tex=%5Calpha控制探索和利用以及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/>欢迎关注我的公众号：炼丹攻略。
页:
[1]