介绍

前面学习了遗传算法，最近又看到在强化学习中的应用：进化算法玩Atari，今天看一下可以用在神经网络中的进化策略（Evolution Strategy,ES）。

ES和GA的思想类似，模仿生物进化原理，也存在了十几年，但具体算法实现有所差别。

思想
进化策略是一种模仿生物进化的一种求解参数优化问题的方法，它使用实数值作为基因，并且假设基因总是服从零均值、某一方差的高斯分布的变化产生新的个体，然后保留较好的个体。
ES可以对实数参数进行优化，给现在的神经网络的训练带来另一个工具。
和GA的不同

  1. ES先产生子代，后评估选取子代；GA先评估选取父母，后产生子代；
  2. ES参数为实数；GA通常为二进制；
  3. ES通过正态分布变异；GA通过二进制取反变异。
  4. ES应用于数值优化；GA应用于参数优化。
  5. ES选择方式确定；GA使用概率进行选择。

算法

确定优化函数f(x)f(x)、算法参数
初始化种群
循环：

进化（交叉变异）
评估排序，选择前p个产生下一种群
直到收敛

论文[3]给出的ES算法流程：
流程

关键步骤

初始化：确定可能存在的参数边界；产生初代种群（通常是服从均匀分布的）；确定变异程度。
交叉：存在离散重组、中值重组、混杂重组三种方式。离散类似与GA的交换参数；中值即取选定父代的参数均值；混杂为选定一个父代，逐参数地随机选定另一个父代进行组合。
变异：在分量上加一个零均值、某一方差的高斯变量。
变异：和GA固定的变异程度不同，ES的变异程序有从大到小的过程。
选择：ES有父代和子代比较的过程，根据选择方式不同，ES可以分为(μ+λ)−ES(\mu+\lambda)-ES和(μ，λ)−ES(\mu，\lambda)-ES。主要使用后者，即初始有μ\mu个个体，每次迭代产生λ\lambda个个体，然后选择μ\mu个作为下一代。

例子

这里试着直接使用ES优化一个两层的网络解决异或问题。
上面的例子实验失败了，基本的ES对于局部最优的情况还需要进一步处理。例子还是经典的袋鼠跳函数：f(x)=xsin(10πx)+2。代码如下：

import numpy as np
_mu = 10
_lambda = 10
_epochs = 20
DNA_SIZE = 1
DATA_BOUND = [-1,2]
p = np.random.rand(_mu,2,DNA_SIZE)
p = p.clip(*DATA_BOUND)
history = []

def F(x):
    return x[:,0,:]*np.sin(10*np.pi*x[:,0,:])+2.0
    
    
def generate(p):
    
    kids = np.zeros((_lambda,2,DNA_SIZE))
    for i in range(_lambda):
        p1_index,p2_index = np.random.choice(range(_mu),2)
        p1 = p[p1_index,::]
        p2 = p[p2_index,::]
        #类似GA的离散交叉
        cp = np.random.randint(0,2,(2,DNA_SIZE),dtype=np.bool)
        kids[i,cp] = p1[cp]
        kids[i,~cp] = p2[~cp]
        #变异
        kids[i,1,:] = np.maximum(kids[i,1,:] + (np.random.rand(*kids[i,1,:].shape)-0.5), 0.)
        kids[i,0,:] += kids[i,1,:] * np.random.randn(*kids[i,0,:].shape)
        kids = kids.clip(*DATA_BOUND)
    p_kids = np.concatenate((kids,p))
    
    return p_kids
    
def select(p,mu):
    
    f = F(p)
    index = f.argsort(axis=0).flatten()
    index = index[::-1]
    p = p[index]
    
    return p[:mu,::]
#主循环
for i in range(_epochs):
    p_kids = generate(p)
    p = select(p_kids,_mu)
    history.append(F(p)[0])
    print("epoch{0}: max f(x) value:{1} \r".format(i,history[i]),end='')
a = np.linspace(-1,2,num=300)
print(np.max(a*np.sin(10*np.pi*a)+2.0))

然后ES得到的最大值为3.8501，直接计算得到3.8492，还是比较接近的。

应用

最近ES的应用就是在强化学习方面，openAI做了很多相关的工作；另外还提到了一种CMA-ES（Covariance-Matrix Adaptation Evolution Strategy）的方法，将协方差矩阵的信息使用在优化过程中，可以达到更快的收敛速度，在这里有介绍和图片演示，另外也有传统ES和GA的比较和演示。

参考
进化算法玩Atari "进化算法玩Atari"
[1] https://blog.csdn.net/u014248127/article/details/79143437
[2] https://www.jiqizhixin.com/articles/2017-03-26-3
[3] https://arxiv.org/pdf/1703.03864v2.pdf