元胞自动机
元胞自动机
（1015051323 李新卫）
元胞自动机(Cellular Automata，简称CA，也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。是一时间和空间都离散的动力系统。散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。
初等元胞自动机(Elementary Cellular Automata，简称ECA)是状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径r=l的一维元胞自动机(谢惠民，1994、李才伟，1997、Wolfram，S，1986)。它几乎是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要，它可取 {0，1}，{-l，1}，{静止，运动}，{黑，白}，{生，死}等等，这里重要的是S所含的符号个数，通常我们将其记为 {0，1}。此时，邻居集N的个数2r=2，局部映射f:S3→S可记为Sit1fSit1,Sit,Sit1，其中变量有三个，每个变量取两个状态值，那么就有2×2×2=8种组合，只要给出在这八个自变量组合上的值，f就完全确定了。 生命游戏 (Came of Life)是J. H. Conway在20世纪60年代末设计的一种单人玩的计算机游戏(Garclner，M.，1970、1971)。他与现代的围棋游戏在某些特征上略有相似：围棋中有黑白两种棋子。生命游戏中的元胞有{"生"，"死"}两个状态 {0，1};围棋的棋盘是规则划分的网格，黑白两子在空间的分布决定双方的死活，而生命游戏也是规则划分的网格(元胞似国际象棋分布在网格内。而不象围棋的棋子分布在格网交叉点上)。根据元胞的局部空间构形来决定生死。只不过规则更为简单。下面介绍生命游戏的构成及规则:
(1)元胞分布在规则划分的网格上；
(2)元胞具有0，1两种状态，0代表"死"，l代表"生"；
(3)元胞以相邻的8个元胞为邻居。即Moore邻居形式；
(4)一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态 (确切讲是状态的和)决定:
·在当前时刻，如果一个元胞状态为"生"，且八个相邻元胞中有两个或三个的状态为"生"，则在下--时刻该元胞继续保持为"生"，否则"死"去；
·在当前时刻。如果一个元胞状态为"死"。且八个相邻元胞中正好有三个为"生"。则该元胞在下一时刻 "复活"。否则保持为"死"。
尽管它的规则看上去很简单。但生命游戏是具有产生动态图案和动态结构能力的元胞自动机模型。它能产生丰富的、有趣的图案。生命游戏的优化与初始元胞状态值的分布有关，给定任意的初始状态分布。经过若干步的运算，有的图案会很快消失。而有的图案则固定不动，有的周而复始重复两个或几个图案，有的婉蜒而行。有的则保持图案定向移动，形似阅兵阵……，其中最为著名的是"滑翔机 (叫Glider)"的图案。
生命游戏模型已在多方面得到应用。他的演化规则近似地描述了生物群体的生存繁殖规律:在生命密度过小(相邻元胞数之2)时，由于孤单、缺乏配种繁殖机会、缺乏互助也会出现生命危机，元胞状态值由1变为0;在生命密度过大 (相邻元胞数>3)时，由于环境恶化、资源短缺以及相互竞争而出现生存危机，元胞状态值由1变为0;只有处于个体适中(相邻元胞数为2或3)位置的生物才能生存(保持元胞的状态值为1)和繁衍后代(元胞状态值由0变为1)。正由于它能够模拟生命活动中的生存、灭绝、竞争等等复杂现象，因而得名"生命游戏"。J·H·Conway还证明，这个元胞自动机具有通用图灵机的计算能力(谢惠民，1994;李才伟，1997)，与图灵机等价，也就是说给定适当的初始条件，生命游戏模型能够模拟任何一种计算机。
相关程序：
% Simulate disease spreading on a 2D grid
% Set parameter values
N=100; % Grid size (NxN)
beta=0.01; % Infection rate
gamma=0.01; % Immunity rate
% define grid
x = zeros(N, N); % The grid x, is coded as: 0=Susceptible, 1=Infected, 2=Removed
% Set the initial grid, x with a circle of infected individuals in the % center of the grid, and with a radius of 10 cells.
for i=1:N
for j=1:N
dx = i-N/2;
dy = j-N/2;
R = sqrt(dx*dx+dy*dy);
if ( R
x(i,j)=1;
end
end
end
% Define the Moore neighborhood, i.e. the 8 nearest neighbors
neigh = [-1 -1; 0 -1; 1 -1; 1 0; 1 1; 0 1; -1 1; -1 0];
% Create a new figure
figure
hold on
% main loop, iterating the time variable, t
for t=1:100000
% iterate over all cells in grid x, for index i=1..N and j=1..N for i=1:N
for j=1:N
% Iterate over the neighbors and spread the disease
for k=1:8
i2 = i+neigh(k, 1);
j2 = j+neigh(k, 2);
% Check that the cell is within the grid boundaries if ( i2>=1 && j2>=1 && i2
% if cell is in state Susceptible and neighboring cell % Infected => Spread infection with probability beta if ( x(i,j)==0 && x(i2, j2)==1 )
if ( rand
x(i,j) = 1;
end
end
end
end
% If infected => Recover from disease with probability gamma if ( x(i,j)==1 && rand
x(i,j) = 2;
end
end
end
% Animate
clf % Clear figure
imagesc(x, [0 2]) % Display grid
pause(0.01) % Pause for 0.01 s
colormap([1 0 0; 0 1 0; 0 0 1]); % Define colors: Red, Green, Blue
% If no more infected => Stop the simulation
if ( sum(x==1)==0 )
break;
end
end
10
20
30
40
50
60
70
80
90
[***********]090100
[***********]100