我如何孵育我的加法虫

（按：这是我三年前闲得发慌，业余学习进化生物学时，所作的课后练习，拿出来献丑，权当是山寨版进化算法的科普作品吧，呵呵）我如何孵育我的加法虫辉格 2005年08月05日在阅读Richard Dawkins的 The Blind Watchmaker 时，我产生了一个冲动，想写个程序来孵育出某个有趣的东西。我考虑了几种东西，包括诸如善于从井里粘食蚂蚁的长舌虫、会学舌的鹦鹉、会啃文字的书蠹，等等。但是，在评估了这些目标的难度，和这种难度与我的能力之间的差距之后，我选择了一个简单的电子产品——加法虫——一种会做加法的虫子，作为我的指望能勉强交差，同时又能满足我的好奇心的课后作业。所谓加法器，就是一种具有这样能力的装置：当它获得两个输入的整数后，便输出另一个整数，其值等于前两个整数之和。为了简化问题，输入／输出的整数的长度需要有所限制，比如，一个32位加法器能进行输出值介于0～4294967295（或-2147483648～2147483647，以下讨论都不考虑负数）的加法运算，而一个8位加法器只能进行输出值介于0～255的加法运算。正如往常那样，我希望最大限度的偷懒，经过斟酌，我选择了3位加法器作为我的孵育目标。为什么不干脆选择1位加法器呢？哈哈，本来我是想这么干，但我很快发现（料想得到，如果你刚好是个数字电路这门课考得不错的工科生，一定在暗自窃笑我的愚笨）1位加法器实际上就是一个异或门（XOR gate），而它和其它三种门电路——正如我将要说明的，恰好是我打算用作我的孵育工作的原料。于是我转向2位加法器，也就是输出数有两个比特位，但这样一来，为了不让结果“溢出”，输入数就只能有1个比特位了，我担心这样是否过于简单，以至于我准备使用的那些原料稍一凑巧就能组合出我想得到来的东西，从而使我精心策划的孵育行动显得平淡无奇。这样，我最终选定了3位加法器，我相信它已足够有趣，因为很容易发现（因为连我也很快发现了）：这种小的加法器经过简单的重复串接，可以组成任意位数的大的加法器；并且我猜想它也将足够复杂，不至于被我的原料们轻易凑巧拼出来。我就这样开始干起来。首先，我假定存在这样一种虫子，它的某一段（如下图，不妨叫它尾巴）的两侧各有4个点，我们称上面的为输入点，下面的称为输出点（就我们的饲养目的而言，只需要三个输出点，我放上第四个只不过为了满足我对对称性的偏好，今后当我们评估这些饲养产品的性能时，自然可以对这个点的状态不予考虑）。在上下两层之间，有着一些特别的“丫”状颗粒（如下图，你可以叫它丫头或者三毛，随你喜欢），它们在虫子生长过程中，可能会从它们的两个“上枝丫”上长出一根枝条连接到其他丫头的“下枝丫”或者某个输入点上，至于某个丫头的某个上枝丫是否长出枝条以及连到哪个点上，由基因G决定。和丫头们一样，那些输出点也会长出枝条（不过每个点只有一个）连接到某个丫头的下枝丫或者某个输入点上，至于与谁连接，同样由基因G决定。为了方便，我决定在每个虫子尾巴里放进28个丫头。输入点上时常会受到一些刺激（比如光照），当某个点受到刺激时，我们称其状态为“1”，未受刺激时则称为“0”；类似地，每个丫头的下枝丫也有两种可能状态（０和１），它取决于其两个上枝丫所连接点的状态，决定的方法由丫头本身的性质而定。有四种丫头，对应四种决定方法，分别称为：“非”、“与”、“或”、“异”（我想不需要解释他们的含义了，只有一点需要指出，“非”丫头的下枝丫状态只与其左上枝丫所连接点的状态有关，其右上枝丫可视若无物）。至于一个丫头到底长成哪种类型，也由基因G决定。输出点总是黑色的（称为0），除非它们长出了枝条连接到某个状态为1的输入点或下枝丫上，这时它是白色的（称为1）。现在来看看我们的基因G。它存储了356bit的信息，其中56个将决定那28个丫头的类型（每个丫头需要两个，因为一共有四种类型），另外300个将决定60个点（28个丫头的56个上枝丫加上4个输出点）是否长出枝条并伸向何方，每5个bit决定1个点，5bit组成一个0～31的整数，其中0表示“没长枝条”，其余分别表示长了枝条并指向第i个点（若i<=4，它是第i个是输入点，若i>4则是第i-4个是丫头的下枝丫（你或许已经发现，这样第28个丫头永远都不会被指到，因为我数错了数，把那个0给漏了，哈哈！不过这无关紧要，因为我是饲养员，不是电子工程师。在我这个老大粗的眼里，27个和28个丫头一样——看起来差不多够用了）。在开始我们的饲养工作之前（是不是等得不耐烦了？），还有几桩小事要做。首先，我的虫群每隔一段时间有一个繁殖季节（实际上，隔多久取决于我的PC的性能和我作为程序员的水平，哈哈），两个繁殖季节之间，他们每个将遭遇N次生活的考验（我把这个N叫做考验频率）。所谓一次考验，抽象地说，就是这样一个过程：他接受一个输入，并形成一个反应（包括毫无反应的反应），然后他的反应和输入之间的关系将被评估，评估的结果可能导致两种影响：1）可能影响他在下一个繁殖季节到来之前继续生存的机会；2）可能影响他在下一个繁殖季节中的生殖能力。（当然，实际上还存在着对进化过程起作用的第三种影响，即他在其后代或血缘近亲需要其帮助的期间继续提供帮助的能力，但在这里我暂时将其忽略。）举个例子，对于一只猴子而言，它附近某棵树上掉下一只苹果这一事件就形成了一次对它的考验，假设他作出了这样的反应：伸手抓住苹果并吃进肚子里，那么自然选择的价值函数将给他打出一个正分；如果他的反应是：对着苹果勃起他的生殖器，他很可能得到一个负分（如果小鸡鸡不幸被苹果打中的话）。所以，重要的是，我们的饲养间应该能提供这种考验，并对考验的结果作出评估，再用评估的结果去影响受考验者在本繁殖周期中的生存机会和生殖能力。幸好，我们的饲养任务很简单，对一个加法器的考验无非就是让他算算看，而评估的方法就是看看算得对不对，恰好，我的饲养间外面那个大房间正以长于此道而著称。如果我的目标是32位加法器，那么用来选择考题的题库就很大（共4294967295道题），这样，只能每次抽取N个考题用作考验（N=考验频率），但目前我们的题库很小，一共才16道题，所以我决定，把N设为1，即每个繁殖周期内每人（应该说每虫）只考一次，每次把所有16道题都做一遍，而且凡旧虫都不需要做（所谓旧虫就是在上个繁殖季节后幸存下来的那些个体），因为他们在上个季节中已经把所有题目都做过了，分数继续有效——多么省力的饲养工作啊！但还是有个问题需要作出决定——我应该使用什么样的价值函数呢？或许我应该做个严格的考官：16道题全部做对得满分，否则零分。但这样的话，我所指望看到的一个完美的加法虫在进化过程中从一开始那堆胡乱堆放的“丫头”中浮现出来的美景，便成为一种“单步选择”了，正如Dawkins所指出，这不是达尔文所说的进化，而是达尔文的反对者们所描绘的那种猴子跳键盘舞敲出莎士比亚妙句的故事。不，我可不想让猴子在我的饲养间里跳舞！我需要的是一种“渐进选择”，一种达尔文式的进化。我最初的想法是一种“彻底的”渐进改进激励函数，即，只要算对一个bit位就给分，每道题的三个输出位上对1个得0.25分，对2个得0.5分，3个1分（第4个bit不予考虑），但后来不知何故我没采用这种方法（大概是因为我出去吃了碗拉面回来时忘了这个念头，讨厌的拉面！）。现在，我的价值函数是这样的，16道题每做对1道给0.0625分，哈哈，无比简单。我不知道这个函数能否形成一条有效的激励途径，将我的虫子引向某条最终让他变成完美加法虫的光辉道路，听天由命吧。现在，我必须建立一个夏娃，即那最初祖先虫个体。我的夏娃很特别——她基因的每个bit全是0，（我不知道用一个随机数是否会好一点，不过从0开始演化的过程看起来更有趣），翻译成16进制码（每位16进制码对应4个bit位）就是： 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 然后，我让她开始繁殖。这时的问题是：应该如何决定一个虫子在某个繁殖季节里该生几个孩子？我认为需要确定一个数字，叫做基准生殖率，意思是那些在本季节的考验中表现中等的个体在当季的生殖率，那些表现较优的个体的当季生殖率将被一个指数函数放大，函数的底是他的本季效能数（我用这个数字来存储他在考验中被评估的结果，其值介于0~1之间，随其表现而渐近于1），函数的指数叫作生殖指数，它表明了考验中表现差异在生殖竞争中被放大的程度。上述运算得到的数字就是该虫在当季被批准的生育数。当然，这个数字可能是各小数，但半个孩子是没用的，解决的办法是抛硬币，比如，经过计算，虫甲本季被允许生1.7个，意思是，他可以先生下一个，至于能否生第二个，向0和1之间抛个硬币，如果硬币落在0.7左面，就可以生第二个。这就是一个繁殖季节里发生的生殖游戏，但这不是游戏的全部，生产过后就是死亡，部分虫子必须死去，谁存谁亡，同样由抛币决定，但机会并不均等，同样因虫们在生存考验中的表现而异，不必赘言。需要解释的是，该死多少虫？和生殖不同，我们不需要预先确定一个死亡率，只需要确定一个大致的种群规模限制，黑话叫“马尔萨斯极限”——正如这位哲人所指出，虫子没那么多不是因为他们不会生，也不是因为他们到时间就会死，而是因为他们总是被压制在资源所允许的数量之下。所以死亡率是个多余的概念——至少在避孕套发明之前，——而我，勤恳的虫子饲养员，不会慈祥到向它们发放Durex（哈哈，说的兴起，差点忘了我的虫子乃无性繁殖一族），另外我也要为我那台破PC担心，所以我决定，把种群规模限制在20000。如果夏娃的每个后代都与她一模一样，那么我的饲养间将不能产生任何新东西了，必须让基因在繁殖过程中有所变化，现实生物界的基因变异率是极低的，但考虑到我们小得可怜的种群规模和我那台破PC的速度，我只好把他调高一点（不好意思，大概高了几十万倍），这样做的代价可能是每代新生个体中出现很多劣化的（在那个价值函数看来）变异，但我希望生殖和生存优势足以扩散和维持既有的优势变异，同时及时驱除劣化变异，后来的情况表明，他做到了。一个新生虫降临时，抛币和给定的变异率将决定它是否变异，如果他被决定变异，则再次抛币（在0和1之间）以决定他的基因中有几个bit位将被改变，比如抛出的值是X，将有Max(1,Log2(1/X))个bit位被改变，这样安排是为了提供一种使多个bit位被同时改变的机会（虽然几率被限制得很低），借此暗暗指望一些奇妙的突变成为可能。在啰嗦了半天之后，好戏终于开场了（别走开，待会儿收赞助）。夏娃开始繁殖。在前几代中，没有什么引人注意的事，变异的确发生了，但结果看上去（黑话叫表现型（phenoype））很无聊，比如夏娃又这样一个孙女：图下面那串数字是基因的16进制码，他的某个bit位上的变化导致了从20号丫头的左辫角上伸出一条线连接到0号输入点，在电子工程师眼里，这当然毫无意义。所以这些孙女的成绩都停留在0.0625上——不是0，因为他们至少做对了一道题目：0+0=0。这样无聊的日子过了五代，这时，有了变化，我发现出现一个基因并且迅速扩散，因为他的成绩达到了0.125，表明他做对了两道题，紧接着另一个家伙出现，并且扩散势头迅速盖过前一个，他的成绩是0.1875，做对了三道。这立即引起了我的注意，我把程序停了下来看个究竟，下面就是那两个家伙（注意：他们只是这群虫子里取得同时最高成绩的那些众多个体中任意抽取的两个，这些个体的基因和表现型并不相同，但成绩相同，以后的例子也是这样）：第一个家伙把0号输出点跟一个“非”丫头连起来，而那个丫头没有输入，在我的规定里，没有输入就是0，所以他的输出永远是1。这家伙因此不能就算不对0+0=0，但是，在付出这样的代价之后，它现在能蒙对两道题了：0+1=1；1+0=1——因为他的输出永远是1——哈哈！说他是蒙对的没人会有意见吧？第二个家伙看上去高明不了多少，只不过他连到“非”丫头上的是1号输出点，因此就能蒙对三道题：0+2=2；2+0=2；1+1=2。如果你还没晕倒，说明你不是电子工程师——和我一样。作为饲养员，我乐于看到这两个撞上大运的家伙吃得白白胖胖，多子多孙。不过我也不免生出一丝担心，如此这般瞎蒙乱撞，真能有朝一日修成正果吗？为了自我安慰，我给这两个家伙的做法取了个名字——“消极适应”，就象整天下雹子的地方，有些人学会如何对雹子的出现和坠落作出反应，这是“积极适应”，而另一些人则变得深居简出——永久性的改变自己的状态，我叫它“消极适应”，虽然消极，也是适应。然而问题在于，就我当前的饲养目的而言，这种消极适应存在一个极限：最多做对四道题。这还不是最糟糕的，根本的问题是，这种适应性变异不具有可累积性。从做对一道题到做对四道题的变迁中，每一阶段并没有从前一阶段的改进中获益，我们已经知道，这不是我们期望看到的进化过程。因此，当虫子们在第8代达到了消极适应的极限后，便陷入了长期的停滞状态。我注视着屏幕上不断刷新的数据，基因的16进制码变得越来越复杂，图案上的线条越来越纷繁杂乱，但是效能指数一直停留在0.25上，丝毫没有动静，只有一个指标好像在稳步增长，它是“多样化率”，它一直增长到大约0.75左右，然后稳定下来。我的迫切和憧憬渐渐被枯燥和无奈所侵蚀，我决定到沙发上睡一觉，而让虫子们自己去连续繁衍上300代（按前面的情形，这大概要花上几个小时）。当我从沙发上跳起来，揉著眼屎去拍醒那个休眠的太深的显示器时，我的急切心情是想必可以被原谅。我没有失望，在第151代，曙光出现了，成绩达到0.5，然后紧接着在第165代，达到0.625。下面就是那条被我叫做G0151的宝贝虫子： G05=XOR(X2,X0) Y0=G05 Y1=X1 Y2=X3 Y3=X3 他的线条已多得难以辨认，所以我在图右边列出了它的逻辑表达式，以便于看清它是如何工作的。表达式中的Xi和Yi分别对应输入和输出点，Gi对应丫头。我惊喜的看到，他学会了使用“异”门，而且把它用在可以立竿见影的地方——他把两个输入数的第一个bit位用“异”门（G05）连起来，并输出给输出数的第一个bit位，而这恰是1位加法的正确做法，这样它保证了Y0位的结果永远是正确的，正是这一点大大提高了他的成绩。对异门的使用是个关键的突破，不只是因为成绩的提高，重要的是，这一改进是可累积的，G0151的下一个创新者G0165继承了它，不仅如此，这一突变结果一直被保留到我的饲养工作的终点（当然，我后来才知道这一点），“G05=XOR(X2,X0)”和“Y0=G05”这两行，一直牢固的占据着后来所有幸存者的基因里相应的那17个bit。 G0165的进步在于，他在尝试使用门电路来改进Y1位的运气上获得了部分成功，在这个位上先前的方法是直接与X1相连，可以蒙对8个（一半），改进后的方法能蒙对10个，当然地，自然选择对此加以鼓励。下面是他的逻辑表达式： G02=AND(X1,G04) G04=NOT(X3) G05=XOR(X2,X0) Y0=G05 Y1=G02 Y2=X3 Y3=X3 我们发现在这两次改进期间，实际上（后来发现），自从G0151之前100多代直到第521代之前，对Y2位的处理没有什么变化，实际上，它一直被直接连在X3上。其实原因很简单：找出更有效的复杂方法之前，这种简单做法已经够好了——能蒙对12个！在Y1上的改进直到第399代才有获得突破，G0399能蒙对12个，表达式如下： G01=XOR(G10,G17) G02=AND(X1,G20) G04=AND(0,G13) G05=XOR(X2,X0) G06=OR(0,G12) G10=AND(X2,G06) G12=NOT(G14) G13=NOT(G05) G14=NOT(X0) G17=OR(G04,X3) G20=NOT(G01) Y0=G05 Y1=G02 Y2=X3 Y3=X3 如你所见，该虫为了多蒙对两个，走了多少弯路！几乎用尽了我所限定的递归深度（9层）。尽管差异很大，但在G0399的表达式里，我们仍然能看到G0165的身影：“Y1=G02”和“G02=AND(X1,G20)”。同时，来自宝贝G0151的那宝贵的两行，“G05=XOR(X2,X0)”和“Y0=G05”，仍在那里，丝毫没动，被自然选择盛情挽留。我全部希望所倚靠的“可累积性”看来正在得到验证。在Y1上的改进最后G0521完成，表达式如下： G01=OR(0,G16) G02=XOR(X1,G21) G05=XOR(X2,X0) G12=NOT(G14) G14=OR(G05,G01) G16=NOT(X0) G18=XOR(0,G02) G21=XOR(G12,X3) Y0=G05 Y1=G18 Y2=X3 Y3=X3 在观看G0521的表达式时，我突然感到一种深深的不安，它和G0399一点也不像，好像是个突然冒出来的野小子，我的“可累积性”似乎在被动摇。在仔细检查了我的数据后，疑团终于解开：G0399的优势变异看来灭绝了，他那带来改进的变异还没来得及在种群中扩散开，就被新的变异所覆盖，这要归咎于我把变异率定的太高。不仅如此，我发现，同等效果的变异实际上灭绝了三次，他们分别来自：G0399，G0400，G0481，幸而，G0484的同效变异没有灭绝，它是这样的： G01=OR(0,G16) G02=AND(X1,G21) G05=XOR(X2,X0) G14=OR(G05,G01) G16=NOT(X0) G18=XOR(0,G02) G21=XOR(G14,X3) Y0=G05 Y1=G18 Y2=X3 Y3=X3 瞧！他和G0521是不是像极了？！“可累积性”被挽救了！到此为止，Y0和Y1已经被解决，进一步改进的可能性只能是拿Y2开刀，这家伙长期以来凭着他能蒙对12道题的本事而养尊处优，现在，他的好日子到头了。在这个新大陆第一个挖到金子的是G0576： G01=OR(0,G16) G02=XOR(X1,G21) G05=XOR(X2,X0) G08=AND(X1,X3) G12=NOT(G14) G14=OR(G05,G01) G16=NOT(X0) G18=XOR(0,G02) G21=XOR(G12,X3) Y0=G05 Y1=G18 Y2=G08 Y3=X3 他蒙对14道题。然后是G0615： G01=OR(0,G16) G02=XOR(X1,G21) G05=XOR(X2,X0) G07=AND(X1,G12) G08=AND(X1,X3) G12=NOT(G14) G14=OR(G05,G01) G16=NOT(X0) G18=OR(0,G02) G21=XOR(G12,X3) G24=OR(G07,G08) Y0=G05 Y1=G18 Y2=G24 Y3=X3 15道。还差一道。最后，在经过了659代繁衍之后，我期待已久的那只“完虫”出现了——G0659： G01=OR(0,G16) G02=XOR(X1,G21) G05=XOR(X2,X0) G06=XOR(G12,X1) G07=AND(X1,G12) G08=AND(G06,X3) G12=NOT(G14) G14=OR(G05,G01) G16=NOT(X0) G18=OR(0,G02) G21=XOR(G12,X3) G24=OR(G07,G08) Y0=G05 Y1=G18 Y2=G24 Y3=X3 我凝视着屏幕上我那只“完虫”的图案，贪婪的享受着它带给我的愉快，然后逐个bit的对照，逐条逻辑的测试，以便确信我的愉快并非建立在沙子上。据说J. von Neumann当初用六个元件就搭出了一个加法器，而我的虫子则乱糟糟整个一团乱麻，Neumann是个大数学家，对于他那简洁漂亮的加法器，他就是上帝，他设计了它，制造了它，向它吹了一口气，于是它就有了活力；而我，只是个饲养员，我甚至连教练都不是，我没有向虫子们传授任何有关加法的知识和技能，我做的唯一的事情就是勤奋的批阅考卷，并冷酷无情的削减那些得低分者的生存和生殖机会，只为一个自私的目的——获得一条加法虫。现在，瞧，——他就在那里。