元胞自动机的一般特征
从元胞自动机的构成及其规则上分析,标准的元胞自动机应具有以下几个特征(谢惠民,1994;李才伟,1997):
(1)同质性、齐性。同质性反映在元胞空间内的每个元胞的变化都服从相同的规律,即元胞自动机的规则,或称为转换函数;而齐性指的是元胞的分布方式相同,大小、形状相同,空间分布规则整齐;
(2)空间离散:元胞分布在按照一定规则划分的离散的元胞空间上;
(3)时间离散:系统的演化是按照等间隔时间分步进行的,时间变量t只能取等步长的时刻点,形似整数形式的t0,t+l,t+2,…,而且,t时刻的状态构形只对其下一时刻,即t+1时刻的状态构形产生影响,而t+2时刻的状态构形完全决定于t+1的状态构形及定义在上面的砖换函数。元胞自动机的时间变量区别于微分方程中的时间变量t,那里t通常是个连续值变量;
(4)状态离散有限:元胞自动器的状态只能取有限(k)个离散值(s1,s2,...,sk)。相对于连续状态的动力系统,它不需要经过粗粒化处理就能转化为符号序列。而在实际应用中,往往需要将有些连续变量进行离散化,如分类,分级,以便于建立元胞自动机模型;
(5)同步计算(并行性):各个元胞的在时刻ti+1的状态变化是独立的行为,相互没有任何影响。若将元胞自动机的构形变化看成是对数据或信息的计算或处理,则元胞自动机的处理是同步进行的,特别适合于并行计算;
(6)时空局部性:每一个元胞的下一时刻ti+1的状态,取决于其周围半径为r的邻域(或者其它形式邻居规则定义下的邻域)中的元胞的当前时刻ti的状态,即所谓时间、空间的局部性。从信息传输的角度来看,元胞自动机中信息的传递速度是有限的;
(7)维数高:在动力系统中一般将变量的个数成为维数。例如,将区间映射生成的动力系统称为一维动力系统;将平面映射生成的动力系统称为二维动力系统;对于偏微分方程描述的动力系统则称为无穷维动力系统。从这个角度来看,由于任何完备元胞自动机的元胞空间是定义在一维、二维或多维空间上的无限集,每个元胞的状态便是这个动力学系统的变量。因此,元胞自动机是一类无穷维动力系统。在具体应用中或计算机模拟时当然不可能处理无限个变量,但一股也总是处理数量很大的元胞组成的系统。因此可以说维数高维是元胞自动机研究中的一个特点。
在实际应用过程中,许多元胞自动机模型已经对其中的某些特征进行了扩展,例如圣托斯兰州立大学(San Tose State University)研究的所谓连续型的元胞自动机,其状态就是连续的。但正如我们在元胞自动机的概念分析中指出的,在上述恃征中,同质性、并行性、局部性是元胞自动机的核心恃证,任何对元胞自动机的扩展应当尽量保持这些核心特征,尤其是局部性特征。
|