什么是元胞自动机?

元胞自动机(cellular automata,CA) 是一种时间、空间、状态都离散,空间相互作用和时间因果关系为局部的网格动力学模型,具有模拟复杂系统时空演化过程的能力。它能构建随时间推移发生状态转移的系统,细胞存在于一维或多维网格中,每个细胞都有一个或多个状态,每个细胞都有邻居(即邻近的细胞)。

元胞自动机分类

平稳型:自任何初始状态开始,经过一定时间运行后,元胞空间趋于一个空间平稳的构形,这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。 周期型:经过一定时间运行后,元胞空间趋于一系列简单的固定结构(Stable Patterns)或周期结构(Perlodical Patterns)。由于这些结构可看作是一种滤波器(Filter),故可应用到图像处理的研究中。 混沌型:自任何初始状态开始,经过一定时间运行后,元胞自动机表现出混沌的非周期行为,所生成的结构的统计特征不再变止,通常表现为分形分维特征。 复杂型:出现复杂的局部结构,或者说是局部的混沌,其中有些会不断地传播。

奇偶规则

奇偶规则是定义在二维网格上的一种元胞自动机。每个网格的状态用0各1表示。

(1)     对应于每一个元胞位置(i,j)计算出其八个最近领居在t时刻的状态值St的总和M(i,j)。

(2)     根据M(i,j)取值的奇偶性来决定下一时刻t+1该点的状态St+1(i,j)。当M(i,j)为偶数时,St+1(i,j)等于0;当M(i,j)为奇数时,St+1(i,j)等于1。八个点和为偶数,则变为0,为奇数则变为 1

平稳型元胞自动机实现

% 规则,先把中间点置为1,每一时间步对每一点,如果周围% 八个点和为偶数,则变为0,为奇数则变为 1Map = [1 1 1; 0 0 0];colormap(Map);% 设置网格大小S = 121;L = zeros(S);% 把中间一个数设置为 1 作为元胞种子M = (S+1)/2;L(M, M) = 1;Temp = L;imagesc(L);% 计算层数Layer = (S-1)/2 + 1;for t=2:Layer    for x=M-t+1:M+t-1       if x==M-t+1 || x==M+t-1                     for y=M-t+1:M+t-1            SUM = 0;            for m=-1:1               for n=-1:1                  if x+m>0 && x+m<=S && y+n>0 && y+n<=S                     SUM = SUM + L(x+m, y+n);                   end               end            end            SUM = SUM - L(x, y);            Temp(x, y) = mod(SUM, 2);          end                 else            y = M-t+1;            SUM = 0;            for m=-1:1               for n=-1:1                  if x+m>0 && x+m<=S && y+n>0 && y+n<=S                     SUM = SUM + L(x+m, y+n);                   end               end            end            SUM = SUM - L(x, y);            Temp(x, y) = mod(SUM, 2);                        y = M+t-1;            SUM = 0;            for m=-1:1               for n=-1:1                  if x+m>0 && x+m<=S && y+n>0 && y+n<=S                     SUM = SUM + L(x+m, y+n);                   end               end            end            SUM = SUM - L(x, y);            Temp(x, y) = mod(SUM, 2);       end    end    L = Temp;    imagesc(L);    pause(0.1);end

效果图