Python实现单亲遗传算法

预计阅读时间：10min

什么是遗传算法？

这是个真实的故事。

从前在海岸边有一群扇贝在悠哉游哉地生活繁衍着。它们自然是衣食不愁，连房子也有了着落。它们担忧的只有一件事：每隔一段时间，总有一个人来挖走它们之中的一部分。当然啦，挖回去干什么这大家都知道。但扇贝们不知道的是，这人的家族图腾是Firefox的图标，所以他总是选择那些贝壳花纹长得比较不像Firefox图标的扇贝。

这种状况持续了好几十万代。大家应该也猜到扇贝们身上发生什么事情了：它们的贝壳上都印着很像Firefox图标的图案。

可能有些读者会说：你这不是糊弄我们么，Firefox才有多少年历史，你就搞了个几十万代的扇贝？

确有其事，但是这些扇贝不是真实的，它们在我电脑的内存里边生活。它们是一个遗传算法程序的一部分，这个程序的目的就是用100个半透明三角形把Firefox的图标尽可能像地画出来。

——摘自科学松鼠会，作者方弦

遗传算法是受到达尔文进化论的启发而提出的一种最优化算法，它采用程序模拟自然选择，最终使结果收敛于最优的一种方法。

遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现是某种基因组合，它决定了个体的形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代中根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。

梳理一下遗传算法的思路：

生成初始种群——>计算种群中各个个体的适应度——>淘汰低适应度个体——>余下个体基因交换变异——>生成新的种群——>重复上述步骤

什么是单亲遗传算法？

单亲遗传算法相比遗传算法更为简化，其种群只有一个个体，通过变异产生子代，如果子代适应度更好，那么旧保留子代而淘汰父代。如果子代适应度不如父代，那么就保留父代。然后再进行变异形成新的子代，如此循环以逐步趋近于最优解。

可以看到，单亲遗传算法相比遗传算法效率较低，因为只有一个个体所以没有基因的交换，其收敛全部依靠有益的变异。因此在编写单亲遗传算法时，应格外注意变异部分的编写，使父代的优秀基因有更大的可能保留下来而不是变异掉。

单亲遗传算法规模较小，所以选择先实现单亲遗传算法。另外，单亲遗传算法和模拟退火算法有很高的相似度，如果有兴趣的话也可以了解下模拟退火算法。

梳理一下遗传算法的思路：

生成父代——>变异形成子代——>计算适应度——>保留高适应度的作为父代——>生成新的子代——>重复上述步骤

使用单亲遗传算法能做什么？

我们采用单亲遗传算法绘制Chrome图标看看效果如何，透明三角个数为100个，最后一张图为目标图像。

再绘制几个微信头像看看效果：

不过这里的算法还有一定的缺陷，超过10w代之后的个体就很难再出现有易变异了，即使有更好的子代出现，其改善效果也不是很多。另外，该方法难以模仿线条也是一个严重的缺点。

如何使用Python实现单亲遗传算法？

Python有完备功能强大的画图库可以让我们很轻松的实现功能。实现的思路如下：

首先一个个体是一张图片，由半透明的100个三角形构成。每个三角包括以下基因：颜色和位置。其中颜色包括R、G、B、A。其中RGB代表三个颜色通道，A代表不透明度。位置包括三组坐标，分别对应三角形的三个顶点位置。

计算个体的适应度：采用PIL库绘制图像，用getpixel获得当前个体的像素矩阵和目标的像素矩阵。计算个体和目标三个颜色通道的方差。

变异：设定一定的变异概率，使父代生成的子代有一定的变化（变化不能太大，否则难以收敛）。

前三部解决了，这个算法就没有什么难点了，只需要理清过程，按照上文的思路编写循环，定期保存图片即可。

如果你有什么疑问或者有更好的想法，欢迎在文章下留言讨论。