元胞自动机

第四章元胞自动机元胞自动机起源于对自我复制的机器的研究冯·诺依曼（VonNeumann）S.Ulam一个由元胞组成的完全离散的构架（现称网格），其中元胞表示系统的个体，个体具有若干个离散状态，个体状态根据网格中的邻元状态按规则同步进行变化。广为人知---生命游戏1970年剑桥大学的JohnH.Conway由《科学美国人》的数学游戏专栏介绍到全世界20世纪80年代以来，CA得到了很大的发展并已经广泛地应用于物理学、生物学、数学、计算机科学和社会科学等研究领域。4.1概述4.2元胞自动机模型A.概述元胞自动机是一个空间、空间和状态都是离散的模型。该模型可用一个四元组表示：其中：,,,aCLSNf•S表示细胞状态，是一个有限的、离散的状态集合；•La表示元胞空间，a是一个正整数，表示细胞空间的维数；•N表示领域内元胞的组合，n表示邻居的个数•f表示状态转移函数，即状态转移规则。B.领域和邻元对于一个元胞，在空间位置上与它相邻的元胞称为它的邻元（有时也称作邻居）。所有由邻元组成的区域称为它的邻域。图d：一维CA网格的领域定义图c：二维CA网格的邻域定义冯·诺依曼邻域不同大小的摩尔邻域邻域和邻元的定义可以是多样的，如图所示C.状态每个元胞有若干个状态，如：物理系统：（分子）固态，液态生物系统：（细胞）活与死社会系统：（个人）相信与不相信谎言政治系统：（国家）战争与妥协……D.网格图5.1一维的CA网格图a：一维的CA网格图b：二维的CA网格一维的CA模型是将直线分成若干相同的等份；二维的CA模型是将一个平面分成许多正方形、六边形或三角形的网格（最常见的是将其划分成正方形）；三维的CA模型将空间划分成许多立体网格。在各种CA模型中，每一个等份（单元格）代表一个元胞，CA的网格可以有不同的形式(维数，大小)。E.状态更新规则（一）根据每个元胞及邻元的不同状态，由状态更新规则决定这个元胞在下一个时刻的状态。序号i个体在t=1,…,n时刻的状态规则可以是确定型的，也可以是随机型的。112(,)(,,...)tttttttiiinSfSNfSSSS12,...tttnSSS，其中为个体i的邻元在t时刻的状态。状态更新规则（二）对于一个一维的CA，一个细胞具有两种可能的状态如生或死，相信或者不相信等等，表示为０或１。如规则一：我们使用前面图c左边的邻元定义，且定义其状态更新规则为：当个体的两个邻元都活或者都死，该个体在下一时刻变为死；反之，他的状态在下一时刻变为活。即，更新规则如下表所示：t时刻邻元的状态111110101100011010001000t+1时刻中心格的状态01011010表：一个一维CA的状态更新规则状态更新规则（三）再如规则二：我们仍然使用前面图c左边的邻元定义，但重新定义其状态更新规则为：当个体的两个邻元都活或者都死，该个体在下一时刻改变状态；反之，该个体的状态在下一时刻保持不变。该规则下状态更新可以如下表所示：t时刻邻元的状态111110101100011010001000t+1时刻中心格的状态01101001表：一个一维CA的状态更新规则4.3元胞自动机仿真技术4.3.1模型的构建考虑以下问题：确定系统中有那些个体，如何分类？个体有几种状态，分别是什么；个体所处的空间形式，是一维、二维还是多维；个体的邻元形式及个数，这与网格形式及交互群体规模有关；根据个体状态、网格形式及邻元，确定个体状态的演变规则。此外，还需确定：系统中的个体与单元格是否一致。简单的、经典的CA模型中，单元格与个体不加区分，每个单位格就是一个个体，个体始终在单元格中，个体的状态即为单元格的状态。但在一些复杂系统中，尤其在个体可以移动的系统中，将个体与单元格区分更为方便。系统中有否有离散事件。采用CA模型描述的系统，每个时刻都需根据规则确定每个元胞的状态。除此之外，有的系统中某些个体会在特定时刻（有条件或无条件）发生状态变化，此时可以采用离散事件仿真方法，将该时刻列于事件表，根据事件表处理该类事件。4.3.2仿真技术1.仿真钟仿真钟步进式推进，步长为1。在每一时刻都需改变个体以及网格状态，还要收集统计数据。2.事件的处理某些系统中有离散事件的发生。对这类事件也采用事件表，将特定时刻及事件类型登记在事件表中。在仿真钟步进式推进的每个仿真时刻，除根据状态转移规则对所有元胞进行状态更新外，还要检查一下是否有特殊事件发生，如果有就产生事件进行处理。3.随机因素的处理CA模型描述的复杂系统中往往带有不确定性4.3.3仿真流程开始设置参数更新后处理事件处理个体状态更新初始化有事件吗?tT仿真次数N输出仿真结果结束t=t+1是是否否否是流言模型流言模型解释了流言通过个体之间局部的交互进行传播的过程：流言从一个人开始传播给某些听众，每个人从自己的邻居那里听到流言，然后他会把流言传给其他的邻居，并且假定一旦某个人听到这个流言，他会记住，不需要再次的传播。4.4流言模型4.4.1基本的流言模型A.概述流言模型刻画了流言通过个体之间局部的交互进行传播的过程：流言从一个人开始传播给某些听众，每个人从自己的邻居那里听到流言，然后他会把流言传给其他的邻居，并且假定一旦某个人听到这个流言，他会永远记住。B.CA模型模型采用二维网格，邻元数量8个（摩尔领域）。模型中的单元格有两种状态：不相信流言和相信流言。单元格的状态更新规则如下：①如果单元格是白色的（不相信），并且它的邻元中有黑色的（相信），则该单元格从白色变成黑色。②如果单元格是黑色的，则该单元格将永远保持黑色不变。C.仿真原理T=0T=1T=2传播过程：曲线图示——表示数量动态变化0123450102030405060708090100numbert曲线：t=0,number=1t=1,number=9t=2,number=25t=3,number=49t=4,number=81个数＝(2n+1)2,n为步数基本模型因为简化了真实情况，流言传播速度很快，与真实系统不符。4.4.2概率规则的流言模型真实系统不是每个人都相信改变想法（逆转）邻元以一定概率相信流言多数模型规则改变1.模型引入概率规则，此类模型与最简单的流言模型不同之处仅在于状态的演变规则中包含了随机因素状态转换规则①发生变化原始规则：“如果单元格是白色的（不相信），并且它的邻元中有黑色的（相信），则该单元格从白色变成黑色。”改变为：如果单元格是白色的（不相信），并且它的邻元中有黑色的（不相信），则该单元格以一定概率从白色变成黑色2.仿真实现当单元格为相信状态，在设置其邻元时，对所有邻元产生一个（0，1）均匀分布随机抽样。由于演变规则为“以50%的概率成为相信者”，则在8个邻元中随机数在（0，0.5）的不相信的单元格变为相信，其他的不变。1t3.仿真结果相信人数的变化对比基本模型（p=1）和概率模型(p=0.5)结论与全部相信的情形相比流言扩散慢的多，也合理的多。但相信人数的变化规律定性上是一样的，只是参数不同而已，说明概率不同没有引起基本规律的变化，只是延缓了变化过程。0123450102030405060708090100p=0.5p=1numbert4.4.3带遗忘的流言模型1.模型上面模型假设一旦个体已经相信流言就永远不会忘记,但如果个体以某种概率忘记流言将会产生什么样的结果呢？带遗忘的流言模型就是描述这一现象的。规则②从原来的“如果一个单元格是黑色的，它将永远保持黑色”变为“如果一个单元格是黑色的，它会以一个固定的小概率变成白色”。2.仿真实现有遗忘的CA模型中，当个体从不相信变为相信的状态，首先要用一个遗忘概率来确定该个体是否属于遗忘个体。若是遗忘个体，则要根据遗忘时间的分布参数设置遗忘时刻，将遗忘事件（包括遗忘时刻与个体序号）登记到事件表中。个体变为相信遗忘型个体？产生遗忘时刻登记到事件表是否遗忘事件作为一个原发事件，当仿真时钟到达此时刻，则将该个体从相信状态变为不相信，这样就实现了遗忘，遗忘事件处理逻辑如图所示。个体状态更新有遗忘事件？找出该遗忘个体将遗忘个体状态变为不相信否是3.仿真结果设定流言相信概率50%,遗忘个体的比例为10%,一次仿真结果如图。黑色中的白色代表已经忘记流言的单元格1.概述在有些情况下，个体的状态是由其周围大多数个体的状态决定的。例如，人们只有在他的大多数朋友已接受一种时尚时，他才接受这一种时尚。用于研究这一类问题的CA模型，我们称之为多数模型。多数模型的特点是：模型中单元格的状态取决于其所有邻元的集体状态。4.5多数模型仍然假定单元格有白与黑两种状态。最简单的模型只有一条规则：单元格下一时刻的状态变为它的大多数Moore邻元的状态决定，或者该单元格保持目前的状态不变。Moore型邻元有8个，因此，这一规则是说：当有5个或更多白色单元格围绕时，单元格将变成白的；如果有5个或更多黑色单元格围绕时，它将变成黑的；当有4个白色4个黑色时，它保持原来状态不变。2.最简单的多数模型3.仿真结果仿真的初始状态是黑白单元格随机分布在网格中，按上述规则的运行结果是形成了一个白色块与黑色块相间的图案4.多数模型的扩展如对这个规则作些修正，假定人们对流行时尚的态度是不同的，一些人较容易受时尚的影响，而另一些人则可能不太容易受到时尚的影响。模型的状态更新规则将变为：一些白色单元格在仅有4个黑色相邻单元格时也会变黑色，而一些则必须至少有6个黑色相邻的单元格时才变色；对每个黑色单元格也是相似的。对于流行时尚易受影响或有抗拒倾向的个体在模型中是随机分布的。每个仿真时钟内，那些需要6个其他颜色的邻居才改变自身颜色的单元格和那些只要4个就会变颜色的单元格数目是相同的。在这一修正模型中，单元格不再是同质的，取而代之的是一些具有个体差异的单元格。482个时间步之后，黑白区块已形成了大的簇。(a)(b)(c)4.6艾滋病传播模型1.艾滋病的传播特性艾滋病传播的主要特点是与个体行为密切相关，病例中家族聚集和特殊行为人群聚集现象十分明显。所以对艾滋病传播相关行为的人群分类，有效的描述不同行为人群的传播特征是研究的前提。艾滋病毒感染者在感染后有几年或十几年的存活期，但各个时期传播强度不一样。在艾滋病传播的仿真中，不仅要模拟传播过程也要模拟个体感染直至死亡的全过程。艾滋病病程结合临床表现，根据其传播特性可以分成这样几个阶段：第一阶段为感染阶段，即从健康人到感染者。第二阶段是感染之后到死亡的患病阶段，在这期间感染者的行为特征与传播他人强度密切相关。其中在感染期由于病症不明显，传播强度大，在发病期传播强度减弱，如死亡则不再传播。不同行为群体的传播特性零传播人群P0：如儿童，出生时没被感染的健康儿童不可能被感染，因母婴传播已感染的儿童一般也不会传播他人。一般人群PL：行为正常者，除正常的性行为外，无其它艾滋病病毒感染机会。这类个体易感度及传播他人的强度均小。高危人群PH：具有高危行为，如共用针管吸毒者、性工作者、同性恋者、卖血者。他们由于特殊行为有较大的概率通过血液、性途径感染艾滋病毒，感染后快速的传播他人。报复者PH+：这些人感染了艾滋病病毒后，敌视报复社会，大量恶意传播他人。这些人极少但破坏性却不小。2.艾滋病传播的CA模型a.个体状态健康S1危险S2感染S3发病S4死亡S5患病阶段感染阶段状态含义特点演变条件逆向演变S1健康未感染且不可能感染成为感染者的邻元→S2无S2危险有可能感染根据一定的概率→S3当不再是感染者的邻元→S1S3感染已感染，症状不明显，会传播他人一定时间之后→S4无S4发病有明显症状，传播强度减弱一定时间之后→S5无S5死亡无传染，邻元的危险解除无b.网格和邻元邻元的个数多少则表示已感染个体对他人的传播强度。由于不同行为个体对他人的传播强度差异很大，所以用不同的邻域来表示不同类型个体不同病程的传播强度。不同类型个体的易感度也有差异，模型中采用被感染概率来表示易感度，概率大的则易感度高。