人工智能算法：遗传算法

遗传算法是一种特殊类型的进化算法，但在描述遗传算法的文献中其定义各不相同。本书将遗传算法定义为一种进化算法，可以使用交叉和变异算子来优化固定长度的向量。评分函数区分好和坏的解决方案来优化这个固定长度的向量。这个定义说明了遗传算法的本质。 本书的前两章从某种抽象意义上定义了进化算法。评分、选择、种群、交叉和变异都是进化算法的重要特征，但我们还没有将所有这些特征集成到具体的算法中。 遗传算法是一种特殊类型的进化算法，但在描述遗传算法的文献中它们的定义各不相同。本书将遗传算法定义为一种进化算法，可以使用交叉和变异算子来优化固定长度的向量。评分函数区分好和坏的解决方案来优化这个固定长度的向量。这个定义说明了遗传算法的本质。 此外，可以将可选功能添加到遗传算法中以增强其性能。物种形成、精英主义和其他选择方法等技术有时可以提高遗传算法的性能。 3.1　离散问题的遗传算法 与其他算法类似，遗传算法对于连续学习和离散学习采用略有不同的方法。连续学习涉及计算数值，而离散学习涉及识别非数值。本节将展示离散学习和连续学习如何应用于以下两个经典的人工智能问题： 旅行商问题； 鸢尾花物种建模。 对于旅行商问题，我们展示了如何将遗传算法应用于离散学习组合问题，以找到最佳城市序列。同时，我们将拟合 RBF 神经网络的权重来识别鸢尾花物种，这将作为连续问题的遗传算法的示例，即调整数值权重。 3.1.1　旅行商问题 旅行商问题 (TSP) 涉及确定旅行商的最短路径。旅行推销员必须访问一定数量的城市，虽然他可以在任何城市开始和结束，但每个城市只能访问一次。 TSP 有多种变体，其中一些允许对每个城市进行多次访问，或者为每个城市分配不同的值。本章中的 TSP 只是寻求一条尽可能短的路线，访问每个城市一次。这里介绍的TSP和最短路径如图3-1所示。 图 3-1　旅行商问题 对于普通的迭代程序来说，寻找最短路径似乎很容易。然而，随着城市数量的增加，可能的组合数量急剧增加。如果问题有1个或2个城市，则只能选择一条路径；如果包含 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条航线 6 227 020 13个城市的800条路径 …… 50 个城市有 3.041 × 10ˆ64 条路径 在上表中，用于计算路径总数的公式是阶乘。使用阶乘运算符！作用于城市编号n。某个任意值 n 的阶乘由 n×(n − 1)×(n − 2)×…×3× 2×1 给出。当程序必须执行强力搜索时，这些值可能会变得非常大。 TSP 是“非确定性多项式时间 (NP)”难题的一个示例。 “NP-hard”（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基因组： [洛杉矶、芝加哥、纽约] 您的初始人口将是这些城市的随机排列。例如，初始随机群体可能类似于以下列表： [洛杉矶、芝加哥、纽约] [芝加哥、洛杉矶、纽约] [纽约、洛杉矶、芝加哥] 您可以通过计算每条路线行驶的英里数来为上述城市创建一个评分函数。考虑第一个人口成员。根据谷歌地图行车路线，从洛杉矶到芝加哥的距离为 2,016 英里，从芝加哥到纽约的距离为 790 英里。因此，第一个人口成员所走的总距离为 2,806 英里。距离是我们想要最小化的分数。上述三名人口成员及其得分如下所示。 [洛杉矶、芝加哥、纽约] -> 得分：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 次迭代，而最佳路径长度却没有任何改进。一次迭代就是一代。下面列出了程序的输出。迭代：1，最佳路径长度 = 5308.0 迭代：2，最佳路径长度 = 5209.0 迭代：3，最佳路径长度 = 5209.0 迭代：4，最佳路径长度 = 5209.0 迭代： 5 ，最佳路径长度 = 5209.0 迭代：6，最佳路径长度 = 5163.0 迭代： 7 ，最佳路径长度 = 5163.0 迭代：8，最佳路径长度 = 5163.0 迭代：9，最佳路径长度 = 5163.0 迭代：10，最佳路径长度 = 5163.0 ... 迭代：260，最佳路径长度 = 4449.0 迭代：261，最佳路径长度 = 4449.0 迭代：262，最佳路径长度 = 4449.0 迭代：263，最佳路径长度 = 4449.0 迭代：264，最佳路径长度 = 4449.0 迭代：265，最佳路径长度 = 4449.0 找到好的解决方案： 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.sychzs.cn/aifh/vol2/tsp_genic.html 3.2　连续问题的遗传算法 程序员还可以使用遗传算法来演化连续（即数值）数据。在下面的示例中，我们将根据 4 个输入测量值来预测鸢尾花的种类。因此，我们的遗传算法将训练径向基函数（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，这对于 iris 数据集似乎效果很好。我通过实验确定了这个数字。 计算机还可以确定超参数，通常通过反复试验来找到它们。只需循环 1 到 10 个 RBF，然后让计算机尝试每种情况。一旦所有 10 个 RBF 都经过测试，程序就会选择得分最高的模型。该模型将告诉您 RBF 数超参数的最佳设置。 最后一个分量是参数向量。当模型被训练时，模型会调整参数向量。这方面与超参数的不同之处在于，一旦训练开始，模型就不会调整超参数。实际上，超参数定义了模型并且无法更改。调整参数向量是训练算法（例如遗传算法、PSO 或 ACO）教导模型对给定输入做出正确响应的一种方法。遗传算法使用交叉和变异来调整参数向量。 下面列出的输出显示了在鸢尾花数据集上使用遗传算法训练 RBF 网络的进度。正如您所看到的，前 10 次迭代中分数没有提高。每一次迭代都代表了一代潜在的解决方案。该分数代表 150 朵鸢尾花被错误分类的百分比，我们努力最小化该分数。迭代 #1，得分 = 0.1752302452792032，物种计数：1 迭代 #2，得分 = 0.1752302452792032，物种计数：1 迭代 #3，得分 = 0.1752302452792032，物种计数：1 迭代 #4，得分 = 0.1752302452792032，物种计数：1 迭代 #5，得分 = 0.1752302452792032，物种计数：1 迭代 #6，得分 = 0.1752302452792032，物种计数：1 迭代 #7，得分 = 0.1752302452792032，物种计数：1 迭代 #8，得分 = 0.1752302452792032，物种计数：1 迭代 #9，得分 = 0.1752302452792032，物种计数：1 迭代 #10，得分 = 0.1752302452792032，物种计数：1 ... 迭代 #945，得分 = 0.05289116605845716，物种计数：1 迭代 #946，得分 = 0.05289116605845716，物种计数：1 迭代 #947，得分 = 0.05289116605845716，物种计数：1 迭代 #948，得分 = 0.051833695704776035，物种计数：1 迭代 #949，得分 = 0.05050776383877834，物种计数：1 迭代 #950，分数 = 0.04932340367757065，物种数量：1 最终得分：0.04932340367757065 [- 0.55, 0.24, -0.86, -0.91] -> 山鸢尾，理想：山鸢尾 　 [-0.66, -0.16, -0.86, -0.91] -> 山鸢尾，理想：山鸢尾 [-0.77, 0. 0, -0.89, -0.91] -> 山鸢尾，理想：山鸢尾 ... [0.22, -0.16, 0.42, 0.58] -> 维吉尼亚鸢尾，理想：维吉尼亚鸢尾 [0.05, 0.16, 0.49, 0.83] -> 维吉尼亚鸢尾，理想：维吉尼亚鸢尾 [-0.11, -0.16, 0.38, 0.41] -> 维吉尼亚鸢尾，理想：鸢尾- 弗吉尼亚州 在上面的输出中，您还可能会看到物种计数仍为 1，因为我们当前没有使用物种。第五章将介绍物种。 3.3　遗传算法的其他应用 Iris 数据集和旅行商问题是人工智能文献中的常见示例。观察不同算法如何解决同一问题可以帮助理解它们的差异，并且检查新问题如何适应遗传算法也同样有价值。本节解释如何使各种问题适应遗传算法。 尽管这些应用程序目前尚未在本书中实现，但将来可能会包含它们。以下小节的主要目的是演示遗传算法在各种情况下的应用。 3.3.1　标签云 标签云是一个方便的工具，用于可视化文档中的词频计数。在实践中，小的标签云可以表示很长的文档中的常见单词，但是，标签云算法通常会从字数统计中删除结构化单词（例如“the”）。基于英文版《人工智能算法（卷1）：基础算法》创建的标签云如图3-4所示。 图3-4　卷1标签云 图 3-4 所示的标签云显示了每个单词出现的频率。你可以很容易地看到“算法”是第一卷中最常见的词。 要创建标签云，必须计算单词数。构建图3-4所示标签云的字数统计如下： 341算法 第239章 训练 203 条数据 201输出 198 随机 192 种算法 169 个号码 163输入 ... 字数统计提供了每个单词相对于其他单词的出现频率。标签云中的单词交织在一起，因此单词之间的空白空间最小。在示例中，较小的单词填充了“algorithm”的“h”和“m”下方的空白。 创建标签云的第一步是选择一些单词并确定它们的大小。上面的字数统计说明了此步骤。最有可能的是，标签云中包含文档中大约 100 个最常见的单词。标签云中的确切字数将根据显示美观度进行调整。单词在文本中出现的次数将决定单词的大小。 消除空白是遗传算法的一个重要应用。 x 和 y 坐标以及方向指示一起代表每个单词。 x 和 y 坐标指示每个单词在显示屏上的位置，方向指示指示单词是水平还是垂直。这3个数据项生成的向量的长度等于标签云中单词数量的3倍。如果显示 100 个单词，则向量的长度将为 300 个元素。基因组将因空白和重叠文本而受到处罚。标签云不应有重叠的文本。因此，您需要创建一个类似于以下的评分函数： [空白像素数] + ([重叠像素数] × 100) 遗传算法应该尝试最小化这个评分函数。如果文本重叠，则需要将系数增加 100。 3.3.2　马赛克艺术 艺术生成是遗传算法的另一个非常常见的例子。为计算机艺术编写评分函数非常容易。您需要将源图像与遗传算法创建的图像进行比较；您还需要为遗传算法提供一组工具，以便它可以生成图像并展示其模拟的创造力。 人类画家的工作方式大致相同。显然，产生图像的最简单方法是用数码相机拍照，但画家用自己的工具创作艺术：画笔和颜料。对于遗传算法，工具是编程语言的图形命令，评分功能只是将原始图像与遗传算法生成的图像进行比较。例如，您可以限制遗传算法，使其仅使用几种颜色绘制圆圈。仅使用程序中允许的元素，遗传算法将不断发展以产生原始照片的最佳渲染效果。这样就体现了模拟的创造力。 用遗传算法创建的计算机艺术的一个例子是马赛克，它是由一系列较小图像组成的较大图像。主图像包含图像网格，较小的图像将放置在每个网格单元中。图 3-5 显示了马赛克。图3-5　玄凤鹦鹉马赛克 图 3-5 描绘了由动物图像生成的玄凤鹦鹉马赛克。玄凤鹦鹉的图像大小为 2048 像素 x 2048 像素，每个尺寸为 32 像素 x 32 像素的较小动物图像网格将构成马赛克。将这些较小动物图像的网格叠加到较大图像上将得到 64×64 网格。 （图 3-5 被裁剪以仅显示其中的一部分。）选择一组较小的动物图像以适合 64×64 网格，以便整个网格最好地代表玄凤鹦鹉。看。 每个基因组都是一个定长数组，长度等于64×64或4096字节。使用评分函数来比较生成的马赛克图像与原始图像之间的差异。一旦分数降至最低，您将得到与玄凤鹦鹉非常相似的马赛克。 3.4　本章小结 遗传算法使用群体、评分、交叉和变异来解决现实世界的编程问题。遗传算法是第一章和第二章中所学概念的具体实现，它与交叉和变异一起工作，为下一代提供更好的解决方案。 遗传算法要求解决方案以固定长度的数组表示。这个要求看似有限制性，但很多解决方案都可以用这种方式表达。在本章中，我们还演示了旅行商问题和 Iris 数据集。此外，我们还讨论了如何将遗传算法应用于标签云和马赛克艺术。 为了超越固定长度数组，第 4 章展示了如何改进实际程序。实际上，遗传编程可以将计算机程序表示为树状结构，以便为下一代创建更好的程序。