元胞自动机(CA)代码及应用

元胞自动机基础元胞自动机（cellular automaton, CA）是最近一个比较热门的研究课题，其是物理、数学、计算机和生物等学科的交叉产物。

在计算机领域中，CA在人工智能、计算复杂性分析以及加密等多个领域中有着较大的用途。

特别是在大约十年前，密码学家H. Gutowitz根据CA的基本原理，提出了分块加密算法CA-1.1，使得CA在密码学中真正的迈出了第一步，也使得越来越多的密码学家开始了对CA的研究。

最近，我也开始对这个方面产生了浓厚的兴趣，并开始了一些学习，就先来简单的说说什么是CA吧！简单的说，元胞自动机是一个空间、时间和状态上都离散的动态系统。

构成CA的基本单位成为元胞（cellular），规则的分布在元胞空间（spatial lattice）的格点上，且各自的状态随着时间按照一定的局部规则变化。

也就是说，元胞的状态只能从一个有限的状态集中取值，每个时刻元胞的状态仅与其自身和邻居在上一时刻的状态有关，并且，所有的元胞在每个时刻均是同时更新的。

以上即是对CA的一个定性的描述，下面给出一个基于集合论的定量描述（L. Hurd等）：设d为CA空间的维数，k代表元胞的状态，集合S表示CA的整体状态，r表示元胞的邻居半径。

为了简单起见，我们在d=1，即一维空间上对CA进行讨论。

CA的动态性可以由一个全局函数F: St→St+1决定，并且，每个元胞的状态可以由一个局部函数f:kt→kt+1决定。

由于多维空间的CA具有很强的复杂性，故目前对CA的研究主要集中在一维和二维空间。

就一维空间而言，CA的结构显然只有可能是线性结构。

在二维空间，CA的结构可能有三角、四边或多边等构成方式。

显然，结构上的差异会对其在计算机表示及其他部分特性上带来一定的差异。

而CA 的邻居结构也通常包括Von. Neumann、Moore、扩展Moore和Margolus等多种形态，不同的邻居结构带来的特性和复杂度也不尽相同。

3. 元胞空间 元胞所分布在的空间网点集合就是 元胞空间 A、元胞空间的几何划分 任意维数的欧几里 德空间规则划分。对于一维元胞自动机，元胞 空间划分只有一种。而高维的元胞自动机，元 胞空间的划分则可能有多种形式。对于常见的 二维自动机，元胞空间通常可按三角形、四边 形或六边形三种网格排列。
Triangle
基于个体的自底向上的研究方法： 程序的行为完全由它的内部机制决定， 通常将个体与程序相连，所模拟的复杂 现象包括许多个体。在计算机里生成一 个与真实世界对等的虚拟的人工世界， 通常这个虚拟的世界包括许多个体，而 这许多个体的行为呈现为复杂性。以此 来探讨微观的个体行为和宏观复杂性之 间的关系。
二.常用元胞自动机
元胞自动机特性
• 把一个空间划分成网络，每一个点表示一个元胞，它们的状态赋值， 在网格中用颜色的变化来表示，在事先设定的规则下，元胞的演化就用 网格颜色的变化来描述，这样的模型就是元胞自动机。 • • 通过对元胞自动机这些网络中的格点的不同定义，以及初始条件的 元胞自动机的基本特征： 离散性：元胞自动机是高度离散的。它不仅仅空间离散时间 离散，而且在函数值，即元胞的状态值也是离散的。 不同，可以模拟出不同的现象和过程。
元胞自动机
元胞自动机是探索复杂系统中局部 — 整体 互动关系的最简单模式，视为演化分析的 基本计算模型；
物理学：一个离散的无穷维的动力学系统
数学：一个时空离散的数学模型，描述连续对 象的偏微分方程的对立体 计算机科学：新兴的人工智能、人工生命的分 支 生物学：生命现象的一种描述
Square
Hexagon
三角网格拥有较少的邻居数目，这在某些时候很 有用。缺点是计算机的表达与显示不方便。 四边形网格直观简单，特别适合于计算机环境下 进行表达显示。 六边形网格能较好的模拟各向同性的现象，因此， 模型能更加自然而真实。其缺点同正三角网格 一样，在表达显示上较为困难和复杂。

元胞自动机在城市扩展方面的应用综述摘要本文在介绍元胞自动机各要素的基础上，综述了元胞自动机用于城市扩展模拟的历史、元胞自动机用于城市扩展模拟的具体研究方向，即在具体的模型中如何确定模型的结构和参数，并对其未来的发展趋势进行了展望，并指出CA中的转换规则的扩展是在将来的研究中的一个首要问题。

关键字：元胞自动机；城市扩展模拟；转换规则一引言元胞自动机（CA）是一种时间、空间、状态都离散，空间的相互作用及时间上的因果关系皆局部的网格动力学模型，其“自下而上”的研究思路，强大的复杂计算功能、固有的平行计算能力、高度动态以及具有空间概念等特征,使得它在模拟空间复杂系统的时空动态演变方面具有很强的能力。

在城市空间动态变化的模拟研究方面，CA模型已应用到除非洲、南极洲的所有大洲的城市模拟研究当中。

CA模型和GIS的集成,一方面增强GIS的空间模型运算及分析能力，另一方面，GIS提供的强大空间处理能力可以为CA模型准备数据和定义有效的元胞转换规则以及对模拟结果进行可视化。

同时CA模型还可以与神经网络、主成分分析、遗传算法、模糊逻辑以及其他研究方法相结合，以增强其在城市空间变化模拟研究方面的能力。

将CA与MAS技术相结合，建立一个能够模拟多个不同参与因子（自然系统）、不同决策者（人文系统）共同影响下的城市发展模型，以此来模拟与预测城市发展的真实状况，将是CA模型在城市空间变化模拟与预测研究中的未来发展趋势。

国内元胞自动机应用研究起步较晚，受国际研究的推动，20世纪90年代末地理学界才开始类似的尝试研究，主要集中在基于元胞自动机的LUC（和城市增长模拟，罗平从经典地理过程分析的基本理论人手，分析和阐述了CA寸于经典，地理过程分析概念的表达程度的局限性，综合地理系统的几何属性和非几何属性提出了基于地理特征概念的元胞自动机（GeoFeature 一CA）,周成虎等人在Batty和Xie的DUE模型的基础上，构建了面向对象的、随机的、不同构的和两个CA莫型耦合的GeoCA- Urban模型，并成功模拟了深圳特区土地利用动态演化过程。

第07卷 第08期 中 国 水 运 Vol.7 No.08 2007年 08月 China Water Transport August 2007收稿日期：2007-5-15作者简介：许 林 男（1980—） 蓝天学院制造系 教师 （330098）徐 明 蓝天学院机械系 （330098）研究方向：数值模拟三维元胞自动机及其在计算机上的实现许 林 徐 明摘 要：元胞自动机是一种时空、状态离散的数学模型，适于计算机模拟实施。

特别适合于处理那些难以用数学定量描述的复杂动态体系问题，如材料微观组织的演变。

本文阐述了元胞自动机法的产生和发展。

并以Visual C++为编译平台，运用OpenGL 图形函数库建立了一种三维元胞自动机模型。

该模型具备了经典元胞自动机的基本特征，因此可以根据需要进行扩展。

文中运用该模型进行了简化的枝晶生长模拟，并与二维的模拟结果进行比较，验证了该模拟的正确性。

关键词：元胞自动机 三维建模 OpenGL中图分类号：TP211 文献标识码：A 文章编号：1006-7973（2007）08-0171-02 一、引言元胞自动机(CA) 又称细胞自动机是建立于细胞发育演化基础上的时空离散、状态离散的并行数学模型[1]。

元胞自动机最早是由数学家、物理学家John Von Neumann 和Stanislaw Ulam 在1940年提出的[2]。

但从应用角度看，直到1960年John Horton Conway 运用元胞自动机建立了一种“生命游戏”后[3,4,5]，元胞自动机才得到广泛的运用。

80年代，由于元胞自动机这类简单模型能十分方便地复制出复杂的现象或动态演变过程中的吸引、自组织和混沌现象，从而引起了物理学家、计算机科学家的极大兴趣，并在许多领域得到了应用，如混沌、分形的产生[6]，模式分类[7]，图像处理[8]，智能材料[9]，复杂现象[1]等，并提出了许多变形的元胞自动机，如以凝固理论为演化规则的元胞自动机[10]，模糊元胞自动机[11]，神经元胞自动机[12]等。

元胞自动机模拟害虫防治python代码元胞自动机（Cellular Automaton）是一种离散模型，由一组按照某种规则进行演化的格子组成。

我们可以使用元胞自动机来模拟害虫的防治过程。

下面是一个简单的Python代码示例，用于模拟害虫的扩散和防治过程。

注意：这个代码只是一个基础的示例，并未考虑许多真实世界中的复杂因素，例如环境变量、害虫种类、防治策略等。

pythonimport numpy as npimport matplotlib.pyplot as plt# 初始化元胞自动机def initialize_grid(size):grid = np.zeros((size, size))# 假设害虫在初始状态位于中心grid[size//2, size//2] = 1return grid# 更新元胞自动机状态def update_grid(grid, size, threshold, kill_prob):new_grid = grid.copy()for i in range(1, size-1):for j in range(1, size-1):# 计算邻居中的害虫数量neighbors = np.sum(grid[(i-1:i+2, j-1:j+2)]) - grid[i, j] if neighbors > threshold:# 如果邻居中的害虫数量超过阈值，当前格子可能会变为害虫new_grid[i, j] = 1 if np.random.rand() < 0.5 else 0elif neighbors == 0:# 如果邻居中没有害虫，当前格子可能会被防治new_grid[i, j] = 0 if np.random.rand() > kill_prob else 1 return new_grid# 绘制元胞自动机状态def plot_grid(grid, title):plt.imshow(grid, cmap='Greys', interpolation='nearest')plt.title(title)plt.show()# 主程序size = 100 # 元胞自动机大小threshold = 5 # 害虫繁殖阈值kill_prob = 0.8 # 防治成功率grid = initialize_grid(size)for i in range(100): # 模拟100个时间步plot_grid(grid, f'Step {i}')grid = update_grid(grid, size, threshold, kill_prob)在这个代码中，我们首先初始化了一个大小为size的元胞自动机，并在中心位置放入一个害虫。

元胞自动机在复杂系统建模中的应用元胞自动机（Cellular Automata，简称CA）是一种用来描述复杂系统行为的数学模型。

它由一组简单的单元（cell）组成，在一个由相同大小的正方形格子（grid）构成的网格上进行演化。

每个单元可以处于不同的状态，并通过更新规则与其邻居进行交互。

尽管元胞自动机的规则非常简单，但它已被广泛应用于生物、物理、社会科学等领域的复杂系统建模中。

本文将介绍元胞自动机在复杂系统建模中的应用，并探讨其优势和局限性。

元胞自动机最早由美国数学家John von Neumann和Stanislaw Ulam 于20世纪40年代提出。

它广泛应用于不同领域，例如生物学中的细胞生长模拟、物理学中的颗粒传输模拟、社会科学中的城市规划模拟等。

元胞自动机的简单规则和复杂行为之间的关系使其成为复杂系统建模中的强大工具。

首先，元胞自动机在生物学中的应用非常广泛。

生物系统中的许多现象可以通过元胞自动机来模拟和解释。

例如，在细胞生长过程中，细胞与周围细胞进行相互作用，从而形成特定的模式和结构。

通过模拟和研究这些交互作用，科学家可以更好地理解生物系统的发展和演化规律。

元胞自动机还可用于模拟病原体传播、生态系统动力学、遗传算法等生物学问题，为生物学研究提供了新的视角和方法。

其次，元胞自动机在物理学中的应用也非常突出。

在物质传输和分布的模拟中，元胞自动机可以精确地描述粒子之间的相互作用和运动规律。

通过定义单元的状态和更新规则，元胞自动机可以模拟物质在介质中的传输、扩散、聚集等复杂过程。

这种建模方法在材料科学、地球科学、天体物理学等领域得到了广泛应用，为研究人员提供了一种高效而有效的模拟工具。

此外，元胞自动机在社会科学中也有重要的应用。

社会系统是一种充满复杂性和非线性特征的系统，元胞自动机能够较好地刻画其内部的各种相互作用和演化规律。

例如，在城市规划模拟中，通过设定不同的元胞状态和邻居交互规则，可以模拟城市人口密度、交通流动、资源分配等问题，为城市规划者提供决策支持和优化方案。

1.sierpinski直角垫片function sierpinski3_by_CA(n);% 使用元胞自动机生成sierpinski直角垫片% Example:% sierpinski3_by_CA(256);% %算法见:孙博文,《分形算法与程序设计：用Visual C++实现》if nargin==0;n=256;endX=zeros(n);X(1,round(n/2))=1;H=imshow(X,[]);set(gcf,'doublebuffer','on');k=1;while k<round(n/2);X(k+1,2:end-1)=and(xor(X(k,1:end-2),X(k,3:end)),... ~X(k,2:end-1));set(H,'CData',1-X);pause(0.05);k=k+1;endnm=round(n/2);k=1;while k<nm;X(nm+k,1:end)=X(nm-k,1:end);set(H,'CData',1-X);pause(0.05);k=k+1;end2.sierpinski直角垫片function sierpinski(n);% 使用元胞自动机生成sierpinski直角垫片% Example:% sierpinski(256);% %算法见:孙博文,《分形算法与程序设计：用Visual C++实现》if nargin==0;n=256;endX=ones(n);X(1,n-1)=0;H=imshow(X,[]);set(gcf,'doublebuffer','on');k=1;while k<n;X(k+1,1:end-1)=xor(X(k,1:end-1),X(k,2:end));X(k+1,n)=1;set(H,'CData',X);pause(0.1);k=k+1;end3.扩散限制凝聚clc;clear;close all;S=ones(40,100);% state matrixS(end,:)=0; % initial sttaeSs=zeros(size(S)+[1,0]); % top line is origin of particleSs(2:end,:)=S; % showing matrixN=size(S,2);II=imagesc(Ss);axis equal;colormap(gray)set(gcf,'DoubleBuffer','on');while sum(1-S(1,:))<0.5;y=1;x=round(rand*[N-1]+1); % random positionD=0;while D<0.5; % random travelr=rand;if abs(x-1)<0.1;SL=1;elseSL=S(y,x-1);endif abs(x-N)<0.1;SR=1;elseSR=S(y,x+1);endif SL+SR+S(y+1,x)<2.5; % check the neighbor: left, right, under D=1;S(y,x)=0; % stop in the positionendif r<=1/3; % travel randomlyx=x-1;elseif r<=2/3;x=x+1;elsey=y+1;endSs(2:end,:)=S;if x<0.5|x>N+0.5;D=1; % out of the rangeelseSs(y,x)=0; % to show the moving particleendset(II,'CData',Ss); % to showpause(0.1);endend模拟卫星云图function CA_sim_cloud;% 使用元胞自动机模拟地球卫星的云图%% reference:% Piazza, E.; Cuccoli, F.;% Cellular Automata Simulation of Clouds in Satellite Images, % Geoscience and Remote Sensing Symposium, 2001. IGARSS '01. % IEEE 2001 International Volume 4, 9-13 July 2001 Page(s): % 1722 - 1724 vol.4 Digital Object Identifier 10.1109/IGARSS. % 2001.977050time=888; % 程序执行步数M=240;N=320;S=round(rand(M,N)*15);p=[1,2,1,6,6,1,2,1];p=sum(tril(meshgrid(p)),2)/20;rand('state',0);SS=S;R=rand(M,N);G=R;B=R;C=cat(3,R,G,B);fig=figure;set(fig,'DoubleBuffer','on');mov = avifile('example2.avi');cc=imshow(C,[]);set(gcf,'Position',[13 355 157 194])x1=(1:3)+round(M/2);y1=(1:3)+round(N/3);x2=(1:3)+round(M/3);y2=(1:3)+round(N/2);x3=(1:3)+round(M/1.5);y3=(1:3)+round(N/2);q=0;qq=15/4;while q<time;SS=zeros(M,N);for k=1:15;r=rand(M,N); % 生成几率rK=zeros(M+2,N+2);T=(S-k>=0); % 粒子数矩阵K(2:end-1,2:end-1)=T;SS=K(1:end-2,1:end-2).*(r<p(1))+...K(1:end-2,2:end-1).*(r<p(2) & r>=p(1))+... K(1:end-2,3:end).*(r<p(3) & r>=p(2))+... K(2:end-1,1:end-2).*(r<p(4) & r>=p(3))+... K(2:end-1,3:end).*(r<p(5) & r>=p(4))+... K(3:end,1:end-2).*(r<p(6) & r>=p(5))+... K(3:end,2:end-1).*(r<p(7) & r>=p(6))+... K(3:end,3:end).*(r>=p(7))+SS;endS=SS; %SS是粒子扩散后的分布S(S>15)=15;S(x1,y1)=15;S(x2,y2)=15;S(x3,y3)=15; % 粒子源赋值G=(S<=7.5);B=(S>qq);R=(S>qq & S<=7.5);C=double(cat(3,R,G,B));set(cc,'CData',C);q=q+1;pause(0.2);title(['q=',num2str(q)]);Nu(q)=sum(S(1:end));F = getframe(gca);mov = addframe(mov,F);endmov = close(mov);figure;plot(Nu)奇偶规则function edwards(N)% 简单元胞自动机—奇偶规则(模式3)同或运算% N is the size of calculational matrix% Examples:% figure% edwards(200)warning offM=ones(N);M(fix(29*N/59):fix(30*N/59),fix(29*N/59):fix(30*N/59))=0; close allimshow(M,[])for t=1:187;[M,Nu]=jisuan(M);pause(0.1)imshow(M)HH(t)=Nu;endfigure;plot(HH)function [Y,Nu]=jisuan(M);[x,y]=find(M==0);Nu=prod(size(x));Xmax=max(max(x));Xmin=min(min(x));Ymax=max(max(y));Ymin=min(min(y));T=ones(Xmax-Xmin+3,Ymax-Ymin+3);T(2:end-1,1:end-2)=M(Xmin:Xmax,Ymin:Ymax);Su=T;T=ones(Xmax-Xmin+3,Ymax-Ymin+3);T(2:end-1,3:end)=M(Xmin:Xmax,Ymin:Ymax);Su=xor(Su,T);Su=not(Su);T=ones(Xmax-Xmin+3,Ymax-Ymin+3);T(1:end-2,2:end-1)=M(Xmin:Xmax,Ymin:Ymax);Su=xor(Su,T);Su=not(Su);T=ones(Xmax-Xmin+3,Ymax-Ymin+3);T(3:end,2:end-1)=M(Xmin:Xmax,Ymin:Ymax);Su=xor(Su,T);Su=not(Su);M(Xmin-1:Xmax+1,Ymin-1:Ymax+1)=Su;Y=M;森林火灾模拟close all;clc;clear;figure;p=0.3; % 概率pf=6e-5; % 概率faxes;rand('state',0);set(gcf,'DoubleBuffer','on');% S=round((rand(300)/2+0.5)*2);S=round(rand(300)*2);% \copyright: zjliu% Author's email: zjliu2001@Sk=zeros(302);Sk(2:301,2:301)=S;% 红色表示正在燃烧(S中等于2的位置)% 绿色表示绿树(S中等于1的位置)% 黑色表示空格位(S中等于0的位置)C=zeros(302,302,3);R=zeros(300);G=zeros(300);R(S==2)=1;G(S==1)=1;C(2:301,2:301,1)=R;C(2:301,2:301,2)=G;Ci=imshow(C);ti=0;tp=title(['T = ',num2str(ti)]);while 1;ti=ti+1;St=Sk;St(Sk==2)=0; % for rule (1)Su=zeros(302);Sf=Sk;Sf(Sf<1.5)=0;Sf=Sf/2;Su(2:301,2:301)=Sf(1:300,1:300)+Sf(1:300,2:301)+Sf(1:300,3:302)+... Sf(2:301,1:300)+Sf(2:301,3:302)+Sf(3:302,1:300)+...Sf(3:302,2:301)+Sf(3:302,3:302);St(Sf>0.5)=2; % for rule (2)Se=Sk(2:301,2:301);Se(Se<0.5)=4;Se(Se<3)=0;Se(Se>3)=1;St(2:301,2:301)=St(2:301,2:301)+Se.*(rand(300)<p); %for rule (3)Ss=zeros(302);Ss(Sk==1)=1;Ss(2:301,2:301)=Ss(1:300,1:300)+Ss(1:300,2:301)+Ss(1:300,3:302)+... Ss(2:301,1:300)+Ss(2:301,3:302)+Ss(3:302,1:300)+...Ss(3:302,2:301)+Ss(3:302,3:302);Ss(Ss<7.5)=0;Ss(Ss>7.5)=1;d=find(Ss==1 & Sk==1);for k=1:length(d);r=rand;St(d(k))=round(2*(r<=f)+(r>f));end % for rule (4)Sk=St;R=zeros(302);G=zeros(302);R(Sk==2)=1;G(Sk==1)=1;C(:,:,1)=R;C(:,:,2)=G;set(Ci,'CData',C);set(tp,'string',['T = ',num2str(ti)]) pause(0.2);end。

CA优化模型原代码:M=load(‘d:\ca\jlwm’)N=load(‘d:\ca\jlwn.asc’)lindishy=load(‘d:\ca\ldfj3.asc’)caodishy=load(‘d:\ca\cdfj3.asc’)gengdishy=load(‘d:\ca\htfj3.asc’)[m,n]=size(M);Xr=[1 1 -1 1 1 1 -1 -1 1 1;1 1 1 1 -1 -1 1 1 1 -1;-1 1 1 1 -1 -1 -1 1 -1 -1;1 1 1 1 1 1 -1 1 1 I; l -1 -1 1 1 -1 -1 -1 1 1;1 -1 -1 1 -1 1 -1 1 -1 -1;-1 1 -1 -1 -1 -1 1 -1 -1 -1;-1 1 1 1 -1 1 -1 1 -1 -1;1 1 -1 1 1 -1 -1 -1 1 1;1 -1 -1 1 1 -1 -1 -1 1 1];caodi=0;lindi=0;gengdi=0;for i=1:mforj=l:nif M(i,j)==4caodi=caodi+1;elseif M(i,j)==3lindi=lindi+1;elseif M(i,j)==2gengdi=gengdi+1;endendendfor i=1:mfor j=1:nif M(i,j)==4if lindishy(i,j)>gengdishy(i,j)if lindishy(i,j)>caodishy(i,j)z=0;for P=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if (M(p,q)~=0)&&xr(M(p,q),3)==-1z=1;endendendif z== 0caodi=eaodi-1;M(i,j)=3;lindi=lindi+1;endelseif lindishy(i,j)==caodishy(i,j)caoditemp=0;linditemp=0;gengditemp=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(i+1,n)if N(p,q)==4caoditemp=caoditemp+1;elseif N(p,q)==3linditemp=linditemp+1;elseif N(p,q)=2gengditemp=gengditemp+1;endendendif linditemp>=max(caoditemp,gengditemp) z=0;for p=max(1,j-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(M(p,q)~=0)&&xr(M(p,q),3)==-1;z=1;endendendif Z==0caodi=caodi-1;M(i,j)=3;lindi=lindi+1;endendendelseif lindishy(i,j)==gengdishy(i,j)if lindishy(i,j)>caodishy(i,j)caoditemp=0:linditemp=0;gengditemp=0:for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if N(p,q)==4caoditemp=caoditemp+1;elseif N(p,q)==3linditemp=linditemp+1;elseif N(p,q)==2gengditemp=gengdltemp+1;endendendif linditemp>=gengditempfor p=max(1,j-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if (M(p,q)~=0)&&xr(M(p,q),3)==-1z=1;endendendif z==0caodi=caodi-1;M(i,j)=3;lindi=lindi+1;endendelseif lindishy(i,j)==caodishy(i,j) caoditemp=0;linditemp=0;gengditemp=0;for p=max(i,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if N(p,q)==4caoditemp=caoditemp+1;elseif N(p,q)==3linditemp=linditemp+1;elseif N(p,q)==2gengditemp=gengditemp+1;endendendif linditemp>=max(caoditemp,gengditemp) z=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(M(p,q)~=0)&&xr(M(p,q),3)==-1z=1;endendendif z==0caodi=caodi-1;M(i,j)=3;lindi=lindi+1;endendendelseif M(i,j)==2if lindishy(i,j)>gengdishy(i,j)if lindishy(i,j)>caodishy(i,j)z=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(M(p,q)~=0)&&xr(M(p,q),3)==-1z=1;endendendif z==0M(i,j)=3;Lindi=lindi+1;gengdi=gengdi-1;endelseif lindishy(i,j)==caodishy(i,j) caoditemp=0;linditemp=0;gengditemp=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if N(p,q)==4caoditemp=caoditemp+1;elseif N(p,q)==3linditemp=linditemp+1;elseif N(p,q)==2gengditemp=gengditemp+1;endendendif linditemp>=max(caoditemp,gengditemp) z=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(M(p,q)~=0)&&xr(M(p,q),3)==-1z=1;endendendif z==0M(i,j)=3;lindi=lindi+1;gengdi=gengdi-1endelseif caoditemp>= gengditemp biaoji=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(M(p,q)~=0)&&xr(M(p,q),4)==-1 z=1;endendendif z==0M(i,j)=4;caodi=caodi+1;gengdi=gengdi-1;endendelseif lindishy(i,j)<caodishy(i,j)z=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(M(p,q)~=0)&&xr(M(p,q),4)==-1 z=1;endendendif z==0M(i,j)=4;caodi=caodi+1;gengdi=gengdi-1;endendelseif lindishy(i,j)==gengdishy(i,j) if lindishy(i,j)<caodishy(i,j)z=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(M(p,q)~=0)&&xr(M(p,q),4)==-1 z=1;endendendif biaoji==0M(i,j)=4;caodi=caodi+1;gengdi=gengdi-1;endelseif lindishy(i,j)>caodishy(i,j) caoditemp=0;linditemp=0;gengditemp=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if N(p,q)==4caoditemp=caoditemp+1;elseif N(p,q)==3linditemp=linditemp+1;elseif N(p,q)==2gengditemp=gengditemp+1; endendendif linditemp>= gengditempz=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(M(p,q)~=0)&&xr(M(p,q),3)==-1 z=1;endendendif z==0M(i,j)=3;lindi=lindi+1;gengdi=gengdi-1endendelsecaoditemp=0;linditemp=0;gengditemp=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if N(p,q)==4caoditemp=caoditemp+1;elseif N(p,q)==3linditemp=linditemp+1;elseif N(p,q)==2gengditemp=gengditemp+1;endendendif linditemp>=max(caoditemp,gengditemp) z=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(M(p,q)~=0)&&xr(M(p,q),3)==-1z=1;endendendif z==0M(i,j)=4;lindi=lindi+1;gengdi=gengdi-1endelseif caoditemp>= gengditempz=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(M(p,q)~=0)&&xr(M(p,q),4)==-1z=1;endendendif z==0M(i,j)=4;caodi=caodi+1;gengdi=gengdi-1;endendendelseifgengdishy(i,j)<caodishy(i,j)z=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(M(p,q)~=0)&&xr(M(p,q),4)==-1z=1;endendendif z==0M(i,j)=4;caodi=caodi+1;gengdi=gengdi-1;endelseif gengdishy(i,j)==caodishy(i,j) elseif lindishy(i,j)==caodishy(i,j) caoditemp=0;linditemp=0;gengditemp=0;for p=max(1,i-1):min(i+1,m)for q=max(j-1,1):min(i+1,n)if N(p,q)==4caoditemp=caoditemp+1;elseif N(p,q)==3linditemp=linditemp+1;elseif N(p,q)=2gengditemp=gengditemp+1; endendendif caoditemp>= caoditempz=0;for p=max(1,j-1):min(i+1,m)for q=max(j-1,1):min(j+1,n)if(N(p,q)~=0)&&xr(M(p,q),4)==-1; z=1;endendendif Z==0M(i,j)=4;caodi=caodi+1;gengdi=gengdi-1;endendendendendendendfid=fopen(‘d:\ca\lucc’,’at+’)for i=1:mfor j=1:nif M(i,j)>4.5M(i,j)=N(i,j);endfprintf(fid,’%d’, M(i,j)); endfprintf(fid,,’\n’);endfclose(fid);。

元胞自动机(Cellular Automata)，简称CA，也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。

是一时间和空间都离散的动力系统。

散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。

大量元胞通过简单的相互作用而构成动态系统的演化。

不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。

凡是满足这些规则的模型都可以算作是元胞自动机模型。

因此，元胞自动机是一类模型的总称，或者说是一个方法框架。

其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。

元胞自动机的构建没有固定的数学公式，构成方式繁杂，变种很多，行为复杂。

故其分类难度也较大，自元胞自动机产生以来，对于元胞自动机分类的研究就是元胞自动机的一个重要的研究课题和核心理论，在基于不同的出发点，元胞自动机可有多种分类，其中，最具影响力的当属S. Wolfram在80年代初做的基于动力学行为的元胞自动机分类，而基于维数的元胞自动机分类也是最简单和最常用的划分。

除此之外，在1990年， Howard A.Gutowitz提出了基于元胞自动机行为的马尔科夫概率量测的层次化、参量化的分类体系(Gutowitz, H.A. ,1990)。

下面就上述的前两种分类作进一步的介绍。

同时就几种特殊类型的元胞自动机进行介绍和探讨S. Wolfrarm在详细分忻研究了一维元胞自动机的演化行为，并在大量的计算机实验的基础上，将所有元胞自动机的动力学行为归纳为四大类 (Wolfram. S.，1986):(1)平稳型:自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。

不随时间变化而变化。

(2)周期型:经过一定时间运行后，元胞空间趋于一系列简单的固定结构(Stable Paterns)或周期结构(Perlodical Patterns)。

2、若x(i, j,t) 1,则
x(i,
j,t
1)
2 1
3、若x(i, j,t) 2,则
withPe (i, j,t) with1 Pe (i, j,t)
x(i, j,t 1) 2, gg(i, j,t 1) gg(i, j,t) 1,若gg(i, j,t) Tl
x(i, j,t 1) 3, gg(i, j,t 1) 0,否则
x(i, j) 0, g(i, j,0) 0,否则
对任一( i, j ) ，状态从t到t+1的演化规则
1、若x(i, j,t) 0，则
x(i, j,t 1) 1, g(i, j,t 1) 1, 若P(i, j,t) Pd (i, j,t);
x(i, j,t 1) 0, g(i, j,t 1) 0, 否则
元胞自动机在数学建模 中的应用示例
元胞简介 （Introduction）
什么是元胞（CA）自动机
元胞自动机是离散动力学系统
CA之所以是离散系统，是因为元胞是 定义在有限的时间和空间上的，并且元 胞的状态是有限。
CA被认为是动力学模型，是因为它的 举止行为具有动力学特征
元胞构成（Components）
潜伏期者 x(i, j,t) 1
病发者
x(i, j,t) 2
免疫者
x(i, j,t) 3
本模型采用Von Neumann邻居，即每个元胞的 上下左右四个元胞作为它的邻居，病菌在邻 居间相互传播。
传播规则一
初始化，生成n个潜伏期者
演化过程
1、若x(i, j,t) 0,则
x(i, j,t 1) 1,只要它有一个邻居为病 发者或潜伏者 x(i, j,t 1) 0,否则

元胞⾃自动机今天，我不不讲元胞⾃自动机的概念是什什么，也不不讲元胞⾃自动机的发展，请⾃自⾏行行百度，反正百度和CNKI啊这种⼀一堆，我就讲⼀一个点——“套路路”。

编程的套路路，详解⼀一下这些套路路。

我们举个例例⼦子啊，下⾯面是基于元胞⾃自动机的⽹网路路舆情变化的元胞⾃自动机，⽐比较简单；其他复杂的请⾃自⾏行行更更改运⾏行行条件等各项约束条件，⾃自⾏行行更更改补充，这⾥里里仅就⼊入⻔门讲解⼀一下元胞⾃自动机的编程。

如图1.1，是随意找的⼀一个论⽂文规定的限制条件图1.1我们稍微说⼀一下这个题⽬目要我们做的事情，⾸首先有个概率让它从休眠状态变成激活状态，之后不不停的从1到2,2到3…8到9,9到0。

这⾥里里从1到2，3到4和之后的过程是有个条件的：这个所在的元胞点cells（i,j）四周，也就是上下左右和斜着四个⻆角⼀一共⼋八个点中⾄至少有三个点是被激活的，并且满⾜足激活的概率，让它变化，否则不不动，整个过程是从休眠到激活再休眠的⼀一整个过程。

好了了上⾯面就是简单说⼀一下规则，我们讲⼀一下套路路（YuanBao1.m⽂文件⾥里里的内容）下⾯面讲的适⽤用于⾼高低版本的matlab均能运⾏行行，但是相对的对于颜⾊色的控制就⽐比较单⼀一了了。

clc;clear;上⾯面这段话肯定没什什么好说的，清空咯，别看简单，⽤用的时候有可能很纠结。

plotbutton=uicontrol('style','pushbutton',...'string','Run',...'fontsize',12,...'position',[100,400,50,20],...'callback','run=1;');这⾥里里说的是Run这个按钮，从第⼀一⾏行行开始看：uicontrol说明这是对GUI的控制命令，style类型为pushbutton按钮类型，就是说这是⼀一个按钮的意思，string为Run就说明这个按钮显示的名字是Run，fontsize为12就是说的字体⼤大⼩小为12，position为[1004005020]的意思是从左下⻆角向右100格，再向上400格，建⽴立⻓长为50宽为20的框，最后callback就⽐比较关键了了这就算是这个按钮的回调，这⾥里里写的是run=1;就是告诉你，按了了这个按钮以后run这个变量量赋值为1.erasebutton=uicontrol('style','pushbutton',...'string','Stop',...'fontsize',12,...'position',[200,400,50,20],...'callback','freeze=1;');这⾥里里和前⾯面说的⼤大致相同，不不同点⽆无⾮非是名字变成了了Stop，位置向右多移了了100格，最后回调的内容变成了了freeze=1，告诉我们按了了以后freeze这个变量量赋值为1 quitbutton=uicontrol('style','pushbutton',...'string','Quit',...'fontsize',12,...'position',[300,400,50,20],...'callback','stop=1;close;');这⾥里里说的也差不不太多就是名字变成了了Quit，位置变了了，回调变了了，告诉我们按了了按钮以后stop这个变量量变成1了了，并且关闭这个GUI界⾯面number=uicontrol('style','text',...'string','1',...'fontsize',12,...'position',[20,400,50,20]);这⾥里里稍微产⽣生了了⼀一些变化就是这个控件的类型变成了了text，⽂文本⽂文件，然后初始显示在界⾯面上的样⼦子是1，如果⼤大家需要更更改的话改掉1，那么初始的值就改掉了了，位置也发⽣生了了改变，这都是套路路，先不不说了了。

基于元胞自动机-概述说明以及解释1.引言1.1 概述概述:元胞自动机（Cellular Automaton，CA）是一种模拟分布式系统的计算模型，由数学家约翰·冯·诺伊曼（John von Neumann）和斯坦利斯拉夫·乌拉姆（Stanislaw Ulam）于20世纪40年代末提出。

它被广泛应用于各个领域，如物理学、生物学、社会科学等，并且在计算科学中也具有重要地位。

元胞自动机模型由一系列的离散的、相互联系的简单计算单元组成，这些计算单元分布在一个规则的空间中，每个计算单元被称为细胞。

细胞根据一组规则进行状态转换，通过与其相邻细胞的相互作用来改变自身的状态。

这种相邻细胞之间的相互作用可以通过直接交换信息实现，也可以通过间接地通过规则来实现。

元胞自动机的基本原理是根据细胞的局部状态和相邻细胞的状态来决定细胞下一时刻的状态。

这种局部的状态转换会逐步扩散并影响整个空间，从而产生出复杂的全局行为。

元胞自动机非常适合用于模拟大规模复杂系统中的行为，如群体行为、自组织系统、流体力学等。

元胞自动机的应用领域非常广泛。

在物理学中，它可以用于模拟晶体的生长、相变过程等。

在生物学中，元胞自动机可以模拟细胞的生命周期、生物群体的演化过程等。

在社会科学中，它可以模拟群体行为的形成、传播等。

此外，元胞自动机还被应用于计算科学中，用于解决许多复杂的计算问题，如图像处理、数据挖掘等。

尽管元胞自动机具有许多优势和广泛的应用，但它也存在一些局限性。

首先，由于元胞自动机的状态转换是基于局部规则进行的，因此难以精确地模拟某些复杂系统中的具体行为。

其次，元胞自动机的规模和计算复杂度随着细胞数量的增加而增加，这限制了其在大规模系统中的应用。

此外，元胞自动机模型的抽象性也使得人们难以解释其内部机制及产生的全局行为。

在未来，元胞自动机仍将继续发展。

随着计算能力的提高，我们可以采用更精确的数值方法和更复杂的规则来描述系统的行为。

中国科学 D 辑: 地球科学2007年 第37卷 第6期: 824~834收稿日期: 2006-11-13; 接受日期: 2007-02-13国家杰出青年基金(批准号: 40525002)、国家高技术研究发展计划(编号: 2006AA12Z206)、国家自然科学基金(批准号: 40471105)、教育部博士点基金(批准号: 20040558023)和“985工程”GIS 与遥感的地学应用科技创新平台项目(批准号: 105203200400006)资助 《中国科学》杂志社SCIENCE IN CHINA PRESS利用蚁群智能挖掘地理元胞自动机的转换规则刘小平①黎 夏①* 叶嘉安②何晋强①陶 嘉①(① 中山大学地理科学与规划学院, 广州510275; ② 香港大学城市规划及环境管理研究中心, 香港)摘要 提出了基于蚁群智能算法(Ant Colony Optimization, ACO)的地理元胞自动机(ACO-CA). 元胞自动机(CA)具有模拟和预测复杂的地理现象演变过程的能力. CA 的核心是如何定义转换规则, 但目前的方法所获取的转换规则大都是隐含的, 是通过数学公式来表达. 当研究区域较复杂时, 确定CA 的模型结构和参数有一定困难, 需要使用智能式的方法获取有效的转换规则. 提出了一种基于蚁群智能来自动获取地理元胞自动机转换规则的新方法. 该方法所提取的转换规则毋需通过数学公式来表达, 能更方便和准确地描述自然界中的复杂关系, 并且这些规则比数学公式更容易让人理解. 将ACO-CA 应用于广州市的城市模拟实验中, 取得了较好的结果. 并 与See5.0决策树模型进行了对比研究, 对比实验结果表明: 蚁群智能算法在提取CA 转换规则时比See5.0 模型更具有优势.关键词 蚁群算法 元胞自动机 地理模拟 人工智能 元胞自动机(CA)是由Ulam 在20世纪40年代提出, 具有模拟复杂系统时空演化过程的能力. CA 的一个重要特点是复杂系统可以由一些简单的局部规则来产生. 它这种“自下而上”的研究思路充分体现了复杂系统局部个体行为产生全局、有秩序模式的理念, 非常适用于复杂地理过程的模拟和预测. Couceleis [1~3]在20世纪80年代未详细阐述了CA 在地学应用的理论框架, 尤其是模拟城市扩张的实验为将来的城市动态演化研究产生了较为深远的影响. 此后, 许多学者在不断扩展标准CA 的基础上, 深入研究了利用CA 模拟城市扩张[4~9]、土地利用动态演变[10]、山火蔓延[11]、动物群种的动态变化[2]、荒漠演化[12]等.转换规则的定义是CA 模型的核心. 它表述模拟过程的逻辑关系, 决定空间变化的结果. 目前, 定义CA 转换规则的方法存在一定的缺陷. Clarke 等[7]提出了利用肉眼判断的方法来获取模型参数值. 该方法受主观因素影响很大, 可靠程度有限, 当空间变量较多时, 有非常多的参数值组合方案; Wu [9]曾提出利用层次分析法(AHP)来确定模型参数值, 后来, Wu [13]又提出使用线性logistic 回归的方法来提取转换规则, 这类方法非常简单实用, 从而得到了较为广泛的应用. 但是, 用线性的方法提取复杂的地理现象规律, 显得过于简单; Li 和Yeh [14]提出了利用神经网络训练的方法自动获取转换规则, 不足的是, 神经网络存在过学习, 局部最小值和收敛速度慢的问题, 属于黑箱结构; 黎夏等[15]随后又提出了利用See5.0决策树的方法来获取CA 的参数值, 但See5.0容易陷入局部最优; 刘小平和黎夏[16]提出了利用核学习机在高维特征空间中提取CA 非线性转换规则的方法, 该方法也存在转换规则物理意义不清晰和运行量大的问题.另外, 当研究区域较复杂时, 目前的方法在确定第6期刘小平等: 利用蚁群智能挖掘地理元胞自动机的转换规则825CA模型结构和参数时有一定困难, 有必要引进智能式的方法来有效地获取转换规则. 蚁群智能将是进行CA转换规则知识挖掘的有效方法. 蚁群智能算法是一种源于大自然中生物世界的仿生类人工智能算法, 最初由Colorni和Dorigo等于1991年提出[17], 其本质是一个复杂的多智能体系统, 由大量的简单智能体——蚂蚁(ants)所组成的团体, 通过相互合作能够有效地完成复杂任务, 例如寻找食物的最优路径. 每个蚂蚁智能体根据路径上的信息作随机选择, 系统无中心控制, 但最终整个蚁群能够得到优化. 这样的系统更具有鲁棒性(Robust), 不会由于一个或者某几个智能个体的故障而影响整个问题的求解, 该算法是群集智能的典型实现. 蚁群算法具有很强的自学习能力, 可根据环境的改变和过去的行为结果对自身的知识库进行更新, 从而实现算法求解能力的进化. 由于蚁群智能算法具有较强的鲁棒性、自适应性、正反馈、优良的分布式计算机制、易于与其他方法结合等优点[18,19], 如今已经成为人工智能领域的一个研究热点, 但在地学方面的应用则鲜见报道. 实际上, 蚁群智能算法这种简单的智能个体通过合作能完成复杂任务是一种“自下而上”的研究思路, 这与元胞自动机的思想不谋而合, 因此, 蚁群智能算法用来提取CA转换规则是非常适合的.本文提出了利用基于蚁群智能的分类规则挖掘算法(Ant-Miner)来自动挖掘CA的转换规则, 该算法模仿蚂蚁寻找食物的方式来构造转换规则. 将基于蚁群智能算法的地理元胞自动机应用于广州市的城市模拟实验中, 取得了较好的结果. 并与See5.0方法进行了对比, 对比实验结果表明: 蚁群智能算法在提取CA转换规则时比See5.0 更具有优势. 目前, 还没有应用蚁群智能来自动获取CA转换规则的研究报道.1 基于蚁群智能算法的地理元胞自动机1.1 蚁群算法的基本原理人工蚁群算法是受到蚂蚁觅食过程中路径选择行为的启发而提出的[18]. 蚂蚁在寻找食物源时, 能在其走过的路径上释放一种蚂蚁特有的分泌物——信息素(pheromone), 该激素随着时间的延续不断挥发. 蚂蚁在运动过程中能够感知信息素的存在及其强度, 并以此指导自己的运动方向. 蚂蚁倾向于朝着信息素强度高的方向移动, 因此, 由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象. 当一些路径上通过的蚂蚁越来越多时, 其留下的信息素轨迹也越来越多, 导致信息素强度增大, 其他蚂蚁选择该路径的概率也越高. 蚂蚁个体之间就是通过这种间接的通信机制达到协同搜索蚁巢到食物源的最短路径的目的. 蚂蚁算法的这种正反馈的迭代思想体现了其自适应特性. 图1是蚁群觅食的过程图, 能更具体、更形象地说明蚁群算法的群集智能原理.蚂蚁在觅食过程中通过相互协作能找到蚁巢到食物源的最短路径, 在没有障碍物的情况下, 所形成的最短路径近乎一条直线, 如图1(a)所示. 蚂蚁群体不仅可以完成复杂的任务, 而且能适应环境的变化, 如在蚁群运动路线上突然出现障碍物时, 刚开始蚂蚁按同等概率选择各条路径, 如图1(b)所示. 在运动过程中, 蚂蚁在其经过的路径上留下信息素, 由于路径F-G-H比路径F-O-H要短, 选择路径F-G-H的蚂蚁要比选择路径F-O-H的蚂蚁先达到食物源. 对每只蚂蚁来讲, 相同时间内释放的信息素量是相同的, 因图1 蚁群觅食过程图826中国科学D辑地球科学第37卷此, 路径H-G-F的信息素浓度比路径的信息素浓度H-O-F要大, 从而使得选择路径H-G-F的蚂蚁增多, 如图1(c)所示. 由于信息素的挥发, 较长路径上的信息素逐渐消失, 如此反复循环, 最终, 所有的蚂蚁都沿着最短路径行进, 见图1(d).蚂蚁觅食过程中选择最优路径的现象表现为一种正反馈过程, 这一过程应用于优化领域便产生了人工蚁群智能算法[18]. 因此, 蚁群算法是对真实蚂蚁觅食行为的一种抽象和模拟.1.2 蚁群智能算法与地理元胞自动机蚁群算法在TSP问题求解、分配问题、数据聚类、组合优化、网络路由等方面取得了系列较好的成果[20~22], 但其在分类规则挖掘方面的研究还刚刚起步. 基于蚁群算法的规则挖掘最初由巴西学者Parpinelli等[23]于2002年提出, 主要是利用蚁群觅食原理在数据库中搜索最优规则. 定义蚁群搜索路径为属性节点和类节点的连线, 其中属性节点最多只出现一次且必须有类结点. 如图2所示, 每条路径对应一条分类规则, 分类规则的挖掘可以当作是对最优路径的搜索. 刚开始时, 随机产生一条规则, 规则形式如下:IF <term1 AND term2 AND……> THEN <class> (1) 式中, term i为条件项, 条件项组合用<特征属性, 操作符, 特征值>表示, 规则结论(THEN部分)则定义了样本的预测类别(class). 值得注意的是: 当特征值为连续值时, 需要对数据进行离散化处理. 例如, 记某一数据库的属性为A1, A2, …, A n, 其属性特征值为V1, V2, …, V n对特征值进行离散化处理后, 特征值记为V11, V12, …, V21, V22, …, V n1, V n2, …, V ij可表示为term ij(属性节点).图2 Ant-Miner算法中分类规则对应的路径基于蚁群原理的分类规则挖掘分为3个阶段. 首先从一条空路径开始重复选择路径节点增加到路径上, 直到得到一条完整路径, 即规则构造; 然后对规则进行剪枝; 最后更新所有路径上的外激素浓度, 对下一只蚂蚁构造规则施加影响.1.2.1 规则构造规则的构造模仿了蚂蚁的觅食行为. 实际上是一个属性节点的选择过程, 首先从第一个属性中的所有节点中按照一定的标准选择一个节点, 就是在图2中的属性1中的节点选择其中的一个, 而后从第二个属性的所有节点中选择一个节点, 以此类推, 直到所有的属性都被蚂蚁走过, 也就是蚂蚁在所有的属性中都选择了一个节点. 在这些属性中, 类别属性作为一类特殊的属性也与其他属性一样, 蚂蚁会在所有的类别中选择其中的一个类别. 这样, 一条规则就产生了.理论上节点的选择可以是完全随机的, 但这可能需要漫长的计算时间作为代价. 在本文中, 蚂蚁属性节点的选择标准由两方面的因素决定: 其一由于蚂蚁算法正反馈机制的存在, 蚂蚁在选择属性的节点时, 会根据前面蚂蚁所留下的信息素来做出判断; 其二, 为了使蚂蚁更快的选择较好的节点, 并加快收敛速度, 通常可以设计一个与问题相关的启发式函数, 相当于给人工蚂蚁安上一双“眼睛”, 从而引导蚁群的搜索, 缩短收敛时间.Parpinell等[23]采用基于信息熵的方法来构造启发式函数, 每个属性节点的启发式函数值与其分类样例的能力成正比. 我们根据数据的统计特征(频数)来构造启发式函数, 定义条件项term ij的启发式函数值ηij为[22]12max(,,,),kij ij ijn n nijijnfreqT freqT freqTTη=∑∑∑∑L(2)式中,ijη表示条件项term ij基于密度的启发式函数值, T ij为满足件项term ij的实例数, w ijfreqT为T ij中类别为w的频数. 在数据挖掘过程中, 每得到一条最终规则后, 要移除符合规则条件部分的记录, 因而,12max(,,,)kij ij ijn n nfreqT freqT freqT∑∑∑L和ijnT∑在得到一条最终规则后其值会发生变化, 需要对其进行第6期刘小平等: 利用蚁群智能挖掘地理元胞自动机的转换规则 827动态更新.当蚂蚁开始构造路径时, 所有路径节点的信息素浓度被初始化为相同的值11(0),ij a i i t b τ===∑ (3)式中, τij 为条件项term ij 的信息素浓度, a 为数据库中属性(不包括类属性)总数, b i 为属性i 所有可能取值的数据.赌轮机制用来选择属性节点. 对每个属性列来说, 其所属节点term ij 被选择的概率按下式进行计算:11()()().()()iij ij ij b a ij ij i j t t P t t t τητη==⋅=⋅∑∑ (4)选择出的属性节点被加入到路径中去. 直到所有属性(包括类属性)都被选入到路径中去, 至此, 一条完整的路径已产生, 即一条分类规则.1.2.2 规则修剪根据属性节点的选择标准, 在每个属性中选择一个节点后得到一条最原始的规则. 规则的有效性通过下面的公式进行计算TruePos TrueNeg ,TruePos FalseNeg FalsePos TrueNeg Q ⎛⎞⎛⎞=⋅⎜⎟⎜⎟++⎝⎠⎝⎠(5)式中, TruePos 表示满足规则条件, 并且和规则预测类型相同的样例数; FalsePos 表示满足规则条件, 并且和规则预测类型不同的样例数; FalseNeg 表示不满足规则条件, 并且和规则预测类型相同的样例数; TrueNeg 表示不满足规则条件, 并且和规则预测类型不同的样例数.由于产生分类规则时, 每个属性节点都被选作为规则的一个条件项, 这样得到的规则其条件项较多, 难于理解; 此外, 有些属性对于某些类别的分类结果贡献不大, 甚至会有负面影响, 因而需要对其进行修剪; 更为重要的是: 路径节点的重复选择可能会带来分类规则对样例的过度拟合. 因此通过删除任何能导致规则精度提高或简化的属性节点来修剪规则是很有必要的, 修剪后的规则才是相应的人工蚂蚁寻找到的最优规则. 一种简单的修剪方法就是依次移去能使规则有效性得到最大提高的属性节点, 即移除多余的属性节点, 直到任一属性节点的移除都会降低规则的有效性. 规则修剪的伪代码如下:No_of_terms=No_of_attributes-1; /*条件项和属性数个数*/validity_newrule=1 While(validity_newrule>validity_previousrule) /*修剪前后修剪后规则的有效性*/ validity_newrule=validity_previousrule;For j = 1 to No_of_termsRemove term j from the rule /*从规则中移去条件项term j */Calculate the validity_newrule j /*计算移去条件项后所得新规则的有效性*/If (validity_newrule<validity_newrule j ) then/*如果规则有效性提高*/ validity_newrule= validity_newrule j/*移去条件项j 后规则的有效性*/ obtaining a better rule/*获得一条更好的规则*/End ifNext jNo_of_terms = No_of_terms -1 /*如果有效性得到提高, 则条件项数减少1项*/LoopObtaining a pruned rule/*获得一条修剪后的规则*/1.2.3 信息素浓度更新人工蚂蚁在属性节点选择过程中的正反馈机制是通过改变属性节点上的信息素浓度来实现的. 当一次迭代中的人工蚂蚁构造的规则经过修剪得到分类规则后, 所有路径节点的信息素浓度都将依据这种分类规则的效率进行更新. 规则中被包含的路径节点的信息素浓度将增加, 信息素浓度量增加的多少与规则的有效性成正相关, 即规则的有效性越好, 信息素浓度增加的量越大; 而没有被包含的路径节点的信息素浓度将减小(引入挥发系数ρ). 属性节点的信息素浓度更新公式如下: (1)(1)()(),ij ij ij t t t τρττ+=−⋅+∆ (6)()(),kij ij kt t ττ∆=∆∑ (7)()kijt τ∆=其中ρk k828中国科学 D 辑 地球科学第37卷图3 基于蚁群智能的地理元胞自动机模型只人工蚂蚁找到的分类规则的质量, ()kij t τ∆为第k 只人工蚂蚁在本次迭代中留在节点term ij 上的信息量, 所有属性节点的信息素尝试被更新. 确定一条最终规则的条件是: 当连续若干蚂蚁搜索到同一路径时, 就认为搜索收敛, 找到的规则进行修剪后成为一条最终规则; 或者当迭代的次数达到指定的次数时, 选择所有迭代过程中蚂蚁找到的规则中质量最好的规则作为最终规则. 在迭代过程中, 规则当中质量较好的规则, 由于其信息素浓度逐渐增强, 从而能够得以保留, 并被视为最终分类规则. 其他质量较差的规则被丢弃.1.2.4 基于蚁群智能的地理元胞自动机蚁群算法具有很强的自学习能力, 能够根据环境的改变和过去的行为结果对自身的知识库进行更新, 从而实现算法求解能力的进化, 因此, 蚁群智能可以有效的解决非线性问题, 特别适合于地理复杂现象. 此外, 蚁群算法“自下而上”的研究思路与元胞自动机的思想不谋而合, 用来提取CA 转换规则是非常适合的. 本文将基于蚁群智能的分类规则挖掘算法(Ant-Miner)应用于城市元胞自动机中, 自动从训练数据中获取CA 转换规则, 并同时完成模型的纠正过程. 图3为基于蚁群智能的地理元胞自动机模型结构图.ACO-CA 模型主要由两部分组成: 规则提取和城市发展模拟. 利用两年的遥感数据监测城市的增长, 转换规则主要是从这两年的遥感图像上通过Ant-Miner 算法挖掘出来的. Ant-Miner 算法是通过Visual Basic 6.0编程实现的. Ant-Miner 算法的伪代码如下:The original trainingSet /*原始数据集*/ Discretization of the original TrainingSet /*离散化数据集*/While(TrainingSet > Max_uncovered_cases)t = 1 /*迭代次数Initialize all nodes with the same amount ofpheromone/*初始化节点的信息素*/calculation the ηij of the training data for allnodes /*计算节点的启发函数值*/While(T<No_of_iteration and m<No_rules_converg) /*当t 小于指定的迭代次数或者m 小于测试蚂蚁收敛的规则数目*/For i =1 to No_of_ants /*蚂蚁数*/ For j =1 to No_of_attributes /*属性数*/Select a node of the attribute /*选择节点*/Next jIf (Rule i is equal to Rule i −1 then /*如果两者规则收敛, 则m 加1*/m = m +1第6期刘小平等: 利用蚁群智能挖掘地理元胞自动机的转换规则829elsem = 1end ifNext irules pruning/*规则修剪*/pheromone update/*信息素更新*/t = t +1LoopSelect the best rule R best among all rules con-structed by all the ants; /*选择最好的一条规则作为最终规则*/Add rule R best to DiscoveredRuleList /*把规则加到规则列表中*/TrainingSet = TrainingSet-{set of cases covered by R best }/* 从训练样本中移除规则所覆盖的样例*/ LoopAnt-Miner挖掘的转换规则与以往基于方程的CA转换规则有所区别, 基于方程的转换规则采用数学方程来隐含地表达转换规则, 而Ant-Miner却能获取明确的转换规则, 例如:规则1:假如离市中心距离<8 km, 离主干道路<0.5 km, 邻域城市用地的元胞数目>5,土地利用类型为农田.则该中心元胞转化为城市用地 (置信度=0.98).规则2:假如离市中心距离>50 km, 邻域城市用地的元胞数目<2,土地利用类型为林地则禁止土地的开发(置信度=0.90).模拟部分则是在Visual Basic 6.0环境下对ArcObjects进行二次开发所实现的, 模拟时需要动态计算中心元胞邻域的变化, ArcGIS的Focal函数可以很容易地计算中心元胞邻域中已城市化的元胞数目. 在进行规则获取和模拟时, 值得注意的是: 遥感图像的观测时间往往比CA模拟的迭代间隔大很多. 而实际上, 只有获取规则的遥感图像时间间隔(∆T)和迭代间隔(∆t)完全一致时, 获取的转换规则才能直接使用[15]. 为此, 需要控制CA在∆t间隔内的城市用地的转变量. 首先, 确定CA模型在模拟时间段内的迭代次数K:,K T t=∆ (9) 其次, 从遥感图像确定观测间隔T∆内城市用地的转变量,Q∆由于∆T>∆t, 在CA的每次迭代过程中, 只有一部分土地的状态发生了变化. 因此, CA在∆t间隔内的城市用地的转变量为00/.q Q K∆=∆ (10) 在每次迭代过程中, 采用全局约束性条件控制CA在∆t间隔内的城市用地的转变量.2模型应用及结果2.1 实验区及空间数据本模型选择广州市作为试验区, 首先利用1988年、1993年2002年的TM卫星遥感图像自动分类, 提取模型所需要的训练数据. 城市发展的概率往往取决于一系列的空间距离变量、邻近现有城市用地的数量和元胞的自然属性等[4,24]. 本文结合研究区的实际情况, 选取以下空间变量(表1), 各空间变量的值从广州市交通地图和遥感分类图中获取.从分类数据中选择训练数据, 本文采用随机分层取样的方法, 从转换为城市用地的元胞中及尚未转换为城市用地的元胞中随机选择3500个样点, 获取这些样点的空间坐标, 再运用ARC/INFO 的Sample功能分层读取对应所需的空间变量. 只以1988年和1993年的数据来获取转换规则, 其他时相的数据用来获取城市增长的动态增量.2.2 转换规则挖掘及城市模拟在运用Ant-Miner挖掘CA转换规则时, 各空间变量作为蚂蚁路径的属性节点, 元胞是否转化为城市用地作为蚂蚁路径的类节点, 转化为城市用地则标记为1, 没有转化为城市用地则标记为0. 在进行表1 Ant-Miner挖掘转换规则所需的空间变量空间距离变量局部变量离市中心的距离离镇中心的距离离国道、省道的距离离一般道的距离离铁路的距离离高速公路的距离3×3邻域内城市单元数元胞约束条件ProD TownD RoadD LaneD RailD ExprD Ω Con830中国科学D辑地球科学第37卷表2 Ant-Miner所挖掘的部分转换规则规则1:IFLaneD<=23 and ExprD<=25 and 181<TownD<=206 and landuse=‘cropland’ and Ω > = 3Thenclass=1 (置信度=0.92)规则2:IFRoadD<=47 and LaneD<=23 and 23<ExprD<=102 and 153<RailD<=179 and TownD<255 and landuse= ’orchard’ and Ω > =4 Thenclass=1 (置信度=0.86)规则3:IF413<PropD<=450 and 115<LaneD<=138 and RailD >230 TownD>235 and Ω < 2 thenclass=0 (置信度=0.83)……规则挖掘前, 首先需要对具有连续值的空间变量进行离散化处理. 每条路径对应一条分类规则, 分类规则的挖掘可以当作是蚂蚁对最优路径的搜索. 采用Visual Basic 6.0编程实现算法. 利用Ant-Miner, 对所获得的GIS和遥感数据进行数据挖掘, 自动获取城市演变的转换规则. 表2列出了所获得的部分转换规则.为了验证Ant-Miner模型的可靠性, 我们对Ant-Miner所挖掘的转换规则进行了精度检验(表3). 其中,转化为城市用地的精度为74.6%, 未转化为城市用地的精度为79.3%, 总精度达到77.2%, 对于复杂的地理数据来说, 这已经满足了其精度要求. 为了进一步验证Ant-Miner模型, 我们用See5.0决策树模型与其进行了对比研究, 这是因为See5.0模型所挖掘出来的规则形式跟Ant-Miner所挖掘出来的规则形式相差不大, 更具有对比意义. 对比实验结果(表3)表明:Ant-Miner模型的总精度要比See5.0模型的总精度高出将近5个百分点, 这说明了Ant-Miner模型的可靠性较好, 比较适合复杂地理数据的知识挖掘.表3 Ant-Miner模型与See5.0决策树模型的精度对比模型转化为城市用地的精度/%未转化为城市用地的精度/%总精度/%Ant-Miner 74.6 79.3 77.2 See5.0 68.7 76.1 72.3根据Ant-Miner所挖掘的转换规则, 分别模拟了1988~1993年、1993~2002年期间广州城市空间演变情况. 城市空间演变的模拟最终是通过ArcGIS的二次开发工具ArcObject在Vsiual Basic 6.0开发环境下编程实现的. 模拟时, 初始状态为1988年TM影像分类所获取的城市用地, 模型进行200次迭代运算后, 获得模拟的1993年广州市城市用地, 运行400次后得到模拟的2002年广州市城市用地(图4).3模型验证与对比将CA应用于模拟真实的城市时, 需要检验其与实际情况的吻合程度. 一种简单的检验方法是用肉眼对模拟结果与真实城市发展情况进行对比. 图4是广州模拟城市用地和实际城市用地的对比图. 从对比图中可以发现, 模拟结果的整体空间布局与实际情况相当接近.肉眼观察对比为模型的精度提供了一个粗略的验证方法. 为了能够定量地表示模型的精度, 通常将模拟的结果和实际发展情况叠加, 然后逐点对比, 并计算其精度, 产生一个混淆矩阵. 表4列出了ACO-CA模型的逐点对比精度, 1993年和2002年模拟的总精度分别为83.3%和76.8%, 其Kappa系数分别是0.64和0.53.为了检验ACO-CA在模拟城市整体结构方面的能力, 我们计算了模拟结果和实际情况的Moran Ⅰ指数. MoranⅠ指数一般用来描述空间的自相关性, 但该指数也反映了空间集中和分散的程度, 可以用来检验模型模拟的整体空间格局是否与实际的整体空间格局相符. 从表5可知, 1993年模拟结果的Moran Ⅰ指数值为0.627, 实际情况的Moran Ⅰ指数值为0.626. 2002年模拟结果的Moran I 指数值为0.687, 实际情况的Moran Ⅰ指数值为0.684. 模拟结果和实际情况的Moran Ⅰ指数值非常接近, 这表明模拟结第6期刘小平等: 利用蚁群智能挖掘地理元胞自动机的转换规则 831图4 广州城市用地模拟结果和实际情况对比图(a) 1998(初始); (b) 1998(实际); (c) 1993(模拟); (d) 1993(实际); (e) 2002(模拟); (f) 2002(实际)表4 ACO-CA 模型模拟的精度1988~1993 (元胞数)模拟非城市用地 模拟城市用地精度/%实际非城市用地 107347 16618 86.6 实际城市用地 16150 55821 77.6 总精度 83.3 Kappa 系数0.641988~2002 (元胞数)模拟非城市用地 模拟城市用地精度/%实际非城市用地 76815 23293 76.7 实际城市用地 22253 73575 76.8 总精度 76.8 Kappa 系数0.53果的整体空间格局和实际情况的整体空间格局较为相近.表5 Moran Ⅰ指数对比时间 1988年 1993年 2002年实际 0.633 0.626 0.684 模拟(ACO) 0.633 0.627 0.686 模拟(See5.0)0.633 0.621 0.680为了更进一步检验模型, 对比了蚁群方法和其他两种方法(See5.0决策树模型和核学习机)的改善.在对比中, 先利用See5.0决策树模型获取的转换规则模拟了本研究区城市的扩张过程,并计算了模拟结果的逐点对比精度和Moran I 指数(表5, 6), 1993年和2002年模拟的总精度分别为81.5%和73.2%, 其Kappa 系数分别只有0.60和0.46. 对比表4~6可知,基于蚁群智能的CA 模型比基于See5.0决策树的CA。

• 用CA演示了机器 能够模拟自身的现 象；
20世纪 8、9 对CA的发展起 了极大的推动作 用，提出CA的五 个基本特征； •生命游戏；
20世 纪90 年代
• 对各种复杂现 象进行模拟
• 模型进一步发 展
现在
•
2015-1-16
– S. Wolfram的研究(1984, Nature) ，发现了110规则，对元 胞自动机理论作出了巨大贡献。
研究背景
城市模型发展阶段
静态的、均衡的、宏观模型（20世纪50，60年代）
城市增长动态模型分类
动态的、微观模型（20世纪 80年代以后）
宏观系统动力学模型：着眼于宏观变量相互关系 微观系统动力学模型：宏观现象的微观作用机制 Cellar Automata Based Model Multi-Agent Based Model
，移动了一百多英里的鼠标，作了上万页的笔记，产生的研究结 果占了10G的硬盘空间，编制了近一百万行的“数学”软件命令 ，运行了一千万亿次的电脑运算。最后形成了一本1200多页、5 磅重的大部头。 《一种新科学》
《一种新科学》
•从“完全打破现有的学术体系，按照完全不同的原理来 •
理解自然界”的意义出发，新作被命名为《一种新科学 》。 《一种新科学》以如下惊人之言开始它的鸿篇巨制：“ 三个世纪以前，人们发现建立在数学方程基础上的规律 能够用于对自然界的描述，伴随着这种新观念，科学发 生了转变。在此书中我的目的是将要用简单的电脑程序 来表达更为一般类型的规律，并在此种规律基础上建立 一种新的科学，从而启动另一场科学变革。”
元胞自动机及其在城市模拟中的应用
2015-1-16
1
元胞自动机及其在城市模拟中的应用
内容如下：

function []=testCA(n)z = zeros(n,n);cells = z;cells(n/2,.25*n:.75*n) = 1;cells(.25*n:.75*n,n/2) = 1;imh = image(cat(3,cells,z,z));set(imh, 'erasemode', 'none')axis equalaxis tight%Ö÷º¯Êý²ÎÊýnx=52; %must be divisible by 4ny=100;Pbridge = .05;z=zeros(nx,ny);o=ones(nx,ny);sand = z;sandNew = z;gnd = z ;gnd(1:nx,ny-3)=1 ;% the ground linegnd(nx/4:nx/2+4,ny-15)=1; %the hole linegnd(nx/2+6:nx,ny-15)=1; %the hole linegnd(nx/4, ny-15:ny) = 1; %side linegnd(3*nx/4, 1:ny) = 1 ;%Ö÷º¯Êýfor i=1:1000p=mod(i,2); %margolis neighborhoodsand(nx/2,ny/2) = 1; %add a grain at the top%upper left cell updatexind = [1+p:2:nx-2+p];yind = [1+p:2:ny-2+p];%randomize the flow -- 10% of the timevary = rand(nx,ny)< .9 ;vary1 = 1-vary;sandNew(xind,yind) = ...gnd(xind,yind).*sand(xind,yind) + ...(1-gnd(xind,yind)).*sand(xind,yind).*sand(xind,yind+1) .* ...(sand(xind+1,yind+1)+(1-sand(xind+1,yind+1)).*sand(xind+1,yind)); sandNew(xind+1,yind) = ...gnd(xind+1,yind).*sand(xind+1,yind) + ...(1-gnd(xind+1,yind)).*sand(xind+1,yind).*sand(xind+1,yind+1) .* ...(sand(xind,yind+1)+(1-sand(xind,yind+1)).*sand(xind,yind)); sandNew(xind,yind+1) = ...sand(xind,yind+1) + ...(1-sand(xind,yind+1)) .* ...( sand(xind,yind).*(1-gnd(xind,yind)) + ...(1-sand(xind,yind)).*sand(xind+1,yind).*(1-gnd(xind+1,yind)).*sand(xind+1,yind+1));sandNew(xind+1,yind+1) = ...sand(xind+1,yind+1) + ...(1-sand(xind+1,yind+1)) .* ...( sand(xind+1,yind).*(1-gnd(xind+1,yind)) + ...(1-sand(xind+1,yind)).*sand(xind,yind).*(1-gnd(xind,yind)).*sand(xind,y ind+1));%scramble the sites to make it look bettertemp1 = sandNew(xind,yind+1).*vary(xind,yind+1) + ...sandNew(xind+1,yind+1).*vary1(xind,yind+1);temp2 = sandNew(xind+1,yind+1).*vary(xind,yind+1) + ...sandNew(xind,yind+1).*vary1(xind,yind+1);sandNew(xind,yind+1) = temp1;sandNew(xind+1,yind+1) = temp2;sand=sandNew;set(imh,'cdata',cat(3,z',sand',gnd'))drawnowend%build the GUI%define the plot buttonplotbutton=uicontrol('style','pushbutton','string','Run','fontsize',12, 'position',[100,400,50,20], 'callback', 'run=1;');%define the stop buttonerasebutton=uicontrol('style','pushbutton','string','Stop','fontsize',12,'position',[200,400,50,20],'callback','freeze=1;');%define the Quit buttonquitbutton=uicontrol('style','pushbutton','string','Quit','fontsize',12 ,'position',[300,400,50,20],'callback','stop=1;close;');number = uicontrol('style','text', 'string','1', 'fontsize',12,'position',[20,400,50,20]);stop= 0; %wait for a quit button pushrun = 0; %wait for a drawfreeze = 0; %wait for a freezewhile (stop==0)if (run==1)%nearest neighbor sumsum(x,y) = cells(x,y-1) + cells(x,y+1) +cells(x-1, y) + cells(x+1,y)+cells(x-1,y-1) + cells(x-1,y+1) + cells(3:n,y-1) + cells(x+1,y+1);% The CA rulecells = (sum==3) | (sum==2 & cells);%draw the new imageset(imh, 'cdata', cat(3,cells,z,z) )%update the step number diaplaystepnumber = 1 + str2num(get(number,'string'));set(number,'string',num2str(stepnumber))endif (freeze==1)run = 0;freeze = 0;enddrawnow %need this in the loop for controls to workend。

数学建模中，元胞自动机（Cellular Automaton，简称CA）是一种离散空间、离散
时间的数学模型。

它由一系列简单的元胞（cells）组成，每个元胞都有一些状态，
并且根据一组规则，这些状态在离散时间步上进行演化。

以下是一个简单的元胞自动机的 Python 代码示例。

在这个例子中，我们使用一维
元胞自动机，并采用最简单的规则——元胞的状态由其自身和相邻元胞的状态决定。

在这个例子中，apply_rule函数用于应用规则，generate_ca函数生成元胞自动机的演
化过程，而plot_ca函数用于绘制演化过程。

你可以通过调整rule_number、size和steps参数来尝试不同的规则、大小和演化步数，观察元胞自动机的不同演化过程。

这只是一个简单的例子，元胞自动机的规则和特性非常丰富，可以根据具体需求进行更复杂的定制。

数学建模讲座：元胞自动机aqua2001数学中国超级版主September4,2010大家好，我是数学中国超级版主aqua2001。

我们这次做元胞自动机的讲座。

元胞自动机是一个在数学建模中有用的工具。

在这里，我们打算通过一些模型，来初步介绍元胞自动机的应用。

使用计算机进行模拟往往在建模过程中有很大的用途，但凭空说“模拟真实世界”往往让人觉得难以下手。

而元胞自动机则往往能给模拟方法提供一个容易思考的框架。

考虑到大家在建模中的实用性，所以在介绍当中，我会尽量多做直观的介绍，尽量避免数学计算。

详细的数学内容大家可以参照相关书籍。

讲解中有一些图片或说法来源于书籍或网络。

我们在讲解当中，除了一些直接用到元胞自动机的模型，也介绍了在元胞自动机的发展过程当中一些比较有影响力的内容。

它们不一定对建模有直接的用途，但我希望大家对它的了解能够更广泛一些，这样可能对它进行更灵活地运用。

元胞自动机（Cellular Automata或Cellular Automaton,CA）是空间和时间都离散，物理参量只取有限数值集的物理系统的理想化模型。

它的提出，最早是冯•诺依曼在研究能够自我复制的自动机时提出来的。

其特点是，空间被分成离散的格子（可以是方形、三角形或六边形等），称之为元胞（Cell）。

元胞处于若干可能的状态之一，而且随着时间，其状态可以演化。

每个元胞状态的演化，往往要受到临近元胞的状态的影响。

而且，在传统的元胞自动机中，每个元胞的变化都是同时进行的。

最著名的元胞自动机的例子，应属Conway提出的“生命游戏”。

它的提出并不是为了具体的应用，但其蕴含的丰富内容引起了许多人的兴趣。

假设二维空间被划分成方形的格子，当然每个格子都是一个元胞。

假设每个元胞只处于两种状态之一：死的与活的。

死的可以记为0，活的可以记为1。

现在我们来考察每个元胞周围的“邻居”。

“邻居”的定义当然并不唯一，1Figure1:标准邻居Figure2:死亡，存活和重生的规则有时考虑的是它的上下左右的邻居（如果是三维空间，则还有前后），这被称为“冯•诺依曼邻居”；有时考虑的是包围在它周围的全部邻居，被称为Moore 邻居。