（应用数学专业论文）初等元胞自动机的演化及模糊元胞自动机.pdf

摘要 元胞自动机是一种有自组织行为的时空离散、状态离散的并行数学模型。作 为实现复杂系统的离散模型，元胞自动机可以用来模拟和解决许多实际问题，从 而成为研究的热点之一。 本文首先对元胞自动机的基本理论和发展情况做了简要的介绍，在此基础上， 通过大量的计算机实验，对初等元胞自动机的动力学行为进行了详细的分类。通 过分类发现某些初等元胞自动机在一些演化规则下具有特殊的性质。本文着重探 讨了初等元胞自动机在其特有规则下的演化规律，然后在此基础上应用代数方法 来探讨初等元胞自动机在其加法规则下的演化性质。这种方法不但为初等元胞自 动机的理论研究提供了可靠的依据，而且使得对于初等元胞自动机的演化研究更 加深入透彻。本文推导出了些相关性的结论，这些结论揭示了初等元胞自动机 在加法规则演化下所特有的性质，这些性质对于简化初等元胞自动机的模型建立 和演化起到了重要的作用。为了便于直观的验证某些结论，本文利用了初等元胞 自动机的状态迁移图来加以描述它们的演化过程。此外本文也对三个状态的元胞 自动机展开了类似的研究，为研究一般元胞自动机的动力学行为分类和演化打下 了坚实的基础。 另外，本文也对模糊元胞自动机理论本身进行了探讨，尝试着将模糊逻辑引 入到元胞自动机模型中，定义了模糊元胞自动机。它用以处理实际问题中出现的 模糊信息和不确定性条件，从而使元胞自动机模型的模拟能力更为强大，更为智 能化，丰富了元胞自动机的理论。 关键词：元胞自动机；演化规则；邻居；状态：模糊元胞自动机 e v o l u t i o no fe l e m e n t a r yc e l l u l a ra u t o m a t aa n df u z z y c e l l u l a ra u t o m a t a 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 a sad i s c r e t em o d e lt or e a l i z ec o m p l e xs y s t e m ，c e l l u l a ra u t o m a t ah a d g e n e r a t e d m a n yi n t e r e s t sb e c a u s eo fi t su s e f u l n e s sf o rr e s o l v i n gm a n yf a c t u a lp r o b l e m s t h i sp a p e rb r i e f l yi n t r o d u c e st h eb a s i ct h e o r ya n dt h ed e v e l o p m e n to fc e l l u l a r a u t o m a t aa n dt h e nt h r o l l g ho fl o t so fe x p e r i m e n to fc o m p u t e r , a n d # y e sad e t a i l e d c l a s s i f i c a t i o no fd y n a m i c sb e h a v i o ro ft h ee l e m e n t a r yc a t h i sp a p e rf i n d sp e c u l i a r p r o p e r t i e su n d e rs o m ee v o l u t i o nr u l e so fs o m ee l e m e n t a r yc a , d i s c u s s e sm a i n l yt h e e v o l u t i o np r o p e r t yo fc e l l u l a ra u t o m a t aw i t ht h ea d d i t i o nr u l e sb ym e a n so ft h e a p p l i c a t i o no fa l g e b r a ，g i v e sad e p e n d a b l eb a s i sf o rt h et h e o r i e sr e s e a r c ho ft h e e l e m e n t a r yc a , m a k e sm u c hm o r et h o r o u g ho ft h ee v o l u t i o nr e s e a r c ho ft h ee l e m e n t a r y c a , a n di n d u c e ss o m er e l e v a n tc o n c l u s i o n s t h e s ec o n d u s i o n sd i s c l o s es p e c i f i cl a wo f t h ee l e m e n t a r yc e l l u l a ra u t o m a t ai nt h ee v o l u t i o no fa d d i t i o nr u l e sa n ds i m p l i f yt h e c o n s t r u c t i o no fm o d u l eo ft h ee l e m e n t a r yc aa n de v o l u t i o n i no r d e rt ot e s t i f ys o m e c o n c l u s i o n sd i r e c t l y , t h i sp a p e ru s e ss t a t et r a n s i t i o nd i a g r a mo fe l e m e n t a r yc e l l u l a r a u t o m a t at od e s c r i b ei t se v o l u t i o np r o c e s sa n dt h e nc a r r i e so ns i m i l a rs t u d yo ft h r e e s t a t e sc a , g i v e sas o l i df o u n d a t i o nf o rs t u d yd y n a m i c sb e h a v i o ra n de v o l u t i o no f c o m m o nc a o t h e r w i s e ，t h i sp a p e ra l s od i s c u s s e st h et h e o r yo fc e l l u l a ra u t o m a t ai t s e l lt r i e st o p u tf u z z yl o g i ci n t ot h ec e l l u l a ra u t o m a t a ，a n dg i v e st h ed e f i n i t i o no ff u z z yc e l l u l a r a u t o m a t a i td e a l sw i t hm a n yu n c e r t a i na s p e c t sa n dp r o b l e m so fi m p r e c i s ea n dv a g u e d a t ao ft h er e a lw o r l d ，t h e r e b ym a k e st h ea b i l i t yo fs i m u l a t i o no fc a s t r o n g e ra n dm o r e i n t e l l i g e n t ，a n de n r i c h e st h et h e o r yo fc a k e yw o r d s ：c e l l u l a ra u t o m a t a ；e v o l u t i o nr u l e ；n e i g h b o r ；s t a t e ；f u z z yc e l l u l a r a n t o 吣t a 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文：翅笠丞堕自动拯的遗丝丛搓塑丞堕自塑担：。除论文中已 经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发 表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：钏了装融d 辞月f7 日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于： 保密口 不保密似请在以上方框内打“”) 论文作者签名：砂惮叫导师签名：肚办 日期：p ( 年弓月一日 第1 章绪论 1 1 元胞自动机的产生与发展 元胞自动机( c e l l u l a r a u t o m a t a ) ，简称c a ，( 也有人译为细胞自动机、点格自 动机、分子自动机或单元自动机) 。元胞自动机起源于2 0 世纪4 0 年代，“现代计 算机之父”冯诺依曼设计可自我复制的自动机时，参照了生物现象的自繁殖原 理，提出了元胞自动机的概念和模型。它是一时间和空间都离散的动力系统，散 布在规则格网中的每一元胞取有限的离散状态，遵循同样的作用规则，依据确定 的局部规则作同步更新，大量元胞通过简单的相互作用而构成动态系统的演化。 不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定， 而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞 自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其 特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的 规则在时间和空间上都是局部的【1 l 。 2 0 世纪6 0 年代，柯卫编制的“生命游戏”是最著名的元胞自动机模型，显示了 元胞自动机在模拟复杂性系统的无穷潜力。引起了物理、数学、生物、计算机、 地理等领域专家的兴趣，“生命游戏”被认为是元胞自动机研究的真正开始。2 0 世 纪8 0 年代是元胞自动机理论的大发展时期。沃夫曼从动力学的角度对元胞自动机 进行了分析，并将计算理论应用于元胞自动机的研究。2 0 世纪9 0 年代元胞自动机 在各个领域得到了广泛的应用。 元胞自动机主要应用在计算机图形学、生物学、复杂的社会经济现象如城市 发展模拟与预测、热扩散、并行计算等领域。例如，在生物学中，可以用元胞自 动机模拟艾滋病病毒的h i v 感染过程、自组织、自复制等生命现象的研究和最新 的克隆技术的研究；在物理学中，可用元胞自动机来处理热力学系统、流体力学 中的n a v i e r - s t o k e s 方程以及随机扩散、结晶过程等等。在计算机科学中，由于元 胞自动机的并行处理能力，被用做高度并行的乘法器、分类器等。在医学上，可 用元胞自动机模拟癌细胞的生长和扩散现象，药物在人体组织细胞中的渗透、扩 散过程，从中可以得到有用的信息来确定药物的用量和用法，以及更好的控制病 情的发展。元胞自动机也可以用来模拟社会人群，由此来预测人们的心理状态， 从中掌握情况，以便更好的把握社会群体的心态吼 1 2 元胞自动机的应用 元胞自动机可用来研究很多一般现象，其中包括通信、信息传递、计算、构 造、生长、复制、竞争与进化等。同时，它为动力学系统理论中有关秩序、紊动、 混沌、非对称、分形等系统整体行为与复杂现象的研究提供了一个有效的模型工 具。下面就对元胞自动机的主要应用做一下介绍。 1 2 1 元胞自动机在城市增长研究与实践中的应用 元胞自动机在城市增长模拟与预测中的应用可以追溯到2 0 世纪6 0 年代，6 0 年代美国学者w e i s s 在城市土地利用变化研究中采用了元胞自动机的思想。在其 模型中用栅格代表居住地的组成，根据元胞间的相邻关系和空间构成来设定相邻 单元的吸引力指标，并根据这个吸引力指标来确定最有可能增长的元胞，即哪些 土地将来最有可能发展成居住地。7 0 年代t o b e r 用元胞自动机的原理进行了美国 底特律地区的城市扩张规律的研究。8 0 年代美国h e l e nc o u c l e l i s 奠定了元胞自动 机在地理现象模拟的理论框架，尤其是在城市增长模拟方面的研究成为后来进行 这方面研究的基础。8 0 年代后期至今是元胞自动机在城市增长应用研究的繁荣时 期。9 0 年代荷兰学者e g e n l e n 采用元胞自动机模拟城市土地使用变化，取得了惊 人的效果。由于g i s 在空间数据的存储、管理、计算、分析等方面功能很强，而 且元胞自动机中的元胞与g i s 中的栅格数据模型十分相似，因此利用元胞自动机 模型建立元胞间的相互作用与规则，构造城市增长元胞自动机模型，用元胞表示 城市各种土地利用类型( 微观尺度) ，结合城市的社会经济系统( 宏观尺度) ，并 将其在模型中表现成一定的规则，在g i s 中进行分析与计算，充分发挥g i s 在空 间数据存储与管理、空间分析、图形显示与可视化方面的优势，通过元胞之间的 空间相互作用来进行城市增长模拟与预测研究，具有广阔的应用前景。目前很多 国家的专家和学者都将元胞自动机和g i s 结合起来，进行城市发展方面的模拟和 预测研究，如b a t t y 和x i e 等进行了柏林城市增长与预测方面的研究，c l a r k e 在 美国地质调查局的支持下，利用大型的空间数据库，采用g i s 和r s 进行了华盛顿 一巴尔迪摩都市区的城市增长变化的研究，h e l e nc o u c l e l i s ，r o g e rw h i t e 和 e g e n l e n 等都先后利用元胞自动机和g 1 s 结合进行了城市增长方面的研究。c o l o n n a 2 和p a p i n i 等人将智能识别系统日i 入c a ，建立学习型的元胞自动机( l e a r n i n g c e l l u l a r a u t o m a t a ) ，并以罗马地区为例，利用遗传算法从经验数据库中学习并归纳 出元胞转换规则，根据这些规则来模拟城市土地利用形态的变化，其中1 9 9 1 年的 模拟结果与实际的城市土地利用状况问的差异仅仅只有4 【3 】。 1 2 2 元胞自动机在数学上的应用 微分方程有着三百多年的发展历史，一批伟火的科学家，如e u l e r 、l a p l a c e 、 都做出了卓越的贡献。而且，后来发展的偏微分方程对量子力学等现代物理学的 产生与发展有着重要的意义，一大批的物理规律就是利用偏微分方程来推理和表 达的，如麦克斯维方程等。 微分方程的主要特点是时间、空间均连续( 如果力程中有空问因子的话) ，这 是建立在时空连续的哲学认识基础上的。而元胞自动机则是完全的空间离散、时 间离散，在这个意义上，微分方程和元胞自动机是一对相对的计算方法。 在人工计算的情况下，由符号组成的( 偏) 微分方程可以灵活地进行约简等符 号运算，而得到精确的定量解，这是其优势。但在现代计算机日益发展，己成为 我们科学研究的重要工具时，微分方程却遇到了一个尴尬的问题。即计算机是建 立在离散的基础上的，微分方程在计算时不得不对自身进行时空离散化，建立差 分方程等；或者展开成幂系列方程，截取部分展开式；或者采用某种转换用离散 结构来表示连续变量。这个改造过程不仅是繁杂的，甚至是不可能解决的，但晟 重要的是在这个过程中，微分方程也失去了它的自身最重要的特性精确性、 连续性。 而对丁二元胞自动机来讲，脱离计算机环境来进行运算几乎是不可能的，但是 借助计算机进行计算，则非常自然而合理，甚至它还是下一代并行计算机的原型。 因此，在现代计算机的计算环境下，以元胞自动机为代表的离散计算方式在求解 方面，尤其是动态系统模拟方面有着更大的优势。元施自动机虽然在理论上具备 计算的完备性，但满足特定目的构模尚无完备的理论支持，其构造往往是一个直 觉过程。用元胞自动机得到一个定量的结果非常困难，即便是可能的话，元胞自 动机也将陷入一个尴尬元胞自动机的状态、规则等构成必然会复杂化，从而不 可避免地失去其简单、生动的特性。 可避免地失去其简单、生动的特性。 然而，正如物理学家玻尔所说：“相对的并不一定是矛盾的，有可能是相互补 充和相互完善的”。二者互有优缺点，相互补充，都有其存在的理由。但在现代计 算机环境下，对于元胞自动机这一类相对来讲还处于幼年阶段的离散计算方式， 需要予以更多的关注和支持。在地理学中，l o w r y 、w i l s o n 、张新生等人的空间动 力学模型都是基于微分方程的模型，由于这些模型大多是复杂的非线性微分方程， 无法求得其解析解，需要按e u l e r 方法或r u n g e k u t t a 方法对微分方程进行一步或 多步差分，完成相应的计算机模型或在g i s 支持下的空间分析模型。对于这些模 型，我们都可以构建相应的元胞自动机模型1 4 j 。 1 2 3 元胞自动机在交通系统上的应用 元胞自动机交通模型正是将元胞自动机理论应用于交通，它与其它模型相比， 在保留交通流这一复杂系统的非线性行为和其它物理特征的同时，更易于在计算 机上操作，并能灵活地修改以考虑真实交通条件的各种效应，例如路障与瓶颈效 应、高速公路连接点、阻滞随机性、驾驶员过度反应引起的随机慢化等等。最早 的元胞自动机交通模型是由m c r e m e r 和j l a d w i g 于1 9 8 6 提出来的，而最重要的 元胞自动机交通模型是n a s c h 模型、f l 模型和b m l 模型。 n a s c h 模型是k n a g e l 和m s c h r e c k e n b e r g 于1 9 9 2 年提出的，其建模的思想是 车辆总是想以最大的速度行驶，不希望发生碰撞，同时，并非每辆车都以最理想 的状态行驶。n a s c h 模型的特点是考虑车辆的速度分布为o - - v ( m a x ) ，同时引入 随机减速延迟规则。该模型的大容量高速并行计算，显示出高速公路车流从运动 畅通相到局部阻塞相的相变。 b m l 模型的特点是在整体上对城市交通网进行研究，它的特点是车辆随机地 分布在该网格上，同时给车辆的运动制定规则，让车辆同时运动，b m l 模型模拟 由交通灯控制的城市街道网络的车流，能呈现城市交通网的畅通到阻塞的相变情 况。 实际城市交通通常是二维的，为了描述二维交通网的性态。1 9 9 2 年b i h a m ， m i d d l e t o n 和l e v i n e 提出了一个理想化模型，称为b m l 模型。 在b m l 模型中，用一个n x n 的二维方形点阵来表示城市交通网络，是方 形点阵的边长，每一格点具有三种状态，即每一格点上可以有一辆由南向北行驶 4 的车辆，或者有一辆由西向东行驶的车辆，或者没有车辆，每辆车的速度v ( i ) - - 1 。 在每一奇数时间步，东西向的车辆向前行驶一个格点( 用向右箭头表示) ；同 样，在每偶数时间步，南北向的车辆向前行驶一个格点( 用向上箭头表示) ，这 样规定的作用相当于用红绿灯来控制城市街道路口的交通，给出车辆不可重叠和 沿两个交叉方向流动的特征。但是，如果车辆前面的格点上有其它车辆的占据， 那么该辆车只能在原来的格点上等待，不能向前行驶。 b m l 模型对随机初始位形系综的模拟，系统经过一个暂态过程后到达渐近稳 态，暂态时间长短与系统尺度j v ，车辆密度，和车辆初始分布有关。模拟的时空斑 图表明，当模拟系统中车辆密度超过一个临界值r e 时，系统就会发生阻塞以至瘫 痪的状态，这就是系统发生从运动相到阻塞相的相变：在相变点r c 以下，系统的 状态是车辆皆可行驶的运动畅行相，车辆分布在自左上至右下的几条带中；在相变 点r c 以上，就存在车辆被堵住的阻塞相，车辆分布在自左下至右上的几条带中。 平均速度v 定义为奇、偶两时间步中前进的车辆数与总车辆数之比。随着密度r 由小变大，平均速度矿开始总保持为最大速度1 ，说明系统处于运动畅行相，几乎 所有的车辆都能前进，而当r 超过某一临界值r c 时，平均速度y 下降到0 ，表明 系统进入了阻塞相，所有的车辆都不能前进，这就是一个重要的自组织临界现象。 元胞自动机交通模型对二维交通系统的模拟还局限于理论研究，但它实践了 一种用离散化模型来描述离散问题的思想，避免了在流动比拟下，将方程的严格 假设以及求解离散化对真实信息的损失【5 j 。 1 3 本文的研究思路 首先，自元胞自动机产生以来，对于元胞自动机分类的研究就是元胞自动机 的一个重要的研究课题和核心理论。在基于不同的出发点，元胞自动机可有多种 分类，本文在详细分析了初等元胞自动机的演化行为后，并在大量计算机实验的 基础上，将所有初等元胞自动机的动力学行为做了更进一步的划分。 其次，从经典元胞自动机的应用中我们发现，元胞自动机在演化方面的研究 比较少。由于这个原因，本文主要研究初等元胞自动机的演化，首先是探讨了初 等元胞自动机在其特殊规则下的演化规律，然后在此基础上采用代数方法来重点 研究了初等元胞自动机在其加法规则下的演化性质，根据性质推导出了一些结论， 并用m a t l a b 软件对这些结论进行了检验。 此外，本文尝试着对具有三个状态的元胞自动机在演化方面做了类似的研究。 最后，在现实世界中出现的主要问题所表达的信息通常是具有不确定性；或 者事实本身就是模糊而不完全确定的，但又必须利用且只能利用这些信息进行判 断和决策。由于这个原因，本文把模糊逻辑加入到元胞自动机的规则中，构造了 建立在模糊逻辑上的模糊元胞自动机，使元胞自动机的应用更具有普遍性。 本文第二部分介绍了经典元胞自动机的基本理论，第三部分探讨了经典元胞 自动机在其特有规则下的演化，第四部分介绍了模糊逻辑在经典元胞自动机中的 应用。 第2 章元胞自动机理论 2 1 元胞自动机的定义 尽管元胞自动机有着较为宽松，甚至近乎模糊的构成条件。但作为一个数理 模型，元胞自动机有着严格的科学定义。同时，元胞自动机是一个地地道道的“混 血儿”，足物理学家、数学家、计算机科学家和生物学家共同工作的结晶。因此， 对元胞自动机的含义也存在不同的解释，物理学家将其视为离散的、无穷维的动 力学系统；数学家将其视为描述连续现象的偏微分方程的对立体，是一个时空离 散的数学模型；计算机科学家将其视为新兴的人工智能、人工生命的分支；而生 物学家则将其视为生命现象的一种抽象。下面给出几种常见的定义 6 1 ： 2 1 1 元胞自动机的物理学定义 元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上， 并按照一定局部规则，在离散的时间维上演化的动力学系统。 具体讲，构成元胞自动机的部件被称为“元胞”，每个元胞具有一个状态。这 个状态只是取某个有限状态集中的一个，例如或“生”或“死”，或者是2 5 6 种 颜色中的一种，等等；这些元胞规则地排列在被称为“元胞空间”的空间格网上， 它们各自的状态随着时间变化。根据一个局部规则来进行更新，也就是说，一个 元胞在某时刻的状态取决于、而且仅仅取决于上一时刻该元胞的状态以及该元胞 的所有邻居元胞的状态；元胞空间内的元胞依照这样的局部规则进行同步的状态 更新，整个元胞空间则表现为在离散的时间维上的变化。 2 1 2 元胞自动机的数学定义 美国数学家l p f l u i d 和k c u l i k 等人在9 0 年代初，对元胞自动机分别从集合 论和拓扑学等角度进行了严格地描述和定义。 1 ) 元胞自动机基于集合论的定义 设d 代表空间维数，k 代表元胞的状态，并在一个有限集合s 中取值，r 表示 元胞的邻居半径。z 是整数集，表示一维空间，t 代表时间。 为叙述和理解上简单起见，在一维空间上考虑元胞自动机，即假定d = 1 。那 么整个元胞空间就是一维空间，将整数集z 上的状态集s 的分布，记为s2 。元 胞自动机的动态演化就是在时间上状态组合的变化，可以记为： f ：s ：一s + 1 这个动态演化又由各个元胞的局部演化规则，所决定的，这个局部函数，通常 又常常被称为局部规则。对于一维空间，元胞及其邻居可以记为s2 ”1 ，局部函数 则可以记为： ，s j ”1 一s 。 对于局部规则，来讲，函数的输入、输出集均为有限集合，实际上，它是一个 有限的参照表。例如，r = l ，的形式则形似如下：【0 , 0 ，0 】一0 ；【0 ，0 ，1 】- - - 0 ； 【0 , 1 ，0 】一1 ；【1 , 0 ，0 】一o ；【0 , 1 ，1 】一1 ；【1 , 0 ，1 】一o ；【1 ，1 ，0 】一o ；【1 , 1 ，1 】一0 对元胞 空间内的元胞，独立旋加上述局部函数，则可得到全局的演化： f ( c ：+ 。) = ，( c ：，r ；，r ：”) c ：表示在位置f 处的元胞，至此，我们就得到了一个元胞自动机模型。 2 ) 元胞自动机的拓扑学定义 为描述和理解方便，同样假定维数d 为1 。设s 为k 个符号的有限集，z 为整 数全体的集合，称z 到s 的映射的全体s 2 为构形空间。显然s 。就是用s 中的符号 组成的双侧无限的符号序列的全体，即一维元胞自动机的所有构形的集合。称 a = ( ，口一。ao a ，。) 为构形空间中的点。在s2 中引进任意两点x 和) ，之间的距离： d o ，y ) - 6 “，y r ) 2 “ 其中当鼍t y j 时6 以，y ，) = o ，当x 。- y ，时6 。，y ，) = 1 。然后，在s 中可以建 立起开、闭、紧等拓扑概念。 在r 中定义移位算子6 为6 ( t ) 筇。，i z 。若连续映射f 与6 可交换，即 f 6 = d f 。或对任意的工s 2 有州6 0 ) ) ) = 6 ) ，则称，为元胞自动机。 对于以上定义，我们很容易将它扩展到一个任意维空间，所要做的工作只是 将s 。记为s2 “，s 。“记为s ( 2 ”“等，同时对一些描述作相应改变即可。 2 2 元胞自动机的特征 从元胞自动机的构成及其规则上分析，标准的元胞自动机应具有以下几个特 征用： 8 1 ) 同质性、齐性：同质性反映在元胞空间内的每个元胞的变化都服从相同的规 律，即元胞自动机的规则，或称为转换函数：而齐性指的是元胞的分布方式相同， 大小、形状相同，空间分布规则整齐； 2 ) 空间离散：元胞分布在按照一定规则划分的离散的元胞空间上； 3 ) 时间离散：系统的演化是按照等间隔时间分步进行的，时间变量t 只能取等 步长的时刻点，形似整数形式的t ，t + l ，t + 2 ，而且，t 时刻的状态构形只对其下 一时刻，即t + l 时刻的状念构形产生影响，而t + 2 时刻的状态构形完全决定于t + l 的状态构形及定义在上面的转换函数； 4 ) 状态离散有限：元胞自动器的状态只能取有限个离散o 。，5 ：，s 。) 。相对 于连续状态的动力系统，它不需要经过粗粒化处理就能转化为符号序列。而在实 际应用中，往往需要将有些连续变量进行离散化，如分类、分级，以便于建立元 胞自动机模型； 5 ) 同步计算( 并行性) ：各个元胞在时刻t 的状态变化是独立的行为，相互没有 任何影响。若将元胞自动机的构形变化看成是对数据或信息的计算或处理，则元 胞自动机的处理是同步进行的，特别适合于并行计算； 6 ) 时空局部性：每一个元胞的下一时刻t 。的状态，取决于其周围半径为r 的 邻域( 或者其它形式邻居规则定义下的邻域) 中的元胞的当前时刻t 。的状态，即所 谓时间、空间的局部性。从信息传输的角度来看，元胞自动机中信息的传递速度 是有限的； 7 ) 维数高：在动力系统中一般将变量的个数称为维数。例如，将区间映射生成 的动力系统称为一维动力系统；将平面映射生成的动力系统称为二维动力系统； 对于偏微分方程描述的动力系统则称为无穷维动力系统。从这个角度来看，由于 任何完备元胞自动机的元胞空间是定义在一维、二维或多维空间上的无限集，每 个元胞的状态便是这个动力学系统的变量。因此，元胞自动机是一类无穷维动力 系统。在具体应用中或计算机模拟时当然不可能处理无限个变量，但一般也总是 处理数量很大的元胞组成的系统。因此可以说维数高是元胞自动机研究中的一个 特点。 9 在实际应用过程中，许多元胞自动机模型已经对其中的某些特征进行了扩展。 例如圣托斯兰州立大学研究的所谓连续型的元胞自动机，其状态就是连续的。但 正如我们在元胞自动机的概念分析中指出的，在上述特征中，同质性、并行性、 局部性是元胞自动机的核心特征，任何对元胞自动机的扩展应当尽量保持这些核 心特征，尤其是局部性特征。 元胞自动机有一维、二维、三维模型。下面详细的介绍一维和二维元胞自动 机。 2 2 1 一维元胞自动机 一维元胞自动机就是元胞空间为一维的元胞自动机模型。设在一条直线上按 等间隔方式分布着完全相同的一系列元胞，每一个元胞的状态只有有限多个，每 个格点附近有限制性的确定规则，即转移函数，。时间是离散的，取整数值，称t = 0 ( t e t ，t 为时间集) 为初始时刻。假设上述直线在两个方向上都没有限制，因 此就有无限多个元胞。所有元胞的状态全体可以用双侧无限的符号序列表示出来， 每一个这样的序列称为元胞自动机的t 时刻构形( c o n f i g u r a t i o n ) ： a ”= ( 4 l i 口；口i 。)( 2 1 ) 其中a ! 表示时刻t 格点i 的值。为了确定起见，可以将分布在直线上的元胞位置 与整数全体对应起来，特别是将与整数0 对应的位置称为基点。这样t 时刻的构形 a 也可以表示为爿= ( 口：，a 护t ) ，其中a 。是在基点上的元胞状态。每个元胞 的状态看成是一个变量，只能取有限个值，即a ，e s ( s 为有限状态集) 。所有元胞 的状态是同时发生变化的，在时刻t + l 的构形4 ( “1 完全由4 ( 决定。同时在时刻t 的第f 个元胞的状态是由时刻t - 1 的第f 个元胞以及相邻的距离不超过r 的2 r 个元 胞的状态所决定的( 共有2 r + 1 个) ，即有： a ；lf ( 口2 ，口f t ，- 1 i ，口f t 一1 ，口i t + - 1 i ，口j t + - ，i ) ( 2 2 ) 其中的转移函数，与f 和f 都无关。下面介绍一下初等元胞自动机的邻居和规则： 1 ) 初等元胞自动机的邻居 初等元胞自动机( e l e m e n t a r yc e l l u l a ra u t o m a t a ，简称e c a ) 是状态集s 只有两 个元素如。，s ： ，即状态个数k = 2 ，邻居半径r = l 的一维元胞自动机- 它几乎是 1 0 最简单的元胞自动机模型。由于在s 中具体采用什么符号并不重要，它可取 0 ， 1 ， - i ，1 ) ， 静止，运动， 黑，白) ， 生，死) 等等。这里重要的是s 所含的 符号个数，通常我们将其记为 o ，1 。在此用单位方格来表示元胞，此时，邻居 集n 的个数2 r = 2 ，也就是每一个方格的左、右两个方格是它的邻居，这样每一个 方格单元和它的邻居可以表示如下： 图2 1 邻居 f i g 2 1n e i g h b o r 其中黑色的方格是当前元胞，两边的灰色方格是它的邻居。由于状态集只有 o ，1 ) 两个状态，也就是说方格只能有黑、白两种颜色，任意的一个方格加上它 的两个邻居就是一个组合，那么这3 个方格的状态组合一共有8 种。这8 种情况 如图2 2 所示： _ 口i 】i 卫 口l 口口】卫 图2 2 邻居状态组合 f i g 2 2c o m b i n a t i o no fn e i g h b o r s t a t e s 图2 2 表示的状态分别是：1 1 1 ，1 1 0 ，1 0 1 ，1 0 0 ，0 1 1 ，0 1 0 ，0 0 1 ，0 0 0 。也就 是说对于状态数为2 ，邻居半径为1 的所有一维元胞自动机的邻居和其自身的状态 组合就这么8 种。 初等元胞自动机的规则 假设当前考虑的元胞为s 。，它在t 时刻的状态为s 训它的两个邻居状态为 s t - 1 , t ，5 - f j f ，在下一时刻的状态为j i 。t ，那么转换规则用函数表示为： s m li 鼬j _ 1 j 声。芦小1 ) 其中，s ；，e o ，1 ，对于任意的i 和t a 由于在这个最简单的元胞自动机中每个元胞和它的邻居状态的所有可能组合 就上面列出来的8 种，所以它的输入就是上面列出的8 种组合。输出表示的是每 个元胞下一时刻的状态，而状态只可能有0 、1 两种，则规则的输出要么是0 ，要 么是1 。这样任何一个规则就是一个或者一组转换，比如图2 _ 3 表示的就是一个规 则： _ 即口皿 ll4l k 陆h 陆 口口 这个规则也可以用表2 1 表示： 一一 图2 3 规则 f i g 2 3r u l e 表2 1 规则 t a b 2 1r u l e l 输入 1 1 11 1 0 1 0 11 0 00 1 10 1 0o 叭0 0 0 i 输出 10l 00o11 那么这组规则就对应着输出编码：1 0 1 0 0 0 1 1 ，也就是把八个位置上的方格进 行一个排列。我们可以把输出部分的二进制编码转换成十进制数的形式：1 6 3 ，称 它是初等元胞自动机的编码。由排列组合得这样的编码一共有2 5 6 种，并且八位 二进制字符串转化成十进制后的值是从0 到2 5 5 的整数，我们就把整数值称为演 化规则的编码，为了方便通常我们称编码1 6 3 为规则1 6 3 。 s w o l f r a m 的研究表明，尽管初等元胞自动机是如此简单，但它们确呈现出高 度复杂的空间形态。s w o l f r a m 按最终的演化结果将元胞自动机分为四种类型： 趋于一个不随时间演化的定态：趋于周期结构；导致混沌行为的出现；演 化为更为复杂的结构。前三类行为相当于低维动力系统中常见的不动点、周期轨 和混沌，第四类行为则可以与生命系统等复杂系统中的自组织现象相比拟。本文 用m a t l a b 软件对初等元胞自动机的演化进行了模拟，这里只列出了四个分别代 表四种类型的规则。初始状态是随机给出的0 和1 的字符串，显示在第一行，白 色点代表1 ，黑色点代表o ，每个规则都演化1 0 0 次。 用m a t l a b 模拟的结果如图所示，图2 4 表示规则1 2 8 ：1 0 0 0 0 0 0 0 ，是第一 种类型的c a ；图2 5 表示规则4 ：0 0 0 0 0 1 0 0 的演化情况，属于第二种类型；图2 6 表示规则2 2 ：0 0 0 1 0 1 1 0 ，属于第三种类型；图2 7 表示规则1 5 0 ：1 0 0 1 0 1 1 0 ，是第 四种类型1 8 】。 图2 ，4 规则1 2 8 f g 2 4r u l e1 2 8 图2 6 规则2 2 f i g 2 6r u l e2 2 图2 5 规则4 f i g 2 5 r u l e4 图2 7 规则1 5 0 f i g 2 7r u l e1 5 0 2 2 2 二维元胞自动机 当元胞自动机的元胞空间是二维平面时，称为二维元胞自动机。在用c a 模 拟实际问题时，一般使用的都是二维元胞自动机。一个二二维元胞自动机包括个 均匀的网格，网格的形状可以是三角形，正方形和六边形。三种网格的形状在模 拟时各有优缺点，在大多数情况下用正方形的网格，由于三角网格和六边形网格 在计算机的表达和显示上不方便，通常都要借助映射转换成正方形网格处理，所 以只有少数情况下才选择三角形或六边形。 理论上的元胞空间通常都是无限的，在实际的应用中，通常把网格限制在有 限的大小内，运用不同边界条件来解决格子有限的问题。边界条件主要有三种类 型：周期型、反射型和定值型。这三种边界条件在实际模拟时，尤其是二维或更 高维数的结构时，可以相互结合。 每个网格的状态值取有限个，状态集为s ，s = o ，1 ，z ，k - 1 ) ，k z ( 整数 集) ，则在t ( f r ，t 为时间集) 时刻，位置( 1 ，j ) 的状态记为n ；口：f 称为此位 置的构形，如图2 8 所示。 辱t 国 o j - 1 )彻露砖轴 o + z j ) 图2 8 两格构形 f i g 2 8m e s hs h a p e 在二维元胞自动机中邻居的半径一般为r = 1 或，= 2 ，对于正方形的网格，它 的邻居可以是v o n n e u m a n n 型邻居，也可以是m o o r e 型邻居。如图所示，图2 9 为v o n n e u m a n n 型的邻居，图2 1 0 为m o o r e 型邻居( 图中，黑色的元胞为中心元 胞，灰色元胞为其邻居元胞) 【9 】。 1 4 图2 9v o n n e u m a r m 型邻居 f i g 2 9n e i g h b o ro fv o n n e u m a n n 图2 1 0 m o o r e 型邻居 f i g 2 1 0n e i g h b o ro fm o o r e 对于v o n n e u m a n n 邻居，其定义为 n “j ) 一似，1 ) e l 恨- i i + l f _ 卅蔓，) 对于m o o r e 邻居，其定义为： n ) t 婶，f ) 工i l k - i i ， 卜1 ，is r ( 2 3 ) ( 2 4 ) 第3 章一维元胞自动机的演化及其代数性质 相对来讲对一维元胞自动机的系统研究最早，其状态、规则等较为简单，所 有可能的规则往往可以一一列出，易于处理，研究也最为深入，而且最大的一个 特点在于容易实现元胞自动机动态演化的可视化。目前，对于元胞自动机的理论 研究多集中在一维元胞自动机上。s w o l f r a m 对元胞自动机的动力学分类也是基于 对一维初等元胞自动机( e l e m e n t a r yc e l l u l a ra u t o m a t a ) 的分析研究得出的，本章分 三部分来探讨一维元胞自动机的演化：首先探讨一维元胞自动机的最简单情况f 即 初等元胞自动机在其特殊规则下的演化1 ；其次在此基础上我们采用代数方法来探 讨初等元胞自动机在其加法规则下的演化性质；最后将其代数方法推广到具有更 多元胞状态的维元胞自动机上来( 元胞状态集含三个值以上) 。在上一章中已经 交代了初等元胞自动机的演化规则一共有2 5 6 种，而且每种规则都可出一组八 位的二进制数来表示，在本章就研究具有代表性的一类规则。 3 1 初等元胞自动机在其特有规则下的演化 在2 5 6 种演化规则中施加两个限定条件：首先，描述演化规则的八位二迸制 数的最后一位要求是0 ，也就是在上一章中要求组合0 0 0 - - - - 0 ；其次，演化规则对 称映射部分的元胞演化要一致，即1 1 0 和0 1 1 ( 1 0 0 和0 0 1 ) 这两组，要求每一组 都要演化为相同的元胞，也就是1 1 0 0 ，0 1 1 0 ，或者1 1 0 1 ，0 1 1 1 。同理， 对于组合1 0 0 和0 0 1 的要求也是如此。由排列组合我们知道，在以上两条限定后， 2 5 6 种演化规则只保留了其中的3 2 种。并且这3 2 种演化规则我们可以用表3 1 来 表裂1 0 1 ： 表3 1 规则 t a b 3 1r u l e 川1 1 01 0 l1 0 00 1 l0 1 00 0 1。 口t a 2口3a 4a 2球5a 4 o 下面就用状态迁移图来具体的探讨一下初等元胞自动机在一些特定规则下的 演化规律，进而得到一些感性的认识。这为在下一部分用代数方法来研究初等元 胞自动机的演化打下举实的基础。 3 1 1 初等元胞自动机在规则9 0 下的演化 表3 2 规则9 0 1 a b 3 2r u l e 9 0 川 1 1 01 0 11 0 00 1 l0 1 00 0 l0 0 0 。l0ll01o 由表3 2 可知它就是初等元胞自动机的演化规则9 0 ，演化规则9 0 是3 2 种特 定规则之一。 注意观察表3 2 就会发现这样一个事实：第二行中每个元胞的值恰好是上一 行中与其对应每个组合中左右两个元胞的摸2 和。令5 ，1 表示元胞m 在时间步n 的 值，那么根据上面表述，等价于演化规则9 0 的布尔等式如下： s 2 7 s ，4 o s ，“ ( 3 1 ) 我们也可以简写成： s 一s o s + ， 其中。表示模2 加法。 图3 1 状态迁移圈 f i g 3 1s t a t et r a n s i t i o nd i a g r a m 1 7 现在来考察初等元胞自动机在规则9 0 下的演化情况，假设有一初等元胞自动 机的初始结构：0 00 0 00 0 0 100 0 0 00 0 0 0 00 0 ，我们现在截取它在规则9 0 演化3 0 次后的状态迁移图3 1 。其中初等元胞自动机结构中的1 用非白色单位小 方块来表示，而结构中的0 我们用白色单位小方块来表示。 这样就能从状态迁移图中很容易观察到初等元胞自动机在每一个时间步中演 化的结果，例如该初始状态的初等元胞自动机在规则9 0 演化下的第三十步结构是： 011101110 11l0 11101111 。 根据演化规则9 0 的布