遗传算法绘制Firefox图标

从前，一群扇贝在海岸边悠哉游哉地生活着。它们衣食不愁，连房子也有了着落，担忧的只有一件事：每隔一段时间，总有人来挖走它们之中的一部分。有意思的是，这个人的家族以Firefox的图标作为纹章，所以他总是选择那些花纹长得比较不像Firefox图标的扇贝。经过几十万代的繁衍后，扇贝壳上的图案逐渐变得与Firefox图标相差无几。

　　这个故事确有其事———它们生活在我的电脑中，是一个遗传算法程序的一部分。程序的目的就是用100个半透明三角形画出Firefox图标。

　　遗传算法是一种解决问题的方法。它模拟大自然中种群在选择压力下的演化，从而得到问题的一个近似解。在上世纪五十年代，生物学家已经知道基因在自然演化过程中的作用了。他们希望能在新出现的计算机上模拟这个过程，用以尝试定量研究基因与进化之间的关系。这就是遗传算法的滥觞。

　　首先，我们把100个半透明三角形组成的东西看成一个生物个体(比如扇贝)，可以说它的样子是由这些三角形的具体位置和颜色决定的。所以，我们可以把一个一个的半透明三角形看做是这些扇贝的“基因”。而组成扇贝的这100个基因就组成了每个扇贝个体的“染色体”。

　　扇贝当然要繁衍后代。生物界中的繁衍无非就是父母的基因组合产生新的个体。所以，我们在程序中选择两个原有的扇贝，然后从这两个扇贝的染色体中随机选取一共100个基因组成新个体的染色体。为了产生新的基因，使基因的种类更多样化，在组合的时候，新的扇贝的基因有一定的概率发生变异。这就是说，其中透明三角形的位置或者颜色有可能发生随机改变。

　　为了使扇贝的样子向Firefox图标靠近，我们要给它们加上一点选择压力：把每一代扇贝中最不像Firefox的淘汰出去。这个选择过程可以通过像素比较来完成。

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

　　好了，现在是万事俱备只欠东风了。定义好基因，写好繁衍、变异、评价适应性、淘汰和终止的代码之后，只需要随机产生一个适当大小的种群，然后让它这样一代代地繁衍、变异和淘汰下去，到最后我们就会获得一个让人惊喜的结果。

　　遗传算法能在相对较短的时间内给出一个足够好、能凑合的答案，它从问世伊始就越来越受到大家的重视，对它的研究也是方兴未艾。当然，它也有缺点，比如说早期的优势基因可能会很快通过交换基因的途径散播到整个种群中，这样有可能导致早熟(premature)。这个问题是难以完全避免的。

　　这也从一个侧面说明，我们不一定需要一个智能才能得到一个构造精巧的系统。无论如何，如果我们要将遗传算法的发明归功于一个人的话，我会将它归功于达尔文，进化论的奠基人。如果我们不知道自然演化的过程，我们也不可能在电脑中模拟它，更不用说将它应用于实际了。

　　向达尔文致敬！　　

“扇贝实验”中的子代输出结果。每个图形下面的数字代表其代数。很显然，最初那些由随机三角形组成的“生物”，在“繁殖”了12万代之后，看起来已经与Firefox图标相差无几了。

from http://tech.sina.com.cn/