遗传算法
切换视频源:

遗传算法

作者: 莫烦 编辑: 莫烦 发布于: 2017-08-12

学习资料:

要点

如果对遗传算法有兴趣的朋友, 强烈推荐先看看我制作的动画短片 什么是遗传算法, 在动画里有了基础的了解, 在接下来的内容中, 你就如鱼得水啦. 如果让我用一句话概括遗传算法: 在程序里生宝宝, 杀死不乖的宝宝, 让乖宝宝继续生宝宝.

在这一节中, 我们的 乖宝宝 就是图中更高的点, 用遗传算法, 我们就能轻松找到 最乖的宝宝.

2-1-0.gif

找一个好的fitness方程

所有的遗传算法 (Genetic Algorithm), 后面都简称 GA, 我们都需要一个评估好坏的方程, 这个方程通常被称为 fitness. 在今天的问题中, 我们找到下面这个曲线当中的最高点. 那么这个 fitness 方程就很好定, 越高的点, fitness 越高.

2-1-1.png

如果这个曲线上任一点的 y 值是 pred 的话, 我们的 fitness 就是下面这样:

DNA 编码

在 GA 中有基因, 为了方便, 我们直接就称为 DNA 吧. GA 中第二重要的就是这 DNA 了, 如何编码和解码 DNA, 就是你使用 GA 首先要想到的问题. 传统的 GA 中, DNA 我们能用一串二进制来表示, 比如:

为什么会要用二进制编码, 我们之后在下面的内容中详细说明这样编码的好处. 但是长成这样的 DNA 并不好使用. 如果要将它解码, 我们可以将二进制转换成十进制, 比如二进制的 11 就是十进制的 3. 这种转换的步骤在程序中很好执行. 但是有时候我们会需要精确到小数, 其实也很简单, 只要再将十进制的数浓缩一下就好. 比如我有 1111 这么长的 DNA, 我们产生的十进制数范围是 [0, 15], 而我需要的范围是 [-1, 1], 我们就将 [0, 15] 缩放到 [-1, 1] 这个范围就好.

注意, 这里的 pop 是一个储存二进制 DNA 的矩阵, 他的 shape 是这样 (popsize, DNAsize).

进化啦

进化分三步:

  • 适者生存 (selection)
  • DNA 交叉配对 (crossover)
  • DNA 变异 (mutation)

我们用 python 的三个功能, 一个循环表示:

适者生存的 select() 很简单, 我们只要按照适应程度 fitness 来选 pop 中的 parent 就好. fitness 越大, 越有可能被选到.

接下来进行交叉配对. 方式很简单. 比如这两个 DNA, Y 的点我们取 DNA1 中的元素, N 的点取 DNA2 中的. 生成的 DNA3 就有来自父母的基因了.

而 python 写出来也很方便, 从 pop_copy 中随便选一个当另一个父辈 和 parent 进行随机的 crossover:

mutation 就更好写了, 将某些 DNA 中的 0 变成 1, 1 变成 0.

有了这些规则, select, crossover, mutate, 我们就能在程序里上演进化论啦. 赶紧运行一下我在github的这套全部代码.

接下来几节内容, 我们就来看看在不同的情况中如何根据不同的标准选择 fitness 和 DNA 编码.


降低知识传递的门槛

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

我组建了微信群,欢迎大家加入,交流经验,提出问题,互相帮持。 扫码后,请一定备注"莫烦",否则我不会同意你的入群申请。

wechat

    进化算法 (Evolutionary-Algorithm)