（凝聚态物理专业论文）一种混沌细胞自动机的特性研究.pdf

摘要 细胞自动机( c a ) 是由j v o nn e u m a n n 提出，用来模拟生物的自组织行为 而构造的空间、时间、变量均离散化的动力学系统，由于c a 在自身迭代过程中， 可产生出多种复杂性行为，是一种研究复杂系统体系的理想化模型，可广泛应用 于物理、化学、天文、计算机等领域。在材料科学研究中，如何有效描述材料的 组织形态及其演变规律是一个关键问题。对于这类复杂的、动态的、带有随机性 的问题一直缺乏定量的数学描述，而细胞自动机所具有的简单、级联、并行特点， 尤其适合于这种复杂系统模型的构建与分析。 本研究以混沌及动力学基本的理论为基础，对一种具有最大混沌行文细胞自 动机特性进行研究。首先，简要介绍了细胞自动机的基本原理和四种分类，并根 据入参数对四种类型的c a 进行了定量分析，据此确定以最大混沌行为链c 规则 细胞自动机作为本文的研究和应用对象；其次，为精确地描述混沌链c 规则c a 的动力学行为，本文通过g 密度和入度对链c 规则吸引域的收敛程度进行了分析； 对一维二态三邻居9 0 规则的同步规律进行了分析和验证，给出在变长度下演化 同步过程模拟。本论文深入分析了细胞自动机演化机理和内在规律，研究了链c 细胞自动机的混沌特性，为在物质结晶、相变等演变规律以及化学混沌模拟研究 提供理论基础和建模依据。 关键词：细胞自动机；混沌；吸引域；同步 a b s t r a c t c e l l u l a ra u t o m a t a ( c a ) a r ed y n a m i c a ls y s t e m si nw h i c hs p a c ea n dt i m ea r e d i s c r e t e c ae x h i b i tc o m p l e xd y n a m i c sb e h a v i o u rs i m i l a rt ot h ec h a o si nw h i c h c o n t a i n sap l e n t yo fc o n f u s i o na n dd i f f u s i o nf u n c t i o n ，t h a tc a nb eu s e dt od om a n y i m p o r t a n ta p p l i c a t i o n s ，i nm a t e r i a l ss c i e n c e ，c ai sp a r t i c u l a r l yo u t s t a n d i n gi n s i m u l a t i n gt h ec r y s t a l l i z a t i o n ，w es t u d yd y n a m i c a lm e c h a n i s mo ft h ec h a o t i cc a f i r s t l y , w ei n t r o d u c et h eb a s i ct h e o r ya n df o u rc l a s s e so fc a ，a n a l y s et h ef o u r t y p e sc ab yt h e 九p a r a m e t e r a n dm a k et h em a x i m a l l yc h a o t i cc h a i ncr u l e st ot h e o b j e c tf o ro u r r e s e a r c h s e c o n d l y , i no r d e rt od e s c r i b ed y n a m i c a lb e h a v i o ra c c u r a t e l y , w ea n a l y s et h e b a s i n so fa t t r a c t i o no fc ab yt h eg - - d e n s i t ya n di n - - d e g r e e ；f i n a l l y , w eb r i n g s y n c h r o n i z a t i o np h e n o m e n ao f9 0c e l l u l a ra u t o m a t a k e y w o r d ：c e l l u l a ra u t o m a t a ( c a ) ；c h a o s ；b a s i n so f a t t r a c t i o n ；s y n c h r o n i z a t i o n 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得 的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文中作了 明确的说明。本声明的法律结果由本人承担。 学位论文作者签名：日期： 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、 汇编本学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库 ( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全文数据库( 中国科学技 术信息研究所) 等数据库中，并以电子出版物形式出版发行和提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：葚苎! 窒乡1 指导教师签名： 日期：互! 士：正日期： 学位论文作者毕业后去向： 电话： 邮编： 1 3 0 1 1 7 塑衅 步一乏銎丑 东北师范大学硕士论文 引言 细胞自动机( c a ) 是由j v o nn e u m a n n 提出，用来模拟生物的自组织行为 而构造的空间、时间、变量均离散化的动力学系统，由于c a 在自身迭代过程中， 可产生出多种复杂性行为嗍引，因此这种模型可广泛应用于物理州司嘲m 、化学 8 3 9 3 、城市交通1 4 1 1 5 16 | d t 、计算机加1 等领域。在材料学研 究中，一个关键的问题是如何有效描述材料的组织形态及其演变规律。对于这类 复杂的、动态的、带有随机性的问题一直缺乏定量的数学描述，而细胞自动机方 法在此方面具有独特优势。h w h e s s e l b a r t h 和i r g o b l e 隗1 在1 9 9 1 年成功地 利用细胞自动机方法模拟了二维情况下的再结晶过程、再结晶形核和核长大的动 力学模型以及不同参数和算法对再结晶行为的影响。另外在材料化学中，细胞自 动机可用来通过模拟原子、分子等各种微观粒子在化学反应中的相互作用和化学 反应过程。李才伟利用细胞自动机模型成功模拟了自催化三分子模型，并研究了 化学混沌与b z 反应的细观元胞自动机模拟2 4 绷。b o s t r o v s k y 和y b a r y a m 乜叼 等人利用细胞自动机模型构造了高分子的聚合过程模拟模型。 由于c a 具有动力学系统所特有的复杂的动力学特性，特别是混沌行为，能为 复杂模型构建与研究提供理想的工具。混沌运动是出现在非线性动力系统中的一 种现象，其典型特征是具有初值敏感性，即所谓的蝴蝶效应。也就是说，一个系 统的混沌行为对初始条件的变化具有高度敏感性，表现出极端的不稳定性”这种 高度不稳定性，是指在相空间内初始极其邻近的两条轨道，随着时间的推进，两条 轨道的距离彼此以指数形式迅速分离而永不相遇，它们的行为具有局部不稳定 性。研究混沌特性，对于动力学的应用具有重要意义。对c a 这种复杂的动力学 特性已有多人进行了研究，最著名就是w a l f r a m 在他的经典论文中1 ，对一维局 域规则c a 的统计机理进行了论述，他的研究结果显示：所有的一维c a 都可归为 四种基本的类型；第一类是从任意的初始状态演化的c a 最终都将到达一种单一 均匀态；第二类是演化到一种简单的短周期性结构；第三类是演化为混沌结构； 这三种行为特征相似于连续动力学行为的极限点、极限环和混沌吸引子。第四种 行为是一种可通过通常计算获得的更复杂行为。延续w a l f r a m 的工作，l a n g t o n 汹1 东北师范大学硕士论文 引入入参数( 入表示c a 中所有细胞在下一代演化中成活的概率) 定量分析四种 动力学行为特征。对于一维二态三邻居c a ，当入= o 5 时，也就是这种c a 的规则 输出表中具有相等的o 和1 分布，c a 呈现混沌的动力学行为特征。并且l a n g t o n 指出w a l f r a m 第四种类型的c a ，是对应一种临界入值时，在定态( o r d e r e d ) 和 混沌态( c h a o t i c ) 之间的相变( p h a s et r a n s i t i o n ) 行为。p a c k a r d 啪3 使用基因 ( g a ) 算法通过一种极其复杂的计算过程演化c a 验证l a n g t o n 的分析，他的实 验结果显示：通过基因算法选择的c a 能够接近临界入值( c r i t i c a l ) 区域，也 就是在混沌的边缘( e d g eo fc h a o s ) 。还有许多科学工作者对c a 的混沌行为进 行了研究啪3 ，但还未有公认的结论性成果。最近，w u e n s c h e 利用反向算法回溯 c a 吸引域来更直接描述c a 的动力学行为特征口1 | ，他指出，具有混沌行为c a 有 比其他几种行为较低的收敛度，反映在吸引域的个数随着系统个数的增大增加不 大，预示增加的系统状态都分布在狭长的暂态树上，吸引域周期变长；吸引域中 具有较少的伊甸园态( g a r d e n - o f e d e n ，是指c a 没有前驱的状态，又称g 态) ， 并且g 密度( 是指c a 中没有前驱状态，g a r d e n o f e d e n 态的比例) 随着系统数 目的增加变化趋为0 。w u e n s c h e 根据z 参数定义一种具有最大混沌行为特性c a 规则，本文依据这种方法选取混沌规则c a ，对其吸引域特性与其它类型吸引域 特性进行了对比分析，并研究了一维三邻居链c9 0 规则细胞自动机的同步规律。 2 东北师范大学硕士论文 第一章细胞自动机原理 1 1 细胞自动机( c a ) 定义 细胞自动机是5 0 年代初由y o nn o e m a n 提出的用于研究生物自组织行为的数 学物理模型。细胞自动机是空间、时间、变量离散化的动力学系统，是现实系统 的理想化品格模型。由于c a 通过短程相互作用可产生多种复杂的动力学行为， 因此这种模型广泛应用于物理、化学、天文、计算机等领域。 c a 由一些结构相同而又分立的细胞组成，这些细胞排列在d 一维空间上，构 成一维二维及d 一维的细胞自动机。c a 的每个细胞可以有多种取值，如颜色、生 与死、开关、整数数值等，目前最常用的是0 和1 取值。每一个细胞的取值都由 上一步最邻近细胞的取值决定，并且按照其局域作用关系( 规则) 在离散时间步 骤下同步进行更新。 1 2 细胞自动机的数学描述 一个d 维细胞自动机的数学定义可用集合表示：膨= ( 幺，s ， 厂) ，其中m 表示为某一细胞自动机系统；厶为d 维的细胞空间，d 取一系列的正整数，用 以表示细胞自动机空间维数；s 为细胞的有限状态空间集合，集合的每一个元素 为c a 的一个状态；为所有包括其本身及邻域内细胞的组合。厂是从j ”映射到 s 上的一个状态转换函数，这种状态转换函数即为细胞自动机规则，它体现了细 胞自动机的邻域作用关系。 1 3 细胞自动机的构成 ( 1 ) 细胞：又可称为元胞、单元或基元，是细胞自动机的最基本的组成部 分。细胞分布在离散的一维、二维或多维欧几里德空间的网格上，构成一维、二 维或多维细胞自动机。在一个规则网络中的每一个点，叫做一个细胞。每一个细 胞可一种存储类型，用来存储状态。在最简单的情况下，每个细胞有两种状态， 用二进制可表示为1 或0 。在更复杂的系统中，细胞有更多不同状态，也可以根 3 东北师范大学硕士论文 据不同应用来表示不同的细胞状态。 ( 2 ) 细胞状态：细胞状态一般是 s 。，s 。，s ，s 。) 整数形似的 离散集。在实际应用中，一个细胞只能有一个状态变量，但也可以根据应用将其 进行扩展，使得每个细胞拥有多个状态变量。目前随着计算机计算能力的逐渐增 强，细胞自动机应用时其状态也趋向于取多个数值，甚至可以是一个不同的变量。 这完全取决研究者的研究对象以及所处理的系统复杂程度。 ( 3 ) 细胞空间：细胞空间有时也称为细胞的状态空间，是指所有细胞放置 的细胞结构。对于细胞自动机空间而言，需要从空间几何维数划分和边界类型两 个方面确定。 a 空间维数划分 细胞自动机的空间维数，理论上可以是任意维数的欧几里德空间。限于目前 科学研究的条件，特别是计算机速度的要求，以往的研究多集中在一维和二维细 胞自动机上，三维以上的研究还比较少见。 b 边界类型 细胞自动机的边界条件是指细胞自动机的边界取值，虽然细胞空间可以在各 维度上是无限延展的，但是在实际应用过程中，必须赋予细胞自动机一定的边界 条件。我们在研究一维加性9 0 规则细胞自动机同步过程中，使用零边界和边界 为1 的条件，最常使用的是零边界条件和周期边界条件，一般的细胞自动机有如 下几种边界条件：周期型、反射型、定值型、随机型。 周期边界：是指细胞自动机的细胞空间状态是一个首尾相连的周期环，如 一般取1 和0 取值的周期环。对于一维空间，细胞空间表现为一个首尾相接的环。 对于二维空间，上下相接、左右相连而形成一个拓扑圆环面。周期型细胞自动机 与无限空间最为接近，在实际应用中常用此类边晁类型来进行边界的设定。 反射型边界：指在边界外邻居的细胞状态是以边界为轴做镜面反射。如在 一维细胞自动机当中，当r = l 时，其反射型邻域左右邻居取值完全一致，呈现出 左右对称的性质。如下图所示： 反射盛垃彝承童曩 4 东北师范大学硕士论文 定值型边界：是指细胞自动机所有边界外细胞状态均取某一固定常量， 如边界细胞取固定值0 或1 等，本同研究中固定边界取l 。 随机型边界：是指细胞自动机的边界可以任意取值，这在实际应用中， 能更加客观、自然地模拟实际复杂行为，但在计算上存在一定困难。随机边界可 以根据实际需要来指定，另外几种类型的边界也可以交替混合使用，尤其是在二 维或更高维数的建模过程中，可以相互结合。如在二维细胞空间中，上下边界采 用周期型，左右边界采用反射型。 ( 4 ) 邻居关系： 细胞自动机演化过程最重要的是要确定细胞之间的邻居关系。邻居关系决 定了细胞自动机的规则，如一维三邻居是指细胞下一个时刻的取值取决于其最邻 近三个细胞的状态，五邻居是指最邻近五个细胞之间的关系，习惯上，以邻域半 径r 来确定邻居，与中心细胞距离小于或等于邻域半径的细胞均在该细胞邻域范 围内。在确定细胞自动机规则之前，必须明确细胞之间的邻居关系。 以下是最常用的细胞自动机划分类型： ( 1 ) 冯诺依曼型( v o nn e u m a n nn e i g h b o r h o o d s ) 邻域大小为四，邻居半径r = 1 ，是一个特定细胞的上、下、左、右相 邻四个细胞为该细胞的邻居。如图a 所示： 硅靳蚺，妇哦n 髓 ( 2 ) 摩尔型( m o o r en e i g h b o r h o o d s ) 是在冯诺依曼型基础上定义的，邻域大小为8 ，半径为l 。一个细 胞的上、下、左、右、左上、右上、右下、左下相邻八个细胞为该细胞的邻居。 如图b 所示： 东北师范大学硕士论文 t b 心礁 ( 3 ) 扩展的摩尔型( e x t e n d e dm o o r en e jg h b o r h o o d s ) 将摩尔型的邻居半径r 扩展为2 或者更大，即得到所谓扩展的摩尔型邻 居。如图c 所示： c ) 扩麟的辚o o r e 鬻 ( 4 ) 马哥勒斯型( m a r g o l u sn e i 曲b o r h o o d s ) 马哥勒斯型是和以上邻居类型完全不同的形式，它是每次将一个2 x 2 的 细胞块做统一处理，而不是向以上邻居按每个细胞进行处理。 除去以上几种类型，还有最简单的一维邻居的组合方式，这种方式是最邻近 细胞之间的作用。在实际应用中，要根据不同的需要来选取不同的邻居类型关系。 如在加密应用中使用的一维3 0 规则细胞自动机，一维9 0 和1 5 0 规则细胞自 动机也应用广泛。在材料组织结晶、再结晶、相变等演变规律研究中，多采用二 维邻居的细胞自动机，这样更能呈现材料组织的微观结构以及规律。本研究中采 用一维五邻居和一维三邻居细胞自动机为研究对象。 ( 5 ) 规则 细胞自动机的规则就是根据细胞当前状态及其邻居状态确定下一时刻该细 胞状态的动力学函数，简单讲，就是一个状态转移函数。规则反映的是最邻近距离 内格点间或细胞间的相互作用即局域作用。依据不同邻域构造类型，细胞自动机 的规则数是规则是邻域半径及状态的指数函数。若每个细胞有k 种可能状态取 值，且邻域范围内有n 个细胞单元，则有k 趴“条规则。比如，对k = 2 ，n = 3 一维 6 东北师范大学硕士论文 细胞自动机，共有2 8 = 2 5 6 种规则。对k = 2 ，n = 5 的v o nn e u m a n n 邻域有2 3 2 种规 则；而对n = 8 的m o o r e 邻域约有2 2 5 8 种规则。这样看来。k ，n 越大，规则数将趋 向无穷大，目前主要应用一维二态三邻居和二维细胞自动机作为研究复杂系统工 具。 ( 6 ) 初态 个完整的细胞自动机模型除演化规则以外，还必须要构造一个初始模 型，就是所有初始细胞及其确定的状态取值，这种初始模型即为种子，细胞自动 机的状态演化过程就是根据规则、边界条件不断地并行更新下时刻细胞状态的变 化情况。 ( 7 ) 时间 细胞自动机是一种随时间变化的动力学系统，它在时间维数上的变化是离 散的。即按照时间t 连续等间距变化。一般情况研究细胞自动机时，取t 的下一 时刻为t + l 时刻，并且取相等的时刻间隔。 1 4 细胞自动机特性 根据细胞自动机的构成及其规则分析，细胞自动机具有以下几个特点： ( 1 ) 高度离散性：细胞自动机是空间、时间、变量均离散的动力学系统。 其时间的离散性是指系统的演化过程是按照等间隔的时间步骤进行的，一般按照 t + l 这种等步长的时间步骤进行；状态的离散性是指细胞自动机的状态只能取有 限离散值，比如0 或者1 ，相对于连续状态动力学系统，细胞自动机单元的有限 状态，排列成一个有规则的阵列结构，如一维、二维、或多维空间上，可以省略 粗粒化处理而直接转化为符号序列，便于计算和进行计算机处理。其演化过程可 消除连续微分方程产生的截断误差以及其他计算方法产生的误差积累。 细胞自动机状态离散性所产生的优势是其他常规计算方法完全无法做到的， 是细胞自动机最具魅力的一个特性。另外细胞自动机在空间上的离散行为也便于 其应用于模型的构建。 ( 2 ) 高度并行性：是指细胞自动机的每一个细胞的状态按照确定的规则同步 演化，各个细胞之间微观上互相独立，在同一时刻上相互没有任何影响，但在宏 观演化上是同步的。在实际应用时若将细胞自动机的状态( 如0 和1 ) 变化过程 看成是对数据或信息的计算或处理，细胞自动机的计算具有空间和时间上的一致 7 东北师范大学硕士论文 性，这种过程适合于并行计算。 ( 3 ) 相互作用的局域性：每一个细胞的下一t + l 时刻的状态取值，按照 规则取决于邻居细胞的状态，即邻居细胞t 时刻的状态。所以，细胞自动机的演 化规则是局部的，而不是全局的，但其表现出来的动力学演化行确是全局的。 ( 4 ) 高维度数：按照细胞自动机的定义，可以是在一维、二维或多维空 间上的无限集，每个细胞的状态便是这个动力学系统的变量，所以细胞自动机可 以看成是无穷维动力系统。这样在实际应用中具备了处理无限个变量的能力，所 以说维数高是细胞自动机研究中的另一优势。 如果令i 、t 、y ：、x ：+ 1 分别表示一个细胞在阵列中的序列号，时间步骤， 一v i，v l 第i 个细胞在第t 时刻的输出状态和第i 个细胞在第t + l 时刻的输出状态。则对 于一维c a 可以表示如下： *o9 x l + 砂 ( 1 ) j2 z 【x f 一，x f+ ，) ( 1 ) 其中r 为邻居半径，z 为组合逻辑，又称做规则。对于一维二态三邻居的c a ，第 i 个细胞的演化状态x ： o ，1 ，由第i + l 、i 一1 、和i 共同作用产生，规则可 以有不同的表示方式，最简单的是二进制的规则输出表形式，如规则输出表： 1 1 11 1 01 0 l1 0 00 1 10 1 00 0 10 0 0 011o11 0o 规则输出也可以表示成十进制形式： 0 1 0 1 1 0 1 0 = 2 6 + 2 4 + 2 3 + 2 1 = 9 0 ；或十六进制为5 a ( h e x ) 9 0 规则相应的组合逻辑表达式是： x ：+ 1 = x ：一。ox r + 。x f x f l 彬x 件1 同样1 5 0 规则可以写成： x ：+ 1 = x ：一。ox ：ox r + 。x f x f l 彤x f 形x j + l 1 0 5 规则可以写成： f + 1 x i 1 4 5 规则可以写成： = x ：+ 。o x ：o x ：一。 8 ( 2 ) ( 3 ) ( 4 ) ( 5 ) 东北师范大学硕士论文 9 ( 6 ) 东北师范大学硕士论文 第二章细胞自动机分类分析 细胞自动机可根据不同的分类原则进行分类，按照维数分为一维、二维或多 维细胞自动机，按照动力学的演化行为，s t e p h e nw o l f r a m 将细胞自动机进行了 分类分析，归纳成四大类型，本研究主要依据s t e p h e nw o l f r a m 的分类方法对具 有混沌细胞自动机进行研究。 2 。1w o i f r a m 的c a 时空演化模型分类 c a 的时空演化模型是指c a 按一定规则从给定初始状态条件出发的全局运行 轨迹。与一般动力学系统不同，c a 在演化过程中要受到诸多条件限制，如边界 条件、初始状态、演化时间和步骤以及c a 规则等，所以c a 可演化多种复杂结构 模型，一般是指显示行为是静态、周期态、局域复杂态( 相互突发作用结构) 、 混沌态。 w o l f r a m 2 7 】把所有一维三邻居c a 规则的时空演化结构模仿连续动力学分类 方式分为4 类，如表2 所示： 表2 1 ：c a 演化模型分类 c a 种类演化状态动力学行为描述 1 类( o r d e r e d )一种空间的单一态极限点 2 类( o r d e r e d )一系列稳定或周期性结构极限环 3 类( c h a o t i c )混沌非周期行为混沌( 奇怪) 吸引子 4 类( c o m p l e x )局域复杂性行为 不定吸引子 第一类型c a ：这种类型的细胞自动机，取任意初始状态经过一段时间的演 化步骤后，到达一种相同的单一态，所有细胞都有相同的值。此种c a 可以为相 空间的一种简单“极限点”，这种演化过程损失所有初始的状态信息，时间和空 间的吸引子都为0 。这类规则有0 ，4 ，1 6 ，3 2 ，3 6 ，4 8 ，5 4 ，6 0 ，和6 2 。 第二类型c a ：这种类型的细胞自动机产生一种简单分离或为稳定的状态或 1 0 东北师范大学硕士论文 为一种短的周期性结构。可将此种行为可视为一种过滤器，能够过滤出一些特殊 的初始序列值，此种初始序列值的密度确定最终演化行为，如果改变每一点值常 常只影响最终状态的某一有限范围，对于有限状态的类2 c a ，最终进化成短周 期的周期环。典型的规则有：8 ，2 4 ，4 0 ，5 6 和5 8 。 第三类型c a ：这种c a 几乎从所有的初始状态演化都能演化成为一种非周 期的结构，具有典型的混沌行为特征，此种c a 经过足够长的演化步骤后，模型 的统计特性和所有初始状态的特性具有相似性，所有非0 点的密度趋向于固定值 1 k ( k 为细胞状态的取值范围) ，再者对于绝大多数的第三类行为c a ，平均周 期长度随着细胞初始数目n 增加缓慢，但在某些点，最大周期随着系统数目指 数性增大。典型第3 类行为的c a 有：6 ，1 0 ，1 2 ，1 4 ，1 8 ，3 0 ，3 4 ，3 8 ，4 2 ， 4 4 ，4 6 和5 0 。 第四类型c a ：这种c a 具有局域复杂和扩散性结构，是一种在类2 和类3 之间的相变行为，此类c a 利于完成通用的计算过程。如果将此类c a 可看成是 一种计算机，c a 初始状态演化的过程可看作计算机中数据处理过程。所谓的通 用计算意味着可以通过合适的c a 初始结构能够模拟任意的计算过程，因此这种 系统可被作为有能力进行通用意义有任意计算功能的计算机。同样给定一个适合 的编码，此系统理论上能够模拟任意行为系统。对于一维二态三邻居c a ，具有 这种行为的规则有：2 0 和5 2 规则。 下面图形为一维二态三邻居c a 的模型举例。图形的最上边是c a 的初始状 态，向下为时间演化步骤，黑点为1 ，白点为0 。 一维三邻居规则3 6 时 间 步 骤 t 图2 1c a 演化成一种单一态 上图类型c a ，经过几轮迭代之后，细胞会全部死亡或是不再做任何改变， 东北师范大学硕士论文 具有典型的均匀性特征，此类型的c a 几乎不受初始状态的影响。 一维三邻居规则4 0 时 间 步 骤 t 图2 - 2c a 演化成一种简单周期态 在上图的c a 中，最后演化的细胞，除了静止不动的细胞外，其他的会进入 周期性振荡，并且不会再有其他的变化，其特征是周期性。 一维三邻居规则3 0 时 间 步 骤 t 图2 - 3 c a 演化成混沌态 在第三类c a 演化行为中，c a 的迭代过程只有极短暂的稳定形态，绝大多数 细胞处于过度活跃与随处变化的过程，观察不到特定的周期模式，具有典型的混 沌行为其特征。此类型的c a 对初始状态非常的敏感( 混沌初值敏感性) 是指： 当所有细胞演化于同一个规则，并以些微差别而几乎一样的两个初始状态，作迭 代比较的时候，将发现随着迭代次数的增加，两个初始状态的运行轨迹差别极大。 一维三邻居规则2 0 时 间 步 骤 t 图2 _ 4c a 演化成一种复杂态 1 2 东北师范大学硕士论文 在第四类c a 规则中，c a 的演化结构处于有秩序和混乱之间，是交错的周期 性的稳定振动与不断分化杂乱区域，而且这种原本混乱无章的细胞群有时会暂时 变的稳定下来，再经过一段时间后又开始分裂与扰动，甚至可以看到有滑翔机类 似情形在不同结构之间进行信息的交换。这样就有有利创造性与自我组织在演化 过程不断呈现，可很好的体现生命的演化行为。 2 2c a 时空模型分类的入参数分析 以上分析的w a l f r a m 四种分类类型中，第三类c a ，即混沌行为具有更复杂 的不可预见的动力学行为，第四类c a 是介于一、二类与三类之间的一种所谓的 相变过程。对于c a 分类特别是混沌的定义学术界尚无一致的定义，比较常用的 方法是l a n g t o n 口1 等人引入入参数对c a 模型进行定量分析。入表示的是c a 中所 有细胞在下一代演化中成活的概率。例如对于一维二态c a ，如果一个规则的入 值是0 的话，那么在经过第一次迭代之后，就没有存活的细胞，那么此规则就 属于第一类型的c a 。如果这个规则的入值是o 5 ，细胞经过迭代演化后会充 满各种活动，平均有一半的细胞存活，也有一半细胞死亡，此规则属于混沌的第 三类型c a 。当入值超过o 5 以后，死亡与成活的细胞不断交替，直到入值 到达1 o 时，又回到第一类型c a 的状态。这种第四类c a 发生在一种临界入值， 可视为在周期性行为和混沌行为的一种相移。 入参数定义：如果c a 的取值范围为k ，这样c a 有0 ，1 ，2 ，k - 1 种可能 的取值，n 表示为规则表中细胞取值为0 ( 静止值) 的数量，n 为邻居数目，那 么入就是c a 规则表中非0 的比例。 五= 后_ n k n 研究发现，通过调整入在0 到卜( 1 k ) 的取值就可以对c a 进行以上分类。 对于混沌c a 规则，分配给予k 的取值在规则表中以相等的概率，所对应这些各 种取值的密度( 包括静止值) 都严格地相等，入兰卜( 1 k ) 。对应这种入值的 c a 时空模型就最大可能地呈现为混沌行为。其它类型的c a 也可按不同的入值进 行构造，最典型的是选定静止值的概率x ，九= l - x ，其它非静止值的值被赋于相 等的概率入( k 一1 ) 。对于二态细胞自动机规则，入是规则表中1 的密度，而最 1 3 东北师范大学硕士论文 大混沌行为是发生在入= 1 2 ，也就意味着在规则表中具有相等数目的0 和1 。如 果调整入参数在0 和1 2 ( 与1 2 和1 具有对称性质) 可对应w o l f r a m 定义的四 种分类，四类c a 与入参数值对应关系可按如下所示： c l a s s =l i ng e n e r a l ，入：0 k = 2 ，入：0 - - - - 复杂性行为 f 2 _ 4 啼3 1 一( 1 k ) 1 2 通过入参数( 入= 1 2 附近) 可分析混沌c a 的初步特征，但入参数值只是c a 混沌行为的一种基本条件，不同的入参数值对应的只是c a 的一种平均动力学行 为，并不能精确地体现混沌行为特征。如具有相同1 和0 分布的c a 规则，o 和1 在规则列表的不同位置，其动力学行为特征并不完全为混沌行为，例如1 7 0 规则， 其规则输出为1 0 1 0 1 0 1 0 ，虽然具有相同的0 和1 分布，但其动力学行为趋向为 周期性类2 行为，其原因还有待研究。 2 3 最大混沌行为链c 规则c a 在上节中主要讨论了w a l f r a m 时空演化模型的四种分类，还有l a n g t o n 等人 借助入参数定量地对c a 的分类分析，可以看出以上两种方法只是c a 统计意义上 的一般性研究，对c a 的混沌行为论述还不充分。最近，w u e n s c h e 盥通过衡量c a 在时间演化过程中输入熵的不同实现对c a 规则的分类，其中对于混沌行为的c a ， 演化过程输出0 和1 查表频率分布均匀，体现系统混乱程度的熵值具有最大值。 w u e n s c h e 对输入熵进行如下定义：如果把一个特定组块出现的概率( 熵) 定义 为输入频率( 熵) ，那么输入频率( 熵) 是指c a 的规则表中所有邻居组合在c a 时间演化过程中出现的频率。假设系统细胞数目为n ，w 为时间窗口的进化步骤， k 为c a 的邻居数目，那么整个时间进化过程的细胞数目就为n w 。计算出所有 n x w 的细胞数目中2 。种邻居组合状态的出现概率即构成了c a 的邻居输入频率 ( 熵) 分布。对于一步时间步骤t 的输入熵s ( w ：1 ) 可表示为： s = 一：( ( q ；n ) x l o g ( q ；刀) ) ( 2 ) 1 4 东北师范大学硕士论文 公式中纠刀是邻居i 在时刻t 的查表频率。如果对整个时间步骤的输入熵 值进行描绘与计算，可得到整个时间演化过程中这个规则c a 的输入熵分布，从 而判定不同c a 的动力学行为。 w u e n s c h e 在依据以上熵值原理性引入z 参数定义了一种具有最大混沌行为 的链c ( c h a i nc ) 规则c a 。z 参数是d d l a b 反向算法中推导下一个未知比特的 概率，z 参数不同对应c a 呈现不同的动力学行为特征，通过这种反向算法可回 溯c a 的演化轨迹，得到其吸引域结构。这种反向算法定义如下：一种一维k 邻居 细胞自动机的细胞数目为n ，通过计算回溯出所有已知状态a 的前驱，如果p 是 部分前驱，其中至少有k 一1 比特是已知的，例如从左边开始，去回溯右边下一个 未知比特。图2 3 1 中p ，、p ：是t 时刻已知细胞前驱状态，而p 。是未知前驱状态， i 。是p 。在t 时刻的演化状态，通过查找规则输出表定值，由已知p 。、p 2 和i 。向 右能够回溯出下一个未知前驱状态p 2 ，回溯过程如图2 3 - i 描述，其中0 代表已 知比特，l c 代表未知比特。 待推测的下一个细胞 p 1p 2p 3 t i部分前驱p o t m已知状态a o ，l c木 o o 图2 3 1 一维三邻居c a 反向算法实现过程简图 定义z 参数是能够确定下一个未知比特的概率，这种概率共有两种情况。z m 。 是计算从左到右的概率，z 珊。是计算从右到左的概率，取z l e f t 和z 嘲。中最大值为 z 值。链c 规则c a 的z 。，。或z r i 柚中有一个为1 ，但不是都为1 ，另外z 。，或z 岫。 都大于0 5 确保这种规则c a 时空模型具有最低的收敛度，在这样的系统状态中 常常仅有一个前驱，所有的这些前驱组成一个链条，即称为c h a i n 。具有链c 特 性的c a 预示整个状态的周期变长，没有前驱状态数量( g 密度) 在这个状态空 间的比例随着系统大小的增加变化趋为0 。链c 的定义方法，既能通过熵值反映 混沌c a 的混沌复杂性特征，又可通过混沌规则的z 参数比入参数更精确体现混 15 东北师范大学硕士论文 沌c a 的吸引域拓扑特征，是一种较理想研究混沌c a 的方法，也是本文主要采用 这种方法选取c a 作为研究对象。 至此本节介绍了c a 的定义、组成以及特征，并依据w a l f r a m 分类方法，对 定态、周期态、空间局域复杂态和混沌态进行了讨论；分析了l a n g t o i l 的入参数 对c a 几种行为定量分析方法。最后本文采用w u e n s c h e 定义的具有最大混沌 c h a i nc 规则作为本文的研究对象。 1 6 东北师范大学硕士论文 第三章链c 规则细胞自动机混沌特性分析 本章以w u e n s c h e 定义的链c 一维五邻居细胞自动机为研究对象，对细胞的 收敛特性与z 参数的关系进行分析，并从吸引域入度、g 密度分布研究链c 规则 细胞自动机收敛特性。 3 1 细胞自动机吸引域收敛特性与z 参数分析 细胞自动机的吸引域是是指细胞所有状态空间的集合。c a 作为一种时间、 空间均离散的耗散性系统，一个细胞状态可以有多个前驱、或者没有前驱，也可 以只有一个前驱，状态前驱的数目叫入度( p r e i m a g e ) 。如果一个c a 的结构确 定，其运行轨迹也就具有了唯一的确定性。细胞自动机所有状态所组成的有限空 间叫做c a 的状态空间。例如对一个大小为n 的二态动力学系统而言其状态空间 中有2 n 种状态。系统中每一个人状态的运行轨迹是系统从初始状态到达下一时 刻状态的路径，这里任何一个状态在运行过程中迟早要遇到一个以前发生的一个 状态，这样状态就陷入到一种重复状态的持续环中，这种重复的状态环又叫做吸 引子( a t t r a c t o r ) ，重复的状态个数叫这个吸引子的周期，如果重复的状态个数仅 仅为一，叫做点吸引子( p o i n ta t t r a c t o r ) ，这时的状态空间模型变的完全稳定， 即为第一类c a ，相反对于一个混沌的动力学系统的空间模型，则存在一种非常 长的吸引子周期。 如果能够回溯动出一个动力学系统所有状态的运行轨迹，找出每一个状态的 前驱，最终所形成的全局结构，就是这个动力学系统的吸引域。对于c a 而言， 不同类型的c a 其吸引域的收敛程度等特征各不相同。k a u f f m a n 4 】研究指出：高 收敛程度的c a 表明状态空间具有短的周期环，对应c a 的1 类和2 类行为；低 的收敛程度意味着具有很长的周期环，对应c a 是一种典型的混沌特征。 在w u e n s c h e 提出的z 参数中，其定义是确定下个未知比特的概率 5 】，可 以通过查找c a 规则输出表计算两种情况的概率。如当z = i 时，意味着规则表中 具有相同的0 与1 的个数，未知前驱状态能够被唯一确定，是一种确定性规则。 对数目大小n 的系统，从开始k 一1 的比特流能够产生最大为2 h 的前驱，其结果 东北师范大学硕士论文 是系统具有最大入度( i 。2 卜1 ) 。如果z 。m 或z 蝴。中只有一个为1 ，意味着在反 向推导未知状态前驱状态时只有一个方向上的前驱能够被唯一确定，另一个方向 则无前驱状态。如当z = 0 时，系统所有的状态在一步内演化成全为0 或全为1 的 状态。可以看出z 值越高，数目大小n 的系统，在吸引域中预示较低的收敛度， 并且随着系统大小n 的增加，入度以较低的速度进行增长；相反如果z 越低，系 统具有较高的入度，随着系统大小n 的增加，入度则以较高的速度进行增长。z 参数不同取值不仅体现c a 了规则表中0 和l 的比例，更重要的是体现了0 与l 在规则表中的排列位置。也就是说即使c a 规则具有相同o 和1 分布，由于0 和 l 在规则中位置不同，c a 的动力学行为也各不相同。 3 2 一维五邻居链c 细胞自动机吸引域分析 通过以上分析发现：z 参数较入参数更能完整反映c a 的动力学行为。不同 类型的细胞自动机对应不同变化的z 参数值，也表现为不同性质的吸引域结构类 型。w u e n s c h e 依据z 参数定义一种具有最大混沌行为的链c 规则。这种规则的 z i e r 或乙吐。都大于o 5 ，其中仅有一个为l ，但不都为1 。本节主要研究一维五邻 居链c 细胞自动机的吸引域特征，此种类型的c a 的邻居关系是最临近五个细胞 共同作用结果，可表示为口f t + l = z ( 口t h ，口t ，口t ，口t ，口t m ) ，如果用简化方式4 、 3 、2 、1 、0 分别表示口：一：口t ha ：口t 口t m 几个邻居索引号，则这种一维五邻居 c a 的规则输出表就可以用如下表示： 4 1 1 1 1 1 1 1 11 1 1 1 1 1 1 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 3 一1 1 1 1 1 1 1 10 0 0 0 0 0 0 01 1 1 1 1 1 1 l0 0 0 0 0 0 0 0 邻居索引号2 1 1 1 1 0 0 0 01 1 1 1 0 0 0 0 1 1 1 1 0 0 0 01 1 1 1 0 0 0 0 1 1 1 0 0 1 1 0 01 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 01 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 il 规则输出表索引号3 l 6 1 0 0 1 0 11 01 0 0 1 0 11 00 11 0 0 11 0 1 0 1 0 1 0 0 1 一规则输出表 规则十六进制表达式= r u l e9 6 9 6 6 6 a 9i nh e x 规则十进制表达式= r u l e2 5 2 6 4 3 9 0 8 1i nd e c 东北师范大学硕士论文 通过z 参数的改变能够选取不同类型的细胞自动机，我们利用d d l a b 软件 随机选取两种类型的一维五邻居c a 规则：混沌链c 规则9 6 9 6 6 6 a 9 ( h e x ) ；非 链c 规则b f 2 f 0 9 6 f ( h e x ) 。图3 2 1 、3 2 2 为上述两类c a 的吸引域图。 蝴蟮吨f d e c l 2 例棚嬲l 伽 x j 弼“胡b o a s t t y p e s = 4 t o t a l b o a i a s - - f f l d s i z e = l o l d = 0 $ 1 d - r = l p = 0 5 z i = l z r = o 2 5 z = l c 4 1 5 n = l o f i e d d = 1 0 2 4 1 i = 3 9 0 = 0 3 s 1o 0 2 9 s e c 图3 2 1 ：混沌链c 规则9 6 9 6 6 6 a 9 吸引域，其中初始细胞数目为n = l o ，整 个状态数目为1 0 2 4 个。共有5 个吸引域，有4 种吸引域类型，伊甸态有3 9 0 个，g 密度为o 3 8 1 。 ao 蝴陋n k r k c ) 3 2 0 7 5 3 0 8 6 3 懦、- w 。硼- 7 - 螺簋留k 捌h t 摊髓= t m 越k 曲晖= 1 3 n 础犯：l i 缸：口- 篮h 呻= 0 7 s p = 0 五2 5 z l + 0 3 7 s 墨= 0 3 7 5 2 4 1 7 $ c = l l t s n = l o f i e d d = 1 0 2 4 9 - - 6 1 ；= o - 6 记1 1 0 1 4 。e c 图3 2 - 2 ：非混沌链c 规则b 2 f 0 9 6 f 吸引域，其中初始细胞数目为n = 1 0 ，整 个状态数目为1 0 2 4 个。共有1 3 个吸引域，有6 种吸引域类型，伊甸态有6 1 6 个，g 密度为0 6 0 2 。 链c 规则9 6 9 6 6 6 a 9 ( h e x ) - z l = l ；z , - - o ，6 2 5 ，z = i 。是一种限制 5 】结构规则， m p 不是以系统数目的增加而增加，具有相对固定值，丽l l l c 、m l 、n b 随着系统数 目的增加成指数性发散。混沌规则9 6 9 6 6 6 a 9 ( h e x ) 的吸引域的类型和个数与其 它两类规则相比增加最小，g 密度