互动科普

颠覆专利的遗传编程

John R. Koza, Martin A. Keane, Matthew J. Streeter

进化是拥有无限创造力的过程。从单个细胞的复杂生化组成到精细的人类大脑结构，进化产生了无数复杂得难以想象的奇迹。通过许多世代的重复，进化依靠突变、有性繁殖和自然选择这些简单的方式实现了伟大的成就。如今，计算机程序员利用这些方法的软件版本，实现了名为遗传编程的机器智能。利用这项技术，已经设计出了能完成某些特定功能的计算机程序和电子电路。

在电子学领域，遗传编程已经复现了15项此前已获得专利的发明。其中有几项在当初提出时受到欢呼，被认为极具前景[参见45页的表格]。这15项发明中有6项是在2000年1月以后由主要研究机构授予专利的，这标志着无论是从纯科学还是从应用的角度来看，它们都代表了当今科学研究的最前沿。在这些复现的发明中，有一些由机器自动产生的发明直接颠覆了原先已获得专利的发明的权利，其他的一些则通过全新的方式复现了原先的设计功能，因此构成了新的发明，还有一个则对原先的产品有明显的改进。

遗传编程还对蛋白质序列进行了分类，并在许多领域产生了足以与人类智慧相媲美的成果，例如天线设计、数值算法以及通用控制器等。我们最近提交了一个涉及遗传编程的通用控制器的专利申请，它的性能比工业中常用的由数字驱动的控制器更为优越。

遗传编程获得实际应用的第一个商业领域也许是设计。从根本上来说，设计是工程师们一天8小时都在干的活，而这也正是进化要干的活。设计特别适合遗传编程的应用，因为对于它所涉及的那些棘手问题，人们总是努力寻求一些非常好但并非最完美的解决方案。通常而言，对那些彼此矛盾的各种因素必须采取复杂的折衷平衡，而如何在各种因素之间达到最佳的平衡可不是一件容易事。最后，设计通常涉及对事物的拓扑学安排(与仅仅优化一组数字形成对比)，而这正是遗传编程最擅长之处。

人类工程师总是倾向于用某些特定的方式看问题，经常是基于理想的数学模型。遗传编程提供了超脱狭隘思维方式的优点。进化对基本的数学一无所知；它所做的不过是努力寻找一系列越来越好的结果。因此，我们常常从进化的结果中看到很多极具创造力的东西，而这些可能是人类设计师永远也想不到的。

遗传编程中的进化生物体

无论应用于何种领域，遗传编程的起始阶段总是由一些随机产生的尝试性的“生物体”所形成的原始形态和一个对这些生物体要完成的功能的高级描述所组成。这个描述就是对这些生物体的适应度进行评价的标准。例如生物体是一些基本数学函数，而我们的目的是寻找一个其图形与某一给定曲线相吻合的函数。在这个例子里，生物体是由数字常量和加、减、乘、除这样一些基本操作所构成。某一函数的适应度就取决于它的图形与给定曲线的吻合程度。

遗传程序在群体中考察每一个数学函数的适应度。那些最初产生的随机函数当然与目标曲线的吻合度很差，但总有一些要比另一些好。遗传程序总是在群体中剔除那些最差的函数，然后对剩下的那些函数进行遗传操作以创造后代。最重要的遗传操作是有性繁殖(又称交叉)，这种操作对两个较好的生物体进行配对并繁殖包含双亲遗传物质的后代。例如，将函数(a+1)一2和1+(a×a)进行配对，就有可能用第一个函数里面的(a+1)替换第二个函数里的一个a，这样产生的后代就是1+[(a+1)×a]。按照这种方式将两个相对适应的生物体的性状合并，就有可能产生更为优良的后代。

除了有性繁殖之外，遗传程序选取约9％的第一代适应度最好的个体，然后不做任何改变地复制到下一代中。通常这将保证每一代中最好的那些生物个体至少会与上一代中最好的那些生物个体具有同样的适应度。此外，约有1％的个体将发生突变——例如，a+2有可能突变成为(3×a)+2——希望通过对某一个相对适应的个体的随机修正能增加它的适应度。

通过这些遗传操作逐渐产生了一个改进的数学函数群。通过很多世代，对适应度微小差别的利用最终导致了性能上的显著提升，这和通过多年的复利累计，很小的利息率也能带来大量的资金增长是一个道理。

我们可以形象化地把进化看成是在一个由所有可能的生物体集合中进行搜索的过程。交叉操作实际上就是在进行最具创造性的搜索，这就是为什么我们要用它来产生每一代中约90％后代的原因[参见43页下图]。与之相反，突变则是在已有较好个体附近进行的一种局部搜索。我们相信，过高的突变概率将降低进化的效率，除非我们面对是那些特别简单的问题。

比数学函数更为复杂的一个例子是某一计算机程序的进化，例如通过叠代和记忆对蛋白质序列进行分类。在这个例子中，遗传程序能通过在程序群体的进化过程中进行创造或者删除子程序、叠代、循环和递归的形式来模拟基因复制和基因删除的生物过程。进化过程本身决定了解决问题所需计算机程序的性质和内容。

1995年得到改进；我们的法则比I995年的法则性能更为优越。其次，我们开发出了3种新的控制器电路拓扑结构，它们的性能也比使用旧转换法则的PID控制电路更优越。对于新的转换法则和新的电路拓扑结构我们都已经提出了专利申请。如果我们如愿以偿，我们相信这将是第一个利用遗传编程产生并被授予专利的发明。

可以进化的硬件

在进化过程中，由于每一世代中拥有数以千计甚至数以百万汁的后代，因此我们对它们的适应度的评价必须是高敛的。对电子电路而言，通常我们利用标准的电路模拟器软件来预测群体中每一电路的特性而在一个被称为可演化硬件的新兴科技领域内，微芯片能在瞬间被配置井被物理应用于遗传程序运行过程中所产生的每一电路中。

这些被称为可快速重配置现场可编程门阵列的芯片包含数以千计的相同单元。按照编程方式的不同．每一个这种单元都能完成多种不同的逻辑功能。芯片上的“基座”中的记忆比特能对每一单元进行定制以保证它们实现不同的逻辑功能。芯片上的其他配置比特能对芯片内的电路互联进行编程，这样就可以实现单元间的不同连接方式以及芯片输人输出引脚的不同安排方式。这样，只要改变它的配置比特，芯片的“个性”(它的逻辑功能及其内部连接)就能在纳秒量级的时间范围内动态改变。

有数十家公司出售这类可快速重配置芯片，然而大部分都只能用于数字电路中。商用模拟芯片的功能非常有限。我们用一种数字可重配置芯片创造的排序网络比原来获得专利的产品拥有更少的步数。

遗传编程的进化时间

自然进化过程用亿万年的“运行时间“来创造它的奇观。如果人工遗传程序也需要这么长的时间，那它就没有多大用处了。通常，一个遗传程序将在数十或者数百世代内产生数万或者数十万的个体。在前页表格中那些能与人类设计相媲美的结果中，其中的一半只需要在一个便携式笔记本上运行一周的时间即可得到；然而，2000年以后获得专利的6项发明则要求更多的运行时间。

当生物体分散在半隔绝的分组群体中时，自然进化将非常兴旺。当遗传程序在一个由计算机松散连接的网络中运行时，我们看到了同样的事情。每台计算机都可以单独完成对它的分组中的个体进行适应度评价这一耗时的步骤。然后，在每一世代结束时，一小部分个体（根据适应度选择）被迁移到网格中其他相邻的计算机中，这样每一个孤立的分组群体都能得到其他地方发生的进化改善所带来的好处。

我们用1000多台过时的350MHz的奔腾计算机组成了一个Beowulf型计算机群。在这个计算机群内，评价一个候选个体的适应度这个最耗时的问题，只需要大约1分钟的计算机时间。这样，一次涉及100世代包括10万个体的运行能够在大约7天就完成。

1000台计算机加在一起能在1秒钟内运行3500亿个cycle。也许这样的计算次数乍看起来显得很多，但是与人脑中的千亿细胞（一般认为，这些细胞中的每一个都具有上万个连接并以每秒1000次的速度在运行）所具有的运算能力相比，就是小巫见大巫了。

我们希望在这个10年的末期，50GHz（每秒运行500亿个cycle）的计算机能得以普及，这样任意一个拥有中等价格桌面工作站的人就能利用遗传编程得到具有专利价值的发明。我们预期遗传编程能被当成一种发明机器而被广泛应用。

机器智能挑战人工智能

半个世纪前，计算机的先驱M. Turing预言再过50年机器智能将能够与人类相媲美。如今，遗传编程正在日常性地取代人类的发明。在这50年间，研究者在努力证实Turing的预言过程中发展了两种主要的学术方法：逻辑演绎和包含人类知识积累成专门技能的数据库（所谓专家系统）。这两者大致对应着Turing 1950年勾勒的两种宽泛的方法。前者的工作是构建可以进行逻辑分析并做出相应反应的程序，这无疑是建立在Turing 1930年关于计算机的逻辑基础之上的。而后者被Tuing称为文化搜索，应用的是从专家那里收集来的知识和技能。

人工智能和机器学习的目标，是使计算机能够按照高层指令来解决问题。遗传编程则是通过最少的人类干预使机器智能达到与人类相媲美的高度，而达到这一目的既不需要逻辑演绎也无需人类知识数据库。

Turing还建议对机器智能进行一项著名的测试。在Turing测试的众多叙述方式中，下面这个被广泛引用：一名裁判“隔着墙“接受信息并判断该信息是来自人类还是机器。我们不敢断言遗传编程在Turing测试中达到了相当于人类认知的程度。但是它的确通过了一个关于创造性和灵活性的测试，而只有很少的人能通过这种测试。美国专利办公室主办这项测试的时间已经超过了200年。

该专利办公室接受发明的书面描述，然后判断这些描述对相关领域的具有一般技能的人而言是否表达得不清楚。一旦某个自动化的方法复现了此前已获专利的人类设计的发明，那么该自动化方法就通过了专利办公室的智力测试。事实是，最初由人类设计的发明能满足专利办公室对专利价值的标准，就意味着计算机创造的替代发明也能满足这些标准。

这个智力测试不涉及无意义的闲聊或者游戏。当某一机构或个人投入时间和金钱来发明某项东西并费力去申请专利时，他必然认定这项工作具有科学上或者实用上的重要性。此外，专利办公室要求所提出的专利具有实用性。专利发明代表着具有非凡创造力的人的非凡工作。

对于用非确定性方法并无需借助逻辑或知识就能达到与人类智能相媲美的常规机器智能，虽然有些人表示吃惊，但是Alan Turing可不会。在他1950年的那篇论文里，他还提及了实现机器智能的第3条途径：“搜索遗传或者进化的基因组合，可以生存为标准。”

Turing并没有具体指出如何进行“遗传或进化搜索”以实现机器智能，但是他确实指出：

我们不能指望一开始就找到一个好的子机器。必须做以下实验：首先教一个机器并考察它学习的程度，然后再去尝试另一个机器并将它与前一个机器比较。从以下这些方面看，该过程和进化过程有一种明显的联系：

子机器的结构=遗传物质

子机器的变化=突变、

自然选择=实验者的判断

遗传编程在很多方面符合Turing对实现机器智能的第3种途径的预言。

【何毓嵩/刘国林／译     曾少立／校】