元胞自动机

2018-02-06

最近在参加数学建模美赛由于需要模拟森林火灾蔓延的动态模型查阅相关资料发现元胞自动机能有效地解决这个问题本文就当作是自己入门元胞自动机的一些心得吧

简介

元胞自动机（简称CA）是定义在一个离散、限状态的元胞空间上，按照一定规则，在离散的时间上演化的动力学系统。其特点是时间，空间，状态都离散，每个状态只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。

在正式介绍元胞自动机之前，先引入一个有限状态自动机（FSA）的概念。

有限状态自动机

有限状态自动机是具有离散输入和输出系统的一种数学模型。

其特点如下：

系统具有有限个状态，不同状态代表不同意义。按实际需要，系统在不同状态下完成规定的任务。
将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理所有的字符串都是这个字母表上的字符串。
系统在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。
系统中有一个开始状态。

有限状态自动机是一个五元组。其数学表达式如下：

$FA=(Q,S,\delta,q_0,F)$

参数	含义
Q	控制器有限状态集
S	输入符号的有限集
$\delta$	状态转移函数
$q_0$	初始状态集
F	终止状态集

FSA可分为确定与非确定两种。非确定有限状态自动机可以转换为确定有限状态自动机。

自动机从初始状态$q_0$开始，逐一读入输入串的每一个字母，根据当前状态，输入字母和转移函数决定自动机的下一个状态；若输入串结束时，自动机处于F的某一个状态，这表示自动机接受该字串；否则自动机不接受该字串。

有兴趣的朋友可以查阅这两者的相关资料，进一步了解。本文不再叙述。

一维元胞自动机

初等元胞自动机（ECA）用数学公式描述如下：
$$
ECA=(N,S，NC，R)
$$

参数	含义
N	元胞组成的网格空间
S	有限状态集，初等有两种状态，S={$S_1,S_2$}
NC	元胞邻域
R	演化规则，最多为$2^8$ =256

下面解释一下为何最多为256种：对于一维元胞自动机而言，他有两种状态{1，0}，但它由本状态和前一状态，后一状态（即其左右邻居）的状态共同决定{$S_{i+1},S_i,S_{i-1}$}，故此时的状态有$2^3=8$，而每种变量有2个状态，故为$2^8$种。

对于元胞空间补充两点：几何划分和边界条件。对于前者：理论上是可以划分为任意维度。但目前多集中在一维和二维。

对于后者：边界条件，由于在计算机中无法模拟理想条件，故人们常常定义三种类型：周期型（相对于边界连接起来的元胞空间，对于一维是一个首尾相连的“圈”；对于二维，上下相接，左右相接，形成一个拓扑圆环面，形似甜甜圈），反射型（以边界为轴的镜面反射），定值型（所有边界元胞均取某一固定常量）。在应用中，可能采用随机型。

演化实例

规定每个变量只有两个状态{1，0}，下面我们解释规则$（76）_{10}$=$（01001100）_{2}$

t	111	110	101	100	011	010	001	000
t+1	0	1	0	0	1	1	0	0

对于初始为{1，1，0，0，1}而言，使用规则76，序列为{111，110，100，001，011}，序列1和序列5为循环放置。第一次演化为：

111	110	100	001	011
0	1	0	0	1

相应的第二次演化为：

101	010	100	001	010
0	1	0	0	1

以此类推演化下去。

二维元胞自动机

特点：元胞分布在二维欧几里德平面上规则划分的网格点上，通常为方格划分。通常元胞自动机考虑两种邻域：Von Neumann型（5邻居）和Moore型（9邻居3*3）两种，如图：

由于从一维到二维会增加很多的演变种类，举个例：当邻居为1时，双色的情况下，需要定义512种。

本文不再详述，感兴趣的朋友可以查阅相关资料。

最后，本人的一点小体会，元胞自动机是根据邻域及当前状态，修改自身状态的一种机制。本文理解得比较粗浅，不足之处还望指教。

简介

一维元胞自动机

二维元胞自动机