常用元胞自动机在元胞自动机是由空间上各项同性的一系列元胞所组成,是在有限元胞自动机基础上发展起来的,用于模拟和分析几何空间内的各种现象。 典型的元胞自动机
在元胞自动机的发展过程中,科学家们构造了各种各样的元胞自动机模型。其中,以下几个典型模型对元胞自动机的理论方法的研究起到了极大的推动作用,因此,它们又被认为是元胞自动机发展历程中的几个里程碑。
l. S. Wolfram和初等元胞自动机
初等元胞自动机(Elementary CellularAutomata,简称ECA)是状态集S只有两个元素{s1,s2},即状态个数k=2,邻居半径r=l的一维元胞自动机(谢惠民,1994、李才伟, 1997、Wolfram,S,1986)。它几乎是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要,它可取 {0,1},{-l,1},{静止,运动},{黑,白},{生,死}等等,这里重要的是S所含的符号个数,通常我们将其记为 {0,1}。此时,邻居集N的个数2r=2,局部映射f:S3→S可记为:
其中变量有三个,每个变量取两个状态值,那么就有2×2×2=8种组合,只要给出在这八个自变量组合上的值,f就完全确定了。例如以下映射便是其中的一个规则:
通常这种规则也可表示为以下图形方式 (黑色方块代表l,白色方块代表0):
这样,对于任何一个一维的0,1序列,应用以上规则,可以产生下一时刻的相应的序列。以下序列就是应用以上规则产生的:
t:010111110101011100010
t+1:1010001010101010001 以上八种组合分别对应0或1,因而这样的组合共有28=256种,即初等元胞自动机只可能有256种不同规则。S. Wolfram定义由上述八种构形产生的八个结果组成一个二进制(注意高低位顺序),如上可得01001100,然后计算它的十进制值R:
R在[0,255]内,S. Wolfram定义R为初等元胞自动机的标号,则上面的元胞自动机模型就是76号初等元胞自动机 (谢惠民,1994;李才伟,1997)。
S.Wolfram对这256种模型一一进行了详细而深入的研究。研究表明,尽管初等元胞自动机是如此简单,但它们表现出各种各样的高度复杂的空间形态。经过一定时间,有些元胞自动机生成一种稳定状态,或静止,或产生周期性结构,那么,有些产生自组织、自相似的分形结构。S. Wolham(1983)借用分形理论计算了它们的维数约为1.59或1.69(Wolfram,S.,1983)。但256种元胞自动机中没有一种属于 S. Wolfram元胞自动机动力学分类得第四种,所谓复杂型。
S. Wolfram对一维元胞自动机,尤其是初等元胞自动机的深入研究奠定了元胞自动机理论的基石。对元胞自动机的理论研究,以及后来的人工生命研究和近来兴起的复杂性科学 (Science of Complexity)研究作出了卓越的贡献。
|