传统的计算模式大多是串行的、中心控制式的。例如图灵机仅有一个读写头在工作,每一个时刻只能完成一步运算。计算机理论科学家们已经证明这种串行机器在原则上能够模拟一切计算,甚至包括大规模的并行运算,前提是我们对效率没有任何要求。然而,在现实世界中,效率是一个非常重要的问题。我们利用大量的并行空间换取运算时间是更重要的问题。
随着计算机网络以及存储设备的大量普及,到了20世纪末期,人们越来越重视这种去中心化的、并行的运算模式。在复杂性科学研究中,人们甚至为这些新的运算模式取了一个好听的名字:涌现计算。以下三个例子将让您真正领会涌现是何等强大的资源,它可以用来解决各式各样的实际问题。
1986年,计算机科学家Craig Reynolds发明了一种被称为Boid的计算机模拟程序。
通过给计算机中的智能体(Boid)设置三条简单的规则:靠近、对齐、避免碰撞,Craig就能模拟出鸟类群体活灵活现的飞行行为。然而,早期的Boid仅仅能够逼真地模拟实际的鸟类飞行情况,如果我们在Boid所处的人工环境中加入食物会出现什么情况呢?在真实世界中,鸟类会争先恐后地奔向食物。
假如我们在Boid飞行的环境中撒上很多食物,颜色深的地方表示食物浓度大,浅的地方浓度小,那么Boid就应该会自动聚集在食物浓度较大的地方。那么能不能把鸟类飞行觅食的行为用来解决实际的优化问题呢?我们仍然采用比喻的方法,把人工Boid飞行的空间比喻成优化问题的解空间,而把优化函数的函数值比喻成食物的浓度。这样,优化函数值越大的地方对应的食物越多,Boid飞向这个点的概率就会越大。
最后,很有可能所有的Boid都集中到了目标函数值最大的点,从而利用Boid群体的涌现行为求解了函数优化的问题。这实际上就是粒子群优化算法(Particle Swarm Optimization,简称PSO算法)的思路。在PSO算法中,一群虚拟的粒子(就相当于是Boid)在优化空间中自由地飞翔,他们会寻找食物并聚集到食物最多的点从而完成优化任务。
如果某个特殊的Boid在问题空间中发现了一个食物浓度更高的点,它就会召集其它的Boid过去。Boid在飞行的过程中会经历一些小的干扰,这样就会使有些Boid的飞行轨道与原轨道发生较小的偏移,从而使得Boid群体具有了一定的创新性。
为了更好地理解涌现计算是怎样在计算机中发生的,Jims Crutchfield用一类最简单的涌现系统——一维的元胞自动机——来实现涌现计算。
由于一维的元胞自动机是一类典型的通过局部相互作用生成复杂的全局模式的系统,所以,通过细致的分析这类系统往往能够让我们对系统的运作机理获得更好的了解。所谓的一维元胞自动机,就是一个一维的方格世界,其中每一个方格(元胞)是由黑白两种颜色构成的,并且,每个元胞下一时刻的颜色仅仅由它左右两侧元胞的颜色决定。
我们知道,因为每个元胞的颜色只有黑白两种,这样,任意一个元胞加上它左右两个元胞的颜色组合就一共有八种情况:黑黑黑、黑黑白,黑白黑、白黑黑、黑白白、白黑白、白白黑、白白白。只要我们为这八种情况的每一种都指定当前元胞在下一时刻的颜色,那么就完全定义了这个一维元胞自动机的规则。
我们可以用一张二维图形来展现一维元胞自动机的运行情况,每一个横行表示这个元胞自动机在某一时刻的状态,从上往下则表示随时间运行的状态。每一个元胞都根据它左、右两个邻居的颜色进行自己颜色的更新。所以,我们可以把元胞自动机的动态展现在一张二维图片上。
2010年1月,著名科学杂志《Science》刊登了一篇题名为“Rules for Biologically Inspired Adaptive Network Design”的文章,作者是来自日本北海道大学的Tero和Takagi等人。他们利用现实世界的一团黏菌(俗称鼻涕虫,一种黏菌门的组织,生长在腐烂的植物或潮湿的地面上,英文名字为Slime mold)设计了一个连通东京及其附近城市的铁路网!
这是一次别开生面的涌现计算!我们知道,黏菌是一群裸露的、无细胞壁、多核的原生质团,它们可以通过连续的形变而缓慢移动。当这团裸露的细胞在空间上遇到多个分散的食物源的时候,就会构建起一些疏运营养的通道。Tero和Takagi等人正是利用了黏菌的这种天性,在实验室中为黏菌们设计了一套人工食物源环境,让这群简单的原生质团形成疏运营养的网络。他们将一张东京以及附近城市的地图作为黏菌生长的环境。
在初始时刻,让黏菌集中在地图上的东京点,然后将其他几个附近的城市放上黏菌喜欢吃的食物,然后就让这群黏菌在实验地图上缓慢变形、游走,经过一天多的时间,它们最终演化出了一条条营养疏运通道。试验人员将黏菌构建的食物疏运网络与现实的东京附近的地铁网络进行对比,发现这两种网络非常的相似!对比的结果向我们展示,两个网络无论从结构还是形状上看都非常相似。
也就是说,这群看起来笨拙无比,没有任何智力可言的黏菌的确完成了可观的计算任务:修筑轨道网络。更有趣的是,为了修建这样一套有效率的网络疏运系统,被称为灵长类动物之首、号称具有超凡智力的人类设计师也要花费数年时间。就这样,这些简单得不能再简单、低级得不能再低级的黏菌通过简单的相互作用就在整体上实现了一次可观的涌现计算。