17.3 无心插柳柳成荫

真正开始将逻辑程序的进化从理论付诸实践的是约翰·柯扎。他是斯坦福大学计算机科学系的教授,约翰·霍兰德的学生。他和霍兰德的另外几个学生一起使六、七十年代一度被冷落的霍兰德遗传算法重放光芒,进入到八十年代末并行算法的复兴时期。

与「艺术家」西姆斯不同,柯扎并不满足于单纯地探索可能之方程的空间,他想进化出能够解决特定问题的最佳方程。举个牵强一点的例子,假设在所有可能的图像中有一幅图会吸引奶牛凝视它,并由此提高产奶量。柯扎的方法就可以进化出能绘制这一特定图像的方程。在这个例子中,柯扎会对那些所绘图像哪怕只是轻微增加产奶量的方程给予赏奖,直至牛奶产量无法再得到提高。当然,柯扎所选的问题要比这实际得多,譬如,找出一个能操纵机器人移动的方程。

广告:个人专属 VPN,独立 IP,流量大,速度快,连接稳定,多机房切换,每月最低仅 5 美元

但从某种意义上来说,他的搜索方式与西姆斯以及其他研究者的相似。他也在由可能存在的计算机程序组成的博尔赫斯图书馆内搜寻——只不过不是毫无目的地东瞧瞧西看看,而是去寻找解决特定实际问题的最佳方程。柯扎在《遗传编程》[1]一书中写道:「这些问题的求解过程可以重新表述为在可能存在的计算机程序中搜索最合适的单个计算机程序。」

柯扎通过繁衍「找到」方程的想法之所以被认为有悖常理,和计算机专家对雷的进化方案嗤之以鼻的理由是一样的。过去,人人都「知道」逻辑程序是脆弱的,不能容忍任何变动。计算机科学理论中,程序只有两种状态:(1)无故障运行;(2)修改后运行失败。第三种状态——随机修改后还能运行——是不可能的。程序轻度出轨被称为程序漏洞,这是人们耗费大量财力试图避免的。专家们过去认为,如果计算机方程渐进式改良(进化)真有可能的话,也肯定只会出现在少数罕见领域或专门类型的程序中。

然而,人工进化的研究成果出乎意料地表明,传统观点大错特错了。西姆斯、雷和柯扎都有绝妙的证据来证明,逻辑程序是可以通过渐进式改良进化的。

柯扎的方法基于一种直观判断,即如果两个数学方程在解决一个问题时多少有些效果,那么它们的某些部分就是有价值的。如果这两者有价值的部分能被重新整合成一个新程序,其结果可能比两个母程序中的任何一个都更有效。柯扎数千次地随机重组两个母程序的各个部分,希望从概率上讲,这些组合中能包含一个程序,对母程序中有价值的部分做了最优安排,因而能更好地解决问题。

柯扎的方法和西姆斯的有很多相似之处。柯扎的「数据培养液」也含有大约一打用LISP语言表达的数学基元,诸如加、乘、余弦。这些基元随机串在一起形成一棵棵逻辑「树」——一种形似计算机流程图的层次结构。柯扎的系统像繁殖人口一样创建了500到10000个不同的独立逻辑树。「数据培养液」通常在繁衍了大约50代之后收敛到某个合适的后代身上。

树与树之间交换分枝迫使它们产生变种。有时嫁接的是一根长树枝,有时仅仅是一根细枝或枝头的「叶子」。每根树枝都可以被看作是由更小的分枝构成的完整无缺的逻辑子程序。通过分枝交换,一小段方程(一根树枝),或一个有用的小程序,可以得到保存甚至传播。

通过方程进化能解决形形色色的古怪问题。柯扎用它来解决的一个经典难题是如何让一根扫把立在滑板上。滑板必须在马达的推动下来回移动,使倒立的扫帚在板中央保持直立。马达控制的计算量惊人,但在控制电路上与操纵机器人手臂的电路并无多大区别。柯扎发现,他可以进化出一个程序来实现这种控制。

被他用来测试方程进化的问题还有:走出迷宫的策略;二次方程的求解方法;优化连接众多城市最短路径的方法(又称为旅行商问题);在tic-tac-toe[2]一类简单游戏中胜出的策略。在每个例子中,柯扎的系统每次都会去寻找解决问题的一般公式,而不是寻找每一个测试实例的具体答案。一个公式经受不同实例的测试越多,这个公式就会进化得越完善。

尽管方程进化能得出有效的解决方案,可这些方案却往往要多难看有多难看。当柯扎拿起他那些高度进化的宝贝开始查看细节时,他和西姆斯以及雷一样感到震惊:解决方案简直是一团乱麻!进化要么绕上一个大弯,要么钻个七里拐弯的逻辑漏洞抄近道。它塞满冗余,毫不雅致。出了错时,宁愿添加一节纠错程序,或者让主流程改道绕过出错的区域,也不愿销去错误的部分。最后的公式颇有几分神奇的鲁宾·戈德堡[3]连动装置的样子,依靠某些巧合才能运作。当然,它实际上就是架戈德堡神奇连动机。

拿柯扎曾经给他的进化机器玩过的一个问题为例。那是一个由两条互相缠绕的螺旋线构成的图形,大致类似于纸风车上的双重螺旋线。柯扎要求进化方程机器进化出一个最佳方程式,来判定约200个数据点各在互绕双螺旋的哪一条线上。

柯扎将10000个随机产生的计算机公式加载到他的数据培养液里。他放任它们进化,而他的机器则挑选出最有可能获得正确公式的方程。柯扎睡觉的时候,程序树交换分枝,偶尔产生一个运行更好的程序。在他度假期间,机器照常运行。待他度假归来,系统已经进化出能完美划分双螺旋线的答案了。

这就是软件编程的未来!定义一个问题,机器就能在程序员打高尔夫球的时候找到解决方案。但是,柯扎的机器找到的解决方案让我们得以一睹进化的手艺。这是它得出的公式:

(SIN (IFLTE (IFLTE (+ Y Y) (+ X Y) (- X Y) (+ Y Y)) (* X X) (SIN (IFLTE (% Y Y) (% (SIN (SIN (% Y 0.30400002))) X) (% Y 0.30400002) (IFLTE (IFLTE (% (SIN (% (% Y (+ X Y)) 0.30400002)) (+ X Y)) (% X 0.10399997) (- X Y) (* (+ -0.12499994 -0.15999997) (- X Y))) 0.30400002 (SIN (SIN (IFLTE (% (SIN (% (% Y 0.30400002) 0.30400002)) (+ X Y)) (% (SIN Y) Y) (SIN (SIN (SIN (% (SIN X) (+ -0.12499994 -0.15999997))))) (% (+ (+ X Y) (+ Y Y)) 0.30400002)))) (+ (+ X Y) (+ Y Y))))) (SIN (IFLTE (IFLTE Y (+ X Y) (- X Y) (+ Y Y)) (* X X) (SIN (IFLTE (% Y Y) (% (SIN (SIN (% Y 0.30400002))) X) (% Y 0.30400002) (SIN (SIN (IFLTE (IFLTE (SIN (% (SIN X) (+ -0.12499994 -0.15999997))) (% X -0.10399997) (- X Y) (+ X Y)) (SIN (% (SIN X) (+ -0.12499994 -0.15999997))) (SIN (SIN (% (SIN X) (+ -0.12499994 -0.15999997)))) (+ (+ X Y) (+ Y Y))))))) (% Y 0.30400002))))).

这公式不但样子难看,而且还令人费解。即使对一个数学家或一个计算机程序员来说,这个进化出来的公式也是一团乱麻。汤姆·雷说,进化写的代码只有喝醉酒的人类程序设计员才写得出来的。依我看,说进化生成的是只有外星人才写得出来的代码恐怕才更确切些。这绝非人类所为。对这个方程追本溯源,柯扎终于找到了这个程序处理问题的方式。完全是凭着百折不挠和不择手段,它才打通了一条艰难曲折又令人费解的解决之道。但这确实管用。

进化得出的答案看起来很奇怪,因为几乎任何一个高中生都能在一行内写出一条非常简洁优雅的方程式来描述这两条螺旋线。

在柯扎的世界里没有要求方案简洁的进化压力。他的实验不可能找到那种精炼的方程式,因为它并不是为此构建的。柯扎试着在运行过程中添加点简约性因素,却发现在运行开始就加入简约性因素会降低解决方案的效率。得到的方案虽然简单却只有中下水平。他有证据表明,在进化过程末期加入简约性因素——也就是说,先让系统找到一个管用的解决方案,再开始对其进行简化——这是进化出简洁方程更好的方法。

但柯扎坚信简约的重要性被过分高估了。他说,简约不过是「人类的审美标准」。大自然本身并不特别简约。举个例子:时为斯坦福大学科学家的戴维·斯托克分析了小龙虾尾部肌肉中的神经回路。当小龙虾想逃走的时候,其神经网络会引发一个奇怪的后空翻动作。对人类来说,那种回路看起来如巴洛克建筑那般繁复,取消几个多余的循环指令马上就可以使它简化一些。但那堆乱七八糟的东西却很管用。大自然并不会只为了优雅而简化。

《遗传编程》:Genetic Programming,

tic-tac-toe:一个很有名的益智游戏。弈者在井字形的九个方格上轮流落子,三点连成一条直线(横、竖、斜均可)的一方获胜。只要弈法得当,双方一定会以和局结束。

鲁宾·戈德堡(Rube Goldberg):美国漫画家,画了许多用极其复杂的方法完成简单小事的漫画。比如把鸡蛋放进小碟子这种事,在戈德堡笔下可能是这样的:一个人从厨房桌子上拿起晨报,于是牵动了一条打开鸟笼的线,鸟被放出来,顺着鸟食走向一个平台。鸟从平台摔到一灌水上,水灌翻倒,拉动扳机,使手枪开火。猴子被枪声吓得把头撞在系有剃刀的杯子上,剃刀切入鸡蛋,打开鸡壳,使鸡蛋落入小碟子中。——摘自「中文维基百科」