元胞自动机.ppt

第四章元胞自动机元胞自动机起源于对自我复制的机器的研究冯·诺依曼(VonNeumann)(现称网格),其中元胞表示系统的个体,个体具有若干个离散状态,个体状态根据网格中的邻元状态按规则同步进行变化。广为人知---《科学美国人》的数学游戏专栏介绍到全世界20世纪80年代以来,CA得到了很大的发展并已经广泛地应用于物理学、生物学、数学、计算机科学和社会科学等研究领域。、空间和状态都是离散的模型。该模型可用一个四元组表示:其中:S表示细胞状态,是一个有限的、离散的状态集合;La表示元胞空间,a是一个正整数,表示细胞空间的维数;N表示领域内元胞的组合,n表示邻居的个数f表示状态转移函数,即状态转移规则。,在空间位置上与它相邻的元胞称为它的邻元(有时也称作邻居)。所有由邻元组成的区域称为它的邻域。图d:一维CA网格的领域定义图c:二维CA网格的邻域定义冯·诺依曼邻域不同大小的摩尔邻域邻域和邻元的定义可以是多样的,,如:物理系统:(分子)固态,液态生物系统:(细胞)活与死社会系统:(个人)相信与不相信谎言政治系统:(国家)战争与妥协……:一维的CA网格图b:二维的CA网格一维的CA模型是将直线分成若干相同的等份;二维的CA模型是将一个平面分成许多正方形、六边形或三角形的网格(最常见的是将其划分成正方形);三维的CA模型将空间划分成许多立体网格。在各种CA模型中,每一个等份(单元格)代表一个元胞,CA的网格可以有不同的形式(维数,大小)。(一)根据每个元胞及邻元的不同状态,由状态更新规则决定这个元胞在下一个时刻的状态。序号i个体在t=1,…,n时刻的状态规则可以是确定型的,也可以是随机型的。,其中为个体i的邻元在t时刻的状态。状态更新规则(二)对于一个一维的CA,一个细胞具有两种可能的状态如生或死,相信或者不相信等等,表示为0或1。如规则一:我们使用前面图c左边的邻元定义,且定义其状态更新规则为:当个体的两个邻元都活或者都死,该个体在下一时刻变为死;反之,他的状态在下一时刻变为活。即,更新规则如下表所示:t时刻邻元的状态1111101011000**********t+1时刻中心格的状态01011010表:一个一维CA的状态更新规则状态更新规则(三)再如规则二:我们仍然使用前面图c左边的邻元定义,但重新定义其状态更新规则为:当个体的两个邻元都活或者都死,该个体在下一时刻改变状态;反之,该个体的状态在下一时刻保持不变。该规则下状态更新可以如下表所示:t时刻邻元的状态1111101011000**********t+1时刻中心格的状态01101001表::确定系统中有那些个体,如何分类?个体有几种状态,分别是什么;个体所处的空间形式,是一维、二维还是多维;个体的邻元形式及个数,这与网格形式及交互群体规模有关;根据个体状态、网格形式及邻元,确定个体状态的演变规则。