cellular automata

元胞自动机(cellular automata，CA) 是一种时间、空间、状态都离散，空间相互作用和时间因果关系为局部的网格动力学
模型，具有模拟复杂系统时空演化过程的能

概述

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

其中：

  • $S$表示细胞状态，是一个有限的、离散的状态集合；
  • $L_a$表示元胞空间，$a$是一个整数，表示细胞空间的维数；
  • $N$表示领域内元素的组合，$n$表示邻居的个数
  • $f$表示状态转移函数，即状态转移规则

对于一个元胞，在空间位置上与它相邻的元胞称为它的邻元(有时也称作邻居)。

邻域和邻元的定义可以是多样的

下图为一维CA网格邻域定义

下图为二维CA网格邻域定义

每个元胞有若干个状态，如：

  • 物理系统：（分子）固态，液态
  • 生物系统：（细胞）死or活
  • 社会系统： （个人）相信与不相信谎言
  • 政治系统： （国家）战争与妥协…

  在各种CA模型中，每个等份（单元格）代表一个元胞，CA的网格可以有不同的形式(维数，大小)。

  • 一维的CA模型是将直线分成若干相同的等份；
  • 二维的CA模型是将一个平面分成许多正方形、六边形或三角行的网格（最常见的是将其划分成正方形）；
  • 三位的CA模型将空间划分成许多立体网格。

  

根据每个元胞及邻元的不同状态，由于状态更新规则决定这个元胞下一个时刻的状态。

序号$i$个体在$t=1,\dots,n$时刻的状态:

其中$S_i^t,S_1^t,S_2^t,\dots,S_n^t$为个体$i$的邻元在$t$时刻的状态。

规则可以是确定型的，也可以是随机型的。对于一个一维的CA，一个细胞具有两种可能的状态如生or死，相信或者不相信等等，表示为0or1.
如果规则一：我使用下图的左边的邻元定义
定义其状态更新规则：当一个个体的两个邻元都活或都死，该个体在下一时刻为死；反之，他的状态在下一时刻变为活。

再如规则二：我仍然使用当前左边邻元定义，但重新定义其状态
更新规则为：当个体的两个邻元都活或都死，该个体再下一时刻改变状态;反之，该个体的状态在下一时刻保持不变。

模型的构建

考虑以下问题：

  • 确定系统中有那些个体，如何分类？
  • 个体有几种状态，分别是什么；
  • 个体所处空间形式，是一位，二维还是多为；
  • 个体的邻元形式及个数，这与网格形式及交互群体规模有关
  • 根据个体状态、网格形式及邻元，确定个体状态的演变规则。
    此外，还需确定：
  • 系统中的个体与单元格是否一致。
    简单的、经典的CA模型中，单元格与个体不加区分，每个单位格就是一个个体，个体始终在单元格中，个体的状态即为单元格的状态。但在一些复杂系统中，尤其在个体可以移动的系统中，将个体与单元格区分更为方便。
  • 系统中是否离散事件。
    采用CA模型描述的系统，每个时刻都需根据规则确定伟哥元胞的状态。除此之外，有的系统中某些个体会在特定时刻（有条件或无条件）发生状态变化，此时可以采用离散时间仿真方法，将该时刻列入事件表，根据事件表处理该类事件。
推荐 python 库中pandas 如果使用 pip install pandas 可以能会无法下载。如果无法下载则使用 
pip --default-time=100 install pandas
这行命令，可以进行下载。