遗传算法系列之二:“欺骗”深度学习的遗传算法

这篇博客主要介绍不同问题的遗传算法。

遗传算法是通用的全局优化算法，因此有很多的应用。有很多应用我是看不懂的，比如机器人步态优化。机器人步态优化应该蛮有趣的，B站视频在此，可惜看不懂。有哪位读者了解相关知识，欢迎科普。另外有一些应用人们已经讨论很多了，比如0-1背包问题、旅行商问题和装箱问题。这里就不做介绍。这篇博客介绍一些我能看懂的有趣应用。

“欺骗”深度学习

Szegedy et al. (2013) 发现虽然深度学习模型在图像物体识别任务已经达到甚至超过了人类水平，但深度学习模型很容易被愚弄(fooled)。下图是论文中的例子，左列的图经过中间的变换成右列的图。对我们人类来说，变换前后图片几乎没有变化，判对左列图片的深度学习模型却将右列图片都判错了。这说明人类和深度学习模型之间的区别还有很多。

Nguyen et al. (2014) 用报告了另一种结果：我们能够产生一组对人类完全没有意义的混乱图片，深度学习模型却会将它们高分值判断图片为某一物体。遗传算法便是产生这样混乱图片的方法之一。论文中使用了不同的编码方式，我们介绍在MNIST数据集上的简单编码方式。种群中个体代表一张MNIST图片，个体中一条染色体长25

25，染色体每一位基因代表了图片对应位置的像素灰度。个体适应度等于深度学习模型将图片判读为一个数字的置信度。下图就是这种编码方式产生的结果。我们人类看下图中的图片，完全就是一片混沌，但state-of-the-art的深度学习模型却以超过99.99%的置信度将它们判断某个数字。

正则表达式生成器

Regex Golf 是一个正则表达式生成竞赛。这个竞赛给两堆字符串M和U，要求参数者给出的正则表达式r尽可能地匹配M堆中的字符串，和尽可能地不匹配U堆中的字符串。下图就是竞赛的示意图。

Bartoli et al. (2014)提出用遗传算法解决这个问题。种群一个个体是一颗正则表达式树，如下图所示。正则表达树的叶子节点是一些从M堆字符串抽取的字母和N-grams。正则表达式树的中间节点是正则表达式的符号，比如“()”、“*”和“?”。

个体对应正则表达式匹配越多M堆字符串，个体适应度应该越大。个体对应正则表达式匹配越多U堆字符串，个体适应度应该越小。因此可以直接用（匹配M堆字符串数量-匹配U堆字符串数量）作为适应度。但这样的话，得到的正则表达式的长度会很长。为了控制正则表达式长度，适应度应该惩罚长的正则表达式。因此我们可以用下面的适应度，其中w是一个权重，

是M堆中匹配的字符串，

是U堆中匹配的字符串。

(1)

下表是Bartoli et al. (2014)报告的结果。其中 Norvig-RegexGolf 是一种基线方法，GP-RegexGolf是作者提出的方法，GP-RegexExtract是应用在Text Extraction任务上的遗传算法。

image.png

有人将这种类型的遗传算法称为遗传编程（Genetic Programming）。种群中一个个体代表一段程序（一段表达式也算一段程序吧），通过遗传算法获得最优的程序，就像算法自己能够编写程序一样。但目前为止，我看到的绝大部分遗传编程都是 toy system，离“程序能够编写程序” 还很远。

机器人路径规划

机器人路径规划是遗传算法很传统的应用之一，很多地方都有讨论。不过对我们这些不搞机器人的人来说，路径规划还是蛮有意思的应用。机器人路径规划技术, 就是机器人根据自身传感器对环境的感知, 自行规划出一条安全的运行路线。下图是用栅格表示的机器人路径规划环境，栅格是最简单的路径规划环境表示方法。图中的路线就是机器人的前进路线。

image.png

遗传算法中的一个个体代表了一条路线。个体染色体有起始点和终止点，起始点和终止之间是机器人的中间停靠点。上图中的路线可以用下面基因序列表示。个体适应度随着路线长度增加而减小。有些路线并不合法（比如穿过障碍物），这时候相应个体的适应度需要加一个惩罚项。

应用于机器人路径规划的遗传算法有很多问题，也就是说有很多改进的空间。比如，变异过程有可能将路线中间点变到障碍物里。我们可以用一些改进的变异操作避免这个问题。Tuncer and Yildirim (2012) 就提出了一种新的变异操作解决这个问题。这个变异操作的大体思路是先将中间点随机变异，然后检查变异的中间点是否在障碍物内，如果是则选择一个附近位置。下图就是这种变异操作的示意图。

image.png

写宋词

这里介绍一个奇技淫巧——周昌乐等(2010)用遗传算法写宋词。在这项工作之前，作者已经建立了一个包含情感类别、语法、语义、音韵等要素的元数据库。种群中一个个体代表了一首词，不同的基因位是不同词。个体代表的一首词的适应度由句法和语义加权获得。由于我对诗词没有啥了解，就不多瞎说了。感兴趣的读者可以直接阅读论文。下表是论文中报告的结果。

image.png

这里插入一点私货，谈谈我对诗词生成、音乐生成和自动作画的看法。一开始我是不喜欢这一类的研究的，原因有两点：1）现在的弱人工智能根本没有发展到吟诗作画的程度，2）这些东西根本没啥用处好吧。不过后面我的观点改变了。现在我的观点是有些研究就是玩啊。这时候我们只需要问有趣吗，而不需要问有用吗。反正这个话题那么有趣，那就继续玩咯。正是有些研究不是冲着有用，而是冲着好玩去的，科学的未来才有无限可能。

某些蛋疼的例子

当然不是所有问题都适合使用遗传算法的。比如很多年前，石三石跟我介绍了一篇国内论文，那篇论文用遗传算法优化k-means聚类的k值。你没有看错，是k-means聚类算法的k值。我当时还不相信，觉得那篇论文应该是优化k-means初始化的值。三石同学还和我确认是k-means聚类算法的k值。他和我对着那篇论文默默吐槽了。我虽然不知道k-means聚类算法k值的选择有什么办法，但我知道遗传算法是绝对不行的。因为我把k值从1到n(n为待聚类的样本数量)全部试一遍的时间，时间和遗传算法的运行时间差不多吧。另外那篇论文的适应度是用 (类间距离的均值)/(类内距离的均值) 衡量的。k设为n时，这个指标肯定是最大的啊。

另外一个例子是用遗传算法调神经网络参数。这个例子倒是常见，比如Matlab就是支持。具体做法可以参考这个网页。遗传算法个体中一条染色代表了一组参数，个体适应度等于用这组参数训练的神经网络在验证集上准确率。在十几年前，神经网络和其他分类算法面对的是小规模的数据。因此训练和预测的时间比较少，这种方法是适用的。但现在神经网络面对都是大规模的数据，训练时间很长。有些神经网络需要一天时间训练，如果遗传算法初始种群有100个个体，光是计算这个一百个个体的适应度就需要100天。遗传算法调参显然是不实用的。

第一次在博客中列参考文献

Bartoli, Alberto, et al. “Playing regex golf with genetic programming.” Proceedings of the 2014 conference on Genetic and evolutionary computation. ACM, 2014.

Nguyen, Anh, Jason Yosinski, and Jeff Clune. “Deep neural networks are easily fooled: High confidence predictions for unrecognizable images.” arXiv preprint arXiv:1412.1897 (2014).

Szegedy, Christian, et al. “Intriguing properties of neural networks.” arXiv preprint arXiv:1312.6199 (2013).

Tuncer, Adem, and Mehmet Yildirim. “Dynamic path planning of mobile robots with improved genetic algorithm.” Computers & Electrical Engineering 38.6 (2012): 1564-1572.

周昌乐, 游维, and 丁晓君. “一种宋词自动生成的遗传算法及其机器实现.” Journal of Software 21.3 (2010): 427-437.