演化策略(Evolutionary Strategies)
演化策略作为一种求解参数优化问题的方法，模仿生物进化原理，假设不论基因发生何种变化，产生的结果（性状）总遵循零均值、某一方差的高斯分布。所以我认为演化策略的核心是 优化问题。
1.1 优化
因为，在机器学习的过程中，根据我们搭建的模型并不是一开始就能根据输入获得我们想要的结果，所以就需要对我们的模型进行优化，以使误差（loss）达到最小。优化分为黑盒优化和白盒优化。
黑盒优化：非形式化的来说，一个黑盒函数 F 可以理解为从 输入 X(x1,x2,x3...) 到 输出 的一个映射.但是映射关系 F 的解析表达式及工作方式未知，我们只能通过不断地将数据输入到黑盒函数中然后通过得到的输出值来猜测黑盒函数的结构信息.下图表示一个黑盒问题的映射关系。
与黑盒优化问题相对应的优化问题便是白盒优化问题。白盒问题要么优化问题的具体形式已知(如线性回归问题的表达式形式是已知的，只是每个自变量的系数未知),要么虽然表达式的形式未知，但是我们可以利用目标对优化参数的梯度进行迭代(如深度神经网络，尽管深度网络也常被看做一个黑盒)。这里的黑盒优化指的是优化目标的具体表达式及其梯度信息均未知的优化问题，因此我们无法利用优化目标的本身特性求得其全局最优解，也无法直接利用参数的梯度信息。
除了深度网络的超参数优化问题之外，深度强化学习中智能体与环境的交互问题也可以看做一个黑盒优化问题。在model-free强化学习问题中,我们不对智能体所处的环境进行建模。在这种情形下,我们将环境当做一个黑盒,智能体通过不断尝试动作来从这个黑盒中获得奖励值,最后的优化目标是使累计获得的奖励值最大。后面会对强化学习的基本原理进行简单讲解。下图展示了强化学习问题的一般步骤。
1.2 黑盒优化方法
1.2.1 网格搜索（Grid Search）
以机器学习中的分类问题为例，在模型训练过程中，我们通常需要多次调整参数以使我们的输出准确率更高，如果涉及到参数过多就需要多次的人工修改，这时我们可以采用网格搜索---也就是多参数的交叉组合，从而在所有组合中一次性找出最优参数。
1.2.2 随机搜索（Random Search）
一个简单的可以替代网格搜索的方法是随机搜索(random search)法.顾名思义,随机搜索在参数的可能取值中随机抽出来进行性能评估,直到我们给定的计算资源耗尽为止.当其中一些参数比另一些参数重要得多时,随机搜索算法往往比网格搜索方法更有效。这一示意图如图3所示，可以看出同样是进行9次性能评估,随机搜索能够搜索更多的重要参数上所对应的值。
其他黑盒优化的方法还有遗传算法（Genetic Algorithm）、进化算法等基于种群的算法，后面会进行介绍。
1.3 黑盒优化遇到的问题
黑盒优化问题其巨大的计算代价限制了其训练数据的规模，比如网格搜索设定n组超参数，每组差参数设定2个值，那么整个模型就会被运行2^n次。因此如何根据模型的不确定程度来指导我们对模型性能进行更为有效的评估至关重要。贝叶斯优化理论是对黑盒问题进行全局优化并且给出模型不确定性的一种前沿方法,其有两个关键的组成部分：一个概率代理模型(probabilistic surrogate model)和一个确定下一步评估哪个点的获取函数(acquisition function)。在每次迭代中,通过目前位置所有的观测值对代理函数进行拟合，然后根据概率模型的预测分布来确定不同候选点对减少模型不确定性所起到的作用来权衡对当前模型的探索与利用(是通过采样新的数据来进一步降低模型的不确定性还是利用当前的模型进行预测)。与需要昂贵评估代价的黑盒函数相比，这里的获取函数的计算成本较低，从而可以对该获取函数进行优化。
1.4 梯度优化
在高数课本中我们可以找到梯度这个概念， 梯度是一个矢量，是函数一个点上导数最大值的方向，也就是函数值在该方向上变化最快，因此只要随着梯度的方向，便能最快的到达极值点。梯度下降（gradient descent）的方法就是这么得来的。梯度下降法的基本思想可以类比为一个下山的过程：想象我们在山顶，只要我们每一步都沿着最陡的方向迈出下一步，那么我们一定可以最快到达山脚。因此，找到了梯度，我们也需要小心注意步长值，若步长值太大，我们可能一步迈出过大，错过了极值点，若步长值太小，我们到达极值点的次数会增加。
1.4.1 小批量梯度下降（mini-batch gradient decent）
一般而言，梯度下降需要在遍历所有的数据后才进行梯度计算然后更新参数。假设现有数据集有10,000条数据，那么在这10,000条数据都进行训练之后才会确定梯度，这样的计算会耗时很长。随机梯度下降解决的这个需要遍历所有数据才更新一次参数的问题。随机梯度下降根据每一个小批量数据进行更新参数。也就是说，10,000个数据，假设分成10个批量，每个批量是1,000个数据，那么在遍历完每个批量后，计算这个小批量的梯度然后进行更新参数，这样在遍历完10,000个多有数据后，梯度下降实际上已经进行了十次，相比于普通梯度下降而言，速度快了10倍。实验结果表明，在数据打乱情况下，随机梯度下降的每一个批量是可以很好近似整个数据集的。随机梯度下降的参数更新公示如下：
α表示的是学习率（learning rate），也就是下山例子中的步长值，所以学习率的设置影响着优化过程。
1.4.2 随机梯度下降（SAG）
在SG方法中，虽然避开了运算成本大的问题，但对于大数据训练而言，SG效果常不尽如人意，因为每一轮梯度更新都完全与上一轮的数据和梯度无关。随机平均梯度算法克服了这个问题，在内存中为每一个样本都维护一个旧的梯度，随机选择第i个样本来更新此样本的梯度，其他样本的梯度保持不变，然后求得所有梯度的平均值，进而更新了参数。
如此，每一轮更新仅需计算一个样本的梯度，计算成本等同于SG，但收敛速度快得多。
1.4.3 自适应矩估计（Adam）
Adam （ adaptive moment estimation）自适应矩估计算法是目前比较流行的一种优化算法 ，于2015 年在ICLR论文 Adam: A Method for Stochastic Optimisation被提出。Adam 算法根据导数的一阶矩阵估计和二阶矩估计（概率论内容）动态调整学习率。一阶矩估计即是导数的均值，二阶矩估计即是导数平方的均值。Adam算法的步骤如下：
beta1 通常取值 0.9 , beta2 通常取值 0.999， eps 取一个微小值防止分母为 0， 其中 mt 和 vt 式子中的 t 代表的是迭代次数，也就是调用了 adam 算法的次数，等价于计算梯度的次数。
1.5非梯度优化
在实际应用中，有些目标函数的梯度不容易计算，即使使用有限差分等近似算法，也会因为噪声的存在导致结果不精确。无梯度优化算法（DFO-Derivative-Free Optimization）可以在不计算梯度的情况下进行问题的最优化，主要有两类思路，一是根据目标函数的样本进行拟合，对拟合函数进行最优化；二是用一些启发式算法。比如1. 有限差分和误差 2. 基于模型近似的方法 3. 坐标和模式搜索方法 4. 其他DFO方法 ，详见https://blog.****.net/fangqingan_java/article/details/48946903 。
2. 协 方 差 矩 阵 自 适 应 进 化 策 略 （CMA-ES）
2.1基本概念
先介绍一下基本概念：协方差 是一种用来度量两个随机变量关系的统计量：结果>0表示两个变量正相关（比如身高越高的人往往体重越大） ，<0表示两个变量负相关， =0表示两个变量独立，公式如下：
均值（期望）：
协方差：
协方差矩阵：两个向量（多个随机变量）之间的相关性统计，协方差矩阵的维度等于随机变量的个数。矩阵中的数据按行排列与按列排列求出的协方差矩阵是不同的，这里默认数据是按行排列。即每一行是一个样本数据，那么每一列就组成一个随机变量。
具体求解步骤见https://blog.****.net/Mr_HHH/article/details/78490576
CMA-ES（Covariance Matrix Adaptation-Evolutionary Strategies）是 在 演化策略 ( Evolution Strategy，ES) 的基础上发展起来的一种高效搜索算法，它将 ES 的可靠性、全局性与自适应协方差矩阵的高引导性结合起来，对求解非凸非线性优化问题具有较强的适应性，目前以其良好的寻优性能在优化领域备受关注。并且，在对全局优化问题（与进化算法相比） 的求解中，CMA-ES 对步长的优化可以避免种群过早收敛以及在种群很大的情况下避免局部最优，并且它是一种黑箱优化算法。
对多元高斯分布（也称多元正态分布，概率论内容）进行采样得到新解，使用其中较好的解更新高斯分布的参数，符合最大熵原理(均值和方差已知时，高斯分布（正态分布）具有的信息熵最大，正因为如此高斯分布在自然界中才会这么普遍)。即：1 产生新解 ，2 更新均值，3 自适应协方差矩阵，4 步长更新。详见 https://blog.****.net/qq_40019838/article/details/99882885
3. 自然选择策略 (Natural Evolution Strategies，NES)
NES 也是是一种黑箱式优化算法。Wirestra等人提出了将进化算法和神经网络中的梯度下降思路结合在一起的想法。传统的进化算法包含突变和重组这两个步骤。 我们通过这两个步骤， 期待找到更好的解法。 然而， 突变和重组是完全随机的，不会根据已知的数据集特征产生 进化的倾向性，所以多数情况下，他们不会产生比当前这一代更优的解法。 因此, 我们想引入梯度下降(自然梯度)的思想, 从而使得突变总是能够朝着使个体适应度更好的方向（比如误差更小的方向）迈进。
换句话说, 我们用梯度下降替代了进化算子中的突变和重组步骤，官方定义 为 NES是一类利用分布参数上的估计梯度策略迭代更新搜索分布的进化策略。种群进化步骤为：
1.利用参数化搜索分布产生一批搜索点（类比种群个体），对每一个个体求适应度函数值。分布的参数允许算法自适应的捕捉适应度函数的局部结构（例如自动求出高斯分布的均值和协方差矩阵）
2.NES估计一个搜索梯度的参数，然后沿着自然梯度（这是一种二阶方法，与普通梯度不同，他会重新标准化 w.r.t不确定性）执行梯度上升步骤（这一步非常重要，因为他可以防止震荡、过早收敛和给定参数化带来的不期望的影响）
3.整个过程迭代进行，直到满足停止条件。
NES引入了一些新技术并解决了很多问题：(以下技术的原理推导及实验详见14年 Wierstra 等人发表的论文Natural Evolution Strategies)
1. 引入自然梯度算法解决普通梯度存在的过早收敛和尺度不变性问题。
2. 引入Fitness shaping使NES算法不受适应度保序变换的影响，增强算法的鲁棒性
3. 适应性抽样调整了在线学习率，在基准上产生了高绩效的结果
4. 指数参数化是维持正定协方差矩阵的关键
5. 自然坐标系保证了计算的可行性。
4. 强化学习
参考的博客及论文：