基于达尔文进化论的遗传算法，还能破解你同事的密码｜附代码

李林 编译自 SICARA blog

量子位 出品 | 公众号 QbitAI

量子位今天编译整理的这篇文章，全面地介绍了遗传算法（genetic algorithm），从它的起源和目标，到如何用python实现它。

本文作者是Louis Nicolle，发在法国大数据创业公司SICARA的博客上。

我们先来思考一个问题：

如何创造一个好的人工智能？

最朴素的方法，是创造一个“经验主义的算法”，由一堆规则构成，比如说“如果遇到西瓜，买一个”。有了足够多的规则，我们就能复制自然智能。

但是，这样做工作量巨大，而最终造出的智能也不可能超过它的创作者。花了好多时间，造的东西又不理想，是不是很伤心？

于是出现了一种新方法：我们不要写规则了，干脆重现一下进化过程，先造出一条史前鱼类，放在合适的环境中让它进化，等着它变成人，甚至更高级的生命。这种方法叫做“遗传算法”。

首先，让我们刷新自己的记忆，试着理解一下达尔文提出的自然选择。

这个理论很简单：物种想要生生不息，就得持续自我提升，适者才能生存。种群中最优秀的特质应该传递给后代，而其他个体也不能被遗忘，这样才能维持一定的多样性，自然环境发生变化时才更容易适应。

这是遗传算法的理论基础。

优化问题

遗传算法在优化问题上特别管用。

我们来举个例子：背包问题。

这个著名的数学问题是理查德·卡普在1972年提出的。问题是这样的：

你有两样东西，一个设定了承重能力的背包、一些重量和价值各不相同的盒子，目标是把盒子装到背包里，在不超过重量限制的情况下，装进尽可能高的价值。

它是一个优化问题，有很多可能方案，因此非常适合用遗传算法来解决。

动手教程：用遗传算法破解密码

为了体验这个算法，我们用它来解决一个简单的问题：破解同事的密码。

选择适应度函数

创建遗传算法的时候，第一件事是建立一个评价函数，用来衡量样本的成功与否。

它能帮我们分清丑小鸭和白天鹅，区分开之后，我们才能给成功的样本更多“机会”，让它参与生成下一代。

这一步看起来很简单，其实……嘿嘿嘿……

我们的目标是什么来着？破解密码。因此，函数的目标应该是将“成功/失败”的二元结果从0（一直失败）转换成100（完美）。

最简单的方法是：

fitness score = (number of char correct) / (total number of char)

这样，fitness得分更高的样本，就比其他个体更接近成功，我们这个fitness函数就能精确地为算法种群分类。

def fitness (password, test_word):

创建个体

我们知道了该怎样评价这些个体，但如何定义它们呢？这部分很难，目标是要知道哪些特征要保持不变，哪些是可变的。

为了理清思路，我们来和基因比较一下。DNA是由基因组成的，而每个基因都来自不同的等位基因，也就是说，DNA中的每一个基因，都是从一组等位基因中选出的。你需要为算法种群创建DNA。

在我们这个案例中，个体是词，每个词和密码的长度差不多；每个字母是一个基因，这个字母的赋值是它的等位基因。比如说banana这个词，b是第一个字母的等位基因。

这种创造有什么意义？现在我们知道每个个体都是长度合格的词，但是我们的种群覆盖了这个长度下所有可能的词。

创建第一个种群

上面我们知道了个体的特征，以及如何评估它们，接下来，该开始严格意义上的“进化”了。

在创建第一个种群时，要时刻记住这一点：我们不能将种群指向一个明显很好的方案。我们需要让种群尽可能广、覆盖尽可能多的可能性，完美的第一代种群应该覆盖现存所有等位基因。

所以，我们就要创建由随机字母构成的单词。

import random

下一代

有了第一代，想创造下一代，我们需要做两件事：1）从现有的这一代中选择一部分；2）让它们结合在一起创造下一代。

首先，要从第一代中选择用来繁殖的“亲本”。

选择有很多方法，但是你必须牢记：我们的目标是从第一代中选择最好的方案，但不能将其他的都去掉。如果在算法开始创建时，就只选择了那些最好的方案，你会迅速收敛到局部最小值，没有机会找到最佳方案。

我的方法是一方面选择表现好的样本，就是下面代码中的best_sample；另一方面选择随机选择一组个体，也就是下面代码中的lucky_few。

import operator

下一步，育种。

我们依然和生物学来进行类比。有性生殖的目的是将两个个体的DNA结合起来，我们这里要做的事情也差不多。

我们有两个个体，Tom和Jerry，它们的DNA是由自己的等位基因（每个字母的赋值）决定的，为了将它们的DNA结合起来，我们需要将它们的字幕混合一下。在诸多方法中，我们选择最简单的一个：子代的每一个字母，都随机取自亲代的Tom或Jerry。

显然，Tom和Jerry这对亲本能生成不止一个后代，我们需要控制后代的数量，来保持种群规模的稳定。也就是说，第一代的个体数要和第二代的个体数相同。

import random

接下来，我们要谈一谈遗传带来的变化。

上一步的育种过程会导致个体的自然变异。育种之后，每个个体都必须有一定可能性会看到自己的DNA发生变异。这样做的目标是防止算法收敛到局部最小化。

以下是控制变异的代码：

import random

关于如何选择变异率，可以参考R.N.Greenwell、J.E.Angus、M.Finck 1995年的论文Optimal mutation probability for genetic algorithms。

地址：http://www.sciencedirect.com/science/article/pii/089571779500035Z

小结

上面，我们讲了遗传算法的理论基础和适用问题，还讲了如何创建自己的遗传算法。

上文涉及的所有Python 3代码都在GitHub上，地址：https://gist.github.com/NicolleLouis/d4f88d5bd566298d4279bcb69934f51d

教程原文地址：https://blog.sicara.com/was-darwin-a-great-computer-scientist-81ffa1dd72f9

如果你想进一步探索AI和遗传算法，可以看看以下资源：

1. 网页应用

BoxCar是这类算法的一个网页应用，这个算法的目标是创造最有效的两轮车辆。

地址：http://rednuht.org/genetic_cars_2/

2. 移动应用

在Evolution这个App里，你需要创建一个有关节、骨骼和肌肉的“生物”，然后算法会优化它的运动方式来完成特定任务，比如跳、跑、爬台阶等等。

地址：https://play.google.com/store/apps/details?id=com.keiwando.Evolution

3. DIY

最后再推荐一个编程游戏网站。每个月，这个网站都会举办为期一周的比赛，让参赛者创造最好的人工智能，获胜者用的几乎一直是遗传算法。

地址：https://www.codingame.com/home

— 完 —

诚挚招聘

量子位正在招募编辑/记者，工作地点在北京中关村。期待有才气、有热情的同学加入我们！相关细节，请在量子位公众号(QbitAI)对话界面，回复“招聘”两个字。

量子位 QbitAI

վ’ᴗ’ ի 追踪AI技术和产品新动态