博文
原文地址：http://songshuhui.net/archives/10462.html
许可协议：知识共享署名-非商业性使用-禁止演绎
这是个真实的故事。
从前在海岸边有一群扇贝在悠哉游哉地生活繁衍着。它们自然是衣食不愁，连房子也有了着落。它们担忧的只有一件事：每隔一段时间，总有一个人来挖走它们之中的一部分。当然啦，挖回去干什么这大家都知道。但扇贝们不知道的是，这人的家族图腾是Firefox的图标，所以他总是选择那些贝壳花纹长得比较不像Firefox图标的扇贝。
这种状况持续了好几十万代。大家应该也猜到扇贝们身上发生什么事情了：它们的贝壳上都印着很像Firefox图标的图案。
可能有些读者会说：你这不是糊弄我们么，Firefox才有多少年历史，你就搞了个几十万代的扇贝？
确有其事，但是这些扇贝不是真实的，它们在我电脑的内存里边生活。它们是一个遗传算法程序的一部分，这个程序的目的就是用100个半透明三角形把Firefox的图标尽可能像地画出来。
什么是遗传算法呢？
简单地说，遗传算法是一种解决问题的方法。它模拟大自然中种群在选择压力下的演化，从而得到问题的一个近似解。
在二十世纪五十年代，生物学家已经知道基因在自然演化过程中的作用了，而他们也希望能在新出现的计算机上模拟这个过程，用以尝试定量研究基因与进化之间的关系。这就是遗传算法的滥觞。后来，有人将其用于解决优化问题，于是就产生了遗传算法。
那么，具体来说，在计算机里边是怎么模拟进化过程的呢？
我们还是以开头提到的程序为例。
首先，我们知道，生物个体长什么样子很大程度上是由染色体上的基因决定的。同样，如果我们把100个半透明三角形组成的东西看成一个生物个体的话（为了说话方便，称为扇贝吧），我们也可以说它的样子是由这些三角形的具体位置和颜色决定的。所以，我们可以把一个一个的半透明三角形看作是这些扇贝的“ 基因”。而组成扇贝的这100个基因就组成了每个扇贝个体的“染色体”（chromosome）。
从下面的图可以大约看出来这些基因是怎么决定扇贝的样子的（为了观看方便，我们只画出其中五个三角形）：
然后，扇贝们除了生活，当然还要繁衍后代。生物界中的繁衍无非就是父母的基因组合产生新的个体，而在这个程序里边我们当然也这么办：选择两个原有的扇贝，然后从这两个扇贝的染色体中随机选取一共100个基因组成新个体的染色体。如图所示：（仍然是将扇贝看成是五个三角形组成的）
为了产生新的基因，使基因的种类更多样化，在组合的时候，新的扇贝的基因有一定的概率发生变异。也就是说，其中的一个透明三角形的位置或者颜色会随机改变，如图（仍然是五个三角形……我偷工减料……）：
其次，为了使扇贝的样子向Firefox图标靠近，我们要给它们加上一点选择压力，就是文章开头故事中提到的那个人的行动：在每一代把最不像 Firefox的扇贝淘汰出去，同时也给新的个体留下生存的空间。怎么评价这个扇贝像不像Firefox呢？最直接的方法就是一个一个像素比较，颜色相差得越多就越不像。这个评价的函数叫做“适应函数”，它负责评价一个个体到底有多适应我们的要求。
在淘汰的过程中，为了便于编程，我们通常会在淘汰旧个体和产生新个体的数目上进行适当的调整，使种群的大小保持不变。淘汰的作用就是使适应我们要求的个体存在的时间更长，从而达到选择的目的。
最后，在自然界中，种群的演化是一个无休止的过程，但程序总要停下来给出一个结果。那么，什么时候终止演化输出结果呢？这就要订立一个终止条件，满足这个条件的话程序就输出当前最好的结果并停止。最简单的终止条件就是，如果种群经过了很多代（这里的“很多”是一个需要设定的参数）之后仍然没有显著改变适应性的变异的话，我们就停止并输出结果。我们就用这个终止条件。
好了，现在是万事俱备只欠东风了。定义好基因，写好繁衍、变异、评价适应性、淘汰和终止的代码之后，只需要随机产生一个适当大小的种群，然后让它这样一代代的繁衍、变异和淘汰下去，到最后终止我们就会获得一个惊喜的结果：（这回是完整的了，图片下的数字表示这个扇贝是第几代中最好的）
怎么样？虽说细节上很欠缺，但是也算是不错了。要不，你来试试用100个透明三角形画一个更像的？就是这样的看上去很简单的模拟演化过程也能解决一些我们这些有智慧的人类也感到棘手的问题。
实际上，在生活和生产中，很多时候并不需要得到一个完美的答案；而很多问题如果要得到完美的答案的话，需要很大量的计算。所以，因为遗传算法能在相对较短的时间内给出一个足够好能凑合的答案，它从问世伊始就越来越受到大家的重视，对它的研究也是方兴未艾。当然，它也有缺点，比如说早期的优势基因可能会很快通过交换基因的途径散播到整个种群中，这样有可能导致早熟（premature），也就是说整个种群的基因过早同一化，得不到足够好的结果。这个问题是难以完全避免的。
其实，通过微调参数和繁衍、变异、淘汰、终止的代码，我们有可能得到更有效的算法。遗传算法只是一个框架，里边具体内容可以根据实际问题进行调整，这也是它能在许多问题上派上用场的一个原因。像这样可以适应很多问题的算法还有模拟退火算法、粒子群算法、蚁群算法、禁忌搜索等等，统称为元启发式算法（Meta-heuristic algorithms）。
另外，基于自然演化过程的算法除了在这里说到的遗传算法以外，还有更广泛的群体遗传算法和遗传编程等，它们能解决很多棘手的问题。这也从一个侧面说明，我们不一定需要一个智能才能得到一个构造精巧的系统。
无论如何，如果我们要将遗传算法的发明归功于一个人的话，我会将它归功于达尔文，进化论的奠基人。如果我们不知道自然演化的过程，我们也不可能在电脑中模拟它，更不用说将它应用于实际了。
向达尔文致敬！
Bonus：如果你看明白了这篇文章，而且你懂英语的话，你自然明白下面这个冷笑话：（来自http://xkcd.com/534/）
Just to make sure you don’t have it maximize instead of minimize.
PS: 这里可以在线做文中的实验，不过听说对IE的支持有问题。还有就是，你最好睡觉前开始“进化”，第二天一早起来看结果:)
下面是我实验的结果：
天气热了，蚊子多了，感觉人有点懒洋洋的，有时无法做到连续性思考。但是，时间不能让它就那样流失掉，于是决定找部小说看，因为我觉得看小说思考的东西要少一些。不过我想看的那部小说我电脑上存的是CHM格式的，用Firefox打开的话，有点问题，直接用chmsee吧，我感觉那白底黑字，那行距真不像我能长时间阅读的。试着解包得到html文件，结果因为编码问题而产生一系列问题(全世界都用UTF8多好:)。最后决定还是自己排吧，因为机子上我有专门做过适合屏幕阅读的样式文件，所以把文本copy进vim，再编译一下花不了多少时间。在后面的查看结果时，我还真郁闷到了，虽然之前有看过《TeX相关软件中文字体嵌入一个存在已久的问题水落石出，兼谈不拘小节的中文字体设计》，但是PDF阅读器方面也是有问题的，也许是为了照顾中文字体的“不拘小节”，不过阅读器的“自作多情”有时会让情况更糟。
先看使用“华文宋体”的情况，上面是xpdf中的图，下面是AdobeReader中的图。显然AdobeReader中效果要好得多，xpdf中笔画太细，特别是在一些笔画的末端。
这次使用“微软雅黑”，在xpdf中的效果最好，笔画均匀清晰，evince中笔画要粗些就显得比较挤，而且感觉比较虚。最下面的是AdobeReader中的效果，完全毁了- -
最后再看英文的情况，字体使用的是系统中的“AlMohanad”，可以看出AdobeReader中的渲染比较重，不过那个下划线就比较可怜了。
屏幕阅读我最喜欢的字体是“微软雅黑”，可偏偏它在AdobeReader中废了，而xpdf的中文书签我又无解。
KeyJnote是一款辅助演示的软件，即用来播放PDF文档或其它一些图片文档，它提供了加强演示效果的一些功能，如翻页动画、探照灯效果，计时等。
原程序中，鼠标的左右键可以控制KeyJnote翻页，但是，同时，鼠标的左右键也有选取区域，取消区域等其它功能。这样，有时就会感觉控制起来不方便，因为一不小心就会出现“意外”的翻页，所以，我就想翻页只用键盘来控制就好了，鼠标左右键不可以控制翻页。
KeyJnote是用python写的，它的源程序只有一个python源文件，使用locate很容易找到它，在我的系统中，它在：
/usr/share/keyjnote/keyjnote.py
直接编辑这个文件，大约在3086行的位置，找到：
dest = GetNextPage(Pcurrent, 1)
改成：
dest = 0
在3112行左右的位置，找到：
TransitionTo(GetNextPage(Pcurrent, -1))
改成：
TransitionTo(0)
这样，鼠标的左右键就没有翻页的控制作用了。
播放PDF时，加一个-e的参数启动KeyJnote，可以“保持文档的矢量性”。
BTW：在sourceforge.net上的KeyJnote项目页好像出了点问题，本来KeyJnote有放出windows下的“编译版”，这个版本同时包含了需要的dll文件，不过二进制的文件你就无法作上述的hack了。这里是对以前KeyJnote项目的镜像。