6复杂性(二).ppt

1、复杂性（二）,yxdcom:hbu,物理学中有一条基本假定，那就是分析分析再分析，把事物的组成分离出来，直到你真正明白基本的东西在单纯的状态以如何简明的规律行事，然后，你就假定那些你还不懂的事物都是细节。 大量系统底层有一反复运行的规律，需要用另一种思维去认识它。这要抛弃纯分析的方法，不能分析分析再分析 人类要另辟新径，必须捉住标度结构这一环，看看大家伙与小家伙的关系如何。这产生复杂性的、持续进行的单一过程却与大小尺寸无关，与地点无关，与时间无关，它是普适的标度变换，它存在于大与小的自相似之中，由小到大自相似的放大比率就是一个普适的费根鲍姆常数 大地充满了美，引人入胜。看你是什么职业你就如何理

2、解。,费根鲍姆,分叉现象,“周期倍化分叉”的发现 非线性逻辑斯蒂（Logistic）差分方程,bifurcation,在动力系统演化过程中的某些关节点上，系统的定态行为可能发生性质的改变，原来的稳定定态变为不稳定定态，同时出现新的更多的定态，这种现象叫作“分叉”（bifurcation）。分叉是由运动方程中参数的变化引起的，所以往往要用“参数空间”来描绘分叉现象。随着参数的变化，分叉可以一次接一次地相继出现，而这种分叉序列又往往是出现混沌的先兆，最终会导致混沌。 生物群体数量（“虫口”）变化的研究以及涉及到的一类典型一维映射的分叉现象的研究，在20世纪70年代混沌学的创立和发展中曾经起到过特殊

3、的作用。,澳大利亚昆虫学家尼科尔森（Nicholson，A.J.）曾经在一个大瓶子里用有限的蛋白质食物喂养一瓶子绿头苍蝇，研究受到空间和食物限制的苍蝇群体数目（“蝇口”）的变化。他观察到有时绿头苍蝇可繁殖到将近一万只；过些时候又会降至几百只。蝇口繁殖过快超过容器的空间限制后数目就急剧减少，而活动空间的扩大又使蝇口快速增长；蝇口决不会单调增大或单调减少，呈现一种周期性的涨落。尼科尔森发现，这个循环周期大约是38天。但每个周期内蝇口数却可能出现两个峰值，而且到约450天后，蝇口的变化（振荡）变得极不规则。在这个实验中，蝇口数的变化包括了周期性、拟周期性和混沌。 生物群体被看做是一个动力系统，是受着

4、某种动力驱使的。在食物受限制的地域单种生物在起起落落地繁殖着；几种生物共存的区域，各种生物在生存竞争中此长彼消；在捕食者与被食者之间，存在着双向抑制作用；在宿主群体内部，流行病在传播。这一切因素，都对生物群体起到约束作用，把群体限制在更合理的数目上。,生态学家们一直试图为生物群体增减寻找一个数学模型。一个合理的简化就是用离散的时间间隔去模拟虫口的变化。因为许多生物群体的数目基本上都是按照一年的时间间隔变化的，而不是连续时间的变化。更有一些昆虫，它们只在一年中的特定季节里繁殖，所以它们的一代一代之间决不会重叠。一年一年的变化，正是生态学家所要了解的全部信息。因此，描写生物群体的方程不是连续的微分

5、方程，而是比较简单的差分方程，这是一种迭代模型，即逐年逐年地反复用同一个函数进行数值运算，它可以反映由一个状态（数目）到另一个状态（数目）的跳跃变化。 这个差分方程应该反映出以下影响虫口增减的因素：第一，虫口的增长必定与前一年的虫口数目成正比，这是一个线性关系，比例系数k即群体的增长率；第二，虫口的增长又受到空间、食物、流行病等许多因素的限制，不可能无限增长。实际情况是，群体小时稳定增长，群体适中时增殖量近于零，群体暴涨时急剧下降。,一个较好的方程是由迭代逻辑斯蒂映射所得到的非线性逻辑斯蒂（Logistic）差分方程 xt+1=kxt(1-xt) x表示虫口的相对数，它被定义为介于0和1之间的

6、数，0代表灭绝，1代表群体的最大虫口数；t表示时间，它只能以整数0，1，2，3跳跃；生殖增长率k代表了这一模型的一个十分重要的特征，表示拉伸或压缩的程度，也即非线性程度。从几何学上讲，逻辑斯蒂映射表示以不均匀的方式拉伸或压缩一个线段，然后再加以折叠。 对于一个生物群体来说，参数k越低，意味着群体最终将在较低的数量水平上灭绝；参数k的值提高以后，群体的数量也不会无限增长，这是可以理解的。但是计算表明，在k值提高后，群体却不可能收敛于一个定态水平，这是令人费解的。,20世纪70年代，美国普林斯顿大学的生态学家罗伯特梅（Robert May）利用计算机对这种单一群体生物随时间而变化的最简单的生态学方

7、程进行系统的研究。他对这一非线性参数试用不同的值进行迭代计算。他发现，改变的不仅仅是输出的数量，而且也改变了输出的性质；因为它不仅影响着平衡时群体的数值，而且还影响群体是否能够实现平衡。 梅编制了计算机程序，慢慢增加k值，对方程进行数值运算。他发现，当k值小于1时，在0到1之间任意取初值x0，经过若干次迭代，虫口数趋于终态x*=0，表示生物群体将灭绝，这是可以预料的。当1k3时，任取初值x0，经过一系列迭代（演化过程）后，虫口数越来越趋于一个稳定态x*=1-1/k；如取k=2，则虫口数将最终稳定在x*=0.5；若取k=2.4，则x*=0.5833；若取k=2.7，则x*=0.6292；随着k值

8、的增大，稳定平衡值也会增大，但系统的行为没有质的变化，都会达到一个稳定的定态（即虫口数达到一个稳定值）。,为了在全局上对逻辑斯蒂差分方程的解（即最终定态）做出了解，梅以参数k值的变化为横坐标，以群体最终虫口数为纵坐标，把二者的变化关系集拢在一张图上。 迭代计算发现，当k值超过3之后，系统的定态失稳了，这条线分裂为两条，虫口交替振荡于两年的两点之间，x*值在两个数之间一年一换地交替跃变，这是周期2循环。当k值增大到3.5左右时，周期2吸引子也开始失稳，出现周期4循环，群体的不同起始值x*都收敛于以4年为周期的循环中，每4年返回近原值一次。当k值增至3.56后，周期又加倍到8；k到3.567时，周

9、期达到16。此后将更快地出现32、64、128的周期倍化序列。这就是“周期倍化级联”；倍周期就是分叉或双分枝现象。周期分裂再分裂，这种双分枝越来越快地发生，以致到k=3.58左右这种分裂突然呈现崩溃之势，周期性态就变成混沌，虫口的涨落再也不会确定下来，虫口的逐年变化完全成为随机的，全部区域染成了墨色。,简单的动力学系统，在非线性作用下，当k从0趋向4时，其动力学性态的复杂性逐步增加，即从定态变为周期性态，通过周期倍化级联而到达混沌性态。 但这还不是最终的图景。更令人惊奇的是，在这个复杂的区域中又会突然出现一个有正规周期的窗口（图8中狭窄的白条部分）；不过周期由偶数变为奇数。如当k=3.835时

10、，出现周期3循环；轻微地增加k值，周期以新的“倍化级联”出现6、12、24、48周期。当k=3.739时，将得到周期5循环，此后又是双分枝的10、20、40的周期。愈来愈快的倍周期双分枝再度爆发出现混沌。 这是一个十分奇妙的图景：分叉再分叉，加快更加快，周期性态走向混沌性态，混沌区内又出现周期窗口；窗口内还有更小的窗口，出现更稠密的周期性态；放大任何窗口，都会重现整个图景的微缩复本。,图象特别明显地显示出，周期区内分叉序列中两个相邻分叉点之间的距离越来越快地缩短，而且似乎有某种规则的比例关系。 美国物理学家费根鲍姆(Feigenbaum，Mitchell) 发现了几何收敛的周期僵化级联现象的规

11、则性，对收敛的速度标度比的值进行了深入的探讨。 19751976年，费根鲍姆开始对逻辑斯蒂映射的研究。用穿孔卡分批输入数据，几天后才能出结果。因此，费根鲍姆选择用惠普HP65型可编程计算器。因为计算器算得很慢，促使操作者在结果出来以前常去思考它。 为了节省时间，费根鲍姆尝试大致揣测级联中的下一个分叉点可能在哪里。不久他就发现了规律，相继的分叉点之差具有恒定的比率，前一个差值约为后一个差值的4倍，更精确地说，这二者的比率约为4.669。对一个物理学家来说，恒定比率意味着标度率，表明物理学特征必在愈来愈小的标度上再现，这当然是极为重要的。费根鲍姆用这个方法对另一个映射即三角映射xksin(x) 进

12、行了计算，同样发现了周期倍化级联和几何收敛现象，更为惊人的是它的标度比值也是4.669。,费根鲍姆利用计算机进行了更精确的计算。对于逻辑斯蒂映射，他很快得出了一个更精确的标度比值：4.6692016090；对三角映射重复计算，到小数点后10位，两数完全相同。看来标度比不依赖于方程，无论逻辑斯蒂映射还是三角映射，没有什么差别。这当然不可能是巧合。 费根鲍姆的发现表明，在逻辑斯蒂映射一类的非线性映射中，倍周期分叉遵循一个普适性规律：当t时，分叉间距比存在一个极限值（更精确的）=4.66920160910399097 同时，分叉也在越来越窄的宽度上出现，这又是一种普适性规律：相邻两个分枝间的宽度按一

13、定比率缩小，缩小因子在t时也存在极限值 =2.5029078750958928485 这两个常数被称为“费根值”(Feigen value)。费根值的普适性也具有相对性，它只适用于具有像抛物线那样的峰的单峰映射；对于多峰或者具有扁平峰和尖峰那样的情况，标度比值将会不同；但每一类的映射，其标度比总是相同的。,费根鲍姆的发现，是一条普遍适用于一切从有序转变到混沌的动力系统在转变点上的自然规律。这种普适性不仅是结构的，而且是测度的。 这一发现的意义在于，动力系统中存在着标度变换，它不仅控制着分叉花样，而且延伸到精确数值。事物整体具有与其部分相似的结构，说明在完全确定的系统中不需要引入任何干扰，就可能

14、出现不规则的随机运动，这是一种内禀特性。 费根鲍姆关于普适性的发现，指引人们走上混沌科学的大道，推动了非线性科学的发展。,元胞自动机,存在不同的解释： 物理学家将其视为离散的、无穷维的动力学系统 数学家将其视为描述连续现象的偏微分方程的对立体，是一个时空离散的数学模型 计算机科学家将其视为新兴的人工智能、人工生命的分支 生物学家则将其视为生命现象的一种抽象,元胞自动机的物理学定义,元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。 具体讲,构成元胞自动机的部件被称为“元胞”，每个元胞具有一个状态。这个状态只取某个有限状态集中

15、的一个，例如或“生”或“死”，或者是256中颜色中的一种，等等 这些元胞规则地排列在被称为“元胞空间”的空间格网上;它们各自的状态随着时间变化。而根据一个局部规则来进行更新，也就是说，一个元胞在某时刻的状态取决于、而且仅仅取决于上一时刻该元胞的状态以及该元胞的所有邻居元胞的状态;元胞空间内的元胞依照这样的局部规则进行同步的状态更新，整个元胞空间则表现为在离散的时间维上的变化。,元胞自动机的数学定义,美国数学家L.P.Hurd和KCulik等人在90年代初，对元胞自动机分别从集合论和拓扑学等角度进行了严格地描述和定义 基于集合论的定义 设d代表空间维数，k代表元胞的状态，并在一个有限集合S中取值

16、，r表元胞的邻居半径。Z是整数集，表示一维空间，t代表时间。为叙述和理解上简单起见，在一维空间上考虑元胞自动机，即假定d=1。那么整个元胞空间就是在一维空间，将整数集Z上的状态集S的分布，记为SZ。元胞自动机的动态演化就是在时间上状态组合的变化，可以记为:这个动态演化又由各个元胞的局部演化规则f所决定的。这个局部函数f通常又常常被称为局部规则。对于一维空间，元胞及其邻居可以记为S2r+1，局部函数则可以记为:,对于局部规则f来讲，函数的输入、输出集均为有限集合，实际上。它是一个有限的参照表。例如，r=1，f的形式则形似如下:0,0,0-O; 0,0,1-0; 0,1,0-1; 1,0,0-0;

17、 0,1,1-1; 1,0,1-0; 1,1,0-0; 1,1,1-0对元胞空间内的元胞，独立施加上述局部函数，则可得到全局的演化: cit 表示在位置i处的元胞，至此，我们就得到了一个元胞自动机模型。,元胞自动机的构成,元胞自动机最基本的组成元胞、元胞空间、邻居及规则四部分。简单讲，元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。,解释,1.元胞元胞又可称为单元。或基元，是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上。 2.状态状态可以是0,1的二进制形式。或是s0,s2,sisk整数形式的离散集。 严格意义上，元胞自动机的元胞只能有一

18、个状态变量。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量。,3.元胞空间(Lattice),元胞所分布在的空间网点集合就是这里的元胞空间。(l)元胞空间的几何划分 理论上，它可以是任意维数的欧几里德空间规则划分。目前研究多集中在一维和二维元胞自动机上。对于一维元抱自动机。元胞空间的划分只有一种。 高维的元胞自动机, 元胞空间的划分则可能有多种形式。最为常见的是二维元胞自动机。二维元胞空间通常可按三角、四方或六边形三种网格排列 (图2-5)。,三种规则的元胞空间划分在构模时各有优缺点: 三角网格的优点是拥有相对较少的邻居数目，在某些时候很有用；其缺点是计算机表达与显示不方

19、便，需要转换为四方网格。四方网格的优点是直观而简单，特别适合于现有计算机环境下进行表达显示；其缺点是不能较好地模拟各向同性的现象，例如后面提到的格子气模型中的HPP模型。 六边形网格的优点是能较好地模拟各向同性的现象，因此，模型能更加自然而真实，如格气模型中的FHP模型；其缺点同三角网格一样，在表达显示上较为困难、复杂。,(2)边界条件,在理论上，元胞空间通常是在各维向上是无限延展的。但在实际应用中，无法在计算机上实现这一理想条件，因此，需要定义不同的边界条件。 归纳起来，边界条件主要有三种类型:周期型、反射型和定值型。有时，为更加客观、自然地模拟实际现象，有可能采用随机型，即在边界实时产生随

20、机值。周期型(Pehodic Boundary)是指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的圈。对于二维空间，上下相接，左右相接。而形成一个拓扑圆环面 (Torus)，形似车胎或甜点圈。周期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间型作为试验。反射型(Reflective Boundary)指在边界外邻居的元胞状态是以边界为轴的镜面反射。例如在一维空间中，当r=1时的边界情形:,定值型 (Constant Boundary)指所有边界外元胞均取某一固定常量，如0，1等。需要指出的是，这三种边界类型在实际应用中，尤其是二维或更高维数的构模时，可以相互结

21、合。如在二维空间中，上下边界采用反射型，左右边界可采用周期型 (相对边界中，不能一方单方面采用周期型)。 (3)构形:在元胞、状态、元胞空间的概念基础上，引入另外一个非常重要的概念，构形(Configuration)。 构形是在某个时刻，在元胞空间上所有元胞状态的空间分布组合。在数学上，它可以表示为一个多维的整数矩阵。,4.邻居 (Neighbor),以上的元胞及元胞空间只表示了系统的静态成分，为将“动态”引入系统，必须加入演化规则。 在元胞自动机中，这些规则是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定的邻居规则，明确

22、哪些元胞属于该元胞的邻居。在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有以下几种形式(以最常用的规则四方网格划分为例)。见图2-6，黑色元胞为中心元胞，灰色元胞为其邻居，它们的状态一起来计算中心元胞在下一时刻的状态。,5 规则(Rule),根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数。将一个元胞的所有可能状态连同负责该元胞的状态变换的规则一起称为一个变换函数。 该函数构造了一种简单的、离散的空间/时间的局部物理成分。要修改的范围里采用这个局部物理成分对其结构的“元胞”重复修改。这样，尽管物

23、理结构的本身每次都不发展，但是状态在变化。 可以记为f: sit+1=f(sit,sNt)，sNt为t时刻的邻居状态组合，我们称f为元胞自动机的局部映射或局部规则 。 6 时间 (Time)元胞自动机是一个动态系统，它在时间维上的变化是离散的，即时间f是一个整数值，而且连续等间距。假设时间间距dt=1，若t=0为初始时刻。那么。t=1为其下一时刻。在上述转换函数中，一个元胞在t十1的时刻只(直接)决定于t时刻的该元胞及其邻居元胞的状态，虽然，在t-1时刻的元胞及其邻居元胞的状态间接(时间上的滞后)影响了元胞在t+1的时刻的状态。,元胞自动机的特征,(1)同质性、齐性，同质性反映在元胞空间内的每

24、个元胞的变化都服从相同的规律，即元胞自动机的规则，或称为转换函数；而齐性指的是元胞的分布方式相同，大小、形状相同，空间分布规则整齐 (2)空间离散:元胞分布在按照一定规则划分的离散的元胞空间上 (3)时间离散:系统的演化是按照等间隔时间分步进行的，时间变量t只能取等步长的时刻点，形似整数形式的t0,t十1,t十2，而且，t时刻的状态构形只对其下一时刻，即t+1时刻的状态构形产生影响，而t+2时刻的状态构形完全决定于t+1的状态构形及定义在上面的转换函数。元胞自动机的时间变量区别于微分方程中的时间变量t，那里t通常是个连续值变量,元胞自动机的特征,(4)状态离散有限:元胞自动机的状态只能取有限(

25、k)个离散值(s1,s2,.,sk)。相对于连续状态的动力系统，它不需要经过粗粒化处理就能转化为符号序列。而在实际应用中，往往需要将有些连续变量进行离散化，如分类、分级，以便于建立元胞自动机模型 (5)同步计算(并行性):各个元胞在时刻ti+1的状态变化是独立的行为，相互没有任何影响。若将元胞自动机的构形变化看成是对数据或信息的计算或处理，则元胞自动机的处理是同步进行的，特别适合于并行计算,元胞自动机的特征,(6)时空局部性:每一个元胞的下一时刻ti+1的状态，取决于其周围半径为r的邻域(或者其它形式邻居规则定义下的邻域)中的元胞的当前时刻ti的状态，即所谓时间、空间的局部性。从信息传输的角度

26、来看，元胞自动机中信息的传递速度是有限的 (7)维数高:在动力系统中一般将变量的个数称为维数。例如，将区间映射生成的动力系统称为一维动力系统;将平面映射生成的动力系统称为二维动力系统;对于偏微分方程描述的动力系统则称为无穷维动力系统。 从这个角度来看，由于任何完备元胞自动机的元胞空间是定义在一维、二维或多维空间上的无限集，每个元胞的状态便是这个动力学系统的变量。因此，元胞自动机是一类无穷维动力系统。在具体应用中或计算机模拟时当然不可能处理无限个变量，但一般也总是处理数量很大的元胞组成的系统。因此可以说维数高是元胞自动机研究中的一个特点,典型的元胞自动机,J. Conway和 生命游戏 格子气自

27、动机 Langton和“能自我复制的元胞自动机”,J. Conway和 生命游戏,生命游戏 (Game of Life)是J. H. Conway在20世纪60年代末设计的一种单人玩的计算机游戏。 与现代的围棋游戏在某些特征上略有相似：围棋中有黑白两种棋子。生命游戏中的元胞有“生”，“死”两个状态 0，1;围棋的棋盘是规则划分的网格，黑白两子在空间的分布决定双方的死活，而生命游戏也是规则划分的网格(元胞似国际象棋分布在网格内。而不象围棋的棋子分布在格网交叉点上)。根据元胞的局部空间构形来决定生死。只不过规则更为简单。下面介绍生命游戏的构成及规则:(1)元胞分布在规则划分的网格上；(2)元胞具有

28、0，1两种状态，0代表“死”，1代表“生”；(3)元胞以相邻的8个元胞为邻居。(4)一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态 (确切讲是状态的和)决定。,在当前时刻，如果一个元胞状态为“生”，且八个相邻元胞中有两个或三个的状态为“生”，则在下一时刻该元胞继续保持为生，否则死去；在当前时刻。如果一个元胞状态为死。且八个相邻元胞中正好有三个为生。则该元胞在下一时刻 复活。否则保持为死。尽管它的规则看上去很简单。但生命游戏是具有产生动态图案和动态结构能力的元胞自动机模型。它能产生丰富的、有趣的图案。生命游戏的优化与初始元胞状态值的分布有关，给定任意的初始状态分布。经过若干步的运算

29、，有的图案会很快消失。而有的图案则固定不动，有的周而复始重复两个或几个图案，有的婉蜒而行。有的则保持图案定向移动，形似阅兵阵，其中最为著名的是滑翔机 (叫Glider)的图案。,生命游戏模型应用,演化规则近似地描述了生物群体的生存繁殖规律：在生命密度过小(相邻元胞数之2)时，由于孤单、缺乏配种繁殖机会、缺乏互助也会出现生命危机，元胞状态值由1变为0；在生命密度过大 (相邻元胞数3)时，由于环境恶化、资源短缺以及相互竞争而出现生存危机，元胞状态值由1变为0。只有处于个体适中(相邻元胞数为2或3)位置的生物才能生存(保持元胞的状态值为1)和繁衍后代(元胞状态值由0变为1)。正由于它能够模拟生命活动

30、中的生存、灭绝、竞争等等复杂现象，因而得名“生命游戏”。 JHConway还证明，此元胞自动机具有通用图灵机的计算能力，与图灵机等价，也就是说给定适当的初始条件，生命游戏模型能够模拟任何一种计算机。,格子气自动机 (LatticeGas Automata，LGA）,又称格气机，是元胞自动机在流体力学与统计物理中的具体化，也是元胞自动机在科学研究领域成功应用的范例 。相对于“生命游戏”来说，格子气自动机更注重于模型的实用性。它利用元胞自动机的动态特征，来模拟流体粒子的运动。第一个时空、速度等变量完全离散的格子气自动机是1973年由法国的JHardy、YPomeau和OPazzis提出的HPP模型

31、，它的模拟结果已经很接近流体力学中描述流体运动的Navier-Strokes方程。但模型中的流体粒子的运动只允许有四个方向，造成应力张量各向异性的致命弱点，尚不能充分反映流体的特征，因此在较长时间内没有受到足够的重视。,直到20世纪80年代，SWolfram等人的研究工作使得元胞自动机理论产生了质的飞跃，同时也带动了格子气自动机的进一步发展。 1986年，法国的UFrish、YPomeau和美国的BHassIacher在HPP模型的基础上提出了一个有实用价值的、基于六角形网络的格子气自动机模型，得名为FHP (Fritsch-Has，lacher-Pomeau)模型，并证明该模型的宏观行为符合

32、标准的Navier-Stokes方程。 FHP模型是第一个成功的格子气模型，并激发了研究格子气模型研究的热潮，人们在几年内发表了数百篇论文。在90年代中后期，一种被称为格点波尔兹曼方程 (Lattice Bolzmann)的改进模型逐步取代了原有的格气模型。,Langton和“能自我复制的元胞自动机”,元胞自动机是一种离散的动态模型，由于它可以模拟自组织、自繁殖、信息储存和传递等现象，因而，被广泛地应用于生命现象的研究中。目前兴起的人工生命的研究就是来源于元胞自动机的深入研究，其主要论点是认为“自我复制”乃生命的核心特征。 Christopher Langton在二维元胞自动机中发现的一个能自

33、我复制的圈或称能自我复制的元胞自动机,过程,Langton在von Neumann和Codd工作的基础上，设计了一个能自我复制的圈。元胞状态在 (0，1，2，3，4，5，6，7)中取值，其中，0，1，2，3构成元胞自动机的基本结构，04，05，06，07代表信号。l代表核元胞;2代表壳元胞，是边界;2包围的部分构成信息通道或称数据路径。邻居模型采用Von Neumann的4邻居模型。元胞自动机通过信号元胞替代相邻的元胞，如状态为1的元胞，而完成信号传递。信号传播的过程可以通过下面的例子说明:,数据路径可以分支，在分支的节点处，信号在各个分支中复制本身，产生多个复制品。下图中，07信号在T形的交

34、叉点处，复制自身:,这个元胞自动机模型的另外一个重要特征就是路径扩张。即一定的信号可以产生数据路径的延伸，如下图所示：,具有路径扩张的、能自我复制的圈,元胞自动机的分类,元胞自动机分类是元胞自动机的一个重要的研究课题和核心理论 S. Wolfrarm在一维元胞自动机的演化行为及计算机实验的基础上，将所有元胞自动机的动力学行为归纳为四大类： (1)平稳型:自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。 (2)周期型:经过一定时间运行后，元胞空间趋于一系列简单的固定结构(Stable Paterns)或周期结构(

35、Perlodical Patterns)。由于这些结构可看作是一种滤波器(Filter)，故可应用到图像处理的研究中。,(3)混沌型:自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统汁特征不再变止，通常表现为分形分维特征。 (4)复杂型:出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。,具有一定局部结构的复杂模式出现的概率相对要小一些。第三种混沌型则出现的概率最大，并且，其概率随着k和r的增大而呈现增大的趋势。,按元胞空间的维数分类，元胞自动机通常可以分为: (l)一维元胞自动机:元胞按等间隔方式分布在一条向两侧无限延伸的直线上，每个元胞

36、 (Cell)具有有限个状态s，sS=s1,s2,.,sk，定义邻居半径r，元胞的左右两侧共有2r个元胞作为其邻居集合N，定义在离散时间维上的转换函数f:S2r+1S可以记为:Sit为第i个元胞在t时刻的状态。 称上述A=S,N,f三元组(维数d1)为一维元胞自动机,(2)二维元胞自动机:元胞分布在二维欧几里德平面上规则划分的网格点上，通常为方格划分。以J. H. Conway的生命游戏为代表，应用最为广泛。由于，世界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法，转换到二维空间上，所以，二维元胞自动机的应用最为广泛，多数应用模型都是二维元胞自动机模型。,(3)三维元胞自动机：目前，Bays（1988)等人在这方面做了若干试验性工作，包括在三维空间上实现了生命游戏，延续和扩展了一维和二维元胞自动机的理论。(