《Java遗传算法编程》—— 1.5 生物进化

本节书摘来异步社区《Java遗传算法编程》一书中的第1章，第1.5节，作者： 【英】Lee Jacobson（雅各布森） , 【美】Burak Kanber（坎贝尔），更多章节内容可以访问云栖社区“异步社区”公众号查看。

1.5 生物进化

生物通过自然选择的过程进化，这首先由达尔文（1859）在他的著作《物种起源》中提出。正是他的生物进化的概念，启发了早期的计算机科学家，转而用生物进化作为其优化技术的模型，并在进化计算的算法中实现。

因为在遗传算法中使用的许多思想和概念直接来自生物进化，对该主题有基本的了解，有利于深入了解这个领域。既然这样，在开始探索遗传算法之前，让我们先浏览一下生物进化的（有点简化）基础知识。

所有的生物都含有DNA，它编码了构成生物体的所有不同性状。DNA可以看成是生命的“说明书”，以便从头开始创建生物体。改变生物体的DNA会改变其性状，诸如眼睛和头发的颜色。DNA由单个基因组成，这些基因负责编码生物体的具体性状。

生物体的基因被分组放在染色体中，一套完整的染色体组成一个生物体的基因组。所有生物体至少具有一条染色体，但通常含有更多，例如人类有46条染色体，有些物种有超过1000条染色体。在遗传算法，我们通常将染色体称为候选解。这是因为遗传算法通常使用一条染色体来编码候选解。

对于特定性状的各种可能设置被称为“等位基因”，性状编码在染色体中的位置被称为“基因座”。我们将特定的基因组称为“基因型”，该基因型编码的物理生物体被称为“表现型”。

两个生物体交配时，来自两个生物体的DNA被带到一起，它们结合的方式导致产生的生物体（通常被称为的后代）从第一个亲代得到50%的DNA，并从第二个亲代得到另外50%的DNA。来自生物体DNA的基因偶尔会发生变异，为它提供双亲所没有的DNA。通过为种群增加以前没有的基因，这些变异为种群提供了遗传多样性。种群中的所有可能的遗传信息被称为种群的“基因库”。

如果产生的生物体对环境适应得足够好，能够生存，它自己很可能交配，让它的DNA继续留在未来种群中。然而，如果产生的生物体对环境适应得不够好，不能生存并最终交配，它的遗传物质将不会传播到未来种群中。这就是为什么进化偶尔被称为适者生存，因为只有适者才能达到个体生存并传递它们的DNA。正是这种选择性的压力，慢慢将进化导向发现越来越适应、越来越好的个体。

生物进化的一个实例
为了阐明这个过程如何逐渐导致进化出越来越适应的个体，请考虑下面的例子。

在一个遥远的星球上，存在一个物种，它的形状是白方块。

白方块的物种已经和平生活了几千年，直到最近，一个新的物种赶到，即黑圆圈。

黑圆圈物种是食肉动物，并开始以白方块种群为食。

白方块没有任何办法来保护自己并抵抗黑圆圈。直到有一天，一个幸存的白方块随机变异，从一个白方块变成一个黑方块。黑圆圈不再以新的黑方块为食，因为它的颜色和自己一样。

一些幸存的方块种群交配，造就了新一代方块。这些新方块继承了黑方块的颜色基因。

然而，白方块继续被吃掉......

最后，由于黑方块的进化优势，看起来类似黑圆圈，他们不再被吃了。现在，只剩下黑方块了。

黑方块不再畏惧黑圆圈，它们再一次自由地生活在和平之中。

《Java遗传算法编程》—— 2.10 练习 1．运行遗传算法几次，观察进化过程的随机性。它通常需要多少代来找到这个问题的一个解？ 2．扩大和减小种群规模。减小种群规模如何影响算法的速度？它是否也影响找到一个解需要的世代数？扩大种群规模如何影响算法的速度？它如何影响找到一个解需要的世代数？
《Java遗传算法编程》—— 2.9 小结 在本章中，你已经学会了实现遗传算法的基本知识。本章开头的伪代码提供了一个通用的概念模型，针对本书其余部分所有要实现的遗传算法：每个遗传算法将初始化并评估种群，然后进入一个循环，进行交叉、变异和再评估。仅当终止条件满足时，才退出循环。
《Java遗传算法编程》—— 2.8 交叉实现 为了实现轮盘赌选择，在GeneticAlgorithm类的任意位置增加一个selectParent( )方法。selectParent( )方法基本上是反着玩轮盘赌。在赌场，轮盘上已经有标记，然后旋转的轮盘，等待球落入位置。
《Java遗传算法编程》—— 2.6 交叉方法 在交叉过程中，除了用不同的选择方法，还有可用不同的方法在两个个体之间交换遗传信息。不同的问题具有不太一样的特点，采用特定的交叉方法更好。例如，“全一”问题只要求完全由1构成的字符串。字符串“00111”与字符串“10101”具有相同的适应度值，因为它们都包含3个1。
《Java遗传算法编程》—— 2.5 轮盘赌选择 轮盘赌选择（也称为适应度比例选择）是用轮盘赌为类比，从种群中选择个体的方法。这种想法是根据种群中个体的适应值，将它们放置在一个假想的轮盘上。个体的适应度越高，在轮盘上占据的空间就越多。图2-1展示了在这个过程中，个体通常如何放置。
《Java遗传算法编程》—— 2.4 基本实现 为了消除所有不必要的细节，保持最初的实现容易尝试，本书中介绍的第一个遗传算法将是简单的二进制遗传算法。 二进制遗传算法比较容易实现，对于解决许多种优化问题，它可能是非常有效的工具。你可能还记得第1章提到，二进制遗传算法是由Holland（1975）提出的原创的遗传算法。
《Java遗传算法编程》—— 2.3 关于本书的代码示例 本书中的每一章都作为一个包，放在附带的Eclipse项目中。每个包都至少有4个类。 GeneticAlgorithm类，它抽象了遗传算法本身，为接口方法提供了针对问题的实现，如交叉、变异、适应度评估和终止条件检查。
异步社区 异步社区(www.epubit.com)是人民邮电出版社旗下IT专业图书旗舰社区，也是国内领先的IT专业图书社区，致力于优质学习内容的出版和分享，实现了纸书电子书的同步上架，于2015年8月上线运营。公众号【异步图书】，每日赠送异步新书。