元胞自动机ppt课件.ppt

《元胞自动机ppt课件.ppt》由会员分享，可在线阅读，更多相关《元胞自动机ppt课件.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、散的模型。该模型可用一个四元组表示： 其中：, , ,aCL S N f S表示细胞状态，是一个有限的、离散的状态集合； La表示元胞空间，a是一个正整数，表示细胞空间的维数； N表示领域内元胞的组合，n表示邻居的个数 f表示状态转移函数，即状态转移规则。 B. 领域和邻元图d：一维CA网格的领域定义 图c： 二维CA网格的邻域定义冯诺依曼邻域不同大小的摩尔邻域 邻域和邻元的定义可以是多样的，如图所示 C. 状态v每个元胞有若干个状态，如： 物理系统：（分子）固态，液态 生物系统：（细胞）活与死 社会系统：（个人）相信与不相信谎言 政治系统：（国家）战争与妥协 D. 网格图a：一维的CA网格图

3、b：二维的CA网格 一维的CA模型是将直线分成若干相同的等份；二维的CA模型是将一个平面分成许多正方形、六边形或三角形的网格（最常见的是将其划分成正方形）；三维的CA模型将空间划分成许多立体网格。v 在各种CA模型中，每一个等份（单元格）代表一个元胞， CA的网格可以有不同的形式(维数，大小)。 E. 状态更新规则（一）v 根据每个元胞及邻元的不同状态，由状态更新规则决定这个元胞在下一个时刻的状态。v 序号i个体在t=1,n时刻的状态v 规则可以是确定型的，也可以是随机型的。112(,)(,.)tttttttiiinSf S Nf S S SS12,.tttnS SS，其中为个体i的邻元在 t

4、 时刻的状态。 状态更新规则（二）v 对于一个一维的CA，一个细胞具有两种可能的状态如生或死，相信或者不相信等等，表示为或。v 如规则一：我们使用前面图c左边的邻元定义，且定义其状态更新规则为：当个体的两个邻元都活或者都死，该个体在下一时刻变为死；反之，他的状态在下一时刻变为活。即，更新规则如下表所示：t 时刻邻元的状态1 11 11 11 11 10 01 10 01 11 10 00 00 01 11 10 01 10 00 00 01 10 00 00 0t + 1 时刻中心格中心格的状态0 01 101 11 10 01 10 0表：一个一维表：一个一维CA的状态更新规则的状态更新规则

5、 状态更新规则（三）v 再如规则二：我们仍然使用前面图c左边的邻元定义，但重新定义其状态更新规则为：当个体的两个邻元都活或者都死，该个体在下一时刻改变状态；反之，该个体的状态在下一时刻保持不变。该规则下状态更新可以如下表所示：t 时刻邻元的状态1 11 11 11 11 10 01 10 01 11 10 00 00 01 11 10 01 10 00 00 01 10 00 00 0t + 1 时刻中心格中心格的状态0 01 11 10 01 10 00 01 1表：一个一维表：一个一维CA的状态更新规则的状态更新规则4.3 元胞自动机仿真技术元胞自动机仿真技术v4.3.1 模型的构建 考虑

6、以下问题： 确定系统中有那些个体，如何分类？ 个体有几种状态，分别是什么； 个体所处的空间形式，是一维、二维还是多维； 个体的邻元形式及个数，这与网格形式及交互群体规模有关； 根据个体状态、网格形式及邻元，确定个体状态的演变规则。 v此外，还需确定： 系统中的个体与单元格是否一致。简单的、经典的CA模型中，单元格与个体不加区分，每个单位格就是一个个体，个体始终在单元格中，个体的状态即为单元格的状态。但在一些复杂系统中，尤其在个体可以移动的系统中，将个体与单元格区分更为方便。 系统中有否有离散事件。采用CA模型描述的系统，每个时刻都需根据规则确定每个元胞的状态。除此之外，有的系统中某些个体会在特

7、定时刻（有条件或无条件）发生状态变化，此时可以采用离散事件仿真方法，将该时刻列于事件表，根据事件表处理该类事件。 4.3.2 仿真技术仿真技术1. 仿真钟 仿真钟步进式推进，步长为1。在每一时刻都需改变个体以及网格状态，还要收集统计数据。2. 事件的处理某些系统中有离散事件的发生。对这类事件也采用事件表，将特定时刻及事件类型登记在事件表中。在仿真钟步进式推进的每个仿真时刻，除根据状态转移规则对所有元胞进行状态更新外，还要检查一下是否有特殊事件发生，如果有就产生事件进行处理。3. 随机因素的处理 CA模型描述的复杂系统中往往带有不确定性 4.3.3 仿真流程仿真流程v 流言模型流言模型 流言模型

8、解释了流言通过个体之间局部的交互进行传播的过程：流言从一个人开始传播给某些听众，每个人从自己的邻居那里听到流言，然后他会把流言传给其他的邻居，并且假定一旦某个人听到这个流言，他会记住，不需要再次的传播。4.4 流言模型流言模型 4.4.1 基本的流言模型基本的流言模型A A.概述概述流言模型刻画了流言通过个体之间局部的交互进行传播的过程：流言从一个人开始传播给某些听众，每个人从自己的邻居那里听到流言，然后他会把流言传给其他的邻居，并且假定一旦某个人听到这个流言，他会永远记住。B.CAB.CA模型模型模型采用二维网格，邻元数量8个（摩尔领域）。模型中的单元格有两种状态：不相信流言和相信流言。单元

9、格的状态更新规则如下： 如果单元格是白色的（不相信），并且它的邻元中有黑色的（相信），则该单元格从白色变成黑色。 如果单元格是黑色的，则该单元格将永远保持黑色不变。 C. 仿真原理T=0T=1T=2传播过程：传播过程：曲线图示表示数量动态变化0123450102030405060708090100numbert曲线：t=0, number=1 t=1, number=9 t=2, number=25 t=3, number=49 t=4, number=81个数(2n+1)2, n为步数v 基本模型因为简化了真实情况，流言传播速度很快，与真实系统不符。 4.4.2 概率规则的流言模型概率规则的

10、流言模型真实系统不是每个人都相信改变想法（逆转）邻元以一定概率相信流言多数模型规则改变1. 模型模型v引入概率规则，此类模型与最简单的流言模型不同之处仅在于状态的演变规则中包含了随机因素 v状态转换规则发生变化状态转换规则发生变化 原始规则：“如果单元格是白色的（不相信），并且它的邻元中有黑色的（相信），则该单元格从白色变成黑色。”改变为： 如果单元格是白色的（不相信），并且它的邻元中有黑色的（不相信），则该单元格以一定概率从白色变成黑色 2. 仿真实现仿真实现v 当单元格为相信状态，在设置其邻元时，对所有邻元产生一个（0，1）均匀分布随机抽样。v 由于演变规则为“以50%的概率成为相信者”，

11、则在8个邻元中随机数在（0，0.5）的不相信的单元格变为相信，其他的不变。 1t 3. 仿真结果仿真结果v 相信人数的变化 对比基本模型（p=1）和概率模型(p=0.5)v 结论 与全部相信的情形相比流言扩散慢的多，也合理的多。但相信人数的变化规律定性上是一样的，只是参数不同而已，说明概率不同没有引起基本规律的变化，只是延缓了变化过程。 0123450102030405060708090100p=0.5p=1numbert4.4.3 带遗忘的流言模型带遗忘的流言模型v1. 模型 上面模型假设一旦个体已经相信流言就永远不会忘记,但如果个体以某种概率忘记流言将会产生什么样的结果呢？带遗忘的流言模型

12、就是描述这一现象的。 规则从原来的“如果一个单元格是黑色的，它将永远保持黑色”变为“如果一个单元格是黑色的，它会以一个固定的小概率变成白色”。 2. 仿真实现仿真实现v 有遗忘的CA模型中，当个体从不相信变为相信的状态，首先要用一个遗忘概率来确定该个体是否属于遗忘个体。若是遗忘个体，则要根据遗忘时间的分布参数设置遗忘时刻，将遗忘事件（包括遗忘时刻与个体序号）登记到事件表中。 v 遗忘事件作为一个原发事件，当仿真时钟到达此时刻，则将该个体从相信状态变为不相信，这样就实现了遗忘，遗忘事件处理逻辑如图所示。3. 仿真结果仿真结果v 设定流言相信概率50%,遗忘个体的比例为10%,一次仿真结果如图 。

13、黑色中的白色代表已经忘记流言的单元格 v 1 .概述 在有些情况下，个体的状态是由其周围大多数个体的状态决定的。例如，人们只有在他的大多数朋友已接受一种时尚时，他才接受这一种时尚。 用于研究这一类问题的CA模型，我们称之为多数模型多数模型。 多数模型的特点是：模型中单元格的状态取决于其所有邻元的集体状态。 4.5 多数模型多数模型v 仍然假定单元格有白与黑两种状态。v 最简单的模型只有一条规则：单元格下一时刻的状态变为它的大多数Moore邻元的状态决定，或者该单元格保持目前的状态不变。Moore型邻元有8个，因此，这一规则是说： 当有5个或更多白色单元格围绕时，单元格将变成白的； 如果有5个或

14、更多黑色单元格围绕时，它将变成黑的； 当有4个白色4个黑色时，它保持原来状态不变。 2. 最简单的多数模型最简单的多数模型3. 仿真结果仿真结果v 仿真的初始状态是黑白单元格随机分布在网格中，按上述规则的运行结果是形成了一个白色块与黑色块相间的图案 4. 多数模型的扩展多数模型的扩展v 如对这个规则作些修正，假定人们对流行时尚的态度是不同的，一些人较容易受时尚的影响，而另一些人则可能不太容易受到时尚的影响。v 模型的状态更新规则将变为：一些白色单元格在仅有4个黑色相邻单元格时也会变黑色，而一些则必须至少有6个黑色相邻的单元格时才变色；对每个黑色单元格也是相似的。v 对于流行时尚易受影响或有抗拒

15、倾向的个体在模型中是随机分布的。每个仿真时钟内，那些需要6个其他颜色的邻居才改变自身颜色的单元格和那些只要4个就会变颜色的单元格数目是相同的。在这一修正模型中，单元格不再是同质的，取而代之的是一些具有个体差异的单元格。482个时间步之后，黑白区块已形成了大的簇。(a)(b)(c)4.6 艾滋病传播模型艾滋病传播模型1. 艾滋病的传播特性艾滋病传播的主要特点是与个体行为密切相关，病例中家族聚集和特殊行为人群聚集现象十分明显。所以对艾滋病传播相关行为的人群分类，有效的描述不同行为人群的传播特征是研究的前提。 艾滋病毒感染者在感染后有几年或十几年的存活期，但各个时期传播强度不一样。在艾滋病传播的仿真

16、中，不仅要模拟传播过程也要模拟个体感染直至死亡的全过程。 v艾滋病病程结合临床表现，根据其传播特性可以分成这样几个阶段：第一阶段为感染阶段，即从健康人到感染者。第二阶段是感染之后到死亡的患病阶段，在这期间感染者的行为特征与传播他人强度密切相关。其中在感染期由于病症不明显，传播强度大，在发病期传播强度减弱，如死亡则不再传播。 v 不同行为群体的传播特性 零传播人群P0 ：如儿童，出生时没被感染的健康儿童不可能被感染，因母婴传播已感染的儿童一般也不会传播他人。 一般人群PL ：行为正常者，除正常的性行为外，无其它艾滋病病毒感染机会。这类个体易感度及传播他人的强度均小。 高危人群PH ：具有高危行为

17、，如共用针管吸毒者、性工作者、同性恋者、卖血者。他们由于特殊行为有较大的概率通过血液、性途径感染艾滋病毒，感染后快速的传播他人。 报复者PH+ ：这些人感染了艾滋病病毒后，敌视报复社会，大量恶意传播他人。这些人极少但破坏性却不小。 2. 艾滋病传播的艾滋病传播的CA模型模型a.个体状态健康S1危险S2感染S3发病S4死亡S5患病阶段感染阶段状态含义特点演变条件逆向演变S1健康未感染且不可能感染成为感染者的邻元 S2无S2危险有可能感染根据一定的概率 S3当不再是感染者的邻元 S1S3感染已感染，症状不明显，会传播他人一定时间之后 S4无S4发病有明显症状，传播强度减弱一定时间之后 S5无S5死

18、亡无传染，邻元的危险解除无b. 网格和邻元网格和邻元v 邻元的个数多少则表示已感染个体对他人的传播强度。由于不同行为个体对他人的传播强度差异很大，所以用不同的邻域来表示不同类型个体不同病程的传播强度。不同类型个体的易感度也有差异，模型中采用被感染概率来表示易感度，概率大的则易感度高。 个体类型行为特性邻元个数被感染概率P0无传播，无感染00PL正常行为13低PH高危行为816高PH+报复行为64低C. 状态变化规则状态变化规则v 第一条规则是从健康状态到危险状态的演变。健康状态的个体成为感染者的邻元后，该个体从健康状态转换到危险状态。实现方式是一旦个体感染后，根据感染者的行为类型设置其邻元，使

19、他的邻元均为危险状态。在设置邻元的同时，应根据各类人群的比例随机设置每个邻元的行为类型。v 第二条规则是从危险状态到感染状态的演变规则。处于危险状态的个体均有一个不同的概率从危险状态变为感染状态。v 个体从感染到发病再到死亡不是一个传播过程，而是病人的病变过程，其中状态演变的主要决定因素是时间。从感染到发病以及从发病到死亡的时间间隔均是随机变量 3. 仿真仿真v 仿真钟 仿真时间单位为周 v 状态更新一个是根据概率规则确定哪些个体从S2 S3，第二是为S3的个体根据其行为属性设置邻元，使其邻元从S1 S2，对每个S2个体给一个行为属性，并产生一个发病时间，登记到事件表。 v 事件处理事件类型名

20、称处理内容登记时间1发病减少邻元，产生并登记死亡事件感染时刻2死亡清除邻元，未感染邻元恢复健康状态发病时刻4. 结果结果v 假设网格由个100*100个单元格构成,人群的规模为2000。初始时刻所有个体随机均匀的分布在网格上，P0 、PL 、PH、 PH+的比例分别为0.1,0.7,0.12,0.08。某次仿真试验中某时刻各类个体的空间分布情况。v 各类行为人群5组不同比例下的感染曲线,保持P0和PL比例不变，变动PH和PH+的比例，为0.14(0.06)，0.16(0.04)，0.18(0.02)，0.20(0.0)。 1. 模型美国社会中不同种族，尤其以黑人，白人为典型，无论白人、黑人都愿

21、意周围有较多的同族，否则将迁移。采用CA模型描述这一动态过程，此时网格代表一个地理区域，网格上格点代表居住点，可以有人居住也可以无人居住。该模型中个体可以移动。个体：家庭属性：黑，白网格：二维（网格上的节点有个体或没个体）邻元：摩尔邻元，8个网格状态：白，黑，空个体状态：不动，迁移规则：如个体的同族邻元阀值则不动，否则迁移迁移规则：寻找满足不动条件的空格 4.7 迁移模型迁移模型2. 仿真仿真v在迁移模型的仿真中，仿真流程与CA仿真基本流程相同，也采用步进式推进。但是在每一仿真时刻执行的内容有些不同 3. 结果结果v“容忍阈值”为37.5%（Moore邻域中至少3/8的个体与自身相同）的仿真结

22、果 (a) (b)4.8 CA模型的相关讨论模型的相关讨论v 1 基本CA模型C（La，S，N，f）个体同质，规则固定，确定性2 扩展扩展CA模型模型v 个体异质：个体带属性，不同个体有不同网格，邻元及规则v规则不确定：v具有概率；规则随个体类型而变化v网格的格点上有空格：个体都在格点上，但格点上不一定都有个体v有特定时刻，发生特定事件 扩展扩展CA模型（续）模型（续）v边界问题：例：班上有64个学生，64个座位，88的网格。其中有5为问题学生，10为守纪学生，其余为一般学生。男女比例为1:1。问题学生必须所有邻元（8个）均为异性，守纪学生邻元可以有部分同性，一般学生必须有6个以上的邻元为异性

23、。如果不考虑边界，将问题学生放在四角；如果考虑边界，列之间要轮流，无边界。v个体的位置：在谎言模型中，相信谎言者向周围人传播谎言，谎言逐步扩散，流传周围，地域上，位置上的传播及无地域的传播v动态问题：初态的影响v个体的移动3.应用领域应用领域v 物理，化学领域：个体是分子，如雪花的形成，云团的形成v 生物领域：个体是细胞，肿瘤的形成和扩散v 工程领域：交通系统v 社会系统v基于CA模型的产业集群中技术扩散问题新技术在各企业中的扩散个体：企业状态：采用，不采用邻元：4或者8网格：二维企业采用新技术，即决定个体状态变化的主要因素不是邻元，企业的其他属性差异太大，决定采用或不采用，故此应用不适合。v传染病传播问题研究对象，传播速度，邻元是传播的最主要影响因素，故适合