第11章 粒子计算

1989年我偶然读到物理学家帕卡德（Norman Packard）的一篇文章，写的是用遗传算法设计元胞自动机规则。我一下就被吸引住了，想自己也试试。当时因为繁忙，无暇顾及（我在写博士论文），但这个想法一直留在我的脑海里。几年后，论文完成了，我也在圣塔菲研究所找到了职位，终于可以有时间深入研究这个问题了。有个叫赫拉贝尔（Peter Hraber）的本科生当时在研究所逗留，想找点事情做，我就把他招进来协助我研究这个课题。很快一个叫达斯（Rajarshi Das）的研究生也加入我们，他当时在独立研究类似的课题。

类似于帕卡德的思想，我们想用遗传算法演化出能执行所谓的“多数分类（majority classification）”任务的元胞自动机规则。这个任务很简单：元胞自动机要能区分初始状态中是开状态还是关状态占多数。如果是开状态占多数，最后所有元胞就应当都变成开状态。同样，如果是关状态占多数，最后所有元胞就应当都变成关状态。（如果初始状态中开状态和关状态的数量一样多，就没有答案，但是可以让元胞的数量为奇数来避免这种可能。）多数分类任务有点类似于选举，是在大家都只知道最近邻居的政治观点的情况下预测两个候选人谁会赢。

多数分类问题对冯·诺依曼结构的计算机而言是小菜一碟。CPU只需要分别对初始状态中的开状态和关状态进行计数，同时在内存中记录计数值就可以了。计数结束后，从内存中读取数值进行比较，然后根据结果将元胞状态都设成开或关。冯·诺依曼结构的计算机可以轻松实现这个工作，因为它有随机存取存储器可以存储初始状态和中间值，还有中央处理器可以计数，进行最后的比较，以及将状态重设。

而元胞自动机则没有CPU和内存可以用来计数。它只有一个一个的元胞，每个元胞除了自己的状态就只知道相邻元胞的状态。这种情形其实也是对许多实际系统的理想化。例如，在大脑中，神经元只与其他少数神经元有连接，而神经元必须决定是否激发，以及以何种强度激发，使得大量神经元的整体激发模式能表示特定的感知输入。类似的，第12章我们还会看到，蚂蚁必须根据与其他少量蚂蚁的交互来决定做什么事情，让蚁群整体能够受益。

因此，基本上很难设计出让所有元胞能协同决策的元胞自动机。赫拉贝尔和我想知道遗传算法是不是能解决这个设计问题。

借鉴帕卡德的工作，我们使用一维元胞自动机，每个元胞与相邻的6个元胞相连，这样元胞的邻域中就有7个元胞（包括自己）。

你可以先想一下如何给元胞自动机设计规则，让它能进行多数分类。

一个合理的想法是：“元胞应当变成邻域中当前占多数的状态。”这就好像根据你自己和邻居的多数意见来预测哪个候选人会当选。然而，这个“局部多数投票”元胞自动机并不能完成任务，图11.1说明了这一点。初始状态中黑色元胞占多数，然后根据局部多数投票规则运行了200步。可以看到元胞自动机很快变成黑白区域相间，然后就不再变化。黑白区域的边界两边的元胞邻域分别是黑白占多数。最后的状态组合中既有黑色元胞也有白色元胞，没有得到想要的结果。其中的问题是，根据这个规则，区域之间无法相互交流信息，因此它们无法得知自己是否是多数。

这个规则的设计并不是那么显而易见，因此依照第9章的做法，我们用遗传算法来试一下是不是能产生出有用的规则。

在遗传算法中元胞自动机规则被编码成0/1序列。每一位对应一种可能的邻域状态组合（图11.2）。

遗传算法的初始群体为随机产生的元胞自动机规则。为了计算规则的适应度，遗传算法用各种初始状态组合进行测试。遗传算法的适应度为产生出的最终状态正确的比例——正确指的是如果初始开状态占多数，元胞就都为开，初始关状态占多数，元胞就都为关（图11.3）。我们将遗传算法运行了许多代，最终算法设计出了一些表现得相当好的规则。

我们通过机器人罗比已经看到，遗传算法演化得出的结果往往无法在其“基因组”层面进行理解。我们在这里演化出的用于多数分类的元胞自动机也是一样。下面是遗传算法演化出的表现最好的基因组之一：

00000101000001100001010110000111000001110000010000010101010 10111011001000111011100000101000000010111110111111111101101 1101111111

第1位是邻域全为0时中间元胞的更新状态，第2位是邻域为0000001时中间元胞的更新状态，依次往后。由于邻域状态有128种可能，因此基因组有128位。但光看这些数位是看不出这个规则如何运作，也无法知道为何它进行多数分类时适应度很高。

图11.4给出了这个规则在两种不同初始状态下的行为：分别为（a）黑色元胞占多数，（b）白色元胞占多数。可以看到在两种情形下最终行为都是正确的——（a）变成了全黑，（b）变成了全白。在得到最终状态组合的过程中，元胞之间似乎在协同处理信息，以达到正确的最终状态。在这个过程中的图样很有意思，它们到底意味着什么呢？

我们花了很多时间盯着图11.4这样的图看，想知道到底发生了什么。幸运的是，伯克利的物理学家克鲁奇菲尔德碰巧访问了圣塔菲研究所，并对此产生了兴趣。他和他的同事正好发展了合适的概念能帮助我们理解这些图样是如何完成计算的。

图11.4中有三种类型的图样：全黑、全白以及类似于棋盘格的黑白交替（图11.4分辨率较低，所以看上去像灰色）。正是这种棋盘格图样传递了局部区域黑白元胞密度的信息。

同遗传算法为机器人罗比演化的策略一样，这个元胞自动机的策略也相当聪明。图11.5是我对图11.4（a）做的标记。大部分为黑色和大部分为白色的区域很快就变成了全黑和全白。注意当黑色区域在左边而白色区域在右边时，中间的分界线总是垂直的。但如果白色区域在左边而黑色区域在右边，则会形成由黑白元胞相间组成的棋盘格图样三角形。如果把元胞自动机的两头回绕连在一起，就能看到三角形的环绕效果。

棋盘格区域的A边和B边以同样的速度扩展（即向两边覆盖同样的宽度）。A线向西南延伸，直到碰到垂直界线。B线则刚好避开了从另一边与这条垂直界线相撞。这表明A线的延伸长度要短一些，也就是说，A线左边的白色区域要小于B线右边的黑色区域。碰撞后，A线消失了，而黑色区域则得以继续扩展。在三角形底部的角上，B线和C线消失了，全部元胞格子都变成了黑色，从而得到了正确的状态组合。

如果我们将这些图样当作是进行计算，那么垂直界线和棋盘格区域就可以视为信号。这些信号通过元胞的局部互动而产生和传播。信号使得元胞自动机能作为一个整体判断相邻的大片黑白区域哪个更大，截去较小的区域，并使较大的区域得以扩展。

这些信号就是图11.1中的局部多数投票元胞自动机与图11.5中的元胞自动机的主要区别。前面提到，前者的黑色和白色区域之间没有信息沟通，因而也无法得知两者谁占多数。而对于后者，棋盘格和垂直边界产生的信号则可以进行这样的信息传递，通过信号之间的相互作用对传递的信息进行处理，从而得出答案。

克鲁奇菲尔德之前发明了一种方法可以研究动力系统行为中的“信息处理结构”，他建议我们用这种方法来分析遗传算法演化出的元胞自动机。克鲁奇菲尔德的思想是区域之间的界线（例如图11.5中的A、B、C线以及垂直界线）携带有信息，而界线发生碰撞就是对信息进行处理。图11.6对图11.5的时空图进行了重绘，将黑色、白色和棋盘格区域都去掉，只留下界线，这样更容易看清楚一些。这张图有点像以前物理实验用的气泡室中的基本粒子轨迹。因此克鲁奇菲尔德就把这些界线称为“粒子”。

物理粒子通常习惯用希腊字母表示，这里也照样。这个元胞自动机能产生6种不同类型的粒子：γ（伽马）、μ（缪）、η（艾塔）、δ（德尔塔）、β（贝塔）、α（阿尔法，一种寿命很短的粒子，衰变成γ和μ）。每种粒子分别对应一种界线——例如，η与黑色和棋盘格区域之间的界线相对应。粒子碰撞有5种，其中3种（β+γ、μ+β、η+δ）会产生出新粒子，而另外两种（η+μ和γ+δ）则会“湮灭”，两个粒子都消失。

将元胞自动机的行为用粒子进行描述能帮助我们理解其如何编码信息和进行计算。例如，α和β粒子编码了关于初始状态的不同类型的信息。α粒子衰变成γ和μ。γ粒子携带了白色区域边界的信息；类似的，μ粒子则携带了黑色区域边界的信息。当γ抢在μ之前与β碰撞，β和γ所携带的信息就结合到了一起，从而可以得知，最初由这几条界线划分的大块白色区域要小于大块黑色区域。这个新的信息被编码在新产生的粒子η中，它的任务就是追上粒子μ，并与其一起湮灭。

这种分析方法也可以被应用于其他几种演化出来的执行多数分类等任务的元胞自动机。这使得我们能预测特定元胞自动机的适应度等特征（而不用去运行元胞自动机本身，只需要分析其“粒子”描述就可以了）。另外我们也能理解为何某个元胞自动机的适应度会较高，以及如何描述各种元胞自动机在执行计算时所犯的错误。

粒子描述让我们看到了仅仅观察元胞自动机规则或是其时空图变化看不到的东西：它们让我们能从信息处理的角度来解释元胞自动机是如何执行计算的。粒子是我们强加给元胞自动机的描述，而不是在元胞自动机中确实发生的事情，遗传算法也没有用它们来演化元胞自动机。然而不知怎的，遗传算法却演化出了行为可以用粒子信息处理解释的规则。事实上粒子以及它们之间的相互作用可以作为一种语言，用来解释以一维元胞自动机为背景的分布式计算。沃尔夫勒姆曾提出《元胞自动机理论的二十个问题》，其中最后一个问题是：“对元胞自动机的信息处理能不能给出高层次的描述？”他想要的可能就是类似于这种语言的东西。

这些都是最近的工作，还需要继续深入研究。我相信，用这种方法理解计算，虽然不符合正统，却对没有中央控制，分布在简单个体中的计算会有用。例如，关于感知信号的高级信息在大脑中如何编码和处理目前仍然是个谜。也许可以用某种类似于粒子的语言对其进行解释，也有可能是类似于波的计算，因为大脑是三维的，神经元在一起形成携带信息的波运动，并通过波的相互作用处理信息。

大脑计算当然与一维元胞自动机不在一个层面上。不过，有一种自然系统却可以用非常类似于粒子的语言解释：植物的气孔网络。所有有叶植物的叶子表面都布满了气孔——根据光线和湿度开合的微小孔隙。气孔打开时可以让二氧化碳进来，用于光合作用。但是气孔打开也会导致植物体内的水分蒸发。犹他州立大学（Utah State University）的植物学家莫特（Keith Mott）、物理学家皮克（David Peak）和他们的同事长期观察叶子气孔的开合模式，他们认为气孔组成了一个有点类似于二维元胞自动机的网络。他们还发现气孔开合的时间模式很像二维形式的粒子相互作用。他们猜测植物通过气孔进行分布式计算——通过优化气孔的开合让二氧化碳的获取和水分流失达到最佳平衡——这种计算也许也能用粒子语言进行解释。