元胞自动机

1 元胞自动机 现在通行的计算机的基本结构是串行的，它把中央处理器、存储器、各个外部设备都连 到一条或少数几条总线上，限制了计算机的速度。计算机发展的方向将是由大量处理器和存储 器并联的新型计算模式。元胞自动机就是符合这一方向的简单计算模型。 元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定 局部规则，在离散的时间维上演化的动力学系统。 1 元胞自动机的诞生和生命游戏 元胞自动机的理论最早由 Von Neumann(冯·诺依曼)创立，他用这种工具研究机器人自我 复制的可能性。在他之后元胞自动机冷落了一段时间，直到 1970 年英国剑桥大学数学家 Conway 提出了一种叫“生命”的游戏，揭开了元胞自动机的研究热潮[1]。他在《科学美国》 杂志上悬赏 50 美元征求游戏的答案。这种简单的游戏是：一个正方的棋盘格，每格只有两个 状态，“生”和“死”，分别表示为是否被一个棋子占有。每个方格有八个邻格，游戏的规则如 下：①对于处在“生”态的格，若八个邻居中有 2 个或 3 个“生”，则继续存活，否则将因过 于孤独或过于拥挤而死亡。②对于处在“死”态的空格，若八个邻格中有 3 个“生”，则该 格转变为“生”(代表繁衍过程)，否则继续空着。利用这些规则来运行，棋盘上可以有如图 1 所示的绝灭、稳定、振荡、爬行等各种有趣的现象发生。康维问：能否出现自我复制的过 程？若棋盘无穷大，这种过程能否无限持续下去？悬赏登出不到一个月，就有许多人对上面 两个问题给出了肯定的回答。图 2 是无限爬行的一个例子，图上 1、3、5、7 位置和图 1 中 “爬行”过程的第二步一致，而 2、4、6、8 位置和“爬行”过程的第四步一致。 绝灭 稳定 振荡 爬行 图 1 正方棋盘格上的“生命”游戏[1] 图 7.2 持续发射“爬虫”的“枪” 2 2 元胞自动机的特征、分类和应用 元胞自动机，英文是 Cellular Automaton，缩写为 CA。在此模型中空间被一定形式的网 格分割为许多单元，即元胞（cell）。在每个元胞或格点上赋予一定离散化的数值，以代表 该点的状态。时间也是离散的，各座的状态同时一步步更新，状态更新采取局域的规则， 即每一步的下一步状态的数值仅取决于该座近邻及其本身此刻的数值。归纳起来元胞自动 机的主要特征有：①空间是离散的；②时间是离散的；③状态取值是离散的；④演化的运 算规则是局域的。在最典型的情况里，状态值取{0，1}二值（用图来表示则为黑白二色）， 演化的规则只依赖于最近邻。当然也可以有各种变通的形式，如每个座的状态有几个（相当 于图上有几个灰度级，或带彩色）；演化规则的依赖范围也可以扩大一些，如扩大到次近邻； 演化规则可以是决定论的也可以是概率性的；状态的更新可以同步也可以不同步。但规则不 宜太复杂。元胞自动机的精神是利用大量的简单元件，通过简单的连接和简单的运算规则， 在时空中并行地持续运行，以模拟出复杂而丰富的现象。 元胞自动机可按其所在元胞空间的维数对其进行简单分类： (1) 一维元胞自动机：元胞按等间隔方式分布在一条向两侧无限延伸的直线上。其状 态、规则等较为简单，研究最为深入和系统。它的最大特征是容易实现其动态演 化的可视化：二维显示中，一维显示其空间构形，空间维；另外一维显示其发展 演化过程，时间维。 (2) 二维元胞自动机：元胞分布在二维欧几里德平面上规则划分的网格点上。由于世 界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法，转换到 二维空间上，所以， 二维元胞自动机的应用最为广泛。 (3) 三维元胞自动机：如三维空间上的生命游戏。 (4) 高维元胞自动机：只是在理论上进行少量的探讨，实际的系统模型较少。 元胞自动机可以得到各种造型、经典的分形图形、动态演化过程中的吸引子、自组织和 混沌现象等。强大的计算速度和复杂的动力学行为还使元胞自动机被广泛应用于自然现象的 模拟中[2-7]。如在凝聚态物理中用它来模拟晶体生长、悬浮体的聚集、缺陷的产生、无序有 序的转变、自旋系统的相变等；在流体力学中用它来模拟粘滞流体的各种流动；在化学中用 它来模拟反应扩散系统中的振荡和螺旋波；在生命科学中用它来模拟心脏的纤颤、肿瘤的生 长、贝壳或毛皮上色素沉积而形成的花纹的发生和进化的过程等；天文学中用它来模拟星系 旋臂结构的形成；在地质学中用它来模拟地壳的断层、石油在多孔介质中的渗流等。 3 一维元胞自动机 (1)Wolfram 一维元胞自动机 20 世纪 80 年代元胞自动机掀起了一股热潮，人们在计算机上模拟得到了各种形状的奇 妙画面，如各种造型、经典的分形图形、动态演化过程中的吸引子、自组织和混沌现象等。 其中对元胞自动机的研究做出杰出贡献的是 Wolfram。Wolfram 本来是研究粒子物理和宇宙 学的，对星系的演化问题有兴趣。但元胞自动机模拟出的复杂的类似真实自然界中某些现象 和过程的图案激发了他对该领域强烈的兴趣。 Wolfram[8]认为生命游戏的缺点是只研究了一种规则，他要尽可能系统地研究各种规则 元胞自动机的行为。先从一维状态链做起，例如演化规则的半径为 1r = 的情况，包括自身 共 3 个近邻。若每个位置可有 2 个状态，则这 3 个近邻可以取 32 8= 种排列，对每一种排列， 3 下一个时刻可以取 2 个不同的值，因此一共有 322 256= 个不同的元胞自动机。不失一般性， 可令 Si 代表 t 时刻第 i 个座的状态，设演化规则的半径为 r，则 1t + 时刻新的状态 tiS 可写成 下列 函 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数形式： 1 1( , , , , , , ) t i i r i i i i rS f S S S S S− − + += " " (7.2.1) 这里 f 是 2 1r + 个宗量的离散函数，有多少可能的 f 函数，就有多少可能的自动机规则。设 状态用 k 个值来描述，则 2 1r + 个邻座可以取 2 1rk + 种状态排列，对于每种排列，函数可以取 k 个不同的值，所以一共可以有 2 1rkk + 个不同的函数 f，即有这么多不同的一维元胞自动机。 计算二维元胞自动机的数目，只需将 2 1r + 换为邻域中的格座数 z。如正方网格， 5z = 可取 52 32= 种排列。六角网格 7z = ，可取 72 128= 种排列。表 1 给出了一些较简单情况下一维 和二维元胞自动机的数目。从表中可以看出，随着 r 和 z 的增大，可能的不同元胞自动机的 数目急剧增加。 表 1 一维和二维元胞自动机的数目 一维元胞自动机 二维元胞自动机 r k 元胞自动机数目 网格形状 z k 元胞自动机数目 1 2 22 3 =28=256 正方 5 2 22 5 =232=4.3×109 2 2 22 5 =232=4.3 ×109 六角 7 2 22 7 =2128≈1038 Wolfram 对 1r = ， 2k = 的 256 种一维元胞自动机作了全面的研究。他定义了演化规则 的编码，示意图（90 号元胞自动机）如图 7.3 所示。图中第一列是对相邻状态的编号（从 0 到 7 共 8 种），第二列中每种相邻状态编号对应的三个二进位数即 f 函数宗量 Si−1，Si，Si+1 的值，第三列是对应中间位置下一时刻的状态。第三列的八个二进位数可换算成十进位数 90（第四行），就得到这条规则的编码，即用演化结果 01011010 代表 90 号元胞自动机。 （7） （6） （5） （4） （3） （2） （1） （0） 111 110 101 100 011 010 001 000 0 1 0 1 1 0 1 0 7 6 5 4 3 2 1 0N= 0 2 +1 2 +0 2 +1 2 +1 2 +0 2 +1 2 +0 2 =90× × × × × × × × 图 3 第 01011010(90)号元胞自动机规则 类似地知道了上述元胞自动机编码，只要将编码分解为 2n∑ ，就可以确定元胞自动机 的规则。如 6 号元胞自动机： 2 16 2 2= + ，即图 7.3 中两种相邻状态（010）和（001）对应 的下一时刻状态为 1，其余六种相邻状态对应的下一时刻状态均为 0。16 号元胞自动机： 416 2= ，即只有图 7.3 中（100）对应的下一时刻状态为 1，其余七种状态对应的下一时刻 状态均为 0。任选一相同的初始的 20 个状态，结合周期性边界条件（把最后一个状态用作 第一个状态前的状态，或把第一个状态用作最后状态后面的状态），6，16 号元胞自动机的 前 5 步演化过程如下： 10001000001100100010 10001000001100100010 10011000010001100110 01000100000010010000 10100000110010001000 00100010000001001000 10100001000110011001 00010001000000100100 00100010001000100010 00001000100000010010 01100110011001100110 00000100010000001001 N=6 N=8 下面给出了 90 号、30 号和 111 号元胞自动机的演化图（图 4），图中用黑点表示该位置 状态为 1，空白处表示该位置状态为 0。每一行代表一维元胞自动机在某时刻的状态，从上 4 到下时间逐行增加一步，两头的边界处需用周期性边界条件。 (a) (b) (c) 图 4 90 号、30 号和 111 号一维元胞自动机的一些演化图 在理论上，元胞空间通常是在各维向上是无限延展的，但是在实际应用过程中，无法在 计算机上实现这一理想条件，因此，需要定义不同的边界条件。边界条件主要有三种类型： (a)周期型：相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接 的“圈”。对于二维空间，上下相接，左右相接。而形成一个 拓扑圆环面，形似车胎或甜点 圈；(b)反射型：在边界外邻居的元胞状态是以边界为轴的镜面反射。例如在一维空间中， 当 r=1 时的边界情形如图 5 所示。(c) 定值型：指所有边界外元胞均取某一固定常量，如 0， 1 等。 图 5 反射型边界 这三种边界类型在实际应用中，可以相互结合。如在二维空间中，上下边界采用反射 型，左右边界可采用周期型 。有时，在应用中，为更加客观、自然地模拟实际现象，还有 可能采用随机型，即在边界实时产生随机值。 图 6 一维的元胞自动机的长期行为 (a) (b) (c) (d) 5 从随机的初始状态出发，Wolfram 在计算机上运行了所有的 256 种一维的元胞自动机， 发现按照它们的长期行为，可将它们定性地归纳为四类（图 6）：(a)演化到全部是 0 或全部 是 1 的均匀状态（0，4，16，32，36，48，54，60，62 等条规则）；(b)演化到不随时间变化 的定态或周期性的循环状态（8，24，40，56，58 等条规则）；(c)演化到混沌状态（2，6， 10，12，14，18，22，26，28，30，34，38，42，44，46，50 等条规则）；(d)演化到更复杂 的结构（20，52 等条规则）。 (2) Willson一维分形元胞自动机 W i l l s o n [ 9 - 1 1 ] 令 多 项 式 ( ) (1 )t tq s s= + 的 系 数 （ 随 t 的 增 大 ， 系 数的数目不断增大）为偶数者为 0，为奇数者为 1，构造了一种分形元胞自动机，如图 7， 其中 s 是变量，t 是幂指数，t 的增加对应于时间的增加。用黑点表示 1，空白则表示 0， 则多项式系数的演化对应着 Sierpinski 三角地毯，其分形维数为 ln 3/ ln 2。 0t = 1 1 1t = 1 s+ 1 1 2t = 21 2s s+ + 1 0 1 3t = 2 31 3 3s s s+ + + 1 1 1 1 4t = 2 3 41 4 6 4s s s s+ + + + 1 0 0 0 1 5t = 2 3 4 51 5 10 10 5s s s s s+ + + + + 1 1 0 0 1 1 6t = 2 3 4 5 61 6 15 20 15 6 s s s s s s+ + + + + + 1 0 1 0 1 0 1 …………………………….. ..…………… 图 7 Willson 分形元胞自动机 (3) 对一维元胞自动机演化图形的进一步分析 近来人们对元胞自动机的兴趣更多的转移到在一定时间内相互作用的位置有多少，以及 一个初始的位置分布会将演化过程导向哪里等问题。例如 Fehsenfeld 等[12]研究了生命游戏相 关构形的演化中的标度律，发现即使是高度相关的初始状态，演化仍能够像在非相关状态中 观察到的那样保持标度关系。Botelho[13]等研究了基于一维元胞自动机演化图形上的随机行 走，行走的规则是在最近邻或次近邻值为 1 的点上跳跃，发现在 9 种非周期性的元胞自动机 的演化图形上，有 7 种即 22，54，90，122，126，150，182 号元胞自动机上的随机扩散是 正常的且各向同性，即 2 2~ vNR N< > ， 1/ 2v = ，这里 N 是行走步数，RN 是总位移；而在另 两种即 18 和 146 号元胞自动机的演化图上，随机扩散是反常的、各向异性的，得到 x 方向 0.22xv ≈ ，y 方向 0.42yv ≈ ，其谱维数 1.25 0.01sD = ± 。 6 4 二维元胞自动机 大多数线性元胞自动机可以用来模拟一维的生长和流动，但实际的生长和流动过程例如 晶体生长、颗粒凝聚、湍流形成等经常发生在二维或三维空间，此时可以用二维元胞自动机 来模拟。以二维元胞自动机为例，通常是先在正方形或长方形平面上划分出许多网格，网格 的形状可以根据实际情况采用正方形、正六角形和三角形。二维元胞自动机邻居的定义复杂 而多样，通常只取简单的几种。网格上元胞的状态更新规则将依赖于系统的宏观过程和微观 机制。 (1) 二维空间常用网格排列 二维元胞空间通常可按三角、四万或六边形三种网格排列。这三种规则的元胞空间划分 在构模时各有优缺点：(a)三角网格的优点是拥有相对较少的邻居数目，这在某些时候很有 用，其缺点是在计算机的表达与显示不方便，需要转换为四方网格；(b)四方网格的优点是 直观而简单，而且特别适合于在现有计算机环境下进行表达显示，其缺点是不能较好地模拟 各向同性的现象，例如后面提到的格子气模型中的 HPP 模型；(c)六边形网格的优点是能较 好地模拟各向同性的现象，因此，模型能更加自然而真实，如格气模型中的 FHP 模型，其 缺点同三角网格一样，在表达显示上较为困难、复杂。 图 8 二维元胞自动机的三种网格划分(a) 三角网格(b) 四方网格(c) 六边形网格 (2) 二维元胞自动机常用邻居 元胞自动机中演化规则是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于 本身和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定的邻居规则。二维元胞 自动机的邻居定义较为复杂，但通常有以下几种形式(以最常用的规则四方网格划分为例)， 如图 9。(a)冯-诺依曼(Von. Neumann)型：元胞有上、下、左、右四个邻居，包括自身共 5 个元胞；(b)摩尔(Moore)型：元胞有上、下、左、右、左上、左下、右上、右下八个邻居， 包括自身共 9 个元胞；(c)扩展的摩尔(Moore)型：将以上的邻居半径 r 扩展为 2 或者更大， 即得到所谓扩展的摩尔型邻居；(d)马哥勒斯 (Margolus)型：前面的三种邻居模型中，每次 以一个元胞(常被称为中心元胞)，为研究对象，考虑其状态的转换，与之不同，马哥勒斯型 每次将一个 2x2 的元胞方块(包含四个元胞)做统一处理,图 9(d)就是一个例子。 7 (a)冯-诺依曼(Von. Neumann)型 (b)摩尔(Moore)型 (c)扩展的摩尔(Moore)型 (d)马哥勒斯 (Margolus)型 图 9 二维元胞自动机的几种邻居类型 (3) 二维元胞自动机举例 下面是几个二维元胞自动机的例子，网格上元胞的状态更新规则将依赖于系统的宏观过程和 微观机制。 （a）表决与退火[14] 初始状态是在正方形网格上随机分布的一些白点○和黑点●，生长的规则是在最近邻和 次近邻及其本身共 9 个网格点上采用少数服从多数的规则，来决定中心座下一时刻是●还是 ○，即 5 个及 5 个以上●得●，5 个及 5 个以上○得○。图 10（a）是初始状态中黑白比例各 50%时，经长时间演化得到的图形，可见形成了一些相当细碎的畴域。若起初黑座很少，则 长时间后白区连成一片，黑区成为白色海洋中的一个个孤岛，反之亦然。这类模型可用来研 究成核或渝渗现象。如果把规则稍作修改，在上述 9 个网格中处于边缘状态、即 4 票和 5 票的结果交换一下：5 个●得○，5 个○得●，得到的结果如图 10（b）所示，黑白边界的棱 角和曲折抹平了许多，黑白的畴界融合起来，成为更大的畴域，这很像是退火过程，产生了 表面张力引起的效果。 8 (a) (b) 图 10 表决与退火模型 (b）Q2 规则—Ising 自旋动力学模型 Q2 规则是 Vichniac 在 20 世纪 80 年代作为 Ising 自旋动力学模型提出的。正方形网格上 每个格位拥有一个向上自旋或向下自旋。系统中与自旋相关的来自自旋对的耦合：相同自旋 排列能量为-J，相反自旋排列能量为 J。演化规则要求保持局部能量守恒，当且仅当不引起 任何能量交换时，自旋 si 才可能翻转，在时间 t+1 时刻变成 1-si 。因此，如果自旋向上的 邻居数和自旋向下的邻居数相同时，则自旋 si 翻转，自旋的这种变化没有引起任何能量交 换。 然而，所有自旋的运动在元胞自动机内都是同时发生的，上述判定某格位上自旋翻转与 否是基于邻居不变化的假定，如果邻居也翻转(因为它们遵循相同的规则)，那么能量将不守 恒。解决这个问题的方法是把网格划分为奇数子格和偶数子格(图 11，如同国际象棋盘上的 黑白方格)；把状态更新分为两步：首先根据偶数子格上自旋的构形，翻转奇数子格上的自 旋；然后再根据奇数子格上自旋的构形，翻转偶数子格上的自旋。这种方法防止了相邻格位 上自旋翻转与否的冲突。这里状态的更新虽然表面上是分成了两步，但实际上它们对应的是 同一时刻的状态更新，与元胞自动机的定义(所有格位同时更新并不相违背)。 图 11 网格划分为奇数子格和偶数子格 图 12 是 Q2R 规则计算机模拟的结果。初始构型(a)中含有约 11%的向上自旋(白色表示)， 89%的向下自旋(黑色表示)。演化最后系统达到静止状态：向上磁化区(白区)被向下磁化区(黑 区)包围。此动力学系统中，由于上述的演化规则，能量是严格守恒的。然而向上自旋和向 下自旋的数目可能发生变化。图 12 中，向上自旋的百分率从初始状态的 11%增加到静止状 态的 40%。过量的向下自旋导致系统的宏观磁化。 ¾ 以各种不同的自旋初始百分率来研究这个模型，结果发现，当系统总能量足够低(初 始百分率偏离 50%较多，多数自旋按同一方向排列，E 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，它们说明了构形引倒塌而进行的演化。这里，将单元块上步是两粒子、下部 为空的构形处理成概率规则(颗粒间可能存在一定的摩擦力，具有某种“成拱”作用，延迟 倒塌)，产生的结果更接近实际行为。当然，实际模拟中，需要引入一个基础面，颗粒在基 础面上将停止下落。图 19 是在此规则下模拟的沙漏，可以看出，演化过程与实际比较接近。 图 18 Margolus 邻居表示沙堆规则 13 图 19 沙堆规则用于沙漏模拟 (f) Langton 蚂蚁规则 此规则通过极其简单的运动算法模拟假想的动物(蚂蚁)的行为。蚂蚁在正方网格上运 动，格位是白色或黑色。演化规则是在白色元胞中，蚂蚁向左转 90 度；在黑色元胞中，蚂 蚁向右转 90 度；蚂蚁移动进入下一个元胞时，原来的元胞颜色反转(原来白色的，变为黑色， 原来黑色的变为白色)。 演化结果发现，蚂蚁表现出很复杂的行为。假设蚂蚁从完全白色的空间出发，经 t=500 步后，它实质上又返回到原位，之后进入混乱的阶段，运动不可测。然而，这个极不规则的 运动在 t>10 000 后，蚂蚁突然又表现出规则的动作，远离起始位置，开辟新的公路(图 20)。 图 20 Langton 蚂蚁规则 上述规则中，原则上每个格位可以被不同数量的蚂蚁占据，然而如果许多蚂蚁同时出现， 它们可能想从不同的侧面进入同一个格位。为了考虑多蚂蚁情况，考虑扩展的 Langton 规则： 格位的颜色是黑色，进入格位的蚂蚁(至多 4 个)全部右转 90 度，格位的颜色是白色，进入 格位的蚂蚁全部左转 90 度，格位的颜色依据蚂蚁存在的数目进行修改(如原来白色的，有 1 个或 3 个蚂蚁变为黑色，有 2 个或 4 个蚂蚁保持白色；如原来黑色的，有 1 个或 3个蚂蚁变 为白色，有 2 个或 4 个蚂蚁保持黑色)。 多蚂蚁行动可以观察到协同行为和干涉行为：经过一段时间后，蚂蚁建立公路；一旦公 14 路建成，其他蚂蚁可利用该公路快速行动；当第二个蚂蚁插手这个公路的建设时将有破 坏性的后果：如进入新的混沌运动，或公路沿其他方向迁移(图 21)。 图 21 多蚂蚁运动 (g)森林火灾模型 元胞自动机规则中还可以引入概率，一个令人关注的例子是森林火灾模型。模型定义在 正方网格上，每个格位用未燃烧的树、正在燃烧的树和空状态填充。演化规则是：下一时刻， 正在燃烧的树变成空格位；如果绿树格位的最近邻居中有一个树在燃烧，则它变成正在燃烧 的树；在空格位，树以概率 p 生长；在最近的邻居中没有正在燃烧的树的情况下，树在每一 时步以概率 f(闪电)变为正在燃烧的树。 图 21 是这个规则下模拟的二维空间行为。若把森林中的树木生长和烧毁的时间尺度完 全分隔开(即 f/p→0) ，这个模型具有自组织的临界状态，即表征系统的物理量存在幂函数行 为，如森林的尺寸分布和森林内树木数量间就存在这样的关系。 图 21 模拟的森林火灾(灰色：生长的树，黑色：燃烧过的格位，白色：正在燃烧的树) （h）管虫礁模型[14] 管虫是海洋环节动物，平时张开像朵花，稍受扰动，即缩回管内，等待一会儿后再出来。 模型中用●代表管虫的活动状态，○代表管虫的藏匿状态。设当一只管虫的邻域内活动的邻 居多到 n 个，它所受到的刺激足以使它藏匿起来，模拟时用计时器计算藏匿起来的管虫何时 该出来，并且采用平面 0 和平面 1 两块板，前者作为管虫的栖息地，后者是各处管虫的计时 15 器。计时器所取数值决定于管虫的藏匿时间，以计时器取 0，1，2，3 四个值为例，对于活 动的管虫计时器的状态为 0，一旦它的活动邻居数达到 n 个，计时器跳到 3，发出警告。下 一步管虫缩回管内，计时器退到 2，然后逐步倒数，经 1 至 0。下一步管虫就重新钻出来了， 计时器保持读数为 0，直到再次受到足够强烈的刺激为止。模拟时初始状态从管虫所处活动 相位都作随机分布开始，短期内即可看到相位相干的涟漪，纹络渐渐长大和融合，形成美丽 的图案，如图 22 所示。这类规则对阈值 n 极为敏感：如 2n = 图案发展很快，但纹络很细， 如图 22（a）； 3n = 纹络变宽而进展缓慢，不久就形成一些自持的活动中心，通常它们作双 螺旋状，形如一对公羊角，如图 22（b）； 4n = 大部分区域的相位被锁定。若将规则稍微改 一下， 3n = 时管虫不缩回， 2n = 时反而缩回，也产生了退火效果，如图 22（c）。 (a) (b) (c) 图 22 管虫礁模型 (i) 圆周元胞自动机 圆周元胞自动机模型[15]的规则极其简单，生长发生在二维正方点阵上。这种圆周元胞 自动机十分敏感于生长次序和初始条件，并能产生分形图形包括著名的 Sierpinski 分形三角 毯。分形维数可以用来表征这种元胞自动机的图案和它们表现出的混沌行为。 圆周元胞自动机可以如下构造：在正方点阵中心放置一粒种子，其值设为 1，用黑点表 示。所有在（ 1i δ− + ， i δ+ ]半开半闭的圆环内（圆环宽度为 1， 1, 2, 3i = "表示圆环增 大，0≤δ ≤1）的点是将要被考虑生长或不生长的点的位置。各个点四个最近邻中有且只有 一个位置是黑点时该局域点将会生长（相应点的值由 0 变为 1），而没有最近邻是黑点（太 孤独）或两、三个最近邻都是黑点时（太拥挤）则不会生长。此条件可以被称为中间程度拥 挤条件。每一个（ 1i δ− + ， i δ+ ]环中选择位置的顺序可以是顺时针、反时针或从上到下 从左到右的扫描方式。为了方便起见，以下将第三种顺序简称为逐行扫描方式。 这个模型中有两个可变的初始条件。一个是初值δ，另一个是上述的环内选择的生长顺序。 图 23 是这个模型在 0δ = 时以逐行扫描方式生长的示意图，其中 I，II，III 和 IV 分别表示 第一、第二、第三和第四象限，图中标出的数字是圆环的序号。 0δ = 时在第一个圆环中有 四个位置，后面的圆环中（ 2, 3, 4, 5, 6i = " ）依次有 8，16，20，32，32…个位置。实 心黑点和空心点分别代表那些位置生长了还是没生长。可以看出，第一象限生长的位置和第 三象限生长的位置呈镜像对称，而第二象限和第四象限却不是。在第二象限中，除了 X 轴 和 Y 轴上及其相邻的部分位置有点生长外，其他位置没有点生长。而第四象限则有众多位 置有点生长。 16 图 23 模型以逐行扫描方式生长的示意图 图 24（a）和（b）是 0δ = 时圆周元胞自动机的生长图形，其中 i ≤365，生长顺序分别 是顺时针和逐行扫描方式。图 24（a）的每一象限都像一张扭曲的渔网，整个图形呈 90°旋 转对称。以反时针生长顺序得到的演化图形与顺时针生长的呈镜像对称。而以逐行扫描方式 得到的图形如图 24（b），尽管第一象限与顺时针生长方式一样，第三象限与反时针生长方 式一样，然而第二象限的大部分位置都不能生长，并且有趣的是第四象限是著名的 Sierpinski 三角分形毯。图 24（b）本身还具有镜像对称性，其对称线与 X 轴成 45°夹角。 (a) 顺时针 (b) 逐行扫描顺序 图 24 圆周元胞自动机的演化图形[15] ( 0δ = ) 不同的δ 值生长图形不一样，图 25 中以δ = 0.04，0.07，0.12 和 0.17 为例画出了逐行扫 描生长顺序下不同δ值第四象限的生长图形，很明显生长图形及其密集程度因δ值而异。 δ=0.04 η=0.191 D4=1.653 (a) δ=0.07 η=0.274 D4=1.750 (b) δ=0.12 η=0.251 D4=1.702 (c) δ=0.17 η=0.247 D4=1.735 (d) 17 图 25 逐行扫描顺序下不同 δ 值第四象限的生长图形[15] 0δ = 时以逐行扫描生长顺序得到的第四象限的生长图形是 Sierpinski 三角毯，它是一 个规则分形，其分形维数为 ln 3/ ln 2 1.58496D = = 。当 0δ > 时发生了一些变化，在这个象 限形成了调制的 Sierpinski 三角毯，并且调制程度因δ值的微小差异而可能有巨变。图 26 中 画出了第四象限分形维数 D4 和第一象限分形维数 D1 随δ 的变化。分形维数 D4 和 D1 的获得 是通过在第一象限和第四象限各截取 256 256× 大小的图形（图形包括中心点），然后用盒计 数法计算而得的。总的来说，D4 随δ 的增加虽有增加趋势，但曲线上有许多不规则的振荡， 振荡幅度可达 0.3 左右，并且对每一个初值δ ，维数都不一样。而对第一象限的分形维数 D1， 尽管 D1 大小比较接近（集中在 1.916 附近，变化幅值最大仅为 0.01），然而与第四象限的情 形相似，对不同的初值δ没有完全相同的分形维数。 1 ~D δ 曲线上也有许多不规则振荡。 第三象限维数与第一象限相同。以上这些表明圆周元胞自动机对初值δ十分敏感，表现出混 沌行为。 2.0 1.9 1.8 1.7 1.6 1.5 D 4 1.924 1.920 1.916 1.912 1.908 D 1 0.0 0.2 0.4 0.6 0.8 1.0 δ 图 26 第四象限和第一象限图形的分形维数随δ的变化[15] 上面所举的是一些简单的二维元胞自动机模型的基本规则，这些模型提出后，为了更真 实的模拟研究对象，各自的规则又得到了进一步的发展，演变成更为复杂的规则，这里不一 一介绍。 参 考 文 献 [1] J.Conway, Scientific American 223 (1970)120 [2] Z.Olami, H.J.S.Feder and K.Christensen, Phys.Rev.Lett. 24(1992)1244 [3] M.Markus and B. Hess, Nature,347(1990)56 [4] G.Peng and H.J.Herrmann, Phys. Rev. E, 49(1994)R1796 [5] S.S.Botelho and F.D.A.Aarão Reis, Physica A 260(1998)338 [6] D.Helbing and M.Schreckenberg, Phys. Rev. E 59(1999)R2505 [7] M.Fukui and Y.Ishibashi, J.Phys.Soc.Japan 65(1996)1868 [8] S.Wolfram, Physica 10D(1984)1 [9] S.J.Willson, Physica D 10(1984)69 [10] S.J.Willson, Physica D 24(1987)179 [11] S.J.Willson,Physica D 24(1987)190 [12] K. M. Fehsenfeld, M. A. F. Gomes, and T. R. M. Sales, J. Phys. A: Math. Gen. 31 (1998) 8412-8417 18 [13] S.S.Botelho and F.D.A.Aarão Reis, Physica A 260(1998)338 [14] 赵凯华, 朱照宣, 黄畇，非线性物理导论，北京大学非线性科学中心(1992) [15] X. Sun, D.M. Wang, Z.Q. Wu, Phys. Rev.E 64(2001)6403 [16] 物理系统的元胞自动机模拟，祝玉学，赵学龙 译，Bastien Chopard, Michel Droz 著，清华大学出版社， 2003