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

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

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.0Iteration: 2 , Best Path Length = 5209.0Iteration: 3 , Best Path Length = 5209.0Iteration: 4 , Best Path Length = 5209.0Iteration: 5 , Best Path Length = 5209.0Iteration: 6 , Best Path Length = 5163.0Iteration: 7 , Best Path Length = 5163.0Iteration: 8 , Best Path Length = 5163.0Iteration: 9 , Best Path Length = 5163.0Iteration: 10 , Best Path Length = 5163.0...Iteration: 260 , Best Path Length = 4449.0Iteration: 261 , Best Path Length = 4449.0Iteration: 262 , Best Path Length = 4449.0Iteration: 263 , Best Path Length = 4449.0Iteration: 264 , Best Path Length = 4449.0Iteration: 265 , Best Path Length = 4449.0Good 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: 1Iteration #2, Score = 0.1752302452792032, Species Count: 1Iteration #3, Score = 0.1752302452792032, Species Count: 1Iteration #4, Score = 0.1752302452792032, Species Count: 1Iteration #5, Score = 0.1752302452792032, Species Count: 1Iteration #6, Score = 0.1752302452792032, Species Count: 1Iteration #7, Score = 0.1752302452792032, Species Count: 1Iteration #8, Score = 0.1752302452792032, Species Count: 1Iteration #9, Score = 0.1752302452792032, Species Count: 1Iteration #10, Score = 0.1752302452792032, Species Count: 1...Iteration #945, Score = 0.05289116605845716, Species Count: 1Iteration #946, Score = 0.05289116605845716, Species Count: 1Iteration #947, Score = 0.05289116605845716, Species Count: 1Iteration #948, Score = 0.051833695704776035, Species Count: 1Iteration #949, Score = 0.05050776383877834, Species Count: 1Iteration #950, Score = 0.04932340367757065, Species Count: 1Final 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 algorithm239 training203 data201 output198 random192 algorithms169 number163 input...

单词计数供应每个单词的涌现频率，并与其他单词比拟。
标签云中的单词互相交织，使得单词之间的空缺空间最小。
在示例中，较小的单词添补了“algorithm”的“h”和“m”下的空缺。

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

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

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

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

3.3.2　马赛克艺术

艺术天生是遗传算法的另一个非常常见的例子。
编写打算机艺术的计分函数非常随意马虎。
你须要将源图像与遗传算法创建的图像进行比较；还要为遗传算法供应一组工具，以便它可以天生图像并显示其仿照的创造力。

人类画家的事情办法基本相同。
显然，产生图像的最大略方法是用数码相机摄影，但是，画家用自己的工具（画笔和颜料）创造了艺术。
对付遗传算法，工具是编程措辞的图形命令，计分函数只是将原始图像与遗传算法产生的图像进行比较。
例如，你可以限定遗传算法，让它仅用少数几种颜色画圆。
仅利用程序中许可的元素，遗传算法将通过蜕变，产生原始照片的最佳渲染效果。
通过这种办法，它展示了仿照的创造力。

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

图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章将先容如何蜕变实际的程序。
实际上，遗传编程可以将打算机程序表示为树状构造，以便为下一代创建更好的程序。

本文摘自《人工智能算法 卷2 受大自然启示的算》

法是人工智能技能的核心，大自然是人工智能算法的主要灵感来源。
本书先容了受到基因、鸟类、蚂蚁、细胞和树影响的算法，这些算法为多种类型的人工智能场景供应了实际办理方法。
全书共10章，涉及种群、交叉和突变、遗传算法、物种形成、粒子群优化、蚁群优化、细胞自动机、人工生命和建模等问题。
书中所有算法均配以详细的数值打算来进行讲解，每章都配有程序示例，读者可以自行考试测验。

本书适宜人工智能入门读者以及对人工智能算法感兴趣的读者阅读参考。