进化策略（Evolution Strategies，ES）

作一个生物学的类比，进化策略将问题的解决方案模型化为物种（多重变量的种群个体正态分布在适应度空间中）。因此，这些种群有能力去进化自己的进化能力来使他们适应他们所处的环境。如果说EP是基于行为进化的，那么ES则是基于进化的进化的（对进化这一行为本身进行进化）。

尽管都是利用变异、交叉（重组），但在操作上，ES同EP和GA都有所不同。ES同EP一样，采取的是自上而下的视角，强调的是表现型行为而非基因型；ES同样使用实数作为变量而非GA中的二进制编码。ES的目标是将种群的大多数进化（移动）到空间的最佳区域；使用一条简单规则：适者生存来指导进化，每一代中的最优个体进行复制，他们同他们的子代很相似，但也有差别（引入了变异）。个体作为问题的潜在解，其表现型特征是由一个数字向量表示，通过给父代表现型特征坐标加一个正态分布的随机数而引入变异，使得子代在原本空间位置附近探索更优的位置，即$x_i^{\prime }(t)=x_i+N(0,{\sigma }^2)$。

总之，在ES中，在父代的特征上进行突变，以随机产生与父代相似但不同的子代。每个存活个体的坐标是以一个正态分布的均值为中心，其对应的策略参数以方差或标准差为中心，子向量的数值根据位置和策略参数生成。

ES的步骤

1. 种群初始化（个体初始化、策略参数初始化）；
2. 用 $\mu$个父代重组生成 $\lambda$ 个子代；
3. 所有子代变异；
4. 对 $\lambda$ 或 $\mu +\lambda$ 个种群成员进行评估；
5. 选择 $\mu$ 个个体作为新种群；
6. 返回第 2 步，直到达到终止条件。
   

进化窗口

ES在变异上的一个独特观点是进化窗口，这一理论背后的原理是可以使适应度提升的变异的步长都在一个限定的步长范围（窗口）内，在进化窗口之外的交叉和变异对进化是无用的。在ES中，变异率应当同个体种群成员的变量数量成反比，同最优解的距离成正比。但实际上，最优解的精确值是未知的，但关于最优解的相关信息是有可能知道的，通常在某个数量级内是知道的。这些有限的信息对于知道ES的搜索是很有帮助的。

策略参数

变异的种群数量，是种群的进化率在ES中是一个很关注的方面。个体体现在一组特征和相应的策略参数上，通常是方差或标准差，利用策略参数可以改变个体后代的特征向量，例如，标准差$\sigma$可被用来刻画正态分布的变化性，以此来衡量扰动父代特征的程度。对策略参数本身进行进化，下一代的变异范围（或改变的可变性）也随着正在优化的特征而进化。直观的，$\sigma$增加，种群个体对应变量的步长也随之增加，可以探索更大范围的空间；$\sigma$减小，则更集中于某一区域内的开发（搜索）。策略参数在生成子代时随机决定步长$△x_i$，大的$\sigma$意味着子代同父代的差异越大，尽管如此，一个大的$\sigma$同样可以产生一个小步长，例如，正态分布中95%的点会落在均值左右1.96个标准差的范围内。即$\sigma$决定生成子代的离散程度。一般采用自适应的策略参数来决定每一代的最佳搜索方向和最大步长。

单一策略参数

用 ${\chi }_i(t)=({\mathbf{x}}_i(t),{\sigma }_i(t))$ 代表第 t 代第 i 个个体，其中 ${\mathbf{x}}_i\in {\mathbb{R}}^{n_x}$ 代表个体性状（即决策变量的向量），${\sigma }_i\in {\mathbb{R}}_{+}^{n_x}$ 表示参数策略向量的偏差,通常，ES对性状的所有组份都采用一个偏差，即${\sigma }_{ij}={\sigma }_i,j=1,2,\cdots ,n_x,其中，{\sigma }_i\in {\mathbb{R}}_{+}$。而使用更多的策略参数可以为个体提供更多程度的自由度来适当的调整他们再所有维度上的变异分布。如偏差被用作唯一的策略参数，则最佳的搜索方向是沿着搜索空间所在的坐标系轴线确定的，但沿着坐标轴并非总是最佳搜索方向。

Hessian矩阵做策略参数

应当利用更多的搜索信息来加速向全局最优解的收敛，关于适应度函数的信息定义了搜索空间的相关性质，可用适应度函数的Hessian矩阵得到，若将Hessian矩阵用于策略参数，则变异形式变为：$x_i^{\prime }(t)=x_i+N(0,{\mathbf{H}}^{-1})，\mathbf{H}$是Hessian矩阵。但并非所有的适应度函数都有Hessian矩阵（Hessian矩阵需要保证有二阶导），而计算Hessian矩阵的代价也是昂贵的。

协方差矩阵做策略参数

同样可以利用个体策略参数偏差的协方差矩阵 ${\mathbf{C}}^{-1}$ 来为最佳分析和最大步长的决定提供辅助信息，即$x_i^{\prime }(t)=x_i+N(0,\mathbf{C})$，其中$N(0,\mathbf{C})$表示一个期望为0，概率密度为$f_G(\mathbf{r})=\frac{det\mathbf{C}}{(\sqrt{2\pi }{)}^{n_x}}{e}^{-\frac{1}{2}{\mathbf{r}}^T\mathbf{C}\mathbf{r}}$，其中， ${\mathbf{C}}^{-1}$ 的对角线元素为方差 ${\sigma }_j^2$，非对角线元素为突变步长的协方差。

协方差是通过旋转角度给出的，旋转角度描述了将一个不相关的变异向量转换为相关向量所需要的旋转。若 ${\omega }_i(t)$ 表示个体 $i$ 的向量旋转角度，则个体可以通过一个三元组表示：${\chi }_i(t)=({\mathbf{x}}_i(t),{\sigma }_i(t),{\omega }_i(t))$，其中${\mathbf{x}}_i\in {\mathbb{R}}^{n_x},{\sigma }_i\in {\mathbb{R}}_{+}^{n_x},{\omega }_i(t)\in {\mathbb{R}}^{n_x(n_x-1)/2}，且{\omega }_{ik}(t)\in (0,2\pi ]，k=1,2,\cdots ,n_x(n_x-1)/2$ 。用旋转角表示个体形状向量 ${\mathbf{x}}_i$ 中的 $n_x$ 个形状之间的协方差。协方差阵是对称阵，
因此可用一个向量（替代矩阵）来表示旋转角，可使用旋转角计算正交旋转矩阵$T({\omega }_i)$，即$T({\omega }_i)=\prod _{l=1}^{n_x-1}\prod _{j=i+1}^{n_x}{R}_{lj}({\omega }_i)$，这是$n_x(n_x-1)/2$个旋转矩阵的积，每个旋转矩阵 ${\mathbf{R}}_{lj}({\omega }_i)$ 是一个 $r_{ll}=cos({\omega }_{ik}),r_{lj}=-r_{jl}=-sin({\omega }_{ik}),fork=1,\cdots ,n_x(n_x-1)/2$的单位矩阵，其中$k=1\iff (i=1,j=2),k=2\iff (i=1,j=3)$。

策略参数的变异

以 $n_{\sigma }$表示使用的参数偏差的个数，$n_{\omega }$表示旋转角度的个数，则有以下几种情况：
（a） $n_{\sigma }=1,n_{\omega }=0$，即对所有表现型形状组份使用同一偏差，无旋转，其变异分布是一个圆，如下图所示。圆心位置表示父代 ${\mathbf{x}}_i$ 的位置，边界表示步长的偏差，其策略参数更新规则为：${\sigma }_i^{\prime }(t)={\sigma }_i(t)\cdot e^{\tau \cdot N(0,1)}$，其中 $\tau =\frac{1}{\sqrt{n_x}}$。这种单参数调整计算速度快，但当空间坐标有不同梯度时不够灵活。

（b） $n_{\sigma }=n_x,n_{\omega }=0$，这种情况下，每一组分都有自己的偏差参数，其偏差分布是一个椭圆，如下图所示。这种方法中，计算复杂度随参数的增加而线性增长，但增加的自由度提供了很好的灵活性，也可以利用沿着坐标轴的不同梯度。其策略参数更新如下：${\sigma }_{ij}^{\prime }(t)={\sigma }_{ij}(t)\cdot e^{{\tau }^{\prime }\cdot N(0,1)+\tau \cdot N_j(0,1)}$，其中 ${\tau }^{\prime }=\frac{1}{\sqrt{2n_x}},\tau =\frac{1}{\sqrt{2\sqrt{n_x}}}$。

（c）$n_{\sigma }=n_x,n_{\omega }=n_x(n_x-1)/2$，这种方法中，除了偏差，还使用了旋转角。其变异分布为一个对坐标轴进行旋转的椭圆变异分布，这种选择使得可以对搜索空间的轮廓进行一个更好的近似。偏差参数更新与（b）相同，旋转角更新规则如下：${\omega }_{ik}^{\prime }(t)={\omega }_{ik}(t)+\gamma \cdot N_j(0,1)mod2\pi ，\gamma \approx 0.0873$。附加旋转角提高了灵活性，但使得计算复杂度提升了 1/4。

（d）$1<n_{\sigma }<n_x$，这一方法允许使用不同程度的自由度，对于 $j>n_{\sigma }$的部分，偏差采用$n_{\sigma }$。

自适应策略参数

强化学习可用于策略参数的自调整，如：${\sigma }_{ij}^{\prime }(t)={\sigma }_{ij}(t)\cdot e^{{\Theta }_i(t)\cdot |{\tau }^{\prime }\cdot N(0,1)+\tau \cdot N_j(0,1)|}$，其中${\Theta }_i(t)$是过去 $n_{\Theta }$代中，个体 i 的时间报酬之和，即：${\Theta }_i(t)=\frac{1}{n_{\Theta }}\sum _{t^{\prime }=0}^{n_{\Theta }}{\theta }_i(t-t^{\prime })$。计算个体在每个时间步长上的汇报可使用以下方法：

（1） ${\theta }_{ij}(t)=\{\begin{array}{rlr}0.5& & if△f({\mathbf{x}}_i(t))>0\\ 0& & if△f({\mathbf{x}}_i(t))=0\\ -1& & if△f({\mathbf{x}}_i(t))<0\end{array}$， 其中$△f({\mathbf{x}}_i(t))=f({\mathbf{x}}_i(t))-f({\mathbf{x}}_i(t-1))$,该方法对适应度的恶化的惩罚是很严厉的。

（2） θ i j ( t ) = s i g n { f ( x i ( t ) ) − f ( x i ( t − △ t ) ) } = { 1 i f    f ( x i ( t ) ) − f ( x i ( t − △ t ) ) > 0 0 i f    f ( x i ( t ) ) − f ( x i ( t − △ t ) ) = 0 − 1 i f    f ( x i ( t ) ) − f ( x i ( t − △ t ) ) < 0 \theta_{ij}(t)=sign\{f(\mathbf x_i(t))-f(\mathbf x_i(t-\triangle t))\}=\left\{ \begin{aligned} 1 & & {if\,\,f(\mathbf x_i(t))-f(\mathbf x_i(t-\triangle t))>0}\\ 0 & & {if\,\,f(\mathbf x_i(t))-f(\mathbf x_i(t-\triangle t))=0}\\ -1 & & {if\,\,f(\mathbf x_i(t))-f(\mathbf x_i(t-\triangle t))<0}\\ \end{aligned} \right. θij​(t)=sign{f(xi​(t))−f(xi​(t−△t))}=⎩⎪⎨⎪⎧​10−1​​iff(xi​(t))−f(xi​(t−△t))>0iff(xi​(t))−f(xi​(t−△t))=0iff(xi​(t))−f(xi​(t−△t))<0​

（3）${\theta }_{ij}(t)=f({\mathbf{x}}_i(t))-f({\mathbf{x}}_i(t-△t))，0<△t<t$，这一方法是基于适应度函数对表现型形状的量化。当前代个体提升越大，酬赏越大；表现越差，惩罚越大；

（4） θ i j ( t ) = ∣ ∣ x i ( t ) − x i ( t − △ t ) ∣ ∣ s i g n { f ( x i ( t ) ) − f ( x i ( t − △ t ) ) } \theta_{ij}(t)=||\mathbf x_i(t)-\mathbf x_i(t-\triangle t)||sign\{f(\mathbf x_i(t))-f(\mathbf x_i(t-\triangle t))\} θij​(t)=∣∣xi​(t)−xi​(t−△t)∣∣sign{f(xi​(t))−f(xi​(t−△t))}，该方法的酬赏（惩罚）与表现型空间的步长成比例。

此外，还有其他方法，这里不一一列举。

交叉与重组

交叉

ES中，交叉对所有的变量值进行操作，记$(\mu /\rho ,+,\lambda )$为对父代的 $\rho$ 个个体进行交叉，通常使用以下两种方法中的一种：
（1）局部交叉（$\rho =2$ ）：从随机选择的两个父本中的变量重组生成新个体；
（2）全局交叉（$2<\rho <\mu$ ）：将整个种群的所有个体作为新个体组成成分的潜在来源。$\rho$越大，产生子代的多样性就越大，大的$\rho$值能够有效提高ES的探索能力。

重组

基于局部交叉和全局交叉，重组有以下两种方式：
离散重组：直接利用父代的某些参数值构建子代，即子代的某个参数值与某个父代的参数值相同。对于表现型或策略参数向量的每个组份，都是从父代中随机选择的。该方式记为$(\mu /{\rho }_D,+,\lambda )$。

调和重组：该方法子代的形状参数是父代不同个体不同权重的性状参数之和，即子代的某个参数值是其父代两个对应参数值之间的某个点，即$x_i^{new}=x_{A,i}+C\cdot (x_{B,i}-x_{A,i})$，其中A和B代表两个父本，i是是其第 i 个参数，C 是常数。该方式记为$(\mu /{\rho }_I,+,\lambda )$。

实际上，对策略参数采用离散重组的局部形式和调和重组的局部形式往往可以获得最佳结果。ES中，主要有五种主要的重组方式：
（1）无重组：若父代为 ${\chi }_i(t)$，则子代与父代相同，即${\tilde{\chi }}_l(t)={\chi }_i(t)$；

（2）局部离散重组（两个父代）：${\tilde{\chi }}_l(t)=\{\begin{array}{rlr}{\chi }_{i_{1}j}(t),& & if{U}_j(0,1)\le 0.5\\ {\chi }_{i_{2}j}(t)& & otherwise\end{array}$，

子代${\tilde{\chi }}_l(t)=(\widetilde{{\mathbf{x}}_l}(t),\widetilde{{\sigma }_l}(t),\widetilde{{\omega }_l}(t))$ 从所有父代 {${\chi }_{i_1}(t)=({\mathbf{x}}_{i_1}(t),{\sigma }_{i_1}(t),{\omega }_{i_1}(t)),{\chi }_{i_2}(t)=({\mathbf{x}}_{i_2}(t),{\sigma }_{i_2}(t),{\omega }_{i_2}(t))$} 中继承；

（3）局部调和重组（两个父代）：

${\tilde{x}}_{lj}=r\cdot x_{i_{1}j}(t)+(1-r)\cdot x_{i_{2}j}(t),\forall j=1,\cdots ,n_x;$

${\tilde{\sigma }}_{lj}=r\cdot {\sigma }_{i_{1}j}(t)+(1-r)\cdot {\sigma }_{i_{2}j}(t),\forall j=1,\cdots ,n_x;$

${\tilde{\omega }}_{lk}=[r\cdot {\omega }_{i_{1}k}(t)+(1-r)\cdot {\omega }_{i_{2}k}(t)]mod2\pi ,\forall k=1,\cdots ,n_x(n_x-1);$

（4）全局离散重组（多个父代）：${\tilde{\chi }}_{lj}(t)=\{\begin{array}{rlr}{\chi }_{i_{1}j}(t),& & if{U}_j(0,1)\le 0.5\\ {\chi }_{r_{j}j}(t)& & otherwise\end{array}$，其中 $r_j\sim {\Omega }_l$，${\Omega }_l$是所选的用具交叉的 $\rho$ 个父本的集合索引。

（5）全局调和重组（多个父代）：
可选方法有：a.所有父代的平均值产生子代${\tilde{\chi }}_l(t)=(\frac{1}{\rho }\sum _{i=1}^{\rho }{\mathbf{x}}_i(t),\frac{1}{\rho }\sum _{i=1}^{\rho }{\sigma }_i(t),\frac{1}{\rho }\sum _{i=1}^{\rho }{\omega }_i(t))$；

b.最优个和其他个体的组合：${\tilde{x}}_l(t)=r\tilde{\mathbf{y}}(t)+(1-r)\frac{1}{\rho }\sum _{i\in {\Omega }_l}^{\rho }{\mathbf{x}}_i(t)$，其中$\tilde{\mathbf{y}}(t)$是当前代的最优个体。这一策略确保了子代分布在最优个体周边。

选择

自然界中，个体能否生存并非依赖于个体适应度值的排序，而是环境和个体的遭遇；因此，其适应度值的测定是有一定误差的，而有可能的提升也可能丢失。这表明，选择是依赖于概率的，因此，不能将很多最好的个体传给下一代。从模拟退火算法可知，有时一步倒退在长远来看是很有意义的，即自然进化产生了次优个体，因为最终的提升很可能是通过不那么明显的途径进行的。

ES同其他进化计算方法的不同之处也在于选择，ES中产生的后代通常很多，在此基础上进行选择。大多是使用的是$(\mu ,\lambda )$方法或$({\mu }^{+},\lambda )$方法。有关选择方法，可以参考遗传算法GA中的描述。$({\mu }^{+},\lambda )$方法可被扩展为$(\mu ,\kappa ,\lambda )$，其中 $\kappa$ 指个体的最大寿命（可以存活几代），一旦个体超过了寿命，则不能被选择到下一代。$(\mu ,\lambda )$等价于$(\mu ,1,\lambda )$。

变异

由交叉重组产生子代${\tilde{\chi }}_l(t)$，进行变异成为${\tilde{\chi }}_l^{\prime }(t)$，其表示如下:${\mathbf{x}}_l^{\prime }(t)={\tilde{x}}_l(t)+△{\mathbf{x}}_l(t)$。 $n_{\sigma }$表示使用的参数偏差的个数，突变有以下几种：

（1）只考虑策略参数偏差的变异，则每个后代的变异如下：
$△x_{lj}(t)=\{\begin{array}{rlr}{\sigma }_l(t)\cdot N_j(0,1),\forall j=1,\cdots ,n_x.& & if{n}_{\sigma }=1\\ {\sigma }_{lj}(t)\cdot N_j(0,1),\forall j=1,\cdots ,n_x.& & if{n}_{\sigma }=n_x\\ \{\begin{array}{rlr}{\sigma }_{lj}(t)\cdot N_j(0,1),\forall j=1,\cdots ,n_{\sigma }.& & \\ {\sigma }_{l{n}_{\sigma }}(t)\cdot N_j(0,1),\forall j=n_{\sigma }+1,\cdots ,n_x.& & \end{array}& & if1<n_{\sigma }<n_x\end{array}$

（2）考虑偏差和旋转角，则 $△{\mathbf{x}}_l(t)=\mathbf{T}(\widetilde{{\omega }_l}(t))\mathbf{S}(\widetilde{{\sigma }_l}(t))\mathbf{N}(0,1)$；

其中，$T(\widetilde{{\omega }_l}(t))=\prod _{a=1}^{n_x-1}\prod _{b=a+1}^{n_x}{\mathbf{R}}_{ab}({\tilde{\omega }}_l(t))$是正交旋转矩阵，是$n_x(n_x-1)/2$个旋转矩阵的积；

每个旋转矩阵 ${\mathbf{R}}_{ab}({\omega }_i)$ 是一个 $r_{aa}=cos({\omega }_{lk}),r_{ab}=-r_{ba}=-sin({\omega }_{lk}),fork=1,\cdots ,n_x(n_x-1)/2$的单位矩阵，其中$k=1\iff (i=1,j=2),k=2\iff (i=1,j=3)$;

而$\mathbf{S}(\widetilde{{\sigma }_l}(t))=diag({\tilde{\sigma }}_{l1}(t),{\tilde{\sigma }}_{l2}(t),\cdots ,{\tilde{\sigma }}_{l{n}_x}(t))$是代表偏差的对角阵。

（3）定向突变（Directed Mutation），其表现在优先给予特定的坐标方向。定向变异的结果是一个对称变异概率分布，如下图所示，$x_2$方向的步骤大于$x_1$的步长，是偏好方向，每个表现型组份是独立变异的，因此使用一个一维的对称概率密度函数就可以进行表达，其形式可以为：$f_D(x)=\{\begin{array}{rlr}\frac{2}{\sqrt{\pi \sigma }(1+\sqrt{1+c})}\cdot e^{-\frac{x^2}{\sigma }}& & ifx<0\\ \frac{2}{\sqrt{\pi \sigma }(1+\sqrt{1+c})}\cdot e^{-\frac{x^2}{\sigma (1+c)}}& & ifx\ge 0\end{array}$，其中，$c>0$是一个正向值。

直接变异方法虽然只使用策略参数的偏差，但对每一个${\sigma }_j$都有相应的方向值$c_j$，对给定的$2n_x$个策略参数，$c和\sigma$都是自适应的。因此，他的计算相较于$n_x(n_x-1)/2$个旋转向量的运算是更有效的，同时也提供了比只使用偏差更多的倾向于搜索方向的信息。若$D(c,\sigma )$代表对称分布，那么则有$△x_{ij}(t)=D_j(c_{ij}(t),{\sigma }_{ij}(t))$。