教程 | 利用达尔文的理论学习遗传算法

摘要: 本文借助生物学中达尔文的进化理论来介绍遗传算法,并展示了通过简短的 Python 教程实现遗传算法的案例。

10-12 13:18 首页 机器之心

选自sicara

机器之心编译

参与:黄小天、路雪


本文借助生物学中达尔文的进化理论来介绍遗传算法,并展示了通过简短的 Python 教程实现遗传算法的案例。


在本文中,我将会解释遗传算法的概念。首先,我会介绍它的起源与目标。接着,我会展示如何通过一个简短的 Python 教程实现它。


所以,问题就是:我们如何打造好的人工智能?


一个天真的解决方案就是创建由一系列规则构成的「经验算法」:「如果你遇到这些条件,就这么执行。」我可以想象到通过这样的足够多的规则,就能再现自然智能。但工作量会异常大,最终方案将永远无法使创建者满意。花大把时间创造一样东西却得知它不可能完美,还是挺让人沮丧的吧?


为了避免这一点,我有了一个新想法。如果我舍弃直接的方案而选择再现进化会怎么样。我们可以创造第一条史前鱼,将其放入适合进化的条件内,让它自由地向人类进化。这个想法被称为「遗传算法」,我们将在下文中亲自创建一个。那么,首先让我们回忆一下,试着理解达尔文的自然选择理论。


这个理论很简单:如果一个种群想要兴盛,它必须不断提升自己,这被称为适者生存。种群中最优秀的品质遗传给后代。但是为了保持一些多样性以及适应自然环境的变化,其他个体也不能被遗忘。



从一代到下一代


这一算法尤其擅长解决优化问题。


实例:背包问题


背包优化是一个经典的算法问题。你有两样东西:一个容量为固定重量的背包和一系列不同重量和价值的盒子。目标是装满这个背包使其价值最大化却又不超出它的最大承载重量。自 1972 年以来,这一直是一个著名的数学问题。遗传算法可以很好地解决这一问题,因为它本质上是一个具有大量可能答案的优化问题。



背包问题


为了亲自测试这一算法的工作原理,我们用它解决一个简单的问题:如何破解同事的密码。


该算法用 Python 3 实现。你可以下载 Windows 版或者使用 brew install python3 、sudo apt-get install python3 或 sudo yum install python3 进行安装。我建议你在 Jupyter notebook 中运行这一代码。


选择一个适应度函数


当你决定创建一个遗传算法时,要做的第一件事情就是创建评估函数,用来评估样本的成功:它允许我们把种群划分为丑小鸭和白天鹅。区分的目标在于成功的样本稍后将有更多机会被挑选来塑造下一代。这看起来很简单,但是不要被愚弄了。


我们的目标是什么?破解密码。因此我们函数的目标是把连续标记中的二值结果「失败或成功」从 0 转换到 100。


这里有一个最简单的方案:


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


如此,一个带有更大适合度结果的个体将比其他样本更接近成功。因此我们的适合度函数能够精确分类种群。


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。


在我们的情况中,个体是单词(密码的长度当然是相同的),每个字母是一个基因,字母的值是等位基因。在单词「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


从一代到下一代


为此,我们有两件事要做:选择我们当前代中的一个特定部分,并且整合育种者孕育下一代。


育种者选择


我们有很多选择,但是你必须牢记两点:目标是选择前一代的最佳方案并且不把其他方案彻底放在一边。危害是:如果你在算法开始时只选择好的方案,你将很快向局部最小值而不是可能的最佳方案收敛。


我的方案是一方面选择更好的样本 N(在我的代码中,N = best_sample),另一方面选择无需区分适合度的 M 个随机个体(M = lucky_few)。


import operatorimport 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」并不会只生一个孩子,为了确保种群数量稳定,你必须确定每对父母所生孩子的数量(0 代中的个体数量等于下一代中的个体数量)。


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


现在,你有了构建遗传算法的所有工具。请随意修改我的实现。每一步都有很多种可能的方案,请采取最合适的那个。


原文链接:https://blog.sicara.com/getting-started-genetic-algorithms-python-tutorial-81ffa1dd72f9



本文为机器之心编译,转载请联系本公众号获得授权

?------------------------------------------------

加入机器之心(全职记者/实习生):hr@jiqizhixin.com

投稿或寻求报道:content@jiqizhixin.com

广告&商务合作:bd@jiqizhixin.com


首页 - 机器之心 的更多文章: