元胞自动机

元胞自动机

元胞自动机（Cellular Automata，简称CA）是一种时间、空间、状态都离散，空间相互作用和时间因果关系为局部的网格动力学模型。它由冯·诺依曼创始，经数学家约翰·何顿·康威和物理学家斯蒂芬·沃尔夫勒姆等人的贡献后迅速发展。元胞自动机广泛应用于计算机科学、物理学、复杂系统、理论生物学和微观结构模型等领域。

元胞自动机的基本概念

元胞自动机由规则的元胞网格组成，散布在规则格网 Lattice Grid 中的每一元胞 Cell 取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。每个单元格都处于有限状态中的一种，例如打开状态和关闭状态（与耦合映象晶格 coupled map lattice 相反）。网格可以是任意有限维数。对于每个单元格，都有一组定义为其邻域的单元格。 每个单元格都将被定义一种状态来作为初始状态（时间t = 0）。根据一些固定的规则（通常是一种数学函数），产生新的状态（t增加1个单位）。单元格当前状态及其附近单元格的状态共同决定了该单元格的新状态。一般而言，更新单元格状态的规则对于每个单元格都是相同的，不随时间变化，适用于整个网格。然而也有例外，例如随机元胞自动机和异步元胞自动机。

历史发展

20世纪40年代，这个概念最初是由当时在洛斯阿拉莫斯国家实验室工作的斯坦尼斯瓦夫•乌拉姆和约翰·冯·诺依曼发现的。尽管20世纪50年代到60年代一直有学者在研究这个问题，但直到20世纪70年代，随着康威的生命游戏的问世（一个二维的元胞自动机），这个问题才引起学术界的关注。20世纪80年代，史蒂芬·沃尔夫勒姆对一维元胞自动机进行了系统的研究，他称其为初等元胞自动机。他的研究助理马修·库克指出，这些规则是图灵完备的。沃尔弗拉姆在2002年发表了《一种新科学》这一著作，文中指出元胞自动机已在许多科学领域得到应用，包括计算机处理器和密码学。

分类

沃尔弗拉姆在《一种新科学》和20世纪80年代中期的几篇论文中，将元胞自动机和其他几种简单的计算模型根据其行为进行分为四个类别：

1. 平稳型：自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。
2. 周期型：经过一定时间运行后，元胞空间趋于一系列简单的固定结构 Stable Paterns 或周期结构 Perlodical Patterns。由于这些结构可看作是一种滤波器 Filter，故可应用到图像处理的研究中。
3. 混沌型：自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统计特征不再变化，通常表现为分形分维特征。
4. 复杂型：出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。从另一角度，元胞自动机可视为动力系统，因而可将初试点、轨道、不动点、周期轨和终极轨等一系列概念用到元胞自动机的研究中。

应用领域

元胞自动机在多个领域都有重要应用：

• 生物学：一些贝壳的图案（如Conus和Cymbiola属的贝壳）是通过自然元胞自动机生成的。这些色素细胞沿着贝壳的边缘分布在一条狭窄的带子上。每个细胞遵循一个自然的数学规则,根据其邻近的色素细胞的激活和抑制活性分泌色素。当贝壳生长缓慢时，细胞带会在贝壳上留下彩色图案。例如，分布广泛的Conus textile的图案类似于沃尔弗拉姆第30条元胞自动机规则。
• 化学类型：Belousov-Zhabotinsky 反应(B-Z反应)是一个时空化学振荡器，可以用元胞自动机模拟。20世纪50年代，阿纳托尔·马尔科维奇·扎博丁斯基（扩展了鲍里斯·帕夫洛维奇·别洛乌索夫的工作）发现，当一层薄薄的均匀的丙二酸、酸化溴酸盐和铈盐混合在一起并且不受干扰时，就形成了迷人的几何图案，如同同心圆和螺旋在介质中传播。
• 计算机科学：元胞自动机处理器是元胞自动机概念的物理实现，可以在计算机上处理信息。处理单元以相同单元的规则网格排列。网格通常是二维正方形或三维的正方体拼贴或平铺。其他拼贴也是可能的，但尚未使用。单元状态仅通过与相邻单元的交互来确定，不存在直接与更远的单元进行通信。
• 密码学：最初建议使用第30条元胞自动机规则作为可能密码学的分组密码。二维元胞自动机可用于构建伪随机数生成器。元胞自动机已被提出用于公钥加密。单向函数是一个有限元胞自动机的演化，其逆向元素很难找到。根据规则，任何人都可以轻易计算未来状态，但是很难计算历史状态。
• 纠错编码：Sen Gupta和P. Pal Chaudhuri在一篇论文中将元胞自动机应用于设计纠错码。这篇论文定义了一种使用元胞自动机构建单比特纠错和双比特错误检测（SEC-DED）码的新方案，并发布了一种用于该码的快速硬件解码器。

元胞自动机举例

生命游戏

康威的生命游戏是英国数学家约翰·何顿·康威在1970年发明的元胞自动机。它最初于1970年10月由马丁·加德纳发表在《科学美国人》杂志中的“数学游戏”专栏，该游戏从此名声大噪。

生命游戏是一种二维的元胞自动机，每个元胞都有黑白两种不同的状态，每个元胞都有周围八个方格作为邻居。生命游戏的规则如下：

1. 当前细胞为存活状态时，当周围的存活细胞低于2个时（不包含2个），该细胞变成死亡状态。（模拟生命数量稀少）
2. 当前细胞为存活状态时，当周围有2个或3个存活细胞时，该细胞保持原样。
3. 当前细胞为存活状态时，当周围有超过3个存活细胞时，该细胞变成死亡状态。（模拟生命数量过多）
4. 当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。（模拟繁殖）

当所有的元胞都按照这个规则检查它的邻居，并运行起来后，我们可以得到非常复杂的动态过程。

另外，生命游戏中还会诞生出一种被称为“滑翔机”的局部结构，它的动态运行情况如右图所示：

“滑翔机”可以作为一种局部传递信息的结构。可以利用“滑翔机”搭建更加复杂的动态结构。

一维基础元胞自动机

最简单的元胞自动机就是一维的元胞自动机。每个元胞都有黑、白两种颜色。邻居是一个半径为1的区域，每个元胞都有左右两个邻居。这样每一个方格单元和它的邻居可以表示如下：

由于每个元胞有两个状态{0,1}，这样，当前元胞加上左右两个邻居一共就有8种状态：

他们表示的状态分别是：000，001，010，011，100，101，110，111，其中0表示白色，1表示黑色。

规则与编号

下面考虑规则，假设当前考虑的细胞为[math]\displaystyle{ c_i }[/math]，他在t时刻的状态为[math]\displaystyle{ s_{i,t} }[/math]，而它的两个邻居状态为[math]\displaystyle{ s_{i-1,t} }[/math],[math]\displaystyle{ s_{i+11,t} }[/math],则[math]\displaystyle{ c_i }[/math]，,在下一时刻的状态为[math]\displaystyle{ s_{i,t+1} }[/math],则转换规则用函数表示为：

其中，[math]\displaystyle{ s_{i,t} }[/math]∈{0,1}，对于任意的i和t。

由于元胞自动机的规则就是根据每个元胞和它的邻居的当前状态转移到下一个时刻该元胞的状态。无论规则是什么样的黑箱，它的输入就是上面列出的8种组合之一，因为表示的是每个元胞下一时刻的状态，而状态只可能有0、1两种，则规则的输出要么是0，要么是1。这样，任何一个规则都是一个或者一组转换，比如下图表示的就是一条规则：

另外，若有一个规则是：“如果输入的三个元胞中黑色方格只有1个，那么下一时刻当前元胞就是黑色”可以表示成下面的图：

下面我们再把目光转到规则集上。由于每一条规则都是一个状态或一组状态的转换，那么把输入的8种可能情况转换到当前元胞的下一状态。我们可以用一个转换表表示一组规则集，例如：

这个规则集也可以用下面的一组数字表示为：

那么这组规则就对应着编码：10100011，也就是把八个位置上的方格进行一个排列。我们可以把输出部分的二进制编码转换成十进制数的形式：163，这就是该细胞自动机的编码。当状态数增多，半径增大的时候，这种编码方式就不实用了，我们需要用另一种方式来编码。考虑下面这样的规则若有一个规则是：“如果输入的三个方格中黑色方格只有1个，那么下一时刻当前方格就是黑色；如果有两个黑色方格，则下时刻是白色，如果有三个方格，则下时刻是黑色，如果有4个方格，那么下一时刻是白色”可以表示成下面的函数表：

[math]\displaystyle{ s_{i,t+1}=1 }[/math], 如果[math]\displaystyle{ s_{i-1,t}+s_{i,t}+s_{i+1,t}=1 }[/math]
[math]\displaystyle{ s_{i,t+1}=0 }[/math], 如果[math]\displaystyle{ s_{i-1,t}+s_{i,t}+s_{i+1,t}=2 }[/math]
[math]\displaystyle{ s_{i,t+1}=1 }[/math], 如果[math]\displaystyle{ s_{i-1,t}+s_{i,t}+s_{i+1,t}=3 }[/math]
[math]\displaystyle{ s_{i,t+1}=0 }[/math], 如果[math]\displaystyle{ s_{i-1,t}+s_{i,t}+s_{i+1,t}=0 }[/math]

其中[math]\displaystyle{ s_{i,t}\in{0,1} }[/math], 对于任意的i和t

这种情况下，输入就仅仅有4种情况，因此可以得到下面的表：

输入 0 1 2 3
输出 0 1 0 1

同样的道理，我们可以对它进行编码为：0101，表示为十进制就是5。显然，这种编码方式比前一种短，但是这种编码方法不能反映所有的细胞自动机。

每一组规则集也可以表示成类似于上面的图和表，例如下面的另外一组规则

由于邻居加上当前元胞一共8种状态，每一个状态对应两种可能转换规则，所以规则一共就有[math]\displaystyle{ 2^8=256 }[/math]种，我们可以为每一个规则编码，然后对其进行穷举。

动态行为

下面我们来考察这256中元胞自动机所具备的可能动态行为。对于一维的情况，我们假设所有的元胞都分布在一条直线上，并且直线的长度为300，也就是说有300个元胞在这条直线上，那么一条断续的横线就是当前所有细胞状态的一种分布。这些方格随着时间变化，就形成了不同的横线。我们把这些随着时间变化的线纵向拼在一起形成了一个网格区域。其中纵轴表示时间的流逝（往下为正），横轴为“元胞自动机在对应时刻的状态，就能得到一幅图像：

这个元胞的每一行都是某一个时刻元胞自动机的状态。因而从上到下数第1、2、3、4、5、6行可以分别表示第1、2、3、4、5、6时间步的元胞自动机状态。因此这里的一个平面的图案就是元胞自动机在时间上的发展动态。下面我们分别挑选几种典型的动态情况示于下图（下方的数字是元胞自动机的编码）：

CA 00：184号

CA 01：250号

CA 02：254号

CA 03：300号

经过对比分析，我们把细胞自动机归为四种类别，它们分别是：

• 固定值型：细胞自动机经过若干步运算便停留在一个固定的状态；
• 周期型：细胞自动机在几种状态之间周期循环；
• 混沌型：细胞自动机处于一种完全无序随机的状态，几乎找不到任何规律；
• 复杂型：细胞自动机在运行的过程中可能产生复杂的结构，这种结构既不是完全的随机混乱，又没有固定的周期和状态。

NaSch模型

1992年，德国学者 Nagel 和 Schreckenberg 在第184号元胞自动机规则的基础上提出了一维交通流CA模型，即，NS 模型（或NaSch模型）。

184规则模拟交通流（1表示有车，0表示无车，并且每辆车只在其前面具有开放空间时（前面一个格子为 0）才向前移动。这里前方定义为格子的右向）。

在其演化的每个步骤中，184规则自动机同时对所有细胞使用以下规则生成下一个阵列中的每个细胞，以确定每个细胞的新状态：

NaSch 模型是一个交通流模型，每辆车的状态都由它的速度和位置所表示，其状态按照以下演化规则并行更新。

NS模型的规则如下：

• 加速过程：，如果车辆的速度低于最大速度，且前方有空余的空间，那么在下一个时刻，速度会增加1。
• 减速过程：[math]\displaystyle{ {v_n \rightarrow min(v_n, d_n)} }[/math]，如果车辆发现前方在某一确定距离内有其他车辆，并且这个距离要小于它的速度，那么车辆的速度会减少。
• 随机慢化：以概率[math]\displaystyle{ {p} }[/math]，[math]\displaystyle{ {v_n \rightarrow max(v_n-1, 0)} }[/math]，由各种不确定因素，会导致车辆的速度减1，速度不低于零。
• 位置更新：[math]\displaystyle{ {x_n \rightarrow x_n+v_n } }[/math]，车辆按照预定的方式前进。

NaSch模型的效果展示:

纵轴是时间轴，横轴是在某一时刻的路况情况。发现随着时间的推移，原本没有堵塞情况的路况会自动出现堵塞，并且拥堵情况会在道路上传递

用NaSch模型模拟得到的车辆运动时空图（车辆从左往右移动，从上到下为时间演化方向）