人工智能算法：遗传算法

遗传算法是一种特殊的演化算法，但是在描述遗传算法的文献中，其定义各不相同。本书将遗传算法定义为一种可以用交叉和突变算子优化固定长度向量的演化算法。计分函数可以区分优劣方案，以优化该固定长度的向量。这个定义说明了遗传算法的本质。

此外，可以将可选特征添加到遗传算法中，以增强其性能。例如物种形成、精英和其他选择方法之类的技术，有时可以改善遗传算法的运行效果。

3.1　离散问题的遗传算法

与其他算法相似，针对连续学习和离散学习，遗传算法采用略有不同的方法。连续学习涉及计算数值，而离散学习涉及识别非数值。本节将展示如何将离散学习和连续学习应用于以下两个经典的AI问题：

旅行商问题；
鸢尾花物种建模。
对于旅行商问题，我们将展示如何将遗传算法应用于离散学习的组合问题，目标是找到最佳的城市序列。同时，我们将拟合RBF神经网络的权重以识别鸢尾花种类，这将作为连续问题的遗传算法示例，即对数字权重进行调整。

3.1.1　旅行商问题

旅行商问题（Traveling Salesman Problem，TSP）涉及为旅行商确定最短路径。旅行商必须访问一定数量的城市，尽管他可以从任何城市开始和结束，但他只能访问每个城市一次。TSP有多个变体，其中一些变体允许多次访问每个城市，或为每个城市分配不同的值。本章中的TSP只是寻求一条尽可能短的路线，每个城市访问一次。图3-1展示了这里介绍的TSP和最短路径。

图3-1　旅行商问题

对于普通的迭代程序而言，找到最短的路径似乎很容易。但是，随着城市数量的增加，可能的组合数量也会急剧增加。如果问题有一个或两个城市，则只能选择一条路径；如果包括3个城市，则可能的路径将增加到6个。以下列表展示了路径数量增长的速度：

1个城市有1条路径
2个城市有2条路径
3个城市有6条路径
4个城市有24条路径
5个城市有120条路径
6个城市有720条路径
7个城市有5 040条路径
8个城市有40 320条路径
9个城市有362 880条路径
10个城市有3 628 800条路径
11个城市有39 916 800条路径
12个城市有479 001 600条路径
13个城市有6 227 020 800条路径
……
50个城市有3.041 × 10ˆ64条路径

在上表中，用于计算总路径条数的公式是阶乘。使用阶乘运算符！作用于城市数n。某个任意值n的阶乘由n×(n − 1)×(n − 2)×…×3× 2×1给出。当程序必须执行蛮力搜索时，这些值会变得非常大。TSP是“非确定性多项式时间”（non-deterministic polynomialtime，NP）难题的一个例子。“NP困难”（NP-hard）被非正式地定义为“一系列不能用暴力搜索法求解的问题”。当超过10个城市时，TSP满足这个定义。NP困难的正式定义可以在Computers and Intractability: A Guide to the Theory of NP-Completeness [1]一书中找到。

动态编程是解决TSP的另一种常用方法，如图3-2的漫画所示。

尽管本书没有全面讨论动态编程，但了解其基本功能还是很有价值的。动态编程将TSP之类的大问题分解为较小的问题，这项工作可以被许多较小的程序复用，从而减少蛮力解所需的迭代次数。

图3-2　解决TSP的方法（来自xkcd网站）

与蛮力解和动态编程不同，遗传算法不能保证找到最优解。尽管它将找到一个很好的解，但分数可能不是最好的。在3.1.2节中讨论的示例程序，将展示遗传算法如何在短短几分钟内为50个城市的TSP产生可接受的解 [2]。

3.1.2　为旅行商问题设计遗传算法

TSP是最著名的计算机科学问题之一。由于传统的迭代算法通常无法解决NP困难问题，因此程序员必须使用遗传算法来生成潜在解。因此，我们将研究如何将遗传算法应用于TSP。

离散遗传算法决定了你要使用的交叉和突变算子的类型。由于离散问题是分类问题，因此你无须处理数值。所以，你可能访问的城市就是TSP中的分类信息。按照访问顺序，城市列表是每个解的基因组。下面展示了如何表达TSP基因组：

[洛杉矶, 芝加哥, 纽约]

你的初始种群将是这些城市的随机排列。例如，初始随机种群可能类似于以下列表：

[洛杉矶, 芝加哥, 纽约] 
[芝加哥, 洛杉矶, 纽约] 
[纽约, 洛杉矶, 芝加哥]

你可以计算在每条路径上行驶的英里（1英里=1 609.344米）数，从而为上述城市创建一个计分函数。考虑第一个种群成员。根据Google Maps的驾驶导航，洛杉矶至芝加哥为2 016英里，芝加哥至纽约为790英里。因此，第一个种群成员覆盖的整个距离为2 806英里。距离是我们要最小化的分数。以上3个种群成员及其分数显示如下。

[洛杉矶, 芝加哥, 纽约] -> 分数: 2 016 + 790 = 2 806
[芝加哥, 洛杉矶, 纽约] -> 分数: 2 016 + 2 776 = 4 792 
[纽约, 洛杉矶, 芝加哥] -> 分数: 2 776 + 2 016 = 4 792

如你所见，最后两条路径的分数相同，因为旅行商可以从任何城市开始，所以最后两条路径产生相同的距离。旅行商问题的某些变体可以固定起点和终点城市。作为旅行商的家乡，起点和终点是相同的。其他变体让旅行商可以多次访问同一座城市。简而言之，如何定义旅行商问题的规则将决定如何实现计算机程序。

考虑一下这种情况：旅行商总是从同一城市（即他的家乡）开始，并最终返回这里。在这个例子中，家乡城市是密苏里州的圣路易斯。此外，分数将是两个城市间最便宜机票的价格。由于基因组仍将由洛杉矶、芝加哥和纽约的排列组成，因此圣路易斯没有必要出现在基因组的开始和结尾。这样可以防止算法将圣路易斯更改为不是路径的起点或终点。换言之，计分函数隐式地将圣路易斯作为路径的起点和终点，并对其进行适当的处理。检查第一个种群成员，如下所示。

[洛杉矶, 芝加哥, 纽约]

该示例包括以下旅程。

圣路易斯至洛杉矶 -> 费用: $393
洛杉矶至芝加哥 -> 费用: $452
芝加哥至纽约 -> 费用: $248 
纽约至圣路易斯 -> 费用: $295 
总计:　$1388

对问题的微小改动带来了很大的复杂性。由于圣路易斯位于美国中部，旅行商无法再从东到西或从西到东走一条简单的路。此外，机票价格不可互换，因为从芝加哥到圣路易斯的票价不一定与从圣路易斯到芝加哥的票价相同。旅行当天机票价格的变化使这个问题更加复杂。因此，基因组可以包括开始和结束日期。这样，遗传算法可以优化出行计划和城市顺序。

你还可以创建算法，以允许旅行商多次访问同一座城市，但是，这个要求增大了计分函数的复杂性。如果你放宽要求，让旅行商可以多次访问同一座城市，则最佳分数可能来自以下解：

[芝加哥, 芝加哥, 芝加哥]

上述解的分数十分理想。该算法选择了从圣路易斯到最便宜的目的地芝加哥的路径。然后，算法再次选择芝加哥作为第2和第3站。因为从芝加哥到芝加哥的机票是0美元，所以这次旅行的分数非常好。显然，在这种情况下，该算法没有为程序员做任何额外的工作。因此，计分函数需要更复杂才能传达真正最优解的参数。也许有些城市更有价值，需要拜访，而另一些则是可选的。设计计分函数对于遗传算法编程至关重要。

3.1.3　旅行商问题在遗传算法中的应用

现在，我们将看到一个简单的遗传算法的示例，它用一条好路径穿过一系列城市。50个城市随机放置在256×256网格上。该程序使用了1 000条路径的种群，来演化出穿过这些城市的最佳路径。因为城市列表是分类值，所以TSP是一个离散的问题。在这个示例中，计分函数计算出一条城市路径所覆盖的总距离，这些城市中的任何一个都不会被访问两次。

这些参数决定了最合适的突变和交叉算子的选择。对于这个示例，改组突变算子是最佳选择。如第2章所述，改组突变算子可与固定长度的分类数据配合使用。同样，我们将使用无重复的拼接交叉算子。两个算子都允许1 000条路径的种群演化，并且无重复的交叉强制实现了我们的要求，即同一城市只被访问一次。

我对该程序进行了数百次迭代，直到连续经过50次迭代而没有出现一次改善最佳路径长度的情况。一次迭代即经过了一个世代。程序的输出在下面列出。

Iteration: 1 , Best Path Length = 5308.0
Iteration: 2 , Best Path Length = 5209.0
Iteration: 3 , Best Path Length = 5209.0
Iteration: 4 , Best Path Length = 5209.0
Iteration: 5 , Best Path Length = 5209.0
Iteration: 6 , Best Path Length = 5163.0
Iteration: 7 , Best Path Length = 5163.0
Iteration: 8 , Best Path Length = 5163.0
Iteration: 9 , Best Path Length = 5163.0
Iteration: 10 , Best Path Length = 5163.0
...
Iteration: 260 , Best Path Length = 4449.0
Iteration: 261 , Best Path Length = 4449.0
Iteration: 262 , Best Path Length = 4449.0
Iteration: 263 , Best Path Length = 4449.0
Iteration: 264 , Best Path Length = 4449.0
Iteration: 265 , Best Path Length = 4449.0
Good solution found:
22>1>37>30>11>33>39>24>9>16>40>3>17>49>31>48>46>20>13>47>23>
0>2>29>27>14>34>26>15>7>35>19>21>18>6>28>25>45>8>38>43>32>
41>5>10>4>44>36>12>42

如你所见，在程序确定一个解之前，发生了265次迭代。由于城市是随机的，因此它们没有实际名称，而是将城市标记为“1”“2”“3”等。上面显示的最优解从城市22开始，接下来是城市1，最终在城市42停止。你可以在以下网址查看在线的TSP实现：

http://www.heatonresearch.com/aifh/vol2/tsp_genetic.html

3.2　连续问题的遗传算法

程序员还可以利用遗传算法来演化连续的（即数值的）数据。在下面的示例中，我们将基于4个输入测量值来预测鸢尾花的种类。因此，我们的遗传算法将训练一个径向基函数（Radial-Basis Function，RBF）网络模型。

模型是一种算法，它基于输入向量进行预测，这称为预测建模。对于鸢尾花数据集，我们将为RBF网络提供4个描述鸢尾花的测量值。RBF网络将根据这4个测量结果预测鸢尾花种属。它通过训练示例中的150朵花的数据来进行学习预测。该模型可以预测训练集中未包含的新花的种属。

让我们回顾一下如何训练模型。3个主要部分确定了遗传算法如何训练任何模型：

训练设置；
超参数；
参数。
训练设置是遗传算法所独有的，例如种群数量、精英数、交叉算法和突变算法。在本书的后文，我们将学习粒子群优化（PSO）和蚁群优化（ACO），它们是RBF网络模型的训练算法。PSO和ACO的训练设置具有独有的特征。程序员通常会建立训练参数，因此，选择最佳的参数可能需要反复试验。

超参数定义模型的结构。考虑图3-3，该图展示了RBF网络的结构。

图3-3　以鸢尾花数据集为输入的RBF网络的结构

在图3-3中，第2列显示的是3个具有凸起形状曲线的框，它们是RBF，使RBF网络能够做出预测。这个任务所需的RBF网络的数量是一个超参数，程序员或计算机可以确定该超参数。尽管RBF数量不影响遗传训练，但是如果你正在使用PSO和ACO进行训练，你仍然需要设置RBF数量。不过，你要小心，如果将RBF数量设置得太低，则创建的模型会很简单，以至于无法从信息中学习；如果将RBF数量设置得太高，则创建的网络会很复杂且难以训练，并可能导致过度拟合。这是我们不希望的情况，这时模型开始将数据存储在数据集中，而不是学习更通用的解。第10章将介绍过度拟合及其避免方法。在本章中，我们将RBF数量设置为5，这对于鸢尾花数据集似乎效果很好。我通过试验确定了这个数字。

计算机也可以确定超参数，其中试错法通常是找到超参数的方法。只需在1～10个RBF之间循环，并让计算机尝试每种情况。一旦测试了全部10个RBF，程序就会选择获得最佳分数的模型。该模型将告诉你RBF数量超参数的最佳设置。

最后的组成部分是参数向量。在训练模型时，模型会调整参数向量。这方面与超参数有所不同，因为一旦训练开始，模型就不会调整超参数。实际上，超参数定义了模型，无法更改。对参数向量进行调整是一种训练算法（例如遗传算法、PSO或ACO）教给模型针对给定输入的正确响应的方法。遗传算法利用交叉和突变来调整参数向量。

下面列出的输出展示了使用遗传算法针对鸢尾花数据集训练RBF网络的进度。如你所见，分数在前10次迭代中并没有提高。这些迭代中的每一次迭代代表一代潜在解。分数代表错误分类的150朵鸢尾花的百分比，我们力求让这个分数最小。

Iteration #1, Score = 0.1752302452792032, Species Count: 1
Iteration #2, Score = 0.1752302452792032, Species Count: 1
Iteration #3, Score = 0.1752302452792032, Species Count: 1
Iteration #4, Score = 0.1752302452792032, Species Count: 1
Iteration #5, Score = 0.1752302452792032, Species Count: 1
Iteration #6, Score = 0.1752302452792032, Species Count: 1
Iteration #7, Score = 0.1752302452792032, Species Count: 1
Iteration #8, Score = 0.1752302452792032, Species Count: 1
Iteration #9, Score = 0.1752302452792032, Species Count: 1
Iteration #10, Score = 0.1752302452792032, Species Count: 1
...
Iteration #945, Score = 0.05289116605845716, Species Count: 1
Iteration #946, Score = 0.05289116605845716, Species Count: 1
Iteration #947, Score = 0.05289116605845716, Species Count: 1
Iteration #948, Score = 0.051833695704776035, Species Count: 1
Iteration #949, Score = 0.05050776383877834, Species Count: 1
Iteration #950, Score = 0.04932340367757065, Species Count: 1
Final score: 0.04932340367757065
[- 0.55, 0.24, -0.86, -0.91] -> Iris-setosa, Ideal: Iris-setosa
　
[-0.66, -0.16, -0.86, -0.91] -> Iris-setosa, Ideal: Iris-setosa
[-0.77, 0. 0, -0.89, -0.91] -> Iris-setosa, Ideal: Iris-setosa
...
[0.22, -0.16, 0.42, 0.58] -> Iris-virginica, Ideal: Iris-virginica
[0.05, 0.16, 0.49, 0.83] -> Iris-virginica, Ideal: Iris-virginica
[-0.11, -0.16, 0.38, 0.41] -> Iris-virginica, Ideal: Iris-
virginica

在以上输出中，你可能还看到了物种计数（species count）。由于我们目前不使用物种，因此它保持为1。第5章将介绍物种。

3.3　遗传算法的其他应用
鸢尾花数据集和旅行商问题是人工智能文献中的常见例子。观察各种算法如何解决相同的问题，可以有助于理解它们的差异，检查新问题与遗传算法相符合的方式同样有价值。本节将说明如何让各种问题适应遗传算法。

尽管本书目前未实现这些应用程序，但将来可能会包含它们。以下各小节的主要目的是演示遗传算法在各种情况下的应用。

3.3.1　标签云
标签云是一种方便的工具，可用于可视化文档中的单词频率计数。实际上，一个小的标签云可以代表一个很长的文档中的常用单词，但是，标签云算法通常会从单词数统计中删除结构化单词（例如“the”）。图3-4展示了根据《人工智能算法（卷1）：基础算法》英文版创建的标签云。

图3-4　卷1的标签云

图3-4所示的标签云展示了每个单词出现的频率。你可以轻松地看到，“algorithm”是卷1中最常见的单词。

要创建标签云，必须统计单词数。下面展示了构建图3-4所示标签云的单词计数：

341 algorithm
239 training
203 data
201 output
198 random
192 algorithms
169 number
163 input
...

单词计数提供每个单词的出现频率，并与其他单词对比。标签云中的单词互相交织，使得单词之间的空白空间最小。在示例中，较小的单词填充了“algorithm”的“h”和“m”下的空白。

创建标签云的第一步是选择一些单词并确定它们的大小。上面的单词计数说明了这个步骤。最有可能的是，你会在标签云中包含文档中大约100个最常见的单词。标签云中的确切字数将根据显示美观度进行调整。单词在文本中出现的次数将决定单词的大小。

消除空白是遗传算法的一项重要应用。x和y坐标、方向指示共同代表了每个单词。其中x和y坐标表明每个单词在显示屏上的位置，方向指示表明单词是水平的还是垂直的。这3个数据项产生的向量长度等于标签云中单词数量的3倍。如果显示100个单词，则向量的长度为300个元素。对于空白和重叠文本，基因组将接受罚分。标签云不应该有重叠的文本。因此，你需要创建类似于以下内容的计分函数：

[空白像素数] + ([重叠像素数] × 100)

遗传算法应设法最小化这个计分函数。如果文本重叠，则需要增加系数100。

3.3.2　马赛克艺术
艺术生成是遗传算法的另一个非常常见的例子。编写计算机艺术的计分函数非常容易。你需要将源图像与遗传算法创建的图像进行比较；还要为遗传算法提供一组工具，以便它可以生成图像并显示其模拟的创造力。

人类画家的工作方式基本相同。显然，产生图像的最简单方法是用数码相机照相，但是，画家用自己的工具（画笔和颜料）创造了艺术。对于遗传算法，工具是编程语言的图形命令，计分函数只是将原始图像与遗传算法产生的图像进行比较。例如，你可以限制遗传算法，让它仅用少数几种颜色画圆。仅使用程序中允许的元素，遗传算法将通过演化，产生原始照片的最佳渲染效果。通过这种方式，它展示了模拟的创造力。

用遗传算法创建计算机艺术的一个例子是马赛克，它是由较小图像集合组成的较大图像。主图像包含一个图像网格，较小的图像将放置在每个网格单元中。图3-5展示了一幅马赛克。

[[386718]]

图3-5　玄凤鹦鹉马赛克

图3-5描绘了由动物图像生成的玄凤鹦鹉马赛克。玄凤鹦鹉的图像尺寸为2 048像素×2 048像素，每张尺寸为32像素×32像素的较小动物图像的网格将构成该马赛克。将这些较小的动物图像的网格覆盖到较大的图像上，则将形成64×64的网格。（图3-5经过裁剪，仅展示其中一部分。）选择一组较小的动物图像放入64×64的网格中，使得网格在整体上可以最佳地呈现出一只玄凤鹦鹉的样子。

每个基因组都是固定长度的数组，长度等于64×64即4 096字节。使用计分函数比较生成的马赛克图像和原始图像之间的差异。一旦得分降到最低，你将拥有与玄凤鹦鹉非常相似的马赛克。

3.4　本章小结
遗传算法利用种群、计分、交叉和突变来解决实际的编程问题。遗传算法是在第1章和第2章中学到的概念的具体实现，这些概念与交叉和突变一起工作，可以为下一代提供更好的解。

遗传算法要求解以固定长度数组表示。这项要求似乎很有局限性，但是许多解都可以用这种方式表示。在本章中，我们还演示了旅行商问题和鸢尾花数据集。另外，我们讨论了遗传算法如何应用于标签云和马赛克艺术。

为了超越定长数组，第4章将介绍如何演化实际的程序。实际上，遗传编程可以将计算机程序表示为树状结构，以便为下一代创建更好的程序。