本书前两章从某种抽象意义上定义了进化算法。评分、选择、种群、交叉和变异都是进化算法的重要特征，但我们还没有将所有这些特征集成到一个具体的算法中。遗传算法是一种特殊的进化算法，但在描述遗传算法的文献中对它的定义各不相同。本书将遗传算法定义为一种可以用交叉和变异算子优化固定长度向量的进化算法。评分函数可以区分好的和坏的替代方案来优化这个固定长度的向量。这个定义说明了遗传算法的本质。此外，可以将可选特征添加到遗传算法中以增强其性能。物种形成、精英主义和其他选择方法等技术有时可以提高遗传算法的工作效率。3.1 离散问题的遗传算法与其他算法类似，对于连续学习和离散学习，遗传算法采取的方法略有不同。连续学习涉及计算数值，而离散学习涉及识别非数值。本节介绍如何将离散学习和连续学习应用于两个经典的AI问题：旅行商问题；鸢尾花物种建模。对于旅行商问题，我们展示了如何将遗传算法应用于离散学习的组合问题，目标是找到城市的最佳序列。同时，我们将拟合RBF神经网络的权重来识别鸢尾花品种，这将是一个连续问题的遗传算法的例子，即调整数值权重。3.1.1 旅行商问题旅行商问题(TSP)涉及确定旅行商的最短路径。旅行商必须访问一定数量的城市，虽然他可以在任何一个城市开始和结束，但他只能访问每个城市一次。TSP有多种变体，其中一些允许多次访问每个城市，或者为每个城市分配不同的值。本章中的TSP只是简单地寻找一条尽可能短的路线，访问每个城市一次。图3-1显示了此处提供的TSP和最短路径。图3-1 旅行商问题寻找最短路径对于普通的迭代程序来说似乎很容易。然而，随着城市数量的增加，可能的组合数量急剧增加。如果问题涉及一两个城市，则只能选择一条路径；如果包含3个城市，则可能的路径增加到6。以下列表显示了路径数量的增长速度：1个城市有1条路径2个城市有2条路径3个城市有6个路径4个城市有24个路径5个城市有120个路径6个城市有720个路径7个城市有5040个路径8个城市40320条航线9个城市362880条航线10个城市3628800条航线11个城市39916800条航线12个城市479001条航线600条航线13个城市6227020800条航线...有3.041×10^6450个城市的路线上表中，计算路线总数的公式为阶乘。使用阶乘运算符！作用于城市数n。某个任意值n的阶乘由n×(n?1)×(n?2)×…×3×2×1给出。当程序必须执行强力搜索时，这些值会变得非常大。TSP是“非确定性多项式时间”(NP)问题的示例。“NP难”（NP-hard）被非正式地定义为“无法通过蛮力搜索解决的一组问题”。当超过10个城市时，TSP满足此定义。NP-hardness的正式定义可以在ComputersandIntractability:AGuidetotheTheoryofNP-Completeness[1]一书中找到。动态规划是解决TSP的另一种常用方法，如图3-2中的动画所示。虽然本书没有全面涵盖动态规划，但了解其基本功能仍然很有价值。动态规划将像TSP这样的大问题分解成更小的问题，这项工作可以被许多更小的程序重复使用，从而减少了暴力解决方案所需的迭代次数。图3-2 求解TSP的方法（摘自xkcd网站）与暴力求解和动态规划不同，遗传算法不能保证找到最优解。虽然它会找到一个好的解决方案，但分数可能不是最好的。3.1.2节中讨论的示例程序将展示遗传算法如何在短短几分钟内为50个城市的TSP生成可接受的解决方案[2]。3.1.2 为旅行商问题设计遗传算法TSP是最著名的计算机科学问题之一。由于传统的迭代算法往往无法解决NP-hard问题，程序员必须使用遗传算法来生成潜在的解决方案。因此，我们将研究如何将遗传算法应用于TSP。离散遗传算法决定了您将使用的交叉和变异算子的类型。由于离散问题是分类问题，因此您不必处理数字。因此，您可能访问的城市是TSP中的机密信息。城市列表是每个解决方案的基因组，按访问顺序排列。以下是表达TSP基因组的方法：[洛杉矶、芝加哥、纽约]您的初始人口将是这些城市的随机排列。例如，初始随机人口可能类似于以下列表：[洛杉矶，芝加哥，纽约][芝加哥，洛杉矶，纽约][纽约，洛杉矶，芝加哥]您可以计算每条路径上行驶的英里数（1英里=1609.344米）为上面的城市创建评分函数。考虑第一个人口成员。根据谷歌地图上的行车路线，洛杉矶到芝加哥是2,016英里，芝加哥到纽约是790英里。因此，第一个人口成员覆盖的整个距离是2,806英里。距离是我们想要最小化的分数。以上3个人口成员及其分数如下所示。[洛杉矶、芝加哥、纽约]->得分：2016+790=2806[芝加哥，洛杉矶，纽约]->得分：2016+2776=4792[纽约，洛杉矶，芝加哥]->分数：2776+2016=4792如您所见，最后两条路径的分数相同，因为旅行商可以从任何城市出发，所以最后两条路径产生相同的距离。旅行商问题的一些变体可以确定出发地和目的地城市。作为旅行商的故乡，起点和终点是一样的。其他变体允许旅行推销员多次访问同一个城市。总之，旅行商问题的规则如何定义，将决定计算机程序如何实现。考虑这种情况：旅行推销员总是从同一个城市（即他的家乡）出发，最后回到这里。在此示例中，家乡城市是密苏里州的圣路易斯。此外，分数将是两个城市之间最便宜的机票价格。由于基因组仍将由洛杉矶、芝加哥和纽约排列组成，因此圣路易斯不需要出现在基因组的开头和结尾。这可以防止算法将St.Louis更改为路径起点或终点以外的其他内容。换句话说，评分函数隐式地将圣路易斯作为路径的起点和终点，并对其进行适当处理。检查第一个人口成员，如下所示。[洛杉矶、芝加哥、纽约]该示例包括以下旅程。圣路易斯到洛杉矶->费用：洛杉矶到芝加哥393美元->费用：芝加哥到纽约452美元->费用：纽约到圣路易斯248美元->费用：295美元总计： 1388美元问题造成很大的并发症性。由于圣路易斯位于美国中部，旅行的推销员再也无法从东到西或从西到东走捷径。此外，机票价格不可互换，因为从芝加哥到圣路易斯的票价不一定与从圣路易斯到芝加哥的票价相同。旅行当天机票价格的变化使问题更加复杂。因此，基因组可以包括开始日期和结束日期。这样，遗传算法就可以优化出行计划和城市序列。您还可以创建允许旅行推销员多次访问同一个城市的算法，但此要求会增加评分函数的复杂性。如果您放宽要求，使旅行推销员可以多次访问同一个城市，则最好的分数可能来自解决方案：[Chicago,Chicago,Chicago]上述解决方案得分非常高。该算法选择了从圣路易斯到最便宜的目的地芝加哥的路线。然后算法再次选择芝加哥作为第2站和第3站。由于从芝加哥到芝加哥的机票是0美元，所以这次旅行的分数非常好。显然，在这种情况下，该算法不会为程序员做任何额外的工作。因此，评分函数需要更复杂才能传达真正最优解的参数。也许有些城市更有价值，需要参观，而另一些则是可选的。设计评分函数对于遗传算法编程至关重要。3.1.3 遗传算法中的旅行商问题我们现在将看到一个简单的遗传算法示例，该算法在一系列城市中选择了一条良好的路径。这50个城市随机放置在256×256的网格中。该程序使用1,000条路径来演化出穿过城市的最佳路径。因为城市列表是一个分类值，所以TSP是一个离散问题。在此示例中，评分函数计算一条城市路线所覆盖的总距离，其中没有一个被访问过两次。这些参数决定了最合适的变异和交叉算子的选择。对于这个例子，改组变异算子是最好的选择。如第2章所述，改组变异算子可用于固定长度的分类数据。同样，我们将不重复地使用缝合交叉运算符。两个算子都允许1000条路径的人口进化，并且没有重复的交叉强制执行我们的要求，即同一个城市只被访问一次。我运行程序数百次迭代，直到连续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.heatonresearch.com/aifh/vol2/tsp_genetic.html3.2 Genetic算法连续问题的程序员也可以使用遗传算法来演化连续（即数值）数据。在下面的示例中，我们将根据4个输入测量值预测鸢尾花的种类。因此，我们的遗传算法将训练一个径向基函数(RBF)网络模型。模型是一种基于输入向量进行预测的算法，这称为预测建模。对于鸢尾花数据集，我们将为RBF网络提供4个描述鸢尾花的测量值。RBF网络将根据这4个测量值预测鸢尾花的种类。它从训练示例中的150朵花的数据中学习预测。该模型可以预测未包含在训练集中的新花的种类。让我们回顾一下如何训练模型。3个主要部分决定了遗传算法如何训练任何模型：训练设置；超参数；参数。训练设置是遗传算法特有的，如种群规模、精英数量、交叉算法、变异算法等。在本书的后面，我们将研究粒子群优化(PSO)和蚁群优化(ACO)，它们是RBF网络模型的训练算法。PSO和ACO的训练设置具有独特的特征。程序员通常会建立训练参数，因此选择最佳参数可能需要反复试验。超参数定义模型的结构。考虑图3-3，它显示了RBF网络的结构。图3-3 以鸢尾花数据集为输入进行预测的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.17523023452，79200.1752302452792032,SpeciesCount:1Iteration#6,Score=0.1752302452792032,SpeciesCount:1Iteration#7,Score=0.1752302452792032,SpeciesCount:1Iteration#8,Score=0.1752302452792032,SpeciesCount:1Iteration#9,Score=0.1752302452792032,SpeciesCount:1Iteration＃10，得分=0.1752302452792032，物种计数：1...迭代＃945，得分=0.052891166605845716，物种计数：1次数946，得分=0.0528911666605845716，物种计数：1ter：1ter：1terration：1terration＃94771111111911111911911911919911991191991199119911911991191191191191191191191191191191191111号，分数=0.051833695704776035，物种计数：1Iteration#949，分数=0.05050776383877834，物种计数：1Iteration#950，分数=0.04932340367757065，物种计数：1Finalscore:0.04932340367757065[-0.55,0.24,-0.86,-0.91]->Iris-setosa，理想：Iris-setosa [-0.66，-0.16，-0.86，-0.91]->Iris-setosa，理想：Iris-setosa[-0.77,0.0,-0.89,-0.91]->Iris-setosa，理想：Iris-setosa...[0.22，-0.16，0.42，0.58]->Iris-virginica，理想：Iris-virginica[0.05,0.16,0.49,0.83]->Iris-virginica，理想：Iris-virginica[-0.11，-0.16，0.38，0.41]->Iris-virginica，理想：Iris-virginica在上面的输出中，您可能还会看到物种计数仍然为1，因为我们目前没有使用物种。第5章将介绍物种。3.3 遗传算法的其他应用鸢尾花数据集和旅行商问题是人工智能文献中常见的例子。观察各种算法如何解决同一问题有助于理解它们之间的差异，检查新问题如何适应遗传算法也同样有价值。本节介绍如何使遗传算法适应各种问题。虽然这些应用程序目前没有在本书中实现，但它们可能会在未来包含在内。以下小节的主要目的是演示遗传算法在各种情况下的应用。3.3.1 TagCloudTagCloud是一个方便的工具，用于可视化文档中的词频计数。在实践中，一个小的标签云可以表示一个很长的文档中的常用词，但是，标签云算法通常会从字数中删除结构化的词（例如“the”）。图3-4是根据《人工智能算法（卷1）：基础算法》的英文版创建的标签云。图3-4 Volume1标签云图3-4中的标签云显示了每个词的出现频率。你可以很容易地看到“算法”是第1卷中最常见的词。要创建标签云，必须统计词数。用于构建图3-4所示标签云的词数如下所示：341algorithm239training203data201output198random192algorithms169number163input...词数提供每个词的频率并将其与其他词进行比较。标签云中的单词交错排列，使得单词之间的空白空间最小化。在示例中，较小的单词填充了“algorithm”的“h”和“m”下的空格。创建标签云的第一步是选择一些词并确定它们的大小。上面的字数说明了这个步骤。最有可能的是，您将在标签云中包含文档中大约100个最常用的词。标签云中的确切字数将根据显示美学进行调整。单词在文本中出现的次数将决定单词的大小。消除空白是遗传算法的一个重要应用。x和y坐标连同方向指示一起表示每个单词。其中x和y坐标表示每个字在显示屏上的位置，方向指示表示字是水平的还是垂直的。这3个数据项产生的向量长度等于标签云中单词数的3倍。如果显示100个单词，则向量的长度为300个元素。Genome将接受对空白和重叠文本的处罚。标签云不应该有重叠的文本。因此，您需要创建类似于以下的评分函数：[空白像素数]+([重叠像素数]×100)遗传算法应尽量减少此评分函数。如果文本重叠，则需要增加100的系数。3.3.2 MosaicArtArtGeneration是另一个非常常见的遗传算法示例。为计算机艺术编写评分函数非常容易。您需要将源图像与遗传算法创建的图像进行比较；还为遗传算法提供了一套工具，使其可以生成图像并展示其模拟的创造力。人类画家的工作方式大致相同。显然，制作图像最简单的方法是用数码相机拍照，然而，画家用自己的工具（画笔和颜料）进行艺术创作。对于遗传算法，工具是编程语言的图形命令，评分函数只是将原始图像与遗传算法生成的图像进行比较。例如，您可以限制遗传算法只用几种颜色绘制圆圈。仅使用程序中允许的元素，遗传算法将进化以产生原始照片的最佳渲染。通过这种方式，它展示了模拟的创造力。使用遗传算法创建的计算机艺术的一个例子是马赛克，它是由一系列较小图像组成的较大图像。主图像包含图像网格，较小的图像将放置在每个网格单元格中。图3-5显示了一个马赛克。图3-5 玄凤鹦鹉马赛克图3-5描绘了从动物图像生成的玄凤鹦鹉马赛克。玄凤鹦鹉的图像大小为2048像素x2048像素，由32像素x32像素的较小动物图像组成的马赛克网格。将这些较小动物图像的网格叠加到较大图像上将产生64x64网格。（图3-5已被裁剪以仅显示其中的一部分。）选择一组较小的动物图像以适应64×64网格，以便整个网格最能代表玄凤鹦鹉的外观。每个基因组是一个定长数组，长度等于64×64或4096字节。使用评分函数比较生成的马赛克图像与原始图像之间的差异。一旦分数触底，您将拥有与玄凤鹦鹉非常相似的马赛克。3.4 章节小结遗传算法利用种群、评分、交叉和变异来解决实际的编程问题。遗传算法是第1章和第2章中所学概念的具体实现，它与交叉和变异一起工作，为下一代提供更好的解决方案。遗传算法要求解决方案以固定长度的数组表示。这个要求可能看起来很有限，但是很多解决方案都可以用这种方式表示。在本章中，我们还演示了旅行商问题和鸢尾花数据集。此外，我们还讨论了如何将遗传算法应用于标签云和马赛克艺术。为了超越固定长度数组，第4章展示了如何发展实际程序。事实上，遗传编程可以将计算机程序表示为树结构，以便为下一代创建更好的程序。
