雷锋网 AI 科技评论按：这是 otoro.net的系列技术博客之一，以通俗可视化的方法讲解了进化策略（Evolution Strategies）中的诸多概念。雷锋网 AI 科技评论全文编译如下。

本文将通过一些可视化的案例向大家解释进化策略是如何工作的。为了方便更多入门读者理解本文，我将对相关公式做简化处理。同时，我也为希望理解更多数学细节的读者提供了相关数学公式的原始论文。这是本系列的第一篇文章，在本系列中，我会向大家介绍如何在诸如 MNIST、OpenAI Gym、Roboschool、PyBullet 等任务中应用这些算法。

引言

神经网络模型是非常灵活的，有着强大的数据表示能力。如果我们能够找到合适的模型参数，我们可以使用神经网络解决许多困难的问题。深度学习的成功在很大程度上归功于使用反向传播算法，它可以高效地计算目标函数梯度的能力，而这个目标函数中包含着所有的模型参数。通过这些基于梯度的计算，我们能高效地在参数空间中寻找到有利于神经网络完成任务的解。

然而，仍然有很多问题是反向传播算法所不适用的。例如，在强化学习（reinforcement learning）问题中，我们同样可以训练一个神经网络去做一系列的行动决策，从而在环境中完成某些任务。但是，根据当前训练个体（agent）做出的操作去估计未来给予该训练个体的奖励信号的梯度是十分复杂的，尤其是在未来的许多时间步骤上都会获得奖励的情况下。更何况即使我们能够计算出准确的梯度，我们仍然可能在训练过程中陷入局部最优，这是普遍存在于很多强化学习任务中的现象。

陷入局部最优

在强化学习研究中，有一个领域专门致力于研究这个归因分配问题，并且在近年来取得了很大的进展。然而，但奖励信号十分稀疏时，归因分配仍然是很困难的。在现实世界中，奖励确实可能是很稀疏而且有噪声的。有时，我们仅仅得到了一个简单的奖励，而不知道它是如何做出的。就像一张年终奖金的支票，它的金额取决于我们的雇主，想确切地弄清楚为什么它如此之低可能是很困难的。对于这些问题，与其依赖于一个充斥着噪声的、并且很可能毫无意义的对未来的我们的策略的梯度估计，我们不妨大胆地直接忽略掉所有的梯度信息，尝试使用黑盒的优化技术，例如遗传算法（genetic algorithms）或进化策略（evolution strategies）。

OpenAI 就曾发表一篇名为《Evolution Strategies as a Scalable Alternative to Reinforcement Learning 》 () 的博文。在这篇文章中，他们认为，尽管进化策略比强化学习利用数据的效率较低一些，它仍然有许多的优势。进化策略摒弃了对于梯度的计算，这使得对于进化策略的估计将更加高效。与此同时，进化策略的计算任务能够被很容易地部署到由上千台机器组成的分布式环境中进行并行计算。实际上，在OpenAI从头开始多次运行了这个算法后，他们发现：使用进化策略算法发现的策略相对于使用强化学习发现的策略，种类更多！

在这里，我要指出，即便是对于确定一个机器学习模型的问题，例如设计一个神经网络架构，我们也是不能直接计算梯度的。尽管强化学习、进化策略、遗传算法这样的方法都能被用于在解空间中搜索能够达到任务要求的模型参数，在本文中，我将仅仅着眼于将这些算法应用到为一个预定义的模型搜索参数的问题中。

进化策略为何物？

二维 Rastrigin 函数有许多局部最优点

下图为转换后的二维的 Schaffer 函数和 Rastrigin 函数的俯视图，这两种函数常常被用作测试连续的黑盒优化算法的用例。在图片中，更亮的区域代表 F(x, y) 有更大的函数值。如你所见，这个函数有许多的局部最优点。我们要做的就是找到一系列的模型参数 (x, y)，从而使 F(x, y) 尽可能地接近全局最大值。

尽管人们对于进化策略的定义版本不一。在这里，我们将其定义为：一个为用户提供一系列用于评估一个问题的候选解决方案的算法。这里的评估方法是基于一个给定了解决方案的目标函数，并且会返回单个适应度。根据当前的解决方案的适应度结果，进化策略接着会生成下一代的候选解决方案，新的方案会更有可能得到更好的结果。一旦提出的最佳方案令用户满意，迭代的进程就会被终止。

我们可以通过类似下面这样的伪码实现一个叫做 EvolutionStrategy 的进化策略算法：

solver = EvolutionStrategy

while True:

# ask the ES to give us a set of candidate solutions solutions = solver.ask

# create an array to hold the fitness results. fitness_list = np.zeros(solver.popsize)

# evaluate the fitness for each given solution.

for i in range(solver.popsize):

fitness_list[i] = evaluate(solutions[i])

# give list of fitness results back to ES solver.tell(fitness_list)

# get best parameter, fitness from ES best_solution, best_fitness = solver.result

if best_fitness > MY_REQUIRED_FITNESS: break

尽管我们通常在每一代的迭代进程中将种群的规模设置为一个常量，但是实际上本可以不必这样做。进化策略可以根据我们的要求生成相应数目的候选方案，这是因为进化策略给出的解决方案是从一个概率分布中抽样而来的，这些分布函数的参数会在每一次的迭代中被进化策略所更新。我将通过一个简单的进化策略来解释这个抽样过程。

简单的进化策略

我们可以想象到的最简单的进化策略，可能是直接从一个均值为 μ、标准差为 σ 的正态分布中抽样得到一系列的解。在我们二维的问题中，μ=（μx，μy）并且 σ=（σx，σy）。一开始，μ 被设置在原点。在适应结果被评估之后，我们将 μ 设置为这一次迭代中在种群中最优解，并且在这个新的均值周围进行抽样得到下一代的解决方案。下图为这个简单的进化策略在之前提到的两个问题中进行20次迭代之后的表现：

在上面的可视化示例中，绿色的点代表每一代分布函数的均值，蓝色的点是被抽样到的解，红色的点是目前我们的算法找到的最优解。

这个简单的算法通常只适用于简单的问题。由于这个算法本身是一个贪婪算法，它会抛弃当前的最优解之外的所有解。因此，在更加复杂的问题中，这个算法可能更易于陷入局部最优点。（因为复杂问题解空间更大，全局最优解可能被隐藏在这种简单算法抛弃掉的空间里）如果能够从代表更多的解决方法的概率分布中对下一次迭代进行抽样，而并非仅仅从当前这一代的最优解附近抽样，可能更为有利。

简单的遗传算法

遗传算法是最经典的黑盒优化算法之一。对于遗传算法来说，它有许多不同程度复杂的变种，在这里，我只为大家介绍最简单的版本。

遗传算法的思路是十分简单的：仅仅将目前这一代最好的前 10% 的解保留下来，让种群中其他的解被淘汰掉（类似于自然界中的优胜劣汰）。在下一代中，我们随机选择上一代幸存下来的两个解作为父亲和母亲，将他们的参数进行重组，从而得到新的解。这个较差重组的过程使用投掷硬币（随机化）的方法来决定从上一代的父亲母亲中的哪一方来继承当前位置上的参数。在我们使用的这两个简单的二维测试函数中，我们新的解可能以百分十50的概率从双亲其中的一方继承 x 或 y。在这个交叉重组的过程结束后，带固定标准差的高斯噪声也会被加入到新的解中。（作为正则项）

上图向大家展示了这个简单的遗传算法是如何工作的。绿色的点代表棕群众上一代被保留下来的「精英」（即用于当代交叉重组的双亲），蓝色的点代表用于产生候选解的后代，红色的点代表最优解。

遗传算法通过与多种候选解保持联系（交叉重组）保证了生成的解的多样性。然而，实际上，种群中大多数幸存下来的「精英」会渐渐地易于收敛到局部最优点。此外，遗传算法还有很多复杂的变形，例如 CoSyNe、ESP 以及 NEAT，它们希望通过将种群中相似的解聚类到不同的物种子集中，从而保证生成解的多样性。

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

简单的进化策略和遗传算法有一个共同的缺点，即我们噪声的标准差参数是固定的。有时，我们会希望在更大的解空间中探索更好的解，因此我们需要增加我们搜索空间的标准差。此外，我们有时十分确信我们已经探索到最优解附近了，那么我们只想对当前的解进行微调。我们主要希望我们的搜索过程能够有下图这样的表现：

多么神奇啊！上图所示的搜索过程是通过协方差矩阵自适应进化策略（Covariance-Matrix Adaptation Evolution Strategy , CMA-ES）得到的。CMA-ES 算法可以得到每一次迭代的结果，并且自适应地在下一代的搜索中增大或者减小搜索空间。他不仅仅会自适应地调整参数 μ 和 σ，同时还会计算整个参数空间的协方差矩阵。在每一次迭代中，CMA-ES 会提供一个多元正态分布的参数，并从这个多元正态分布中抽样得到新的解。那么，这个算法如何知道该增大还是减小搜索空间呢？

在我们讨论该算法做到自适应的方法之前，我将先带大家复习一下如何对协方差矩阵做估计。这对于我们之后理解 CMA-ES 算法所使用的自适应方法十分重要。如果我们想要对一个我们整个抽样得到的大小为 N 的协方差矩阵进行参数估计，我们可以使用下面列出的公式去计算协方差矩阵C的最大似然估计。我们首先计算我们的种群中 xi和 yi的均值：

2*2的协方差矩阵中的元素可以表示为：

当然，这样得出的 μx和μy的均值估计，以及协方差项 σx、σy和 σxy仅仅是实际的原始抽样协方差矩阵的参数估计，对我们来说并不是特别有用。

CMA-ES 巧妙地修正了上面的协方差计算公式，从而使得它能够适用于最优化问题。我会详细说明它是如何做到这一点的。首先，它的主要任务是找出当前这一代最优秀的 N 个解 Nbest。为了方便起见，我们规定 Nbest为最优秀的前 25% 的解。在根据适应情况将得出的解排序后，我们将仅仅通过当代（g）最优秀的前25%的解去计算下一代（g+1）的均值 μ（g+1），换句话说，我们的计算过程可以被表示为下面的公式：

接下来，我们仅仅使用最优的前 25% 的解去估计下一代的协方差矩阵 C（g+1）。在这里，我们想到了一个聪明的计算方法：使用当代的均值 μg，而不是我们刚刚更新的 μ（g+1）。具体的计算公式如下：

在我们得到了下一代（g+1）的 μx、μy、σx、σy、σxy等参数后，我们现在可以抽样得到下一代的候选解。

这一连串图片形象地解释了这个算法如何根据当代（g）的计算结果去构造下一代（g+1）的解：

计算第 g 代中每一个解的适应程度

将第 g 代的最优的前 25% 的解挑选出来，如图中紫色的点所示

仅仅使用这些最优的前 25% 的解和当代的均值 μg（如图中绿色的点所示），来计算下一代的协方差矩阵C（g+1）

使用更新后的均值μ（g+1）和协方差矩阵C（g+1）得到的分布函数，抽样得出新的候选解集。

下面，让我们再一次将在两个问题中的整个搜索过程可视化地呈现在大家面前：

由于 CMA-ES 算法可以利用最优解的信息调整其均值和协方差矩阵，它可以在还距离最优解很远时对较大的空间进行搜索，在距离最优解较近时对较小的搜索空间进行探索。为了便于理解，我这里通过一个简单的 2 维问题对 CMA-ES 的介绍是高度简化的。如果想了解更多的细节，我建议你去阅读 CMA-ES 的作者为大家准备的教程 CMA-ES Tutorial ()。

CMA-ES 算法是如今最流行的无需梯度计算的优化算法之一，并且已经被许多研究者和实际工程人员选用。它真正的唯一的缺点是：当模型中的参数过多时候，算法的性能如何。通过计算，我们发现计算协方差的时间复杂度是 O(N2)，尽管最近人们已经将时间复杂度降到了近似于 O(N)。对我来说，当搜索空间内的参数少于 1000 时，我往往会选择 CMA-ES 算法。如果我足够有耐心，我发现在高达 10000 个参数的搜索空间中使用该算法也是同样可行的。

自然进化策略

假设你已经构建了一个人工生命模拟器，并且你想从中抽取出一个神经网络去控制一群中每个蚂蚁的行为。而如果我们使用简单的进化策略，这种优化方式会让蚂蚁的特性和行为朝着使每个蚂蚁个体各自受益的方向演变。这样一来，我们的种群中会充满只顾自己死活的自私的蚂蚁。

在这里我们不再使用让最适应环境的蚂蚁生存下来的准则。如果我们改变策略，使用整个种群中所有个体适应程度的总和作为度量标准，并且转而优化这个总和使得整个种群的康乐指数最大，结果会如何呢？哈哈，你最终将会创造一个马克思主义的蚂蚁乌托邦！

对于上述的这些信息算法，人们已经意识到它们都有一个缺点：它们会抛弃掉大多数的解而仅仅保留最优解。然而，那些较差的解往往包含「不要做」什么的信息，这种信息对于更好的计算出下一代的参数估计是十分有价值的。

许多研究强化学习的研究者对于这篇名为 REINFORCE 的论文（）十分熟悉。在这篇1992年发表的论文中，Williams 概述了一个用于估计关提出了于策略神经网络模型的参数的期望奖励的方法。在这篇论文的第 6 章中，作者也提出了使用强化学习作为一种进化策略的方式。这个强化学习和进化策略相结合的特例在 Parameter-Exploring Policy Gradients (PEPG, 2009) and Natural Evolution Strategies (NES, 2014)这两篇文章中得到了进一步的讨论和扩展。

在这个计算方法中，我们希望利用种群中所有个体的信息，无论是好是坏。这么做是为了估计出能够使整个种群在下一代朝着更好的方向发展的梯度信号。由于我们在这里需要对梯度进行估计，我们同样可以使用被广泛应用于深度学习的标准的随机梯度下降（SGD）法则来更新梯度。如果需要，我们甚至可以使用动量随机梯度下降法（Momentum SGD）、均方根传播法（RMSProp）以及自适应动量估计算法（Adam）来求解模型参数。

在这里，我们的思路是最大化抽取出的解的适应程度到的期望值。如果期望的结果足够好，那么抽样得到的种群中表现最好的个体甚至会更好，因此对期望进行优化是一个很合乎情理的方案。最大化抽样得到的解的期望适应程度，可以近似地被看作最大化整个种群的适应程度。

假设z是从概率分布函数 π（z，θ）中抽样得到的解向量，我们可以将目标函数F的期望值定义为：

其中，θ是概率分布函数的参数。例如，假设 π 是一个正态分布，那么相应地，θ 就是 μ 和 σ。对于我们简单的二维问题而言，每一个 z 都是一个二维向量（x，y）的整体。

论文 Natural Evolution Strategies (NES, 2014) 很详细地说明了 J（θ）关于 θ 的梯度是如何计算得来的。我们可以使用和 REINFORCE 算法相同的对数似然方法计算 J（θ）的梯度，具体公式如下：

在一个规模为 N 的种群中，我们将解表示为 z1、z2...zn，我们可以通过下面的和式估计梯度：

在得到了梯度之后，我们可以使用参数 α（例如 0.01）来表示学习率，并且开始优化概率分布函数 π 的参数 θ，从而使得我们抽样得到的解能够更有可能在目标函数 F 上取得更高的适应度。使用随机梯度下降法（或者 Adam 算法），我们可以按照如下的方式更新下一代的参数θ：

之后，我们从这个更新后的概率分布函数中抽样得到新的候选解集。我们会循环迭代以上的操作，直到我们找到了一个令人满意的解。

在论文 REINFORCE 的第六章中，Williams 推导出了梯度

的通用解法的公式，他考虑了 π（z，θ）是分解后的多元正态分布的特例（换而言之，参数的相关系数为 0）。在这个特例中，θ是 μ 和 σ 向量。因此，解的每一个元素可以从单元正态分布中抽样得到：

对于每一个解 i 的 θ 向量中每一个独立元素，通用的梯度公式

可以按照如下的方式进行推导：

为了更清楚地向大家说明，我使用角标 j 在参数空间中进行计数，而我们使用上标 i 来对总种群抽样得到的个体进行计数，这二者不会被混淆。在我们的二维问题中，z1=x, z2 = y, μ1=μx, μ2=μy, σ1=σx, σ2=σy。

上面这两个公式可以被带回到梯度近似公式中，并且推导出明确的对 μ 和 σ 进行更新。本文之前提到的论文都推导出了更明确的更新规则，包含了一个用于比较的基线，并且可以引入其他的类似于 PEPG 中对偶抽样的蒙特卡罗技巧，这也是我们赖以执行算法的基础。举例而言，论文 Natural Evolution Strategies (NES, 2014) 提出了将 Fisher 信息矩阵的逆矩阵引入梯度更新规则的方法。然而，这个思想与其他的进化策略算法是相同的，它们都在每一代中更新了多元正态分布的均值和标准差，并且从更新后的概率分布中进行抽样得到新的解集。下图是这两个公式执行动作的可视化图解：

如图所示，这种算法能够按需动态地改变 σ，用以探索或者微调解的空间。与 CMA-ES 不同，本算法的实现并不涉及相关性结构（如协方差）的计算。因此在这里，我们并没有得到对角型的椭圆样本，仅仅得到了垂直或者水平的样本。当然，如果需要的话，我们也可以在以机选效率为代价的情况下，引入整个协方差矩阵，从而推导出新的更新规则。

另外一个我喜欢这个算法的原因是，它能像 CMA-ES 那样，动态调整标准差，以致于我们可以逐渐增大或减小我们的搜索空间。因为在这个算法中，我们没有使用刻画相关性的参数，所以这个算法的时间复杂度为 O（N），那么当搜索空间较大，以致于 CMA-ES 性能比较差的时候，我会选择使用 PEPG。通常，当模型参数超过几千时，我会选择 PEPG。

OpenAI的进化策略

在 OpenAI 的论文中，他们实现的算法是之前提到的强化学习和进化策略相结合的那个特例。特别地，σ被固定为一个常量，只有参数 μ 会在每一代中被更新。下图所示为将σ固定为常量后这个进化策略工作的过程示例：

除了对这个原始算法进行简化，本文也提出了一个新的更新规则的修正，使其能够在不同的工作站机器组成的集群中进行并行计算。在这个更新规则中，大量的基于固定种子的随机数被事先与计算了出来。由此，每个工作站可以复制其他机器的参数，并且它只需要与其他机器进行一个数字的通信，即最终的适应度结果。如果我们想将进化策略扩展到数以千计、甚至数以百万计的不同的计算节点中去，这个修正的更新规则就显得十分重要了。因为，在每一次迭代的更新中每次都将整个解向量传输百万次是不切实际的。但如果每次值传输最终的适应度结果就应该是可行的了。在这篇论文中，他们展示了：使用亚马逊 EC2 平台上的 1440 个工作站可以在大约十分钟内解决 Mujoco 人形机器人行走的问题。

我认为，理论上来说，这个并行更新规则应该也对那些同样能够调整标准差 σ 的算法奏效。然而，实际的情况是，他们只是为了大规模的并行计算，希望将需要传输的部分降到最少。这篇颇具启发意义的文章同时也讨论了许多其他的将进化策略部署到强化学习领域的任务中的实践工作。我强烈推荐你们仔细研读这篇文章，进行深入探究。

构造适应度

上面提到的大部分算法通常都会与构造适应度的方法结合起来，例如接下来我要讨论「基于排序的适应度构造方法」。对适应度的构造可以让我们避免之前提到的种群中的离群点对于近似梯度计算的控制。具体的公式如下：

如果一个特殊的点 F（zm）比种群中其它的点 F（zi）都大得多，那么梯度可能被这个离群点控制，并且增加算法陷入局部最优的概率。为了缓解这个问题，我们可以使用适应度的排序转换。我们在这里不使用适应度函数的真实值，转而使用一个与解在种群中的排序成正比的增强适应度函数对结果进行排序。下图是分别使用原始的适应度和基于排序的适应度函数的效果对比图：

如图所示，假如我们有一个包含 101 个样本的种群，我们会估计种群中每个个体的真实适应度函数值，并且根据他们的适应度将解排序。在这里，我们将会给表现最差的个体赋予一个值为 -0.50 的强化适应度函数值，给倒数第二的解赋予 -0.49，...，赋予0.49 给表现第二好的解，赋予0.50给最好的解。这个强化适应度的集合会被用来计算梯度的更新。从某种程度上来说，这类似于在深度学习中直接使用批量归一化（batch-normalization）处理结果，但我们这种方式更为直接。还有一些其它的构造适应度的方法，但是他们最终基本上都会给出一个相似的结果。

我发现，当策略网络的目标函数是非确定性函数时，适应度构造在强化学习任务中是十分有用的。而由于随机生成的映射关系和各种各样的随机策略，这种情况是十分常见的。对于那些确定性的、性能良好的函数而言，使用适应度构造方法的用处不大，而且有时还会使找到最优解的速度变慢。

MNIST 上的测试结果

尽管相较于基于梯度的算法，进化策略可能是一种能够找到更多有奇效的解的方法。它仍然在很多能够计算出高质量的梯度的问题上，比基于梯度的算法效果差。就好比，用遗传算法做图像分类是十分荒谬的事情！但是，有时候，还真有人这么做，而且竟然有时这种尝试还挺有效！

由于目前几乎所有的机器学习算法都会在 MNIST 数据集上进行测试，我在这里也试着去将这些各种各样的进化策略算法应用到一个简单的、两层的用于对 MNIST 手写数字进行分类的卷积网络中。我只想看看我们的算法与随机梯度下降（SGD）相比，性能如何。由于这个卷积网络只有大约 11000 个参数，所以我们可以使用较为慢一点的 CMA-ES 算法。相关的代码和实验信息可以在下面的链接中找到。（）

以下是使用不同的进化策略得到的结果，我们使用了一个包含 101 个个体的种群，迭代计算了 300 次。我们持续记录了每一代结束时表现最好的模型的参数，并且在 300 次迭代后评估了这个模型。有趣的是，这个模型有时在测试集上的准确率大大高于那些得分较低的训练集的模型。

我们应该批判地看的这个实验结果，这是因为我们只运行了一次代码，而不是取 5-10 次运行结果的平均值。这个基于一次实验的结果似乎说明了，CMA-ES 模型在 MNIST 手写数字任务中是表现最好的，但是PEPG 算法也并没有差太远。这两个算法都达到了大约 98% 的测试准确率，比用作对比的基线 SGD 和Adam 低大约 1%。也许，能够动态地在每一次迭代中调整协方差矩阵和标准差参数的能力使得它能够微调权重，这比 OpenAI 提出的更简单的进化策略的变体要更好。

自己实现一个进化策略算法吧！

我们之前在文章中提到的所有这些算法都可能有开源的实现。CMA-ES的作者 Nikolaus Hansen 已经维护了一个基于 numpy 库的带有许多附加功能的 CMA-ES 的实现。他的 CMA-ES 的 python 实现版本使我在之前接触到了循环训练借口。因为这个接口十分易于使用，我也使用这个接口实现了一些其他的算法，例如简单的遗传算法、PEPG 以及 OpenAI 的进化策略算法。我将这些实现放在了一个小的名为 es.py 的 python 文件中，并且将原始的 CMA-ES 算法库也打包了进来。由此，我可以通过改变代码中的一行进行切换，从而快速比较不同的进化策略算法：

import es

#solver = es.SimpleGA(...)

#solver = es.PEPG(...)

#solver = es.OpenES(...)

solver = es.CMAES(...)

while True:

solutions = solver.ask

fitness_list = np.zeros(solver.popsize)

for i in range(solver.popsize): fitness_list[i] = evaluate(solutions[i])

solver.tell(fitness_list)

result = solver.result

if result[1] > MY_REQUIRED_FITNESS: break

你可以在 Github 和 Ipython notebook 上看到使用不同进化策略的 es.py 文件：

在这个包含 es.py文件的 Ipython notebook ( ) 中，展示了在 es.py 中使用进化策略去解决解决具有更多局部最优的一百维 Rastrigin 函数优化问题。这个一百维的版本比上述用与生成可视化图解的二维版本更加具有挑战性。下图是我们之前讨论过的那些算法在这个问题上的性能对比图：

在这个 100 维的 Rastrigin 函数优化问题中，没还有一个优化算法达到了全局最优解，其中使用 CMA-ES 算法得到的结果是最接近全局最优的，比其他算法都好多得多。PEPG 算法的性能排在第二位，OpenAI 的进化策略算法和遗传算法的性能则相对较差一些。这让我不得不用一个模拟退火方法去渐渐减小标准差 σ，让它在这个任务中表现得好一些。

使用CMA-ES算法在100维的Ras函数优化问题中最终得到的解，全局最优解应该是一个100维的元素的值为10的向量

在接下来的文章中，我会尝试将进化策略应用到其它的实验和有趣的问题中。欢迎大家持续关注本系列文章！

via otoro，雷锋网 AI 科技评论编译