元胞自动机.ppt

第四章元胞自动机
元胞自动机起源于对自我复制的机器的研究
冯·诺依曼(Von Neumann)

一个由元胞组成的完全离散的构架(现称网格),其中元胞表示系统的个体,个体具有若干个离散状态,个体状态根据网格中的邻元状态按规则同步进行变化。
广为人知---生命游戏
1970年剑桥大学的John
由《科学美国人》的数学游戏专栏介绍到全世界
20世纪80年代以来,CA得到了很大的发展并已经广泛地应用于物理学、生物学、数学、计算机科学和社会科学等研究领域。
概述
元胞自动机模型

元胞自动机是一个空间、空间和状态都是离散的模型。该模型可用一个四元组表示:

其中:
S表示细胞状态,是一个有限的、离散的状态集合;
La表示元胞空间,a是一个正整数,表示细胞空间的维数;
N表示领域内元胞的组合,n表示邻居的个数
f表示状态转移函数,即状态转移规则。
B. 领域和邻元
对于一个元胞,在空间位置上与它相邻的元胞称为它的邻元(有时也称作邻居)。
所有由邻元组成的区域称为它的邻域。
图d:一维CA网格的领域定义
图c: 二维CA网格的邻域定义
冯·诺依曼邻域
不同大小的摩尔邻域
邻域和邻元的定义可以是多样的,如图所示
C. 状态
每个元胞有若干个状态,如:
物理系统:(分子)固态,液态
生物系统:(细胞)活与死
社会系统:(个人)相信与不相信谎言
政治系统:(国家)战争与妥协……
D. 网格
图a:一维的CA网格
图b:二维的CA网格
一维的CA模型是将直线分成若干相同的等份;二维的CA模型是将一个平面分成许多正方形、六边形或三角形的网格(最常见的是将其划分成正方形);三维的CA模型将空间划分成许多立体网格。
在各种CA模型中,每一个等份(单元格)代表一个元胞, CA的网格可以有不同的形式(维数,大小)。
E. 状态更新规则(一)
根据每个元胞及邻元的不同状态,由状态更新规则决定这个元胞在下一个时刻的状态。
序号i个体在t=1,…,n时刻的状态
规则可以是确定型的,也可以是随机型的。
,其中
为个体i的邻元在 t 时刻的状态。
状态更新规则(二)
对于一个一维的CA,一个细胞具有两种可能的状态如生或死,相信或者不相信等等,表示为0或1。
如规则一:我们使用前面图c左边的邻元定义,且定义其状态更新规则为:当个体的两个邻元都活或者都死,该个体在下一时刻变为死;反之,他的状态在下一时刻变为活。即,更新规则如下表所示:
t 时刻邻元的状态
111
110
101
100
011
010
001
000
t + 1 时刻中心格的状态
0
1
0
1
1
0
1
0
表:一个一维CA的状态更新规则
状态更新规则(三)
再如规则二:我们仍然使用前面图c左边的邻元定义,但重新定义其状态更新规则为:当个体的两个邻元都活或者都死,该个体在下一时刻改变状态;反之,该个体的状态在下一时刻保持不变。该规则下状态更新可以如下表所示:
t 时刻邻元的状态
111
110
101
100
011
010
001
000
t + 1 时刻中心格的状态
0
1
1
0
1
0
0
1
表:一个一维CA的状态更新规则
元胞自动机仿真技术
模型的构建
考虑以下问题:
确定系统中有那些个体,如何分类?
个体有几种状态,分别是什么;
个体所处的空间形式,是一维、二维还是多维;
个体的邻元形式及个数,这与网格形式及交互群体规模有关;
根据个体状态、网格形式及邻元,确定个体状态的演变规则。