元胞自动机仿真与实现.docx

1、元胞自动机仿真与实现第一章 绪 论1.1 元胞自动机的历史进程元胞自动机(Cellular Automata，简称 CA)，亦被称为细胞自动机，它起源于Von.Neumann和A.Turing的数值计算，乃至更早一些的时期。计算机鼻祖Von Neumann等人给出了元胞自动机的基本概念和初等模型，在美国计算机科学家S.Wolfram 写的A New Kind of Science 书中，把元胞自动机提升到了一个新的科学层面。这使得一种用于复杂系统的计算模拟的新理论依据和实现方法得以提出，所以，这个领域的科研又一次成为了人们研究的热门。到了上个世纪70年代，由于计算机的飞速发展，剑桥的数学家J.

2、H.Conway2编写了 “生命游戏”（Game of life）这一十分典型的元胞自动机。Game of life的基本原理是制定一个简单的规则，在这种规则下，通过元胞在空间网格中运行和演化，使得元胞的状态在生与死之间进行改变，最后的可以得出复杂的图形。这种自动机可以对一些复杂现象进行模拟，例如在生命进程中的生存、竞争、灭绝等一些复杂的过程。J.H.Conway还论证出，这个自动机有着和通用图灵机类似的的计算力，且等价于图灵机，这就意味着，当在合适的初始条件下，我们可以用这种元胞自动机模拟任意的计算机。到了80年代，S.Wolfram3等人对元胞自动机的进一步研究使得CA理论产生的质变。他对

3、CA进行的动力学角度处理，而且把计算理论用在研究之中。它的研究理论结果得出，看似很简单的系统亦会得到十分复杂的结构，这从而也证明了出了CA方法理论可作很多理论的基础这一观点，这使元胞自动机变成了一个可以在动态演化方向进行探究的非常实用的工具，从此对元胞自动机的理论探索渐渐的快速发展开来。80年代末，伴随着一些诸如混沌、分形、计算机图形学和复杂性理论等一些有关学科的兴起，CA理论逐渐快速的变成了非线性前沿科学的一个非常重要分支学科，而且它也慢慢的以一种非常实用的应用技术，逐渐的向其它学科之间进行交叉渗透。1.2 元胞自动机的应用元胞自动机从被研发出来的那一天起，它就被人们广泛地应用在了与人活动息

4、息相关的诸多领域，例如，经济方面、社会方面、科学方面以及军事研究方面。这其中用到的学科有社会科学、生态科学、生物科学、计算机科学、信息科学、数学、物理学、化学、环境科学、地理、军事科学等等。CA亦能对诸多的一般现象进行研究，这其中包括信息传递、通信、构造、计算、复制、生长、竞争与进化等。同样，在系统整体行为与复杂现象的研究方向，例如，动力学系统理论中有关秩序、紊动、混沌、非对称、分形等，元胞自动机亦给出了一个十分有效的模型工具。此外，在对称加密方面和伪随机序列生成方面，元胞自动机也都有着很大的发展。元胞自动机最大的内在优势是它的并发运算，这个优势可以使它用来研究计算机科学中的并行运算，可以取得

5、很好的运算效果。把元胞自动机应用在物理学领域中，可以用它来模拟具体的一些物理学现象的动态过程。而应用在社会学领域中，一些经济危机的形成与爆发过程，元胞自动机可以进行很好的研究。在环境科学中的应用，森林生长的模型也被一些学者通过元胞自动机成功的应用出来了。1.2.1格子气自动机格子气自动机(Latt1ce Gas Autmoata，简称LGA)，是由CA演变而来，它主要是元胞自动机具体应用在流体力学和统计物理中而演变的一种算法，其更是CA的科学研究方向应用成功的典型代表。它不同于“生命游戏”，LGA会在模型的实用性方面更加加以注重。LGA可以很好的用来模拟流体粒子的运动，在其利用了CA的动态特征

6、的条件下 4。20世纪70年代初，法国的三位科学家J.Hardy、Y.Pomeau和0.Pazzis提出了HPP模型，这个具有划时代意义的模型就是第一个时空、速度等变量完全离散的格子气自动机，用这种格子气自动机运算模拟出来的结果和流体力学中的著名的Nvaier-Strokes方程算出来的结果非常接近，但是有一个最大的缺点，格子气自动机模拟出的流体粒子它的运动方向只允许四个，这个严重的缺点直接导致了应力张量的各向异性，其结果就是不能完全的体现出流体本身的特点，所以，由于这个缺陷的存在，导致了格子气自动机这个算法长期得不到足够的关注。直到1980年开始，在S.Wolrfma等人的研究下，使得元胞自

7、动机理论长生了实质性的进步，这直接的带领了格子气自动机的飞速发展。到了1986年，法国科学家钱U.Frish、Y.pomeau和美国科学家B.HaSSlaeher在前人J.Hardy、Y.Pomeau和0.Pazzis提出的HPP模型的基础上，共同开发出了一种具有很好的实际使用价值的并且基于六角形网络的LGA模型，他们把它称为FHP(Fritsch-HaS，lacher一Pomeau)模型，同时三个人论证出了基于这种模型的宏观行为与标准的Nvaier-Stokes方程得出的结论是相符合的。这种新的模型是第一个取得成功的LGA模型，同时，这种模型的成功提出，大大激发出了人们对LGA模型的研究热情

8、。LGA自动机可以看成是一个扩展的LG模型。我们拿早期的LGA模型作为例子，进行其特征的概述 5：(1) 由于格子气自动机自身的特点，因此LGA必须是一个可以逆向进行的CA模型，其中主要原因是流体粒子本身并不会轻易的消逝在模型空间内。(2) Margu1os类的邻居模型通常是被用作在LGA中，它的意思是在一个22的网格空间内，它的规格才可以有效的运行。它的规则可以用图1-1来进行简要的说明6:图 1-1 格子气自动机的规则如图所示，我们将图中的黑色小球定义为流体粒子，我们将图中的白色小球定义为元胞。这样定义以后，我们可以得出这样的结论，和其他的CA不同，LGA本身的研究对象不仅仅是单一的一个元

9、胞，更多的是研究包含四个元胞的一个四方块，将其看成一个整体研究它的状态。(3)如果按照以上的规则和邻居模型进行一次完整的计算后，还需要再依照另一种规则重新计算一次，我们把这种规则定义为将这个22的模板沿对角方向滑动。1.2.2人工生命研究1990年开始，人工生命开始兴起，并且逐渐发展成为一种复杂的，支柱性的研究学科。作为以一种可以通过科学研究来显示大自然里面各种和生命相关的系统行为特征的人工系统的复杂的科学研究，这种系统可以通过在计算机、机器人等一些人工的媒体上进行一系列的仿真、合成与生命有机体有关系的基本的现象，还可以通过来对“可能的生命现象”的相关的研究和观察，让人们对这些“已知的生命现象

10、进行更好的理解 7。Christopher Langton等科学家们通过对CA的系统的复杂的研究，得出而且延续了人工生命。反过来，人工生命的延续又给元胞自动机带来的新的意义和研究目标。这些使CA模型获得了大家的许可并且让人们重新认识到这项研究的意义。从而使人工生命的研究在上世纪90年代又一次成了科研的热门方向，也让研究的理论和研究的方法得到了更深层次的发展8。第二章 元胞自动机的简要介绍2.1元胞自动机的定义根据前人研究的经验，通常意义上我们把元胞自动机定义为两种方式：即物理学上的定义与数学上的定义。2.1.1物理学定义元胞自动机(CA)在实质上看来是一个元胞空间，这个空间被一些很有规则的网格

11、分割成一系列的元胞，每一个被分割出来的单个元胞的状态属性都是有限而离散的，而每一个被分割出来的元胞它的演化的规则也都是局部的，依照这些局部的规则，元胞都会在离散的时间维度上实时更新自身的状态属性，经过这一系列复杂的实时动态演化过程，元胞自动机形成一套完整的动力学系统循环。和一般意义上的动力模型不一样，CA将物理方程替换成为了演化规则9。2.1.2数学定义2.1.2.1集合论角度的定义假设CA的空间维数是d，是t时刻时在整数集Z上元胞状态的所有有限集。当d= 1时，即为一维元胞自动机时，CA的动态演化过程即为从t时刻开始的元胞状态组合依照演化规则F在t+1时刻时更新成了新的元胞状态组合，如式2.

12、1所示。 F: (2.1)CA的动态演化从本质上来说决定于局部规则本身，这种局部规则函数其输入与输出集是有限的状态集合体。一维CA中，假设元胞的邻居半径是r，它的局部规则为f，在t时刻时元胞i状态为，则局部规则F如式2.2所示。 F()=f(,) (2.2)2.1.2.2拓扑学角度的定义假设CA的空间维数是d，Sz是一个整数集Z到有限集S的映射，这种映射是元胞所有状态的集合。如a=(，a-1，a0，a1)是一维CA空间中的任意点，我们定义Sz中任意两个点x和点y之间的距离，由计算结果在Sz中可建立幵、闭、紧等一些拓扑方面的概念，用定义移位算子来进行构建CA的演化规则。2.2元胞自动机的组成部分

13、CA的构成可以用图2.1来进行表示，从图中我们可以看出其四个主要组成部分。(1)元胞：它是CA里面最基本的元素组成，具有状态属性。它在元胞空间的格点上分布着，并且会根据元胞空间划分的差异导致其具有不一样的形状，而且由于研究问题的差异也会导致其状态的差异。(2)元胞空间：它是指元胞分布的所有空间里的网格点的集合整体。依照CA维数的差异，元胞空间的划分方式也存在这诸多的不一样，例如一维CA是一条直线，二维以及二维以上的划分方法其划分的形式有很多种。(3)邻居：邻居指的是这个元胞在更新状态的时候所产生的所有可能影响到的空间范围，而且规定，所有邻居的大小都必须是一样的，而邻居里面的元胞的数量正比于规则

14、的复杂性。一维CA的邻居可以用邻居半径r来进行确定，二维CA的划分方式主要分为VonNemnann型、Moore型以及扩展Moore型这三种方式，如图2.2所示。由于位于边界的元胞和位于内部的元胞它的邻居并不相同，所以我们根据这些不同分为周期型边界、固定边界、绝热边界和映射边界等几种边界处理方式10。 (4)规则：所谓的规则，首先应该做的是确认这个元胞现在的状态以及邻居的状态，然后由仿真要求可得出下一时间点这个元胞可能的状态，进而确定其状态转移函数，这个过程即被称作是演化规则，演化规则它是整个CA模型中的精髓部分。演化规则是否合理直接决定着仿真的结果是否可靠以及是否可信，而其灵活性与否也直接的

15、决定了CA模型的适用的范围11。2.3元胞自动机的特征和分类通常来说，CA有下列的几种特性：(1)空间和时间离散：空间的离散具有两方面的含义，它既指元胞空间自身结构的离散，又指元胞在元胞空间里面分布的离散；而在时间上的离散则是指系统按照等时步长来演化，和微分方程里的连续时间不一样的是，它的时间的取值是与t、t+1、t+2等的这些时刻点相类似的时间点。(2)齐性和同质性：所谓齐性指的是元胞的大小相同、形状相同以及分布方式都完全相同；所谓同质性则指的是在元胞空间范围中所有的元胞都会遵守一样的演化规则。(3)时空局域性：所谓时空局域性它说的是一个元胞在t+1时刻时的状态是由邻居半径r范围里的所有的元

16、胞在t时刻时的状态所决定出来的，但是在t时刻时的元胞的元胞状态只会给t+1时刻时的状态产生影响，所以会在时间与空间上有一些局限。(4)并行性：并行性的定义是在元胞空间内的每一个元胞的元胞状态的更新是时时同步进行的。(5)状态离散有限：这里的状态离散有限是指元胞本身的状态量只能在有限的而且离散的状态集合里面进行取值。(6)高维数：维数是CA里面研究变量的数目。在应用的具体实例中，计算机模拟会根据变量的个数来处理大数目、高维度的系统12。由元胞空间的维数可把CA划为三类，如图2.3所示。(1)一维：一维元胞自动机指的是元胞等距离的分布在直线上，其状态与规则都很简单，它的动态演化过程比较容易观察。(

17、2)二维：二维CA有三角形、正方形和正六边形这几种空间的划分方式。(3)高维：顾名思义，指的是三维和三维以上的元胞自动机，这中自动机在实际的模拟过程中应用的很少。2.4元胞自动机理论自动机是一种自动的设备，它并不需要由人来一步一步的操作，自动机根据其存储带的是否有限性，可分无限带自动机与有限带自动机这两种。如图灵机之类的这种无限带自动机的主要用途是来描述算法以及算法的繁衍的过程。有限自动机它是一种具有离散的输入与输出的自动机，例如元胞自动机13。第三章 初等元胞自动机的实现初等元胞自动机(Elementary Cellular Automata, 又称ECA)是指状态集S只存在2个元素0,1,

18、邻居半径r为1的一维元胞自动机,初等元胞自动机是所有元胞自动机里面最简单的模型。ECA的局部映射f :S3 S可以表示成为:Si(t+1)=f(Si-1(t),Si(t),Si+1(t)根据局部映射规则所有的不同的情况一共有28即为256种,因此在S.Wolfram对不同种局部规则的做了进一步的研究之后,他发现 虽然ECA模型非常简单, 但是其可以表现出来异常繁杂的空间性形态。S.Wolfram把最后的结论表示成四种形式: (1)趋向于与时间无关稳定状态;(2)趋向于一种周期性的结构形式;(3)会有混沌行为发生的可能性;(4)可以衍变成为更加繁杂的构象。S. Wolfram对ECA的探索为后来

19、CA的研究扫除了障碍, 此外，他还对CA的理论性发展和后面的人工生命以及最近几年新兴的复杂性科学的探究奠定了卓越基础14。设计CA的时候通常会利用一个二维数组m(n,t)来对数据进行储存,在Matlab软件中将一个axis分成nt个格子, 每一个方格都会与m中的一个元素相对应, 我们用t来表示时刻,用n表示一个元胞空间；这样m(i,t)就代表第i个元胞在t这个时刻的时候它的状态,我们定义0代表该元胞“死”,1代表“活”；我们还用黑色代表“活的”元胞,用白色代表“死的”元胞；它的边界条件用周期型来进行表示；邻居长度表示成1；对于定编号ECA来说，它的转变规则是已知的15。算法可以用下面来表示：初

20、始化元胞状态随机；键入转换规则(0- 255)；将转换规则号处理把其变成个算法子程序；具体的算法如下:在t 时刻的时候读取初值：m(1:n,t)；根据规则进行判断并且生成t+1时刻的时候各个元胞的状态：m(1:n,t+1)；从1-t的循环进行这个子程序的调用；输出结果；基于上述步骤，我们对ECA做了设计, 下面是经典的ECA在时间上进行运算的情况。图3-1 ECA的运算(a)编码为22的一维基本元胞自动机(b)编码为40时, 元胞趋向于消失(c)编码为60时的周期型(d)编码为78时的静态型第四章 仿真实现3.1仿真工具简介用于CA的仿真的软件有很多种，比如Mathworks公司开发的MatL

21、ab、圣塔菲研究所开发的Swarm等。Matlab是一个很知名的仿真软件，它由美国Mathworks公司推出并在数值计算方面和图形处理方面有着很广泛应用的一个软件。它给用户建立了一套人机可以交互的数学系统环境，同时还设计出了一个直观的可视化界面来当作编程的环境, Matlab系统的基本的数据结构是矩阵, 它具有定义比较简单，编程比较容易, 它还给出了一些完整的函数，这使得很多的基本的数学运算都能用其特有的功能函数得以完成，此外，Matlab也给出了一些外部数据接口，用户可以用这些接口调用Java语言这些类似的外部子程序。基于Matlab的这些优点，用它来对CA程序的编写是很适合的。以下我们用M

22、atlab来进行模型的仿真实现16。3.2 Matlab实验模拟由于CA的变化规则，从而决定了元胞的行为和元胞邻居的状态，下面，我们用Matlab来进行具体的仿真模拟：1)定义元胞矩阵在Matlab中的表示形式，Matlab能够有效的对它们进行互相转换，矩阵会通过图像直观的显示在Matlab中，元胞Z的矩阵只有2种状态并且存在，那么，我们可以使用cat命令来建立RGB图像，用image命令返回句柄：imh = image(cat(3,cells,z,z);set(imh, erasemode, none)axis equalaxis tight图 3-1矩阵转换图2)因为图像和元胞矩阵是可以相

23、互转换的，即图形或者元胞矩阵都可以作为模拟的初始条件。用以下的代码来生成一个中心元胞状态是1，周边元胞状态是0的初始化矩阵：z = zeros(n,n);cells = z;cells(n/2,.25*n:.75*n) = 1;cells(.25*n:.75*n,n/2) = 1;图 3-2 初始化3)在计算元胞的邻居时，我们可以根据元胞自动机规则来进行求解，提高Matlab的运算效率，用以下代码来计算元胞相邻邻居：y=2:n-1;x=2:n-1;sum = veg(y,x+1)+veg(y,x-1)+ .veg(y+1,x)+veg(y-1,x);图 3-3 计算邻居元胞x = 2:n-1;

24、y = 2:n-1;sum(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(x+1,y-1) + cells(x+1,y+1);cells = (sum=3) | (sum=2 & cells); 图 3-4 计算邻居元胞4)为了使模拟的效果更加人性化，可以在图形界面中增加启动、暂停和退出功能来操作元胞，同时也增加了显示框显示模拟运算的次数：plotbutton=uicontrol(style,pushbutton,.stri

25、ng,Run,.fontsize,12, .position,100，400，50，20, .callback, run=1;);erasebutton=uicontrol(style,pushbutton,.string,Stop,.fontsize,12,.position,200，400，50，20， .callback,freeze=1;);quitbutton=uicontrol(style,pushbutton，.string,Quit, .fontsize,12, .position,300,400,50,20, .callback,stop=1;close;);number =

26、 uicontrol(style,text,.string,1,.fontsize,12,.position,20,400,50,20);图 3-5 元胞自动机控制界面5)对元胞自动机进行初始化以后，程序会按设定的规则不断的演化，每次演化中由 image函数返回句柄：stop= 0;run = 0;freeze = 0;while (stop=0)if (run=1)sum(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

27、:n,y-1) + cells(x+1,y+1);cells = (sum=3) | (sum=2 & cells);set(imh,cdata,cat(3,cells,z,z) )stepnumber = 1 + str2num(get(number,string);set(number,string,num2str(stepnumber)endif (freeze=1)run = 0;freeze = 0;enddrawnowend第五章 Game Of Life的实现上世纪60年代末，J.H. Conway设计了一种计算机游戏-生命游戏(Game of Life)。Game of Lif

28、e在某方面有点类似于围棋，其构成与规则如下：被规律分成的网格上的元胞分为0，1这两个状态，其中0表示着“死”，1表示着“生”；相互靠近的8个元胞为邻居，称之为Moore邻居，在某一时刻元胞本身与其附近8个邻居决定了这个元胞的生死；当在这个时间点的时候，假如某一元胞其状态是“生”，而且与它相邻的8个元胞内有两个或三个也是“生”,那么下一个时刻的时候这个元胞的状态为“生”，反之即为“死”；假设在某一个时刻，元胞的状态是“死”，而且与其相邻的8个元胞里面刚刚好有3个是“生”的状态，那么这个元胞将会在下一刻“复活”，反之则继续为“死”的状态17。虽然Game of Life的规则看起来十分的简单，但是

29、其作为一种CA模型有产生动态结构的能力，Game of Life能够显示出复杂并且多变的图案。Game of Life和初始元胞的状态值分布有着很大的相关性，假定任意一个初始元胞的状态值，通过计算，有些图案会消失的很迅速，但是有的却没有任何的变化，还有一些会反复的在两个或者几个图案之间进行重复，这里面最有代表性的就是 “滑翔机( Glider)”18。Game of Life模型在很多的领域内已经得到了运用，其演化的规则能够近似地反应生物物种群体之间的繁衍生息的一些规律。此外，J.H. Conway还通过实验证明出，CA具有与通用图灵机相类似的计算能力，这就意味着Game of Life模型可

30、用来模拟出任意的一种计算机19。通过对“Game of Life”进行的不间断的深入探索，A.K Dewdney等人还把Conway 的Game of Life拓展到三维甚至四维空间中去。在“Game of Life”的设计中，我们把一个平面分为类似与方格棋盘的状态，每个方格表示为单一的一个元胞，假设元胞的状态为“0”则代表了元胞死亡，如果元胞的状态为“1”则代表元胞是活的，邻域半径是1，邻域类型为Moore型，那么它的演化规则可以表示成下列的状态： 1 S= 2,3若S(t)=1，S(t+1)= 0 S2,3 1 S= 3若S(t)=0，S(t+1)= 0 S3在这里我们用S(t) 代表t时

31、刻时元胞的状态，用S表示8个相邻元胞里面还活着的元胞的个数。在这套程序里面，客户可以在直观的图形界面内定义元胞的初始值；在定义完邻居和局部规则之后,程序会自动的进行运算,进而得到复杂的多种演变形式。这里，元胞在t时刻时的状况用二阶矩阵X( m, m) 进行定义。具体算法如下:1) 求相邻矩阵: 定义四个方向向量:n= 1 1: m- 1； 表示上方( 北方) 向量e = 1:m- 1 m ； 表示右方(东方) 向量s = m 2: m； 表示下方( 南方) 向量w= 2: m 1； 表示左方(西方) 向量2) 求和：由Moore邻居模型和矩阵N为东、南、西、北、东南、西南、东北、西北八个邻居的和；用矩阵表示如下:N= X( n,:) + X( s,: ) + X( :, e) + X(: ,w) + X( n, e) +X(