切换视频源:

(1+1)-ES

作者: 莫烦 编辑: 莫烦 2017-08-28

学习资料:

要点

如果你想对进化策略有一个快速了解, 这个几分钟的短动画是个很好的方式.

(1+1)-ES 是 ES 进化策略的一种形式, 也是众多形式中比较方便有效的一种. 接下来我们来细说他们的类别. 如果要我用一句话来概括 (1+1)-ES: 一个爸爸和一个孩子的战争

本节要实践的内容提前看:

3-2-0.gif

ES的不同形式

像上面看到的, 统一来说都是 (μ/ρ +, λ)-ES, (1+1)-ES 只是一种特殊形式. 这里的 μ 是 population 的数量, ρ 是从 population 中选取的个数, 用来生成宝宝的. λ 是生成的宝宝数, 如果采用的是 + 形式的, 就是使用将 ρ + λ 混合起来进行适者生存, 如果是 , 形式, 那么就是只使用 λ 进行适者生存.

形式多种多样有些头疼. 不过在这一节中, 我们考虑的只是一个爸爸, 生成一个宝宝, 然后在爸爸和宝宝中进行适者生存的游戏, 选择爸爸和宝宝中比较好的那个当做下一代的爸爸. (1+1)-ES 总结如下:

  • 有一个爸爸;
  • 根据爸爸变异出一个宝宝;
  • 在爸爸和宝宝中选好的那个变成下一代爸爸.

进化啦

上节一样, 这次我们还是两个功能, make_kidkill_bad

def make_kid(parent):
    # 根据 parent 正态分布生一个 kid

def kill_bad(parent, kid):
    # 杀了坏孩子或者坏爸爸

所以所有的操作都只有一个数量的 pop. 这时我们在 (1+1)-ES 中的策略是 parent DNA 中只有存平均值, 没有变异强度 (标准差). 这次的变异强度 MUT_STRENGTH 是一个 global variable. 一个标量表示它就好.

def make_kid(parent):
    k = parent + MUT_STRENGTH * np.random.randn(DNA_SIZE)
    return k

kill_bad 中, 我们选择更为适合的, 不管是爸爸还是孩子, 只要是适合的就留下, 不适合的杀掉. 但是还有注意的一点是, 在这一步我们还要对 MUT_STRENGTH 进行一点改变. 改变的方法遵循了 1/5 successful rule. 这个方法是 ES 的开山鼻祖提出来的. 文献在这:

Rechenberg, I. 1973. Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution, Frommann-Holzboog.

网上有个课件Tutorial: CMA-ES — Evolution Strategies and Covariance Matrix Adaptation里面一张图, 让你秒懂这个1/5的意思.

3-2-1.png

图中的意思是, 还没到收敛的时候(上面左图), 我们增大 MUT_STRENGTH, 如果已经快到收敛了(上右图), 我们就减小 MUT_STRENGTH. 那如何判断是否快到收敛没呢, 就是如果有1/5的变异比原始的 parent 好的话, 就是快收敛了(像上右图). 在上左图中, 有一半比原始 parent 好, 一半比较差, 所以还没到收敛. 在上面提到的课件中, 用一个公式就能概括这种1/5关系.

3-2-2.png

最后仿照上面的课件, 我写下了下面的 kill_bad 功能.

def kill_bad(parent, kid):
    global MUT_STRENGTH
    fp = get_fitness(F(parent))[0]
    fk = get_fitness(F(kid))[0]
    p_target = 1/5
    if fp < fk:     # kid better than parent
        parent = kid
        ps = 1.     # kid win -> ps = 1 (successful offspring)
    else:
        ps = 0.
    # adjust global mutation strength
    MUT_STRENGTH *= np.exp(1/np.sqrt(DNA_SIZE+1) * (ps - p_target)/(1 - p_target))
    return parent

加上训练的主循环, 就大事告成.

parent = 5 * np.random.rand(DNA_SIZE)   # parent DNA

for _ in range(N_GENERATIONS):
    kid = make_kid(parent)               # 生宝宝
    parent = kill_bad(parent, kid)       # 杀宝宝

下次我们来看看一种加入了梯度下降原则的 ES 算法 Natural Evolution Strategy.

降低知识传递的门槛

莫烦很常从互联网上学习知识,开源分享的人是我学习的榜样。 他们的行为也改变了我对教育的态度: 降低知识传递的门槛免费 奉献我的所学正是受这种态度的影响。 通过 【赞助莫烦】 能让我感到认同,我也更有理由坚持下去。

想当算法工程师拿高薪?转行AI无门道?莫烦也想祝你一臂之力,市面上机构繁杂, 经过莫烦的筛选,七月在线脱颖而出, 莫烦和他们合作,独家提供大额 【培训优惠券】, 让你更有机会接触丰富的教学资源、培训辅导体验, 祝你找/换工作/学习顺利~


    进化算法 (Evolutionary-Algorithm)