cad如何快速计算道路面积（神奇的涌现计算）

张江 （北京师范大学系统科学学院副教授、集智俱乐部创始人）

传统的计算模式大多是串行的、中心控制式的。例如图灵机仅有一个读写头在工作，每一个时刻只能完成一步运算[1]。计算机理论科学家们已经证明这种串行机器在原则上能够模拟一切计算，甚至包括大规模的并行运算，前提是我们对效率没有任何要求。

然而，在现实世界中，效率是一个非常重要的问题。我们利用大量的并行空间换取运算时间是更重要的问题。随着计算机网络以及存储设备的大量普及，到了20世纪末期，人们越来越重视这种去中心化的、并行的运算模式。在复杂性科学研究中，人们甚至为这些新的运算模式取了一个好听的名字：涌现计算。以下三个例子将让您真正领会涌现是何等强大的资源，它可以用来解决各式各样的实际问题。

1粒子群的优化算法

1986年，计算机科学家Craig Reynolds发明了一种被称为Boid的计算机模拟程序。通过给计算机中的智能体（Boid）设置三条简单的规则：靠近、对齐、避免碰撞，Craig就能模拟出鸟类群体活灵活现的飞行行为[2]。

然而，早期的Boid仅仅能够逼真地模拟实际的鸟类飞行情况，如果我们在Boid所处的人工环境中加入食物会出现什么情况呢？在真实世界中，鸟类会争先恐后地奔向食物。假如我们在Boid飞行的环境中撒上很多食物，颜色深的地方表示食物浓度大，浅的地方浓度小，那么Boid就应该会自动聚集在食物浓度较大的地方。那么能不能把鸟类飞行觅食的行为用来解决实际的优化问题呢？

我们仍然采用比喻的方法，把人工Boid飞行的空间比喻成优化问题的解空间，而把优化函数的函数值比喻成食物的浓度。这样，优化函数值越大的地方对应的食物越多，Boid飞向这个点的概率就会越大。最后，很有可能所有的Boid都集中到了目标函数值最大的点，从而利用Boid群体的涌现行为求解了函数优化的问题。

这实际上就是粒子群优化算法（Particle Swarm Optimization，简称PSO算法）的思路[3]。在PSO算法中，一群虚拟的粒子（就相当于是Boid）在优化空间中自由地飞翔，他们会寻找食物并聚集到食物最多的点从而完成优化任务。如果某个特殊的Boid在问题空间中发现了一个食物浓度更高的点，它就会召集其它的Boid过去。Boid在飞行的过程中会经历一些小的干扰，这样就会使有些Boid的飞行轨道与原轨道发生较小的偏移，从而使得Boid群体具有了一定的创新性。

图3：用PSO优化函数：

的动态展示

将PSO算法中的Boid（箭头）与函数f(x,y)的等高线图画在同一个坐标平面上。(a)是算法开始时候的Boid分布情况，(b)是算法结束时候Boid的分布情况，Boid找到了函数f(x,y)的最大值点。

如图3所示，PSO可以很快地搜索问题的空间，并找到最大值点。目前，PSO作为一种独立的算法已经被用来解决各种优化问题[4]。

2一维元胞自动机的涌现计算

为了更好地理解涌现计算是怎样在计算机中发生的，Jims Crutchfield用一类最简单的涌现系统——一维的元胞自动机——来实现涌现计算[5]。由于一维的元胞自动机是一类典型的通过局部相互作用生成复杂的全局模式的系统，所以，通过细致的分析这类系统往往能够让我们对系统的运作机理获得更好的了解。

所谓的一维元胞自动机，就是一个一维的方格世界，如下图：

图4：一维元胞自动机

其中每一个方格（元胞）是由黑白两种颜色构成的，并且，每个元胞下一时刻的颜色仅仅由它左右两侧元胞的颜色决定。我们知道，因为每个元胞的颜色只有黑白两种，这样，任意一个元胞加上它左右两个元胞的颜色组合就一共有八种情况：黑黑黑、黑黑白，黑白黑、白黑黑、黑白白、白黑白、白白黑、白白白。只要我们为这八种情况的每一种都指定当前元胞在下一时刻的颜色，那么就完全定义了这个一维元胞自动机的规则。

图5：一维元胞自动机的运行

我们可以用一张二维图形来展现一维元胞自动机的运行情况，如图5和图6所示。其中，每一个横行表示这个元胞自动机在某一时刻的状态，从上往下则表示随时间运行的状态。每一个元胞都根据它左、右两个邻居的颜色进行自己颜色的更新。所以，我们可以把元胞自动机的动态展现在一张二维图片上。

图6：一维元胞自动机的运行

由于一维的元胞自动机完全是一个确定性的系统，这样，只要给定初始状态（第一行的黑白排列情况），根据固定的规则，元胞自动机所画出的图像就是固定的。

我们完全可以把这个元胞自动机看作是一个计算系统，只要我们把该自动机的初始条件看作是这个元胞自动机的输入数据，而把运行（比如说100步之后的黑白元胞的分布情况）看作是它的计算结果，那么给定一组输入条件之后，这个元胞自动机就会完成一系列局部的操作，最终在第100步的时候给出一个结果。当元胞自动机的规则确定之后，不同的输入一般会对应不同的输出结果。但是，问题是，一般情况下，这个元胞自动机不会进行有意义的运算，因为它的规则太任意了。

能不能设计某种非常简单的计算任务，从而在各种各样（即规则不同）的元胞自动机中找到一种合适的自动机，使它完成指定的计算任务呢？Crutchfield运用遗传算法对所有可能的一维元胞自动机（回想一下，一维元胞自动机的所有可能规则集合是有限的）进行搜索，通过不断的进化，系统终于可以找到一些元胞自动机完成简单的运算。

比如，Crutchfield设计的一个简单的运算任务就是对初始的黑白元胞的比例进行分类。如果初始条件下，黑色的元胞偏多一些，元胞自动机100步后的输出就必须全部都是黑色元胞；反之如果白色的元胞多一些，则要求元胞自动机在100步后全部输出白色。这样，如果我们把初始的黑白元胞看作输入，把100步后的结果看作输出，那么这个一维元胞自动机就能够完成密度分类这个简单的任务[5]。如下图示：

图7：让一维元胞自动机完成密度分类任务

虽然这个任务表面上看起来很简单，然而，对于元胞自动机来说却非常难。因为每个元胞仅仅能跟它左右两个邻居通信，而看不到输入时候的整体情况。在计算过程中，每一个元胞也只能根据左右邻居的颜色来机械地按照固定的规则变换颜色，不存在某个超级元胞能够对所有的元胞发号施令而决定系统的运行。也就是说，这群元胞们必须学会相互协调合作才能完成对于他们来说非常复杂的任务。

然而，通过遗传算法，Crutchfield终于找到了这种能够完成密度分类任务的一维元胞自动机。

图8：用遗传算法找到的可以成功分类初始元胞黑色密度的自动机

左图的初始黑色元胞密度为0.48，该元胞自动机正确给出了全部是白色的答案；右图的初始密度为0.51，该元胞自动机正确给出了全部是黑色的答案。

如图8，遗传算法终于找到了可以正确分类的元胞自动机。那么究竟这些简单的自动机是如何完成这种复杂的计算任务的呢？

Crutchfield进一步研究发现，这些成功分类的自动机的运行图都具备一种明显的特征：有很多横跨区域的大斜线，以及一些明显的三角形块状区域。我们知道，在元胞自动机的运行图中，一条黑色的斜线就相当于是一个传播的信号（黑色元胞的信息从一侧传递到另一侧）。也就是说，这些元胞之间会建立一种相互通信的机制。当某一个初始区域有更多的黑色元胞的时候，在这些元胞的边界处就会产生某种“粒子”（由一些传播的元胞组成），从而与白色元胞区域产生对消的现象。这样，通过不断的“粒子对消”就完成了黑色元胞数与白色元胞数的比较，最后输出正确的运算结果。

图9：“粒子碰撞”图

为了看清楚这些简单的元胞自动机的运行原理，Crutchfield甚至过滤掉了那些规则的三角块区域，而把边界的“粒子”凸现出来（图9）。我们看到，这些粒子（标为希腊字母的线条）在时空中运动，把信息从世界的一端传递到另一端，并与其他的粒子相互碰撞、反应，生成其他的粒子或者湮灭，从而完成对于这些元胞自动机来说非常复杂的计算任务。

总结来看，Crutchfield所研究的演化元胞自动机属于一类涌现计算模型，因为每个元胞都仅仅完成简单的局部运算，但是这些元胞通过相互作用，完成了全局的运算。Crutchfield的研究进一步指出，这些简单的并行相互作用的元胞之所以能够完成全局运算，其中一个最重要的因素就是在于它们可以通过“粒子”进行跨区域的通信，使得不同区域的两个或者多个元胞之间能够发生相互作用而实现整体的协调与合作。

他的研究给我们指出，涌现计算的一个重要的必要条件就是：信息的流动。因为只有信息的流动才能完成不同区域的通信，也才能真正让本来相互分散的个体连接而成一个整体。

3

“鼻涕虫”绘制城市交通路网

之前提到的各种涌现计算或者对涌现的模拟都是在计算机中完成的。下面，我们来看一个发生在现实世界中的涌现计算的例子。

2010年1月，著名科学杂志《Science》刊登了一篇题名为“Rules for Biologically Inspired Adaptive Network Design”的文章，作者是来自日本北海道大学的Tero和Takagi等人。他们利用现实世界的一团黏菌（俗称鼻涕虫，一种黏菌门的组织，生长在腐烂的植物或潮湿的地面上，英文名字为Slime mold）设计了一个连通东京及其附近城市的铁路网[6]！这是一次别开生面的涌现计算！

我们知道，黏菌是一群裸露的、无细胞壁、多核的原生质团，它们可以通过连续的形变而缓慢移动。当这团裸露的细胞在空间上遇到多个分散的食物源的时候，就会构建起一些疏运营养的通道。Tero和Takagi等人正是利用了黏菌的这种天性，在实验室中为黏菌们设计了一套人工食物源环境，让这群简单的原生质团形成疏运营养的网络。

他们将一张东京以及附近城市的地图作为黏菌生长的环境。在初始时刻，让黏菌集中在地图上的东京点，然后将其他几个附近的城市放上黏菌喜欢吃的食物，然后就让这群黏菌在实验地图上缓慢变形、游走，经过一天多的时间，它们最终演化出了一条条营养疏运通道。

图10：黏菌演化出的食物疏运网络

其中中心的黄点为东京所在地，其它的黄点为附近的一些城市，其上放置了食物。黏菌开始从东京扩散到其他的城市，并开始构建食物疏运网络。

起初，这群简单的细胞群体在地图上扩散，几个小时后，当它们遇到了食物之后就开始精炼这些模式而形成若干疏运食物的隧道。再经过几个小时，一些较大的运输隧道开始慢慢形成，而更多的小型隧道逐渐消失，最终，只有几个主干隧道保留了下来。试验人员将黏菌构建的食物疏运网络与现实的东京附近的地铁网络进行对比，发现这两种网络非常的相似！（如下图）

图11：黏菌计算出的疏运网络与东京和附近城市的铁路网络对比

对比的结果向我们展示，两个网络无论从结构还是形状上看都非常相似。也就是说，这群看起来笨拙无比，没有任何智力可言的黏菌的确完成了可观的计算任务：修筑轨道网络。更有趣的是，为了修建这样一套有效率的网络疏运系统，被称为灵长类动物之首、号称具有超凡智力的人类设计师也要花费数年时间。

就这样，这些简单得不能再简单、低级得不能再低级的黏菌通过简单的相互作用就在整体上实现了一次可观的涌现计算。

参考文献

[1] Harry R. Lewis (1998). Elements of the Theory of Computation, Prentice-Hall, Inc.

[2] Reynolds, Craig(1987), "Flocks, herds and schools: A distributed behavioral model.", SIGGRAPH 87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques (Association for Computing Machinery): 25–34.

[3] Stephanie Forrest: Emergent Computation, MIT Press,1991.

[4] James Kennedy, Russell Eberhart: Particle Swarm Optimization, Proc. IEEE Int’l. Conf. on Neural Networks(Perth, Australia), IEEE Service Center, Piscataway, NJ, IV:1942-1948.

[5] James P. Crutchfield. Melanie Mitchell, and Rajarshi Das, "The Evolutionary Design of Collective Computation in Cellular Automata", Machine Learning Journal,1998.

[6] A.Tero,S. Takagi, et.al. Rules for Biologically Inspired Adaptive Network Design,Science 22 January 2010:Vol. 327. no. 5964, pp. 439 - 442.

,