元胞自动机的应用

2019-01-20 本文已影响0人 Xindolia_Ring

【定义】
元胞自动机（Cellular Automata, CA）
定义在一个具有离散、有限状态的元胞组成的元胞空间上，并按照一定的局部规则，在离散的时间维度上演化的动力学系统。

【构成】
可以视为由一个元胞空间和定义于该空间的变换函数所组成

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

基本组成：

网格类型	优点	缺点
三角形	拥有相对较少的邻居数目，易于处理复杂边界	在计算机的表达与显示不方便，需要转换为四方网格
正方形	直观简单，而且适合于在现有计算机环境下进行表达显示	不能较好地模拟各向同性的现象
正六边形	能够较好地模拟各向同性的现象，因此，模型更更加自然而真实	在表达显示上较为困难、复杂

(2)元胞空间的边界条件
理论上，元胞空间是无限的，实际应用中无法达到这一理想条件。常用的边界条件有以下几种：周期型、定值型、绝热型、反射型

周期型边界条件(Periodic Boundary)
是指相对边界连接起来的元胞空间
对于一维空间，首尾相接形成一个圆环；
对于二维空间，上下相接、左右相接，形成一个拓扑圆环面，形似车胎
周期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间作为实验
e.g: b|a|...|b
定值型边界条件(Constant Boundary)
所有边界外元胞均取某一固定常量
e.g: 1|a|...| |
绝热型边界条件(Adiabatic Boundary)
在指边界外邻居元胞的状态始终和边界元胞的状态保持一致，即具有状态的零梯度。
e.g: a|a|...| |
反射型边界条件(Constant Boundary)
在边界外邻居的元胞状态是以边界元胞为轴的镜面反射
e.g: b|a|b|...| |

邻居
1.冯诺依曼型
邻居数目=2d
2.摩尔型
邻居数目 $3^d - 1$
3.扩展摩尔型
邻居数目 $(2r+1)^d - 1$
4.马格勒斯型(Margolus)
主要区别：以22的元胞块为单元进行处理，而不是单独处理
主要应用领域：格子气流体、颗粒流
规则
根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单来说就是一个状态转移函数。
$f : S_i^{t+1} = f(S_i^t, S_N^t)$
这里f为元胞自动机的局部映射或局部规则
状态
(1)二进制形式
(2)有限整数集内S取值，e.g 交通领域的CA模型 $[-(V_{max}+1) , +(V_{max}+1)]$
(3)状态参量：严格意义上的CA只能有一个状态参量，但是实际应用中可以有多个状态参量。
时间
元胞自动机中的时间是离散的，是一系列的整数值，是一个无量纲的整数。
若时间步长以dt = 1，t = 0为初始时刻，则t+1为下一时刻。