元胞自动机doc资料.ppt

《元胞自动机doc资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第四章元胞自动机元胞自动机起源于对自我复制的机器的研究冯·诺依曼（VonNeumann）S.Ulam一个由元胞组成的完全离散的构架（现称网格），其中元胞表示系统的个体，个体具有若干个离散状态，个体状态根据网格中的邻元状态按规则同步进行变化。广为人知---生命游戏1970年剑桥大学的JohnH.Conway由《科学美国人》的数学游戏专栏介绍到全世界20世纪80年代以来，CA得到了很大的发展并已经广泛地应用于物理学、生物学、数学、计算机科学和社会科学等研究领域。4.1概述4.2元胞自动机模型A.概述元胞自动机是一个空间、空间和状态都是

2、离散的模型。该模型可用一个四元组表示：其中：S表示细胞状态，是一个有限的、离散的状态集合；La表示元胞空间，a是一个正整数，表示细胞空间的维数；N表示领域内元胞的组合，n表示邻居的个数f表示状态转移函数，即状态转移规则。B.领域和邻元对于一个元胞，在空间位置上与它相邻的元胞称为它的邻元（有时也称作邻居）。所有由邻元组成的区域称为它的邻域。图d：一维CA网格的领域定义图c：二维CA网格的邻域定义冯·诺依曼邻域不同大小的摩尔邻域邻域和邻元的定义可以是多样的，如图所示C.状态每个元胞有若干个状态，如：物理系统：（分子）固态，液态生物系统

3、：（细胞）活与死社会系统：（个人）相信与不相信谎言政治系统：（国家）战争与妥协……D.网格图a：一维的CA网格图b：二维的CA网格一维的CA模型是将直线分成若干相同的等份；二维的CA模型是将一个平面分成许多正方形、六边形或三角形的网格（最常见的是将其划分成正方形）；三维的CA模型将空间划分成许多立体网格。在各种CA模型中，每一个等份（单元格）代表一个元胞，CA的网格可以有不同的形式(维数，大小)。E.状态更新规则（一）根据每个元胞及邻元的不同状态，由状态更新规则决定这个元胞在下一个时刻的状态。序号i个体在t=1,…,n时刻的状态规

4、则可以是确定型的，也可以是随机型的。，其中为个体i的邻元在t时刻的状态。状态更新规则（二）对于一个一维的CA，一个细胞具有两种可能的状态如生或死，相信或者不相信等等，表示为０或１。如规则一：我们使用前面图c左边的邻元定义，且定义其状态更新规则为：当个体的两个邻元都活或者都死，该个体在下一时刻变为死；反之，他的状态在下一时刻变为活。即，更新规则如下表所示：t时刻邻元的状态111110101100011010001000t+1时刻中心格的状态01011010表：一个一维CA的状态更新规则状态更新规则（三）再如规则二：我们仍然使用前面图

5、c左边的邻元定义，但重新定义其状态更新规则为：当个体的两个邻元都活或者都死，该个体在下一时刻改变状态；反之，该个体的状态在下一时刻保持不变。该规则下状态更新可以如下表所示：t时刻邻元的状态111110101100011010001000t+1时刻中心格的状态01101001表：一个一维CA的状态更新规则4.3元胞自动机仿真技术4.3.1模型的构建考虑以下问题：确定系统中有那些个体，如何分类？个体有几种状态，分别是什么；个体所处的空间形式，是一维、二维还是多维；个体的邻元形式及个数，这与网格形式及交互群体规模有关；根据个体状态、网格

6、形式及邻元，确定个体状态的演变规则。此外，还需确定：系统中的个体与单元格是否一致。简单的、经典的CA模型中，单元格与个体不加区分，每个单位格就是一个个体，个体始终在单元格中，个体的状态即为单元格的状态。但在一些复杂系统中，尤其在个体可以移动的系统中，将个体与单元格区分更为方便。系统中有否有离散事件。采用CA模型描述的系统，每个时刻都需根据规则确定每个元胞的状态。除此之外，有的系统中某些个体会在特定时刻（有条件或无条件）发生状态变化，此时可以采用离散事件仿真方法，将该时刻列于事件表，根据事件表处理该类事件。4.3.2仿真技术1.仿真

7、钟仿真钟步进式推进，步长为1。在每一时刻都需改变个体以及网格状态，还要收集统计数据。2.事件的处理某些系统中有离散事件的发生。对这类事件也采用事件表，将特定时刻及事件类型登记在事件表中。在仿真钟步进式推进的每个仿真时刻，除根据状态转移规则对所有元胞进行状态更新外，还要检查一下是否有特殊事件发生，如果有就产生事件进行处理。3.随机因素的处理CA模型描述的复杂系统中往往带有不确定性4.3.3仿真流程流言模型流言模型解释了流言通过个体之间局部的交互进行传播的过程：流言从一个人开始传播给某些听众，每个人从自己的邻居那里听到流言，然后他会把

8、流言传给其他的邻居，并且假定一旦某个人听到这个流言，他会记住，不需要再次的传播。4.4流言模型4.4.1基本的流言模型A.概述流言模型刻画了流言通过个体之间局部的交互进行传播的过程：流言从一个人开始传播给某些听众，每个人从自己的邻居那里听到流言，然