元胞自动机 47页.pptVIP

第四章 元胞自动机 4.1 概述 元胞自动机起源于对自我复制的机器的研究 冯·诺依曼（Von Neumann） S.Ulam 一个由元胞组成的完全离散的构架（现称网格），其中元胞表示系统的个体，个体具有若干个离散状态，个体状态根据网格中的邻元状态按规则同步进行变化。 广为人知---生命游戏 1970年剑桥大学的John H.Conway 由《科学美国人》的数学游戏专栏介绍到全世界 20世纪80年代以来，CA得到了很大的发展并已经广泛地应用于物理学、生物学、数学、计算机科学和社会科学等研究领域。 4.2 元胞自动机模型 A.概述 元胞自动机是一个空间、空间和状态都是离散的模型。该模型可用一个四元组表示： 其中： B. 领域和邻元 对于一个元胞，在空间位置上与它相邻的元胞称为它的邻元（有时也称作邻居）。 所有由邻元组成的区域称为它的邻域。 C. 状态 每个元胞有若干个状态，如： 物理系统：（分子）固态，液态 生物系统：（细胞）活与死 社会系统：（个人）相信与不相信谎言 政治系统：（国家）战争与妥协…… D. 网格 E. 状态更新规则（一） 根据每个元胞及邻元的不同状态，由状态更新规则决定这个元胞在下一个时刻的状态。 序号i个体在t=1,…,n时刻的状态 状态更新规则（二） 对于一个一维的CA，一个细胞具有两种可能的状态如生或死，相信或者不相信等等，表示为０或１。 如规则一：我们使用前面图c左边的邻元定义，且定义其状态更新规则为：当个体的两个邻元都活或者都死，该个体在下一时刻变为死；反之，他的状态在下一时刻变为活。即，更新规则如下表所示： 状态更新规则（三） 再如规则二：我们仍然使用前面图c左边的邻元定义，但重新定义其状态更新规则为：当个体的两个邻元都活或者都死，该个体在下一时刻改变状态；反之，该个体的状态在下一时刻保持不变。该规则下状态更新可以如下表所示： 4.3 元胞自动机仿真技术 4.3.1 模型的构建 考虑以下问题： 确定系统中有那些个体，如何分类？ 个体有几种状态，分别是什么； 个体所处的空间形式，是一维、二维还是多维； 个体的邻元形式及个数，这与网格形式及交互群体规模有关； 根据个体状态、网格形式及邻元，确定个体状态的演变规则。 此外，还需确定： 系统中的个体与单元格是否一致。 简单的、经典的CA模型中，单元格与个体不加区分，每个单位格就是一个个体，个体始终在单元格中，个体的状态即为单元格的状态。但在一些复杂系统中，尤其在个体可以移动的系统中，将个体与单元格区分更为方便。 系统中有否有离散事件。 采用CA模型描述的系统，每个时刻都需根据规则确定每个元胞的状态。除此之外，有的系统中某些个体会在特定时刻（有条件或无条件）发生状态变化，此时可以采用离散事件仿真方法，将该时刻列于事件表，根据事件表处理该类事件。 4.3.2 仿真技术 1. 仿真钟 仿真钟步进式推进，步长为1。在每一时刻都需改变个体以及网格状态，还要收集统计数据。 2. 事件的处理 某些系统中有离散事件的发生。对这类事件也采用事件表，将特定时刻及事件类型登记在事件表中。在仿真钟步进式推进的每个仿真时刻，除根据状态转移规则对所有元胞进行状态更新外，还要检查一下是否有特殊事件发生，如果有就产生事件进行处理。 3. 随机因素的处理 CA模型描述的复杂系统中往往带有不确定性 4.3.3 仿真流程 4.4 流言模型 流言模型 流言模型解释了流言通过个体之间局部的交互进行传播的过程：流言从一个人开始传播给某些听众，每个人从自己的邻居那里听到流言，然后他会把流言传给其他的邻居，并且假定一旦某个人听到这个流言，他会记住，不需要再次的传播。 4.4.1 基本的流言模型 C. 仿真原理 传播过程： 曲线图示——表示数量动态变化 4.4.2 概率规则的流言模型 基本模型因为简化了真实情况，流言传播速度很快，与真实系统不符。 1. 模型 引入概率规则，此类模型与最简单的流言模型不同之处仅在于状态的演变规则中包含了随机因素 状态转换规则①发生变化 原始规则：“如果单元格是白色的（不相信），并且它的邻元中有黑色的（相信），则该单元格从白色变成黑色。” 改变为： 如果单元格是白色的（不相信），并且它的邻元中有黑色的（不相信），则该单元格以一定概率从白色变成黑色 2. 仿真实现 当单元格为相信状态，在设置其邻元时，对所有邻元产生一个