元胞自动机建模方法的原理详解

复杂系统一般是由许多子系统或基本单元组成的，它们之间的相互作用产生并非叠加效果的系统整体（涌现）特性。基于这种思想，建模中元胞自动机将模型空间以某种网格形式划分为许多单元（亦称之为基元、格位、网格或元胞），每个元胞的状态以离散值表示，简单情况下可取0或1，复杂情况下可取多值。按照马尔可夫链理论，元胞状态的更新由其自身和相邻元胞的前一时刻状态共同决定。不同的网格形状、状态集和操作规则将构成不同元胞自动机。

从本质上讲，元胞自动机是模拟复杂结构和过程的一种数学模型，由元胞空间、元胞、元胞状态集、邻居和演化规则组成，可用形式化的语言来描述，即可以用下列四元组表示：

式中，CA代表元胞自动机；Ωd代表一个规则划分的元胞空间（d是空间维数），是一种离散的空间网格集合，每个网格单元就是一个元胞；C表示元胞的状态空间，是一个有限的状态集，用以表示各个元胞的状态；N表示一个元胞的邻域，是一个对中心元胞下一时刻的状态值产生影响的元胞集合，记为N=（c1，c2，…，cn），ci∈Z（整数集合），i=1，2，…，n。F为一个映射函数→Ct+1，即根据t时刻某个元胞的所有邻居的状态组合来确定t+1时刻元胞的状态值，故F通常又被称为状态转换函数或局部规则。

为简便起见，我们在一维空间上考虑元胞自动机，即假定d=1。

对于一维空间，元胞及其邻居可以记为C2r+1，局部函数则可记为

对于局部规则F，函数的输入、输出集均为有限集合，实际上它是一个有限的参照表。例如，r=1，则F形式如下：

［0，0，0］→0，［0，0，1］→0，［0，1，0］→1，［1，0，0］→0，［0，1，1］→1，［1，0，1］→0，［1，1，0］→0，［1，1，1］→0。

对元胞空间内的元胞，独立施加上述局部函数，可得到全局的演化，

式中表示i位置处的元胞。

至此，我们就得到了一个一维空间上一维规则、二值状态、三邻居的元胞自动机模型。(www.xing528.com)

若以式（6.3.2）中每组态的值表示每个可能的元胞自动机规则，则有256条演化规则。每条规则数NR可由（6.3.4）计算。

式中ai表示二进制数从右到左按递增顺序排列，即a0=000，a1=001，…，a7=111。

上述256种演化规则可分为4类。

（1）经有限时步，几乎全部初始状态都演化成单值均匀状态。

（2）初始状态演化为不随时间变化的定态或周期性循环状态。

（3）初始状态演化为非周期图形或演化为混沌状态。

（4）初始状态演化为持续不断的复杂结构。

另外，应指出，通常网格形状会因模型维数的不同而各异。一维时网格形状为格点；二维时网格形状为三角形、正方形或六边形；三维时网格形状是许多立体网格。