专题：元胞自动机 - 图文

对一些呈现出“复杂”状态的规则而言，甚至人们并不能确信，是否在足够多步以后，它们会变成别的状态，例如不动点？

Wolfram写了一本书，叫做A New Kind of Science。是专讲元胞自动机的各种应用。里面的研究包括海螺的花纹，包括交通流的性质，包括金融市场的“内在”随机性，等等。大家有兴趣可以去看，有专门的网站，可以看电子版。也可以下载得到。

在此我们还可以专门提一下，二维的元胞自动机，更可能在很简单的规则下，产生出奇怪的结果来。最简单的恐怕就是Chris Langton 和 Greg Turk提出的“蚂蚁”了。

顺便说一下，他是SFI（Santa Fe Institute）的成员。SFI是对研究复杂系统的很领先的研究机构，包括复杂系统的动力学，对社会和金融市场的模拟和研究、人工智能等问题都有很前沿的研究工作。官方网站是 www.santafe.edu，大家有兴趣的话可以去看。

我们来看这个最简单的蚂蚁自动机。曾有篇著名论文，题目叫做二维图灵机，专门讲了这个例子。假设一个“蚂蚁”在平面的方形网格中爬行，每个格子有两个状态：白色或黑色。蚂蚁爬进一个白色的格子时，就左转90度，并且把这个格子改成黑色。蚂蚁爬进一个黑色的格子时，就右转90度，并且把这个格子改成白色。最初时，整个“世界”都是白色的。 我们可以预测一下，这个蚂蚁会如何运动？

很简单的规则，很简单的初始条件。但情况却是意想不到的复杂。这个图是不到100步的时候，蚂

蚁留下的图案：

图里红色箭头就是蚂蚁。黑白色的格子是现在的世界的样子。下面是接近400步的时候，蚂蚁留下的图案（没有画元胞的边界线）：

这个蚂蚁画得太大了，挡住了中间的几个元胞，不过不影响大局。在大概500步以内，它不时地回到原点，留下中心对称的图案。但随后开始出现奇怪的现象，请看下图，大概是四千步的状态：

在从500步左右开始，直到接近11000步，它的图案完全失去了对称性，并且变得乱七八糟。再看

继续的图，大约10000步的时候：

我们看到，在10000步左右，它的运动突然开始出现了规律。再往下：

每过104步，蚂蚁的位置向左下方推移一“节”。这种现象有时被叫做“公路”。

其实可以通过一个很简单而巧妙的分析，证明蚂蚁的轨道必然是无界的。这个证明我这次不多说了，大家也可以试试（提示：反证法）。而且蚂蚁的轨道无论多么复杂，把时间倒转过来，都是完全可逆的。

在平面上如果存在两只或多只蚂蚁，情况会变得非常复杂。随着两只蚂蚁的初始位置不同，情况会不同，但多数情况下，蚂蚁都会通过建造“公路”的方式远离，但有时也会出现周期很大的周期轨道。也就是过几万步之后，居然能够完全回到初始状态。对此类问题的研究也有很多。

以上讲的是比较传统的元胞自动机例子。对它的研究虽然有许多，但总的来说，如果直接用它来对付实际问题，其思路不是很容易理解，也不是很容易推广。即使是Wolfram的那本A New Kind of Science，也有许多批评的声音。但元胞自动机的计算机实验非常好做，有一个开源软件Netlogo，也可以简单地做一些可视化的演示。我在上面的蚂蚁等图案都是用Netlogo生成的。

而下面我们要讲的，则是一种容易理解的元胞自动机。它来源于对实际问题的模拟，有时被称为格子气自动机，LGA（Lattice Gas Automata）。LGA是为了进行流体力学的计算而发展的离散方法。假设流体是由许多颗粒组成的，而不是连续的。再假设每个颗粒都在网格上运动，而不是在连续的空间中。而且时间也是离散的。如图20所示。

粒子就从一个格点运动（其实说成跳跃也可以）到另一个格点，其间它们可能碰撞。 从这个角度上看，这个设定完全符合元胞自动机的定义。每个元胞就是空间的网格，状态有“被粒子占据”或“不被粒子占据”两种（其实更精确地说，粒子的运动方向也是要说到的）。这里的关键是粒子的运动规则。在简单的问题中（譬如静态气体中的扩散），甚至完全不需要考虑粒子的速度，只需要考虑运动方向就够了。 首先，其碰撞的规则必须是一种“变换”。如果所有粒子匀速运动并可以互相穿过，这就体现不出来流体的“流动”了。所以在粒子碰撞的时候，其运动方向应发生变化。但这同时要保持质量守恒和动量守恒。在正方形网格的假设下，最简单的规则就是HPP规则：

如果还要考虑到气体是在容器里的，容器壁对气体分子还要有一个反射的规则。这就不赘述了。 HPP规则已经能体现出和真实气流很类似的运动趋势了。譬如初始条件是绝大多数地方的粒子密度都是基本均匀的，而且运动方向都是随机设定的。而在中间有一团密度极大的粒子，我们可以明显地看到密度以波的形式在向四周扩散。波阵面碰到容器壁会反射。其实声波也无非就是这样传播的。

但其在定量的角度上还不太好。主要是各个方向并不同性，在垂直方向和斜向的扩散性质不同。解决的方法是使用正三角形的网格，并配合稍复杂些的碰撞规则，这就是FHP规则：