进化策略
学习资料:
要点¶
如果你想对进化策略有一个快速了解, 这个几分钟的短动画是个很好的方式.
进化策略 (Evolution Strategy) 后面都简称 ES. 它和 遗传算法 GA 是好兄弟. 步骤和流程都非常相似. 如果你对遗传算法也感兴趣, 前面几节内容都是有关于遗传算法的. 要我用一句话概括ES: 在程序里生宝宝, 杀死不乖的宝宝, 让乖宝宝继续生宝宝. 乍一听, 怎么和 GA 是完全一样的逻辑呢? 没关系, 我们在接下来的内容中揭晓他们的不同.
本节要实践的内容提前看:
和遗传算法的异同¶
遗传算法 (后面简称 GA) 和 ES 真 TM 差不多. 导致很多朋友学习的时候, 都傻傻分不清. 不过我具体的列出来, 方便看清楚.
- 选好父母进行繁殖 (
GA); 先繁殖, 选好的孩子 (ES) - 通常用二进制编码 DNA (
GA); 通常 DNA 就是实数, 比如 1.221 (ES) - 通过随机让 1 变成 0 这样变异 DNA (
GA); 通过正态分布(Normal distribution)变异 DNA (ES)
具体来说, 传统的 GA 的 DNA 形式是这样:
DNA=11010010
而传统的 ES DNA 形式分两种, 它有两条 DNA. 一个 DNA 是控制数值的, 第二个 DNA 是控制这个数值的变异强度. 比如一个问题有4个变量. 那一个 DNA 中就有4个位置存放这4个变量的值 (这就是我们要得到的答案值). 第二个 DNA 中就存放4个变量的变动幅度值.
DNA1=1.23, -0.13, 2.35, 112.5 可以理解为4个正态分布的4个平均值.
DNA2=0.1, 2.44, 5.112, 2.144 可以理解为4个正态分布的4个标准差.
所以这两条 DNA 都需要被 crossover 和 mutate.
进化啦¶
写基础的 ES 算法其实很简单. 我总结起来, 其实就两个功能, make_kid 和 kill_bad
对于今天的问题, 我们就是要找这张图中的最高点.
而这个点只有一个, 所以我们的 DNA 的长度就只有一个. 我们用一个 python 字典来存这两种 DNA 的信息. 这里 DNA 存的是均值, mut_strength 存的是标准差.
训练的主循环, (生死循环... 觉得血腥味很重..为什么我的遗传算法教程就没这么重血腥味呢..) 如下:
首先的 make_kid 功能. 我们随机找到一对父母, 然后将父母的 DNA 和 mut_strength 基因都 crossover 给 kid. 然后再根据 mut_strength mutate 一下 kid 的 DNA. 也就是用正态分布抽一个 DNA sample. 而且 mut_strength 也能变异. 将变异强度变异以后, 他就能在快收敛的时候很自觉的逐渐减小变异强度, 方便收敛.
接下来到了惊心动魄的杀人时间. 根据适应度 fitness 选择适应度最靠前的一些人, 抛弃掉那些适应度不佳的人. 这个很简单.
这样我们就完成了最一般的 ES 算法的主体. 还有一些零散的, 可视化的代码都可以在我的 github 中找到. 这里就不细说了.
下次我们会总结基础的 ES 算法类型. 并且看看一种比较流行的 ES 算法.
