CEM

先介绍几个概念

进化算法，英文为Evolutionary Algorithm。

遗传算法，英文为genetic algorithm (GA) ,是进化算法的一种。

进化策略,英文为Evolution Strategy(ES),是一种黑盒优化算法，也属于进化算法的一种。

另外两种进化算法分别是遗传编程（Genetic Programming）和演化编程(Evolution Programming)。

进化策略感觉和遗传算法的区别是遗传算法使用二进制进行编码，进化策略使用实数进行编码，假设数据属于某种分布，然后通过该分布的一些参数来控制如何进化。

《Evolution Strategies as a Scalable Alternative to Reinforcement Learning》这篇论文看起来是将进化策略应用于强化学习的一篇很重要的论文。

自然演化策略(Natural Evolution Strategy,NES) 引入了“natural gradient”，使得搜索方向朝着“high fitness”的方向前进。

CEM 也是一种进化策略算法

CEM 伪代码:

 # Step1: initialization
初始化采样概率分布参数：mu, sigma；
初始化当前迭代次数t=0，设置最大迭代次数max_its，样本个数N，精英样本个数Ne，以及采样方差的误差范围epsilon；
for t in range(0, max_its):
  # Step2: 使用高斯分布进行随机采样
  X = SampleGaussian(mu, sigma, N)
  # Step3: 评估样本
  S = EvaluateSamples(X)
  # Step4: 重要性采样
  X = sort(X, S)
  mu = mean(X[0:Ne-1])
  sigma = var(X[0:Ne-1])
  if sigma > epsilon:
    break
# Step5: 返回精英样本的均值
return mu

遗传算法参考代码:https://github.com/zhangtianle/Genetic-Algorithms

NES参考代码:https://gist.github.com/karpathy/77fbb6a8dac5395f1b73e7a89300318d

参考:

遗传算法

进化算法

https://tianle.me/2017/04/19/GA/

https://zhuanlan.zhihu.com/p/28622201

https://zhuanlan.zhihu.com/p/31028329

https://www.jiqizhixin.com/articles/2017-11-11

https://www.echenshe.com/class/ea/

https://blog.otoro.net/2017/10/29/visual-evolution-strategies/

https://people.idsia.ch//~tom/nes.html

https://segmentfault.com/a/1190000021499631

http://web.mit.edu/6.454/www/www_fall_2003/gew/CEtutorial.pdf

https://gist.github.com/kashif/5dfa12d80402c559e060d567ea352c06

Evolution Strategies as a Scalable Alternative to Reinforcement Learning

https://www.zhihu.com/question/21923317