进化策略

随机梯度下降是优化深度学习模型的通用选择。然而，它并非唯一选项。借助黑箱优化算法，你可以评估目标函数 $f(x): \mathbb{R}^n \to \mathbb{R}$，即使你不知道 $f(x)$ 的精确解析形式，因而无法计算梯度或海森矩阵。黑箱优化方法的例子包括模拟退火、爬山法和内尔德-米德方法。

进化策略（ES）是一种黑箱优化算法，诞生于进化算法（EA）家族。在这篇文章中，我将深入探讨几种经典的进化策略方法，并介绍进化策略如何在深度强化学习中发挥作用的一些应用。

什么是进化策略？

进化策略（ES）属于进化算法大家族。进化策略的优化目标是实数向量 $x \in \mathbb{R}^n$。

进化算法是指受自然选择启发的一类基于种群的优化算法。自然选择认为，具有有利于生存特征的个体能够代代存活，并将优良特性传递给下一代。进化通过逐步的选择过程发生，种群对环境的适应能力不断增强。

进化算法可以概括为以下格式，作为一种通用的优化解决方案：

假设我们要优化一个函数 $f(x)$，并且无法直接计算梯度。但我们仍然可以在给定任意 $x$ 的情况下评估 $f(x)$，并且结果是确定性的。我们对 $x$ 作为 $f(x)$ 优化问题良好解的概率分布的信念是 $p_\theta(x)$，该分布由参数 $\theta$ 参数化。目标是找到 $\theta$ 的最优配置。

这里，在给定固定分布形式（即高斯分布）的情况下，参数 $\theta$ 承载着关于最优解的知识，并会在各代之间迭代更新。

从 $\theta$ 的初始值开始，我们可以通过循环以下三个步骤来持续更新 $\theta$：

1. 生成一个样本群体 $D = \{(x_i, f(x_i)\}$，其中 $x_i \sim p_\theta(x)$。
2. 评估 $D$ 中样本的“适应度”。
3. 选出最佳个体子集，并根据适应度或排名，用它们来更新 $\theta$。

在遗传算法（GA）中，$x$ 是一个二进制编码序列，$x \in \{0, 1\}^n$。而在进化策略（ES）中，$x$ 只是一个实数向量，$x \in \mathbb{R}^n$。

简单高斯进化策略

这是进化策略最基本、最经典的版本。它将 $p_\theta(x)$ 建模为一个 $n$ 维的各向同性高斯分布，其中 $\theta$ 仅追踪均值 $\mu$ 和标准差 $\sigma$。

$$ \theta = (\mu, \sigma),\;p_\theta(x) \sim \mathcal{N}(\mathbf{\mu}, \sigma^2 I) = \mu + \sigma \mathcal{N}(0, I) $$

给定 $x \in \mathcal{R}^n$，简单高斯进化策略（Simple-Gaussian-ES）的过程如下：

1. 初始化 $\theta = \theta^{(0)}$ 和世代计数器 $t=0$
2. 通过从高斯分布中采样，生成大小为 $\Lambda$ 的子代群体：$D^{(t+1)}=\{ x^{(t+1)}_i \mid x^{(t+1)}_i = \mu^{(t)} + \sigma^{(t)} y^{(t+1)}_i \text{ 其中 } y^{(t+1)}_i \sim \mathcal{N}(x \vert 0, \mathbf{I}),\;i = 1, \dots, \Lambda\}$。
3. 选出具有最优 $f(x_i)$ 的 $\lambda$ 个样本的顶部子集，该子集称为精英集。不失一般性，我们可以认为 $D^{(t+1)}$ 中的前 $k$ 个样本属于精英群体——将它们标记为

$$ D^{(t+1)}\_\text{elite} = \\{x^{(t+1)}\_i \mid x^{(t+1)}\_i \in D^{(t+1)}, i=1,\dots, \lambda, \lambda\leq \Lambda\\} $$

1. 然后，我们使用精英集来估计下一代的新的均值和标准差：

$$ \begin{aligned} \mu^{(t+1)} &= \text{avg}(D^{(t+1)}_\text{elite}) = \frac{1}{\lambda}\sum_{i=1}^\lambda x_i^{(t+1)} \\ {\sigma^{(t+1)}}^2 &= \text{var}(D^{(t+1)}_\text{elite}) = \frac{1}{\lambda}\sum_{i=1}^\lambda (x_i^{(t+1)} -\mu^{(t)})^2 \end{aligned} $$

1. 重复步骤（2）-（4），直到结果足够好为止 ✌️

协方差矩阵自适应进化策略（CMA-ES）

标准差 $\sigma$ 决定了探索的程度：$\sigma$ 越大，我们对子代种群进行采样的搜索空间就越大。在标准进化策略中，$\sigma^{(t+1)}$ 与 $\sigma^{(t)}$ 高度相关，因此该算法无法在需要时（即置信度发生变化时）快速调整探索空间。

CMA-ES，全称为“协方差矩阵自适应进化策略”，通过利用协方差矩阵 $C$ 追踪分布中样本之间的成对依赖关系来解决这一问题。新的分布参数变为：

$$ \theta = (\mu, \sigma, C),\; p_\theta(x) \sim \mathcal{N}(\mu, \sigma^2 C) \sim \mu + \sigma \mathcal{N}(0, C) $$

其中 $\sigma$ 控制分布的整体尺度，通常称为步长。

在深入探讨 CMA-ES 中参数如何更新之前，最好先回顾一下协方差矩阵在多变量高斯分布中的作用。作为一个实对称矩阵，协方差矩阵 $C$ 具有以下优良特性（参见证明 & 证明）：

• 它总是可对角化的。
• 总是半正定的。
• 它的所有特征值都是非负实数。
• 它的所有特征向量都是正交的。
• 存在一个由其特征向量构成的 $\mathbb{R}^n$ 标准正交基。

设矩阵 $C$ 有一个由特征向量 $B = [b_1, \dots, b_n]$ 构成的标准正交基，对应的特征值为 $\lambda_1^2, \dots, \lambda_n^2$。令 $D=\text{diag}(\lambda_1, \dots, \lambda_n)$。

$$ C = B^\top D^2 B = \begin{bmatrix} \mid & \mid & & \mid \\ b_1 & b_2 & \dots & b_n\\ \mid & \mid & & \mid \\ \end{bmatrix} \begin{bmatrix} \lambda_1^2 & 0 & \dots & 0 \\ 0 & \lambda_2^2 & \dots & 0 \\ \vdots & \dots & \ddots & \vdots \\ 0 & \dots & 0 & \lambda_n^2 \end{bmatrix} \begin{bmatrix} - & b_1 & - \\ - & b_2 & - \\ & \dots & \\ - & b_n & - \\ \end{bmatrix} $$

$C$ 的平方根是：

$$ C^{\frac{1}{2}} = B^\top D B $$

更新均值

$$ \mu^{(t+1)} = \mu^{(t)} + \alpha_\mu \frac{1}{\lambda}\sum_{i=1}^\lambda (x_i^{(t+1)} - \mu^{(t)}) $$

CMA-ES 有一个学习率 $\alpha_\mu \leq 1$，用于控制均值 $\mu$ 的更新速度。通常将其设为 1，此时该公式与标准进化策略中的公式相同，即 $\mu^{(t+1)} = \frac{1}{\lambda}\sum_{i=1}^\lambda (x_i^{(t+1)}$。

控制步长

采样过程可以与均值和标准差解耦：

$$ x^{(t+1)}_i = \mu^{(t)} + \sigma^{(t)} y^{(t+1)}_i \text{, 其中 } y^{(t+1)}_i = \frac{x_i^{(t+1)} - \mu^{(t)}}{\sigma^{(t)}} \sim \mathcal{N}(0, C) $$

参数 $\sigma$ 控制分布的整体尺度。它与协方差矩阵分离，这样我们就可以比调整完整协方差更快地改变步长。步长越大，参数更新越快。为了评估当前步长是否合适，CMA-ES 通过累加一系列连续的移动步长 $\frac{1}{\lambda}\sum_{i}^\lambda y_i^{(j)}, j=1, \dots, t$ 来构建一条进化路径 $p_\sigma$。通过将该路径长度与其在随机选择（即单步之间不相关）下的期望长度进行比较，我们能够相应地调整 $\sigma$（见图 2）。

每次进化路径都会用同一代中移动步长 $y_i$ 的平均值进行更新。

$$ \begin{aligned} &\frac{1}{\lambda}\sum_{i=1}^\lambda y_i^{(t+1)} = \frac{1}{\lambda} \frac{\sum_{i=1}^\lambda x_i^{(t+1)} - \lambda \mu^{(t)}}{\sigma^{(t)}} = \frac{\mu^{(t+1)} - \mu^{(t)}}{\sigma^{(t)}} \\ &\frac{1}{\lambda}\sum_{i=1}^\lambda y_i^{(t+1)} \sim \frac{1}{\lambda}\mathcal{N}(0, \lambda C^{(t)}) \sim \frac{1}{\sqrt{\lambda}}{C^{(t)}}^{\frac{1}{2}}\mathcal{N}(0, I) \\ &\text{因此 } \sqrt{\lambda}\;{C^{(t)}}^{-\frac{1}{2}} \frac{\mu^{(t+1)} - \mu^{(t)}}{\sigma^{(t)}} \sim \mathcal{N}(0, I) \end{aligned} $$

通过乘以 $C^{-\frac{1}{2}}$，进化路径被变换为与其方向无关。变换项 ${C^{(t)}}^{-\frac{1}{2}} = {B^{(t)}}^\top {D^{(t)}}^{-\frac{1}{2}} {B^{(t)}}$ 的作用如下：

1. ${B^{(t)}}$ 包含 $C$ 的特征向量的行向量。它将原始空间投影到垂直的主轴上。
2. 然后 ${D^{(t)}}^{-\frac{1}{2}} = \text{diag}(\frac{1}{\lambda_1}, \dots, \frac{1}{\lambda_n})$ 将主轴的长度缩放至相等。
3. ${B^{(t)}}^\top$ 将空间变换回原始坐标系。

为了给较近的世代赋予更高的权重，我们使用 Polyak 平均法，以学习率 $\alpha_\sigma$ 更新进化路径。同时，权重经过平衡，使得 $p_\sigma$ 是共轭的，在单次更新前后均满足 $\sim \mathcal{N}(0, I)$。

$$ \begin{aligned} p_\sigma^{(t+1)} & = (1 - \alpha_\sigma) p_\sigma^{(t)} + \sqrt{1 - (1 - \alpha_\sigma)^2}\;\sqrt{\lambda}\; {C^{(t)}}^{-\frac{1}{2}} \frac{\mu^{(t+1)} - \mu^{(t)}}{\sigma^{(t)}} \\ & = (1 - \alpha_\sigma) p_\sigma^{(t)} + \sqrt{c_\sigma (2 - \alpha_\sigma)\lambda}\;{C^{(t)}}^{-\frac{1}{2}} \frac{\mu^{(t+1)} - \mu^{(t)}}{\sigma^{(t)}} \end{aligned} $$

在随机选择条件下，$p_\sigma$ 的期望长度为 $\mathbb{E}|\mathcal{N}(0,I)|$，即一个 $\mathcal{N}(0,I)$ 随机变量的 L2 范数的期望。按照图 2 中的思路，我们根据 $|p_\sigma^{(t+1)}| / \mathbb{E}|\mathcal{N}(0,I)|$ 的比值来调整步长：

$$ \begin{aligned} \ln\sigma^{(t+1)} &= \ln\sigma^{(t)} + \frac{\alpha_\sigma}{d_\sigma} \Big(\frac{\|p_\sigma^{(t+1)}\|}{\mathbb{E}\|\mathcal{N}(0,I)\|} - 1\Big) \\ \sigma^{(t+1)} &= \sigma^{(t)} \exp\Big(\frac{\alpha_\sigma}{d_\sigma} \Big(\frac{\|p_\sigma^{(t+1)}\|}{\mathbb{E}\|\mathcal{N}(0,I)\|} - 1\Big)\Big) \end{aligned} $$

其中 $d_\sigma \approx 1$ 是一个阻尼参数，用于控制 $\ln\sigma$ 的变化速度。

自适应协方差矩阵

对于协方差矩阵，可以利用精英样本的 $y_i$ 从头开始估计（回顾一下，$y_i \sim \mathcal{N}(0, C)$）：

$$ C_\lambda^{(t+1)} = \frac{1}{\lambda}\sum_{i=1}^\lambda y^{(t+1)}_i {y^{(t+1)}_i}^\top = \frac{1}{\lambda {\sigma^{(t)}}^2} \sum_{i=1}^\lambda (x_i^{(t+1)} - \mu^{(t)})(x_i^{(t+1)} - \mu^{(t)})^\top $$

上述估计仅在所选种群规模足够大时才可靠。然而，我们希望每一代用少量样本快速迭代。正因如此，CMA-ES 发明了一种更可靠但也更复杂的方法来更新 $C$。该方法涉及两条独立的路径：

• 秩-min(λ, n) 更新：利用 $\{C_\lambda\}$ 的历史数据，其中每个 $C_\lambda$ 是在某一代中从头估计得到的。
• 秩一更新：利用历史数据估计移动步长 $y_i$ 及其符号信息。

第一条路径考虑从 $\{C_\lambda\}$ 的完整历史来估计 $C$。例如，如果我们经历了大量世代，那么 $C^{(t+1)} \approx \text{avg}(C_\lambda^{(i)}; i=1,\dots,t)$ 将是一个良好的估计量。与 $p_\sigma$ 类似，我们也使用带学习率的 Polyak 平均来融入历史信息：

$$ C^{(t+1)} = (1 - \alpha_{c\lambda}) C^{(t)} + \alpha_{c\lambda} C_\lambda^{(t+1)} = (1 - \alpha_{c\lambda}) C^{(t)} + \alpha_{c\lambda} \frac{1}{\lambda} \sum_{i=1}^\lambda y^{(t+1)}_i {y^{(t+1)}_i}^\top $$

学习率的一个常见选择是 $\alpha_{c\lambda} \approx \min(1, \lambda/n^2)$。

第二条路径试图解决 $y_i{y_i}^\top = (-y_i)(-y_i)^\top$ 丢失符号信息的问题。类似于我们调整步长 $\sigma$ 的方式，这里使用一条进化路径 $p_c$ 来追踪符号信息，其构造方式使得 $p_c$ 是共轭的，在新一代生成前后均满足 $\sim \mathcal{N}(0, C)$。

我们可以将 $p_c$ 视为计算 $\text{avg}_i(y_i)$ 的另一种方式（注意两者均满足 $\sim \mathcal{N}(0, C)$），同时利用了全部历史信息并保留了符号信息。注意，上一节中我们已经知道 $\sqrt{k}\frac{\mu^{(t+1)} - \mu^{(t)}}{\sigma^{(t)}} \sim \mathcal{N}(0, C)$，

$$ \begin{aligned} p_c^{(t+1)} &= (1-\alpha_{cp}) p_c^{(t)} + \sqrt{1 - (1-\alpha_{cp})^2}\;\sqrt{\lambda}\;\frac{\mu^{(t+1)} - \mu^{(t)}}{\sigma^{(t)}} \\ &= (1-\alpha_{cp}) p_c^{(t)} + \sqrt{\alpha_{cp}(2 - \alpha_{cp})\lambda}\;\frac{\mu^{(t+1)} - \mu^{(t)}}{\sigma^{(t)}} \end{aligned} $$

然后，协方差矩阵根据 $p_c$ 进行更新：

$$ C^{(t+1)} = (1-\alpha_{c1}) C^{(t)} + \alpha_{c1}\;p_c^{(t+1)} {p_c^{(t+1)}}^\top $$

这种秩一更新方法据称在 $k$ 较小时能比秩-min(λ, n) 更新方法带来显著改进，因为移动步长的符号以及连续步长之间的相关性都被充分利用并代代相传。

最终我们将两种方法结合起来：

$$ C^{(t+1)} = (1 - \alpha_{c\lambda} - \alpha_{c1}) C^{(t)} + \alpha_{c1}\;\underbrace{p_c^{(t+1)} {p_c^{(t+1)}}^\top}_\textrm{秩一更新} + \alpha_{c\lambda} \underbrace{\frac{1}{\lambda} \sum_{i=1}^\lambda y^{(t+1)}_i {y^{(t+1)}_i}^\top}_\textrm{秩-min(lambda, n) 更新} $$

在我上面的所有示例中，每个精英样本都被视为贡献了相等的权重 $1/\lambda$。该过程可以轻松扩展到根据性能为所选样本分配不同权重 $w_1, \dots, w_\lambda$ 的情况。更多细节请参见教程。

自然进化策略

自然进化策略（NES；Wierstra 等人，2008）在参数的搜索分布中进行优化，并沿着自然梯度所指示的高适应度方向移动该分布。

自然梯度

给定一个由参数 $\theta$ 参数化的目标函数 $\mathcal{J}(\theta)$，假设我们的目标是找到最优的 $\theta$ 以最大化目标函数值。普通梯度寻找的是距离当前 $\theta$ 欧几里得距离较小的最陡方向；该距离限制施加在参数空间上。换句话说，我们计算的是相对于 $\theta$ 绝对值微小变化的普通梯度。最优步长为：

$$ d^{*} = \operatorname*{argmax}_{\|d\| = \epsilon} \mathcal{J}(\theta + d)\text{, 其中 }\epsilon \to 0 $$

与之不同，自然梯度处理的是由参数 $\theta$ 参数化的概率分布空间 $p_\theta(x)$（在 NES 论文中称为“搜索分布”）。它寻找的是分布空间中，以 KL 散度衡量距离的较小步长内的最陡方向。通过这一约束，我们确保每次更新都沿着分布流形以恒定速度移动，而不会因其曲率而减慢速度。

$$ d^{*}_\text{N} = \operatorname*{argmax}_{\text{KL}[p_\theta \| p_{\theta+d}] = \epsilon} \mathcal{J}(\theta + d) $$

利用 Fisher 信息矩阵进行估计

但是，如何精确计算 $\text{KL}[p_\theta | p_{\theta+\Delta\theta}]$ 呢？通过对 $\log p_{\theta + d}$ 在 $\theta$ 处进行泰勒展开，我们得到：

$$ \begin{aligned} & \text{KL}[p_\theta \| p_{\theta+d}] \\ &= \mathbb{E}_{x \sim p_\theta} [\log p_\theta(x) - \log p_{\theta+d}(x)] & \\ &\approx \mathbb{E}_{x \sim p_\theta} [ \log p_\theta(x) -( \log p_{\theta}(x) + \nabla_\theta \log p_{\theta}(x) d + \frac{1}{2}d^\top \nabla^2_\theta \log p_{\theta}(x) d)] & \scriptstyle{\text{; 对 }\log p_{\theta+d}\text{ 进行泰勒展开}} \\ &\approx - \mathbb{E}_x [\nabla_\theta \log p_{\theta}(x)] d - \frac{1}{2}d^\top \mathbb{E}_x [\nabla^2_\theta \log p_{\theta}(x)] d & \end{aligned} $$

其中

$$ \begin{aligned} \mathbb{E}_x [\nabla_\theta \log p_{\theta}] d &= \int_{x\sim p_\theta} p_\theta(x) \nabla_\theta \log p_\theta(x) & \\ &= \int_{x\sim p_\theta} p_\theta(x) \frac{1}{p_\theta(x)} \nabla_\theta p_\theta(x) & \\ &= \nabla_\theta \Big( \int_{x} p_\theta(x) \Big) & \scriptstyle{\textrm{；注意 }p_\theta(x)\textrm{ 是概率分布。}} \\ &= \nabla_\theta (1) = 0 \end{aligned} $$

最终我们得到：

$$ \text{KL}[p_\theta \| p_{\theta+d}] = - \frac{1}{2}d^\top \mathbf{F}_\theta d \text{，其中 }\mathbf{F}_\theta = \mathbb{E}_x [(\nabla_\theta \log p_{\theta}) (\nabla_\theta \log p_{\theta})^\top] $$

其中 $\mathbf{F}_\theta$ 被称为 Fisher 信息矩阵，由于 $\mathbb{E}[\nabla_\theta \log p_\theta] = 0$，它是 $\nabla_\theta \log p_\theta$ 的协方差矩阵。

以下优化问题的解：

$$ \max \mathcal{J}(\theta + d) \approx \max \big( \mathcal{J}(\theta) + {\nabla_\theta\mathcal{J}(\theta)}^\top d \big)\;\text{ 约束条件：}\text{KL}[p_\theta \| p_{\theta+d}] - \epsilon = 0 $$

可以通过拉格朗日乘数法求得：

$$ \begin{aligned} \mathcal{L}(\theta, d, \beta) &= \mathcal{J}(\theta) + \nabla_\theta\mathcal{J}(\theta)^\top d - \beta (\frac{1}{2}d^\top \mathbf{F}_\theta d + \epsilon) = 0 \text{ 约束条件：} \beta > 0 \\ \nabla_d \mathcal{L}(\theta, d, \beta) &= \nabla_\theta\mathcal{J}(\theta) - \beta\mathbf{F}_\theta d = 0 \\ \text{因此 } d_\text{N}^* &= \nabla_\theta^\text{N} \mathcal{J}(\theta) = \mathbf{F}_\theta^{-1} \nabla_\theta\mathcal{J}(\theta) \end{aligned} $$

其中 $d_\text{N}^*$ 仅提取 $\theta$ 上最优移动步长的方向，忽略了标量 $\beta^{-1}$。

NES 算法

与一个样本相关的适应度标记为 $f(x)$，而 $x$ 上的搜索分布由 $\theta$ 参数化。NES 旨在优化参数 $\theta$ 以实现最大期望适应度：

$$ \mathcal{J}(\theta) = \mathbb{E}_{x\sim p_\theta(x)} [f(x)] = \int_x f(x) p_\theta(x) dx $$

使用与 REINFORCE 相同的对数似然技巧：

$$ \begin{aligned} \nabla_\theta\mathcal{J}(\theta) &= \nabla_\theta \int_x f(x) p_\theta(x) dx \\ &= \int_x f(x) \frac{p_\theta(x)}{p_\theta(x)}\nabla_\theta p_\theta(x) dx \\ & = \int_x f(x) p_\theta(x) \nabla_\theta \log p_\theta(x) dx \\ & = \mathbb{E}_{x \sim p_\theta} [f(x) \nabla_\theta \log p_\theta(x)] \end{aligned} $$

除了自然梯度之外，NES 还采用了一些重要的启发式方法，以使算法性能更加稳健。

• NES 应用了基于排名的适应度塑形，即使用在单调递增的适应度值下的排名，而不是直接使用 $f(x)$。或者，它也可以是排名的函数（“效用函数”），这被视为 NES 的一个自由参数。
• NES 采用自适应采样来在运行时调整超参数。当从 $\theta$ 变为 $\theta’$ 时，将从 $p_\theta$ 抽取的样本与从 $p_{\theta’}$ 抽取的样本通过 [Mann-Whitney U 检验(https://en.wikipedia.org/wiki/Mann%E2%80%93Whitney_U_test)] 进行比较；如果显示出正或负的符号，则目标超参数会按一个乘法常数减小或增大。注意，样本 $x’_i \sim p_{\theta’}(x)$ 的得分应用了重要性采样权重 $w_i’ = p_\theta(x) / p_{\theta’}(x)$。

应用：深度强化学习中的 ES

用于强化学习的 OpenAI ES

在强化学习中使用进化算法的概念可以追溯到很久以前，但由于计算限制，此前仅局限于表格型强化学习。

受 NES 启发，OpenAI 的研究人员（Salimans 等人，2017）提出使用 NES 作为无梯度黑盒优化器，以找到能最大化回报函数 $F(\theta)$ 的最优策略参数 $\theta$。关键在于向模型参数 $\theta$ 添加高斯噪声 $\epsilon$，然后利用对数似然技巧将其表示为高斯概率密度函数的梯度。最终，噪声项仅作为衡量性能的加权标量保留下来。

假设当前参数值为 $\hat{\theta}$（添加的 hat 符号是为了将该值与随机变量 $\theta$ 区分开）。$\theta$ 的搜索分布被设计为具有均值 $\hat{\theta}$ 和固定协方差矩阵 $\sigma^2 I$ 的各向同性多元高斯分布。

$$ \theta \sim \mathcal{N}(\hat{\theta}, \sigma^2 I) \text{ 等价于 } \theta = \hat{\theta} + \sigma\epsilon, \epsilon \sim \mathcal{N}(0, I) $$

用于 $\theta$ 更新的梯度为：

$$ \begin{aligned} & \nabla_\theta \mathbb{E}_{\theta\sim\mathcal{N}(\hat{\theta}, \sigma^2 I)} F(\theta) \\ &= \nabla_\theta \mathbb{E}_{\epsilon\sim\mathcal{N}(0, I)} F(\hat{\theta} + \sigma\epsilon) \\ &= \nabla_\theta \int_{\epsilon} p(\epsilon) F(\hat{\theta} + \sigma\epsilon) d\epsilon & \scriptstyle{\text{; 高斯分布 }p(\epsilon)=(2\pi)^{-\frac{n}{2}} \exp(-\frac{1}{2}\epsilon^\top\epsilon)} \\ &= \int_{\epsilon} p(\epsilon) \nabla_\epsilon \log p(\epsilon) \nabla_\theta \epsilon\;F(\hat{\theta} + \sigma\epsilon) d\epsilon & \scriptstyle{\text{; 对数似然技巧}}\\ &= \mathbb{E}_{\epsilon\sim\mathcal{N}(0, I)} [ \nabla_\epsilon \big(-\frac{1}{2}\epsilon^\top\epsilon\big) \nabla_\theta \big(\frac{\theta - \hat{\theta}}{\sigma}\big) F(\hat{\theta} + \sigma\epsilon) ] & \\ &= \mathbb{E}_{\epsilon\sim\mathcal{N}(0, I)} [ (-\epsilon) (\frac{1}{\sigma}) F(\hat{\theta} + \sigma\epsilon) ] & \\ &= \frac{1}{\sigma}\mathbb{E}_{\epsilon\sim\mathcal{N}(0, I)} [ \epsilon F(\hat{\theta} + \sigma\epsilon) ] & \scriptstyle{\text{; 负号可被吸收。}} \end{aligned} $$

在一个世代中，我们可以采样多个 $\epsilon_i, i=1,\dots,n$ 并并行评估其适应度。其精妙之处在于，无需共享任何大模型参数。只需在工作节点之间传递随机种子，主节点就足以完成参数更新。这种方法后来被扩展为自适应学习损失函数；详见我之前关于进化策略梯度（Evolved Policy Gradient）的文章。

为了提升性能的鲁棒性，OpenAI ES 采用了虚拟批量归一化（用于计算统计量的小批量固定的批量归一化）、镜像采样（采样一对 $(-\epsilon, \epsilon)$ 进行评估）以及适应度塑形（fitness shaping）。

基于进化策略的探索

探索（相对于利用）是强化学习中的一个重要课题。在上述 ES 算法中，优化方向仅从累积回报 $F(\theta)$ 中提取。如果没有显式的探索机制，智能体可能会陷入局部最优。

新颖性搜索进化策略（NS-ES；Conti 等人，2018）通过朝着最大化新颖性分数的方向更新参数来鼓励探索。新颖性分数取决于特定于领域的行为表征函数 $b(\pi_\theta)$。$b(\pi_\theta)$ 的选择因任务而异，且似乎有些随意；例如，在论文中的人形机器人运动任务里，$b(\pi_\theta)$ 是智能体的最终 $(x,y)$ 位置坐标。

1. 每个策略的 $b(\pi_\theta)$ 都会被推入一个存档集合 $\mathcal{A}$ 中。
2. 策略 $\pi_\theta$ 的新颖性通过计算 $b(\pi_\theta)$ 与 $\mathcal{A}$ 中所有其他条目之间的 k 近邻分数来衡量。（存档集合的用法听起来与情景记忆非常相似。）

$$ N(\theta, \mathcal{A}) = \frac{1}{\lambda} \sum_{i=1}^\lambda \| b(\pi_\theta), b^\text{knn}_i \|_2 \text{，其中 }b^\text{knn}_i \in \text{kNN}(b(\pi_\theta), \mathcal{A}) $$

进化策略的优化步骤依赖于新颖性分数而非适应度：

$$ \nabla_\theta \mathbb{E}_{\theta\sim\mathcal{N}(\hat{\theta}, \sigma^2 I)} N(\theta, \mathcal{A}) = \frac{1}{\sigma}\mathbb{E}_{\epsilon\sim\mathcal{N}(0, I)} [ \epsilon N(\hat{\theta} + \sigma\epsilon, \mathcal{A}) ] $$

NS-ES 维护一组 $M$ 个独立训练的智能体（“元种群”），$\mathcal{M} = \{\theta_1, \dots, \theta_M \}$，并根据新颖性分数按比例选择一个进行推进。最终我们选出最佳策略。此过程等同于集成方法；在 SVPG 中也可见到相同的思想。

$$ \begin{aligned} m &\leftarrow \text{根据概率}\frac{N(\theta_i, \mathcal{A})}{\sum_{j=1}^M N(\theta_j, \mathcal{A})} \text{选取 } i=1,\dots,M \\ \theta_m^{(t+1)} &\leftarrow \theta_m^{(t)} + \alpha \frac{1}{\sigma}\sum_{i=1}^N \epsilon_i N(\theta^{(t)}_m + \epsilon_i, \mathcal{A}) \text{ 其中 }\epsilon_i \sim \mathcal{N}(0, I) \end{aligned} $$

其中 $N$ 是高斯扰动噪声向量的数量，$\alpha$ 是学习率。

NS-ES 完全舍弃了奖励函数，仅针对新颖性进行优化，以避免陷入欺骗性的局部最优。为了将适应度重新纳入公式，又提出了另外两种变体。

NSR-ES：

$$ \theta_m^{(t+1)} \leftarrow \theta_m^{(t)} + \alpha \frac{1}{\sigma}\sum_{i=1}^N \epsilon_i \frac{N(\theta^{(t)}_m + \epsilon_i, \mathcal{A}) + F(\theta^{(t)}_m + \epsilon_i)}{2} $$

NSRAdapt-ES (NSRA-ES)：自适应权重参数 $w$ 初始值为 1.0。如果性能在若干代内保持平稳，我们就开始降低 $w$。当性能开始提升时，我们停止降低 $w$，转而增加它。这样，当性能停止增长时，适应度被优先考虑；否则，新颖性被优先考虑。

$$ \theta_m^{(t+1)} \leftarrow \theta_m^{(t)} + \alpha \frac{1}{\sigma}\sum_{i=1}^N \epsilon_i \big((1-w) N(\theta^{(t)}_m + \epsilon_i, \mathcal{A}) + w F(\theta^{(t)}_m + \epsilon_i)\big) $$

CEM-RL

CEM-RL 方法（Pourchot & Sigaud, 2019）将交叉熵方法（CEM）与 DDPG 或 TD3 相结合。这里的 CEM 工作原理与上述简单高斯 ES 基本相同，因此可以使用 CMA-ES 替换相同的函数。CEM-RL 建立在进化强化学习（ERL；Khadka & Tumer, 2018）框架之上，在该框架中，标准 EA 算法选择并进化一个演员群体，过程中生成的 rollout 经验随后被添加到回放缓冲区中，用于训练 RL 演员和 RL 评论家网络。

工作流程：

• 1. CEM 群体的平均演员 $\pi_\mu$ 使用一个随机演员网络进行初始化。
• 1. 评论家网络 $Q$ 也被初始化，它将由 DDPG/TD3 进行更新。
• 1. 重复直到满意：
  • a. 采样一个演员群体 $\sim \mathcal{N}(\pi_\mu, \Sigma)$。
  • b. 对一半的群体进行评估。它们的适应度分数被用作累积奖励 $R$，并添加到回放缓冲区中。
  • c. 另一半与评论家一起更新。
  • d. 新的 $\pi_mu$ 和 $\Sigma$ 是使用表现最优的精英样本计算得出的。CMA-ES 也可用于参数更新。

扩展：深度学习中的进化算法

（本节内容并非关于进化策略，但仍属有趣且相关的阅读材料。）

进化算法已被应用于许多深度学习问题。POET（Wang 等人，2019）是一个基于进化算法的框架，它试图在问题本身被解决的同时，生成多种不同的任务。POET 在我上一篇关于元强化学习的文章中已有介绍。进化强化学习（ERL）是另一个例子；见图 7 (b)。

下面我将更详细地介绍两个应用：基于种群的训练（PBT）和权重无关神经网络（WANN）。

超参数调优：PBT

基于种群的训练（Jaderberg 等人，2017），简称 PBT，将进化算法应用于超参数调优问题。它联合训练一个模型种群及其对应的超参数，以实现最优性能。

PBT 从一组随机候选开始，每个候选包含一对模型权重初始化和超参数，即 $\{(\theta_i, h_i)\mid i=1, \dots, N\}$。每个样本并行训练，并定期异步评估其自身性能。当某个成员认为准备就绪时（即，在进行了足够多的梯度更新步骤后，或者当性能足够好时），它有机会通过与整个种群进行比较来进行更新：

• 利用（exploit()）：当此模型表现不佳时，其权重可以被一个表现更好的模型替换。
• 探索（explore()）：如果模型权重被覆盖，探索步骤会用随机噪声扰动超参数。

在此过程中，只有有前景的模型和超参数组合才能存活并继续进化，从而更好地利用计算资源。

网络拓扑优化：WANN

权重无关神经网络（简称 WANN；Gaier & Ha 2019）通过实验探索如何在不训练网络权重的情况下，搜索能够实现最优性能的最小网络拓扑结构。由于不考虑网络权重的最佳配置，WANN 将更多重点放在架构本身，这使得其研究方向与 NAS 有所不同。WANN 深受一种用于演化网络拓扑的经典遗传算法——NEAT（“增强拓扑的神经演化”；Stanley & Miikkulainen 2002）的启发。

WANN 的工作流程与标准遗传算法几乎完全相同：

1. 初始化：创建一个由最小网络组成的种群。
2. 评估：使用一系列共享权重值进行测试。
3. 排序与选择：根据性能和复杂度进行排序和选择。
4. 变异：通过对最佳网络进行变异来创建新种群。

在“评估”阶段，所有网络权重被设置为相同值。通过这种方式，WANN 实际上是在搜索可以用最小描述长度来描述的神经网络。在“选择”阶段，网络连接和模型性能都会被考虑。

如图 11 所示，WANN 的结果分别使用随机权重和共享权重（单一权重）进行了评估。有趣的是，即使对所有权重强制进行权重共享并仅调整这一个参数，WANN 仍能发现实现不俗性能的拓扑结构。

---

引用格式：

@article{weng2019ES,
  title   = "Evolution Strategies",
  author  = "Weng, Lilian",
  journal = "lilianweng.github.io",
  year    = "2019",
  url     = "https://lilianweng.github.io/posts/2019-09-05-evolution-strategies/"
}

参考文献

[1] Nikolaus Hansen. “The CMA Evolution Strategy: A Tutorial” arXiv 预印本 arXiv:1604.00772 (2016).

[2] Marc Toussaint. 幻灯片：“Introduction to Optimization”

[3] David Ha. “A Visual Guide to Evolution Strategies” 博客 otoro.net. 2017 年 10 月.

[4] Daan Wierstra 等人. “Natural evolution strategies.” IEEE 世界计算智能大会, 2008.

[5] Agustinus Kristiadi. “Natural Gradient Descent” 2018 年 3 月.

[6] Razvan Pascanu 与 Yoshua Bengio。《重访深度网络的自然梯度》。arXiv 预印本 arXiv:1301.3584 (2013)。

[7] Tim Salimans 等人。《进化策略作为强化学习的可扩展替代方案》。arXiv 预印本 arXiv:1703.03864 (2017)。

[8] Edoardo Conti 等人。《通过新奇探索智能体群体改进深度强化学习中进化策略的探索能力》。NIPS。2018。

[9] Aloïs Pourchot 与 Olivier Sigaud。《CEM-RL：结合进化与梯度方法进行策略搜索》。ICLR 2019。

[10] Shauharda Khadka 与 Kagan Tumer。《强化学习中进化引导的策略梯度》。NIPS 2018。

[11] Max Jaderberg 等人。《基于群体的神经网络训练》。arXiv 预印本 arXiv:1711.09846 (2017)。

[12] Adam Gaier 与 David Ha。《权重无关神经网络》。arXiv 预印本 arXiv:1906.04358 (2019)。