适者生存：算法中的自然选择——遗传算法

一般来说，听起来，算法和自然界的生物是扯不上什么关系的，但实际上计算机科学算法是受到自然界和生物过程的启发的。其中一些算法包括神经网络，粒子群算法，人造蜂群，蚁群优化，演化算法等等。事实上，你可以将生物过程视为自然界解决问题的简单算法。从这个角度来看，很容易看出为什么这些算法中有许多是优化启发式和元启发式。毕竟，大自然都是为了生存而不断优化。

可能你不熟悉启发式算法这个术语，它是通过做一些假设来更快地解决问题的算法。因此，启发式算法通常不是最优的，但在获得最佳结果花费太长时间的情况下更有用。元启发式（Metaheuristics）将其提升到了一个新的水平，它们是一种启发式的方法，可以产生或发现启发式。

遗传算法

遗传算法是基于自然选择过程的元启发式算法。遗传算法是一种演化算法。

自然选择是进化的关键机制。这是一个自然的过程，会导致（有机体）群体随着时间的推移适应环境。这些种群在性状上有差异，更适合的个体生物在环境中具有更高的生存机会，从这些幸存的生物中复制的下一代将继承它们的性状。

但是，如果所有的种群具有相同的特征，一旦环境发生变化，人口将会灭绝。幸运的是，会偶尔发生一些突变导致性状的变异，并且这些变异允许具有更适合于改变的环境的特性的生物体生存并成为主导。

一个普遍使用的例子是在英国的胡椒粉蛾的颜色变化。在十九世纪初，英格兰的飞蛾主要是白色的，并且它的着色帮助它躲避掠食性鸟类，因为它与浅色的地衣和英国树木融合在一起。然而在工业革命时期，由于污染，浅色的地衣死亡，许多蛾类休息的树木被烟灰熏黑。这使得深色的飞蛾有利于躲避食肉动物，而浅色的飞蛾很容易被发现。到了十九世纪中叶，黑色飞蛾的数量增加了，到本世纪末，几乎所有的飞蛾都是黑色的。直到1956年“清洁空气法案”的出现产生的影响才扭转了这一平衡，暗色的飞蛾再次变得罕见。

所以这是自然的选择。那么遗传算法如何进入图像？遗传算法是启发式的，它使用与自然选择相同的机制——DNA、种群、变异、适应性、选择、繁殖、遗传和变异。

·DNA - 定义有一个或多个DNA的生物体

·人口 - 从具有不同基因（值）的生物体的初始种群开始

·健身 - 确定每个有机体对环境的适应性

·选择 - 选择最适合的生物体，给予更高的繁殖机会

·繁殖 - 从选定的最适合的生物体中创造下一代种群

·继承 - 下一代人口必须继承基因的价值

·突变 - 每一代，基因都有一个小小变化

猴子，打字机和莎士比亚

无限的猴子定理：无数的猴子坐在无数打字机前随机敲击键盘，如果有足够的时间，就会随机地敲击键盘，最终会重现莎士比亚的全部作品。假设我们只需要一只猴子来重现这句话：“做不做”，你认为猴子随机打出这句简单的话会花费多长时间？

该报价有18个字符（包括空格）。猴子输入“t”的概率二十六分之一。因此，输入“是或不是”的确切顺序的概率是26个中的1个以18,479,510,200,013,920,000,000,000的比例分配给18或1的权力。如果我们说猴子每秒钟打一封信，那么在934,789,136,225,707,600年之间只有一个机会会输出那个报价。这是934万亿年里的1次。

显然，这样做成效一般，如果我们试图“进化”这句话呢？让我们看看如何使用遗传算法来做到这一点。以下是用于解决问题的遗传算法的步骤：

定义一个由一个或多个DNA组成的生物体

我们的莎士比亚发明算法中的有机体由一个单一的DNA组成，它是一个字节数组，代表生物的适应性。

从最初的生物种群开始

我们需要为最初的人口创造有机体，所以这里有一个功能来做到这一点。

目标就是我们想要达到的目标，在这种情况下，它是字符串'是或不是'的字节数组的表示形式。 在这个函数中，我们随机创建一个长度与目标长度相同的字节数组，并将其设置为新创建的生物体中基因的值。

现在我们可以创建生物体，需要创建一个种群。

人口是有机体的数组，而PopSize则是定义总体大小的全局变量。

找到有机体的适应性

我们需要计算人群中生物的适应度。 这在我们创造生物体的时候就已经提到过了，但是当我们交叉生物体的时候也会被调用。

这里的变异仅仅意味着确定一个随机生成的数字是否低于MutationRate。为什么我们需要改变孩子的机体呢？如果突变永远没发生，人口中的DNA将始终保持与原始群体相同。这意味着如果原始人口没有一个特定的基因（价值），最优的结果将永远不会实现。正如在这个例子中，如果字母t在最初的人口中根本找不到，那么无论我们经历了多少代，我们都不可能拿出这个名字。换句话说，自然选择没有突变是行不通的。

更技术性地说，突变使我们脱离局部最大值以找到全局最大值。如果我们将遗传算法看作寻找最优解的机制，那么如果我们没有变异，那么一旦找到局部最大值，机制就会简单地解决这个问题，而不会继续寻找全局最大值。突变会使人口超出局部最大值，从而为算法提供继续寻找全局最大值的机会。

一旦我们检查了突变，我们就可以计算出儿童有机体的适应度，并将其插入到下一代人群中。

这就是遗传算法！现在让我们把它放在主函数中。

在主要的函数中，经历了几代人，并为每一代，找到最适合的有机体。 如果最适合的生物体的基因与目标相同，就会找到答案。

现在运行软件程序！ 你需要多长时间？

因为最初的人口是随机生成的，所以每次都会得到不同的答案，但大部分时间我们可以在不到一秒的时间内完成报价！ 这与934万亿年前的时间差距相当大。

不断演变的蒙娜丽莎

进化的莎士比亚似乎很简单。 毕竟这只是一个字符串，有什么样的东西，怎么样的不同，比如一张照片，还是有史以来最著名的画作，达·芬奇的蒙娜丽莎？ 我们可以就此演变吗？

让我们给它同样的待遇。 我们将从定义有机体开始，代表蒙娜丽莎的画面。

定义一个由一个或多个DNA组成的生物体

我们的DNA现在不是一个字节数组，而是一个来自图像标准库的结构。

从最初的生物种群开始

像以前一样，我们先看看创建一个有机体。

我们调用另一个函数来创建一个随机图像，而不是创建一个随机字节数组。

一个image.RGBA结构由一个字节数组Pix（byte和uint8是一样的东西）、一个Stride和一个Rect组成。对我们来说重要的是Pix，我们使用与目标图像（这是蒙娜丽莎的图像）相同的步幅和直角。对我们来说幸运的是，math / rand标准库有一个名为Read的方法，可以很好地填充随机字节的字节数组。

你可能会好奇，我们在这里讨论的是多大的一个字节数组？ Pix只不过是一个字节数组，其中4个字节表示一个像素（R，G，B和A，每个字节都由一个字节表示）。对于800 x 600的图像，我们在每个图像上都说了192万字节！为了保持程序相对快速，我们将使用一个尺寸为67 x 100的较小的图像，这将得到一个26,800字节的数组。

此外，你可能会意识到，因为每个像素都是随机着色的，我们最终会得到一个彩色的静态雪花图案。

让我们继续。

找到有机体的适应性

有机体的适应性是这两幅图像的不同之处。

为了找出差异，我们可以回到勾股定理。如果你还记得，我们可以求出两点间的距离如果我们把x和y值的差平方，把它们加起来，然后平方根结果。

给出2点a（x1，y1）和b（x2，y2），a与b之间的距离d为：

这是在二维空间中。在三维空间中，我们只做了两次勾股定理，在四维空间中，我们做了三次。像素的RGBA值本质上是一个四维空间中的一个点，所以为了找到两个像素之间的差异，我们将r、g、b和两个像素值的差值平方，把它们全部加起来，然后再把结果平方。

这就是2个像素之间的差异。为了找到所有像素之间的差异，我们只是把所有的结果加起来，就有了最后的区别。由于Pix本质上是一个连续的RGBA值的长字节数组，所以我们可以使用一个简单的快捷方式。我们简单地将图像中每个相应字节与目标之间的差值进行平方，然后将它们全部加起来，并将最终数字平方根找出两幅图像之间的差异。

作为参考，如果2张图像完全相同，则差值为0，如果2张图像完全相反，则差值为26800。换句话说，最适合的生物体应该具有0的适应性，数量越高，生物体的适应性越低。

选择最适合的生物体，并给它们更高的繁殖机会

我们仍然在这里使用繁殖池机制，但有区别。首先，我们将人口从最佳状况调整为最差状况。然后，我们把最好的生物放到繁殖池中。我们使用一个参数PoolSize来表示我们想要在池中有多少最适合的生物体。

为了弄清楚把什么投入到繁殖池中，我们用顶部最不合适的生物体减去每个最好的生物体。这在最好的生物体之间创造了一个有区别的排名，根据差异排名，我们在生殖池中放置相应的生物体数量。例如，如果最适合的生物体与最不适合的生物体之间的差异是20，那么我们在繁殖池中放置20个生物体。

如果顶级最适合的生物体之间没有差异，这意味着种群是稳定的，我们不能真正创造一个适当的繁殖池。为了克服这个问题，如果差值为0，我们将池设置为整个种群。

从选定的最适合的生物创造下一代

在我们拥有了这个池之后，我们需要创造下一代游戏。 这里的自然选择代码与以前的程序没有什么不同，所以我们将在这里跳过。

下一代必须继承基因的价值

交叉函数稍有不同，因为孩子的DNA不是一个字节数组，而是一个image.RGBA。 实际的交叉机制在像素的字节数组Pix上工作，取而代之。

随机变异每一代

mutate函数也有相应的不同。

现在我们拥有了所有的东西，我们把它放进去。

现在开始运行它，看看能够得到什么。

根据我设定的参数，当我运行它时，我通常以19,000左右的适应度开始。 平均来说，会需要20多分钟才能达到不到7500的体能。

以下是一段时间以来制作的图像序列：

与圆和三角形演变的蒙娜丽莎

我通过绘制圆圈，在图像上绘制三角形，对进化的蒙娜丽莎有了一些乐趣。 结果不是那么快，图像也不那么明显，但它显示了实际发生的一幕。 你可以检查出库中的其余代码，并调整参数，看看是否可以得到更好的图片，但这里有一些得到的图像。

蒙娜丽莎三角形

蒙娜丽莎圆圈

在终端上显示图像

你可能已经注意到，在屏幕截图中，实际上是在终端上显示图像。 我可以创建一个Web应用程序来显示，但我想保持简单，所以直接在终端上显示图像。 虽然终端控制台不是通常期望显示图像的地方，但实际上有几种方法可以实现。

这里选择了最简单的一个。 碰巧使用了优秀的iTerm2，它是MacOS默认终端应用程序的替代品，iTerm2中有一个有趣的黑客可以显示图像。

诀窍是，如果你可以使用Base64编码图像，则可以使用特殊命令将图像打印到终端。 这是Go代码来做到这一点，但你也可以用任何其他语言做到这一点。 上面的文档中有几个脚本显示了如何使用简单的shell脚本来完成。

这意味着不幸的是，如果你在其他任何其他iTerm2中运行此代码，你将无法看到图像的演变。 但是，可以随时调整输出，以便每隔几代捕获一次输出。

代码

在这篇文章中的所有代码和图像可以在这里找到：https：//github.com/sausheong/ga