元胞自动机学习笔记

2021.7.19

一、简介：

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

二、构成：

元胞：可称为单元或基元，是元胞自动机最基本的部分
元胞状态：在最简单情况下，元胞有两种可能的状态；较复杂情况下，具有多种状态；元胞的状态都按照元胞动力机的动力规则不断更新。
元胞空间：元胞在空间分布上的集合
元胞邻居：某一元胞状态更新时所要搜索的空间域（能够影响该元胞下一时刻状态的元胞）

最常用的三种邻居

边界条件：理论上，元胞空间是无限的，实际应用中无法达到这一理想条件，为了给元胞空间边界上的元胞拥有规则所需要的邻居，就需要构建出一些虚拟邻居，常用的邻居边界条件类型有：固定型，周期型，绝热型和映射型。

固定型边界：虚拟邻居的状态自拟且固定
周期型边界：元胞空间的右边界作为左边界左边的虚拟邻居，左边界作为右边界右边的虚拟邻居
绝热型边界：虚拟邻居的状态为元胞本身
映射型边界：左边界上元胞的虚拟左邻居为该元胞的右邻居的状态

元胞规则：根据元胞当前的状态及邻居的状态来决定下一时刻该元胞的状态，元胞自动机根据规则进行局部元胞间的相互作用而引起全局变化

元胞自动机的特性：

离散性：空间、时间及状态都是离散的
同质性：服从相同的规律分布方式相同
并行性：元胞的状态更新规则变化时同步进行的
高维度：元胞自动机时一类无穷维动力系统

初等元胞自动机：

一维元胞自动机的元胞邻居半径为1
元胞有且只有两种状态

初等元胞自动机只有这八种状态

因为每种状态的元胞的下一状态都有两种情况：0 or 1，每种情况对应一种规则，所以共有 $2^8=256$ 种规则

三、实例

实例1：奇偶规则

元胞有两种状态{ 0,1 }；

邻居之和为奇数，中心元胞变为1；

邻居之和为偶数，中心元胞变为0；

MATLAB代码实现：

clc;clear;
n=200; %元胞空间大小
%元胞自动机的实现本质是矩阵的变化
Se=zeros(n);
z=zeros(n);
Se(n/2-2:n/2+2,n/2-2:n/2+2)=1; %设置初始状态Ch=imagesc(Se) %用红蓝色显示目前元胞状态Ch=imagesc(cat(3,Se,z,z)) %用红黑色显示目前元胞状态
axis square; %加方形边框Sd=zeros(n+2); %边界条件（上下左右各加一全为0的行/列）while(1)Sd(2:n+1,2:n+1)=Se; %相当于给Se加了一个全为0的框%边界条件sum=Sd(1:n,2:n+1)+Sd(3:n+2,2:n+1)+Sd(2:n+1,1:n)+Sd(2:n+1,3:n+2); %上邻居+下邻居+左邻居+右邻居%注意：Se和sum都是矩阵Se=mod(sum,2); %判断奇偶并赋值set(Ch,'cdata',cat(3,Se,z,z)) %控制性质（形状、颜色）的变化  %矩阵的更新pause(0.03) %每隔0.03秒变一次end

实例2：生命游戏

在一个正方形的棋盘中，每个小格有两种状态，“生”或“死”，每个小格有八个邻居：

① 对于“生”的格子，若他的8个邻居中有两个或者三个为“生”，则该格继续保持“生”，否则就变为“死”；

②对于“死”的格子，若他的8个邻居中有3个“生”，则该格变为“生”，否则继续保持“死”。

MATLAB代码实现：

clc;clear;
n=200; 
p=0.4 %初始化，以0.4"生"的概率生成
z=zeros(n);
Se=rand(n)<p;
Sd=zeros(n+2);
Ph=imagesc(cat(3,Se,z,z))
axis square; while(1)Sd(2:n+1,2:n+1)=Se;sum=Sd(1:n,2:n+1)+Sd(3:n+2,2:n+1)+Sd(2:n+1,1:n)+Sd(2:n+1,3:n+2);%元胞规则for i=1:nfor j=1:nif sum(i,j)==3||(sum(i,j)==2&&Se(i,j)==1)Se(i,j)=1;elseSe(i,j)=0;endendendset(Ph,'cdata',cat(3,Se,z,z)) %控制性质（形状、颜色）的变化  %矩阵的更新pause(0.03) %每隔0.03秒变一次 end

实例3：澳洲森林火灾

在正方形网络上，有三种状态：树，火，空地。

MATLAB代码：

clc;clear;
n=300; %定义森林矩阵的大小
Plight=5e-6; Pgrowth=1e-2; %定义闪电和生长的概率
UL=[n,1:n-1];DR=[2:n,1]; %定义上左、下右邻居???(周期型）veg=zeros(n);   %初始化森林矩阵 veg= 0:空地  1:着火  2：树imh=imagesc(cat(3,veg,veg,veg))
axis square; for i=1:3000%计算所有格子着火的数量sum=(veg(UL,:)==1)+(veg(:,UL)==1)+(veg(:,DR)==1)+(veg(DR,：)==1);%根据规则更新森林矩阵：是否树=是否着火的树+是否新生的树（0-1运算）veg=2*(veg==2)-((veg==2)&(sum>0|(rand(n,n)<Plight)))+2*((veg==0)&rand(n,n)<Pgrowth);set(imh,'cdata',cat(3,(veg==1),(veg==2),zeros(n)))pause(0.05);end