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

李林 编译自 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):

    if (len(test_word) != len(password)):
        print("taille incompatible")
        return
    else:
        score = 0
        i = 0
        while (i < len(password)):
            if (password[i] == test_word[i]):
                score+=1
            i+=1
        return score * 100 / len(password)

创建个体

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

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

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

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

创建第一个种群

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

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

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

import random

def generateAWord (length):
    i = 0
    result = ""
    while i < length:
        letter = chr(97 + int(26 * random.random()))
        result += letter
        i +=1
    return result

def generateFirstPopulation(sizePopulation, password):
    population = []
    i = 0
    while i < sizePopulation:
        population.append(generateAWord(len(password)))
        i+=1
    return population

下一代

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

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

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

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

import operator
import random

def computePerfPopulation(population, password):
    populationPerf = {}
    for individual in population:
        populationPerf[individual] = fitness(password, individual)
    return sorted(populationPerf.items(), key = operator.itemgetter(1), reverse=True)

def selectFromPopulation(populationSorted, best_sample, lucky_few):
    nextGeneration = []
    for i in range(best_sample):
        nextGeneration.append(populationSorted[i][0])
    for i in range(lucky_few):
        nextGeneration.append(random.choice(populationSorted)[0])
    random.shuffle(nextGeneration)
    return nextGeneration

下一步，育种。

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

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

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

import random

def createChild(individual1, individual2):
    child = ""
    for i in range(len(individual1)):
        if (int(100 * random.random()) < 50):
            child += individual1[i]
        else:
            child += individual2[i]
    return child

def createChildren(breeders, number_of_child):
    nextPopulation = []
    for i in range(len(breeders)/2):
        for j in range(number_of_child):
            nextPopulation.append(createChild(breeders[i], breeders[len(breeders) -1 -i]))
    return nextPopulation

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

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

以下是控制变异的代码：

import random

def mutateWord(word):
    index_modification = int(random.random() * len(word))
    if (index_modification == 0):
        word = chr(97 + int(26 * random.random())) + word[1:]
    else:
        word = word[:index_modification] + chr(97 + int(26 * random.random())) + word[index_modification+1:]
    return word

def mutatePopulation(population, chance_of_mutation):
    for i in range(len(population)):
        if random.random() * 100 < chance_of_mutation:
            population[i] = mutateWord(population[i])
    return population

关于如何选择变异率，可以参考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