本文由 简悦 SimpRead 转码， 原文地址 www.zhihu.com

“欺骗” 深度学习

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 是一个权重，$n_M$n_M 是 M 堆中匹配的字符串，$n_U$n_U 是 U 堆中匹配的字符串。

$fitness(r) = w(n_M - n_U) - length(r)$fitness(r) = w(n_M - n_U) - length(r)

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

有人将这种类型的遗传算法称为遗传编程（Genetic Programming）。种群中一个个体代表一段程序（一段表达式也算一段程序吧），通过遗传算法获得最优的程序，就像算法自己能够编写程序一样。但目前为止，我看到的所有遗传编程的个体都是一段表达式或者一段公式，离 “算法能够编写程序” 差十万八七里。

机器人路径规划

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

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

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

写宋词

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

这里插入一点私货，谈谈我对诗词生成、音乐生成和自动作画的看法。一开始我是不喜欢这一类的研究的，原因有两点：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.

Pirate Henry​

任何需要优化的模型参数求解问题，但是因为参数数量的庞大，用 “穷举法” 的成本高昂。这时，遗传算法是最佳选择。遗传算法中判据的选择、变异的设置、初始的数值都很重要，否则很容易被困在局部最优化。

例如：

物流成本最小化问题。

还有，求解愤怒的小鸟！！ yay!

http://www.zhihu.com/question/19694251/answer/12881985

转自科学松鼠会！！！！！ 科学松鼠会

这是个真实的故事。

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

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

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

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

什么是遗传算法呢？

简单地说，遗传算法是一种解决问题的方法。它模拟大自然中种群在选择压力下的演化，从而得到问题的一个近似解。

在二十世纪五十年代，生物学家已经知道基因在自然演化过程中的作用了，而他们也希望能在新出现的计算机上模拟这个过程，用以尝试定量研究基因与进化之间的关系。这就是遗传算法的滥觞。后来，有人将其用于解决优化问题，于是就产生了遗传算法。

那么，具体来说，在计算机里边是怎么模拟进化过程的呢？

我们还是以开头提到的程序为例。

首先，我们知道，生物个体长什么样子很大程度上是由染色体上的基因决定的。同样，如果我们把 100 个半透明三角形组成的东西看成一个生物个体的话 （为了说话方便，称为扇贝吧），我们也可以说它的样子是由这些三角形的具体位置和颜色决定的。所以，我们可以把一个一个的半透明三角形看作是这些扇贝的 “基因”。而组成扇贝的这 100 个基因就组成了每个扇贝个体的 “染色体”（chromosome）。

从下面的图可以大约看出来这些基因是怎么决定扇贝的样子的（为了观看方便，我们只画出其中五个三角形）：

然后，扇贝们除了生活，当然还要繁衍后代。生物界中的繁衍无非就是父母的基因组合产生新的个体，而在这个程序里边我们当然也这么办：选择两个原有的 扇贝，然后从这两个扇贝的染色体中随机选取一共 100 个基因组成新个体的染色体。如图所示：（仍然是将扇贝看成是五个三角形组成的）

为了产生新的基因，使基因的种类更多样化，在组合的时候，新的扇贝的基因有一定的概率发生变异。也就是说，其中的一个透明三角形的位置或者颜色会随机改变，如图（仍然是五个三角形…… 我偷工减料……）：

其次，为了使扇贝的样子向 Firefox 图标靠近，我们要给它们加上一点选择压力，就是文章开头故事中提到的那个人的行动：在每一代把最不像 Firefox 的扇贝淘汰出去，同时也给新的个体留下生存的空间。怎么评价这个扇贝像不像 Firefox 呢？最直接的方法就是一个一个像素比较，颜色相差 得越多就越不像。这个评价的函数叫做 “适应函数”，它负责评价一个个体到底有多适应我们的要求。

在淘汰的过程中，为了便于编程，我们通常会在淘汰旧个体和产生新个体的数目上进行适当的调整，使种群的大小保持不变。淘汰的作用就是使适应我们要求的个体存在的时间更长，从而达到选择的目的。

最后，在自然界中，种群的演化是一个无休止的过程，但程序总要停下来给出一个结果。那么，什么时候终止演化输出结果呢？这就要订立一个终止条件，满 足这个条件的话程序就输出当前最好的结果并停止。最简单的终止条件就是，如果种群经过了很多代（这里的 “很多” 是一个需要设定的参数）之后仍然没有显著改 变适应性的变异的话，我们就停止并输出结果。我们就用这个终止条件。

好了，现在是万事俱备只欠东风了。定义好基因，写好繁衍、变异、评价适应性、淘汰和终止的代码之后，只需要随机产生一个适当大小的种群，然后让它这 样一代代的繁衍、变异和淘汰下去，到最后终止我们就会获得一个惊喜的结果：（这回是完整的了，图片下的数字表示这个扇贝是第几代中最好的）

怎么样？虽说细节上很欠缺，但是也算是不错了。要不，你来试试用 100 个透明三角形画一个更像的？就是这样的看上去很简单的模拟演化过程也能解决一些我们这些有智慧的人类也感到棘手的问题。

实际上，在生活和生产中，很多时候并不需要得到一个完美的答案；而很多问题如果要得到完美的答案的话，需要很大量的计算。所以，因为遗传算法能在相 对较短的时间内给出一个足够好能凑合的答案，它从问世伊始就越来越受到大家的重视，对它的研究也是方兴未艾。当然，它也有缺点，比如说早期的优势基因可能 会很快通过交换基因的途径散播到整个种群中，这样有可能导致早熟（premature），也就是说整个种群的基因过早同一化，得不到足够好的结果。这个问 题是难以完全避免的。

其实，通过微调参数和繁衍、变异、淘汰、终止的代码，我们有可能得到更有效的算法。遗传算法只是一个框架，里边具体内容可以根据实际问题进行调整， 这也是它能在许多问题上派上用场的一个原因。像这样可以适应很多问题的算法还有模拟退火算法、粒子群算法、蚁群算法、禁忌搜索等等，统称为元启发式算法 （Meta-heuristic algorithms）。

另外，基于自然演化过程的算法除了在这里说到的遗传算法以外，还有更广泛的群体遗传算法和遗传编程等，它们能解决很多棘手的问题。这也从一个侧面说明，我们不一定需要一个智能才能得到一个构造精巧的系统。

无论如何，如果我们要将遗传算法的发明归功于一个人的话，我会将它归功于达尔文，进化论的奠基人。如果我们不知道自然演化的过程，我们也不可能在电脑中模拟它，更不用说将它应用于实际了。

向达尔文致敬！

GA 直接应用就是做优化。有人把 GA 的思想运用到公司管理中，据说也有效果。

遗传算法 - 尘世小迷糊的文章 - 知乎 https://zhuanlan.zhihu.com/p/488047888