元胞自动机模型

元胞自动机理论

元胞自动机（Cellular Automata，CA）是一种时空离散的局部动力学模型，是研究复杂系统的一种典型方法，特别适合用于空间复杂系统的时空动态模拟研究。

元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。

在CA模型中，散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。

CA模型的特点：时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。

元胞自动机的构成

元胞自动机最基本的组成：元胞、元胞空间、邻居及规则四部分。
简单讲，元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。

元胞自动机的构成

  1. 元胞

    元胞自动机的最基本组成部分。它分布在离散的一维、二维或多维欧几里德空间的晶格点上。

  2. 状态

    状态可以是{0,1}的二进制形式，或是{s0,s1,s2,…，si}整数形式的离散集。严格意义上，元胞只能有一个状态变量，但在实际应用中，往往将其进行扩展。

  3. 元胞空间

    元胞所分布在的空间网点集合就是元胞空间

    • 元胞空间的几何划分

      任意维数的欧几里德空间规则划分。对于一维元胞自动机，元胞空间划分只有一种。而高维的元胞自动机，元胞空间的划分则可能有多种形式。对于常见的二维自动机，元胞空间通常可按三角形、四边形或六边形三种网格排列。

      • 三角网格

        拥有较少的邻居数目，这在某些时候很有用。缺点是计算机的表达与显示不方便。

      • 四边形网格

        直观简单，特别适合于计算机环境下进行表达显示。

      • 六边形网格

        能较好的模拟各向同性的现象，因此，模型能更加自然而真实。其缺点同正三角网格一样，在表达显示上较为困难和复杂。

    • 边界条件

      理论上，元胞空间在各个维向上是无限延展的。实际应用过程中，无法在计算机上实现这一理想条件。

    • 构形

      在某个时刻，在元胞空间上所有元胞状态的空间分布组合。在数学上，它通常可以表示为一个多维的整数矩阵。

    邻居、元胞和元胞空间只表示了系统的静态成分，为了将动态引入系统，必须加入演化规则。这些规则是定义在局部空间范围内的，即一个元胞下一时刻的状态决定于本身的状态和它的邻居元胞的状态。因此，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。

    一维元胞自动机中，通常以半径r来确定邻居，距离一个元胞r内的所有元胞都属于该元胞的邻居。

    二维元胞自动机的邻居定义较为复杂，但通常有以下几种（以正方形网格为例 ）

  4. 规则

    根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是状态转移函数。这个函数构造了一种简单的离散的时间和空间范围的局部物理成分。状态的变化可以由状态转移函数表示：
    f: S t t+1 =f( S i t,…, S N t)S N t为t时刻的邻居状态组合f:S_t^{t+1}=f(S_i^t,…,S_N^t)\\ S_N^t为t时刻的邻居状态组合 f:Stt+1​=f(Sit​,…,SNt​)SNt​为t时刻的邻居状态组合

  5. 时间

    元胞自动机是一个动态系统，它在时间维上的变化是离散的，即时间t是一个整数值，而且连续且等间距。在上述转换函数中，一个元胞在t+1时刻的状态只直接决定于t 时刻的该元胞及其邻居的状态。

元胞自动机特性

把一个空间划分成网络，每一个点表示一个元胞，它们的状态赋值，在网格中用颜色的变化来表示，在事先设定的规则下，元胞的演化就用网格颜色的变化来描述，这样的模型就是元胞自动机。

通过对元胞自动机这些网络中的格点的不同定义，以及初始条件的不同，可以模拟出不同的现象和过程。

元胞自动机的基本特征：

  • 离散性：元胞自动机是高度离散的。它不仅仅空间离散时间离散，而且在函数值，即元胞的状态值也是离散的。
  • 动力学演化的同步性：元胞自动机具有利用简单的，局部规则的和离散的方法，描述复杂的，全部的和连续系统的能力。
  • 相互作用的局部性：元胞自动机的规则是局部的，而动力学行为规则是全局的，在模拟的过程中，具体的演化过程也是局部的，即仅同周围的元胞有关系。

元胞自动机应用的思想

复杂系统又称为非线性系统。如城市的发展与演化、城市人流与交通流以及交通堵塞的形成、自然环境下的动物的空间分布、河网的形成、疾病的传播等。

传统的自顶向下的分析方法是把系统分割成几个部分，对每一个部分逐个进行研究。而目前提出来的分析复杂动态系统的思想：自底向上的研究方法。

基于个体的自底向上的研究方法：
程序的行为完全由它的内部机制决定，通常将个体与程序相连，所模拟的复杂现象包括许多个体。在计算机里生成一个与真实世界对等的虚拟的人工世界，通常这个虚拟的世界包括许多个体，而这许多个体的行为呈现为复杂性。以此来探讨微观的个体行为和宏观复杂性之间的关系。

初等元胞自动机

初等元胞自动机是状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径r=1的一维元胞自动机。由于在S中具体采用什么符号并不重要，它可取 {0，1}，{-1，1}，{静止，运动} 等等，重要的是S所含的符号个数，通常我们将其记为 {0，1}。
此时，邻居集N的个数2⋅r=2，局部映射f: S 3−>S可记为： S i t+1 =f( S i−1t, S i t, S i+1t)此时，邻居集N的个数2·r=2，局部映射f:S_3->S可记为：S_i^{t+1}=f(S_{i-1}^t,S_i^t,S_{i+1}^t) 此时，邻居集N的个数2⋅r=2，局部映射f:S3​−>S可记为：Sit+1​=f(Si−1t​,Sit​,Si+1t​)

二维元胞自动机

  • J. Conway和生命游戏

    下面介绍生命游戏的构成及规则：

    1. 元胞分布在规则划分的网格上；

    2. 元胞具有0，1两种状态，0代表“死”，1代表“生”；

    3. 元胞以相邻的8个元胞为邻居。即Moore邻居形式；

    4. 一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态 (确切讲是状态的和)决定：

      在当前时刻，如果一个元胞状态为“生”，且八个相邻元胞中有两个或三个的状态为“生”，则在下一时刻该元胞继续保持为“生”，否则“死”去；

      在当前时刻，如果一个元胞状态为“死”，且八个相邻元胞中正好有三个为“生”，则该元胞在下一时刻 “复活”。否则保持为”死”。

    从数学模型的角度看，该模型将平面划分成方格棋盘，每个方格代表一个元胞。

    元胞状态: 0- 死亡，1- 活着

    领域半径: 1

    领域类型：Moore型

    元胞自动机是一个不可逆的离散动力系统

  • 元胞自动机的演化行为的统计特征

    Wolfram将元胞自动机的演化行为归纳为四大类：

    1. 平稳型（homogeneous）：自任何初始状态开始，经过一定时间演化后，经过若干步运算便停留在一个固定的状态。
    2. 周期型(periodic)：经过一定时间演化后，在几种状态之间周期循环。
    3. 混沌型(chaos)：自任何初始状态开始，经过一定时间演化后，处于一种完全无序随机的状态，几乎找不到任何规律。
    4. 复杂型(edge of chaos)：在演化的过程中可能产生复杂的结构，这种结构既不是完全的随机混乱，又没有固定的周期和状态。

    固定点—>周期—>复杂—>混沌

  • 森林火灾

    规则：
    元胞有3个不同的状态。状态为 0是树木，状态= 1是空地，状态= 5是燃烧着的树木。
    如果4个邻居中有一个或一个以上的是燃烧着的并且自身是树木，那么该元胞下一时刻的状态是燃烧。
    森林元胞（状态为 0 ）以一个低概率（例如0.000005 ）开始烧（因为闪电）。
    一个燃烧着的元胞（状态为 5 ）在下一时刻（时间步长可以控制）变成空位的（状态为0 ） 。
    空元胞以一个低概率（例如0.01 ）变为森林以模拟生长

  • 元胞自动机交通流模型

    特别注意：第184号规则

    车辆行驶规则为：黑色元胞表示被一辆车占据，白色表示无车，若前方格子有车，则停止。若前方为空，则前进一格。

    1992年，德国学者Nagel和Schreckenberg在第184号规则的基础上提出了一维交通流CA模型，即，NS 模型（或NaSch模型）

    NS模型是一个随机CA交通流模型，每辆车的状态都由它的速度和位置所表示，其状态按照以下演化规则并行更新 ：

    • 加速过程：

    • 安全刹车过程：

    • 随机慢化过程：（以随机慢化概率p）

    • 位置更新：

    d n= x n+1 − x n−L 其中：L——车辆长度7.5md_n=x_{n+1}-x_n-L\\ 其中：L——车辆长度 ~ 7.5m dn​=xn+1​−xn​−L其中：L——车辆长度7.5m

    NS模型的演化规则：

    1. 加速: 司机总是期望以最大的速度行驶
    2. 安全刹车: 为避免与前车碰撞
    3. 随机慢化（以随机慢化概率p）:由于不确定因素
      • 过度刹车
      • 道路条件变化
      • 心理因素
      • 延迟加速
    4. 位置更新:车辆前进