《胞自动机仿真与实现》由会员分享，可在线阅读，更多相关《胞自动机仿真与实现（24页珍藏版）》请在金锄头文库上搜索。
1、元胞自动机仿真与实现目 录第一章 绪 论11.1 元胞自动机的历史进程11.2 元胞自动机的应用11.2.1格子气自动机21.2.2人工生命研究3第二章 元胞自动机的简要介绍52.1元胞自动机的定义52.1.1物理学定义52.1.2数学定义52.2元胞自动机的组成部分62.3元胞自动机的特征和分类72.4元胞自动机理论8第三章 初等元胞自动机的实现9第四章 仿真实现113.1仿真工具简介113.2 Matlab实验模拟11第五章 Game Of Life的实现17结 论20参考文献21致 谢23第一章 绪 论1.1 元胞自动机的历史进程元胞自动机(Cellular Automata，简称 CA
2、)，亦被称为细胞自动机，它起源于Von.Neumann和A.Turing的数值计算，乃至更早一些的时期。计算机鼻祖Von Neumann等人给出了元胞自动机的基本概念和初等模型，在美国计算机科学家S.Wolfram 写的A New Kind of Science 书中，把元胞自动机提升到了一个新的科学层面。这使得一种用于复杂系统的计算模拟的新理论依据和实现方法得以提出，所以，这个领域的科研又一次成为了人们研究的热门。到了上个世纪70年代，由于计算机的飞速发展，剑桥的数学家J.H.Conway2编写了 “生命游戏”（Game of life）这一十分典型的元胞自动机。Game of life的基
3、本原理是制定一个简单的规则，在这种规则下，通过元胞在空间网格中运行和演化，使得元胞的状态在生与死之间进行改变，最后的可以得出复杂的图形。这种自动机可以对一些复杂现象进行模拟，例如在生命进程中的生存、竞争、灭绝等一些复杂的过程。J.H.Conway还论证出，这个自动机有着和通用图灵机类似的的计算力，且等价于图灵机，这就意味着，当在合适的初始条件下，我们可以用这种元胞自动机模拟任意的计算机。到了80年代，S.Wolfram3等人对元胞自动机的进一步研究使得CA理论产生的质变。他对CA进行的动力学角度处理，而且把计算理论用在研究之中。它的研究理论结果得出，看似很简单的系统亦会得到十分复杂的结构，这从
4、而也证明了出了CA方法理论可作很多理论的基础这一观点，这使元胞自动机变成了一个可以在动态演化方向进行探究的非常实用的工具，从此对元胞自动机的理论探索渐渐的快速发展开来。80年代末，伴随着一些诸如混沌、分形、计算机图形学和复杂性理论等一些有关学科的兴起，CA理论逐渐快速的变成了非线性前沿科学的一个非常重要分支学科，而且它也慢慢的以一种非常实用的应用技术，逐渐的向其它学科之间进行交叉渗透。1.2 元胞自动机的应用元胞自动机从被研发出来的那一天起，它就被人们广泛地应用在了与人活动息息相关的诸多领域，例如，经济方面、社会方面、科学方面以及军事研究方面。这其中用到的学科有社会科学、生态科学、生物科学、计
5、算机科学、信息科学、数学、物理学、化学、环境科学、地理、军事科学等等。CA亦能对诸多的一般现象进行研究，这其中包括信息传递、通信、构造、计算、复制、生长、竞争与进化等。同样，在系统整体行为与复杂现象的研究方向，例如，动力学系统理论中有关秩序、紊动、混沌、非对称、分形等，元胞自动机亦给出了一个十分有效的模型工具。此外，在对称加密方面和伪随机序列生成方面，元胞自动机也都有着很大的发展。元胞自动机最大的内在优势是它的并发运算，这个优势可以使它用来研究计算机科学中的并行运算，可以取得很好的运算效果。把元胞自动机应用在物理学领域中，可以用它来模拟具体的一些物理学现象的动态过程。而应用在社会学领域中，一些
6、经济危机的形成与爆发过程，元胞自动机可以进行很好的研究。在环境科学中的应用，森林生长的模型也被一些学者通过元胞自动机成功的应用出来了。1.2.1格子气自动机格子气自动机(Latt1ce Gas Autmoata，简称LGA)，是由CA演变而来，它主要是元胞自动机具体应用在流体力学和统计物理中而演变的一种算法，其更是CA的科学研究方向应用成功的典型代表。它不同于“生命游戏”，LGA会在模型的实用性方面更加加以注重。LGA可以很好的用来模拟流体粒子的运动，在其利用了CA的动态特征的条件下 4。20世纪70年代初，法国的三位科学家J.Hardy、Y.Pomeau和0.Pazzis提出了HPP模型，这
7、个具有划时代意义的模型就是第一个时空、速度等变量完全离散的格子气自动机，用这种格子气自动机运算模拟出来的结果和流体力学中的著名的Nvaier-Strokes方程算出来的结果非常接近，但是有一个最大的缺点，格子气自动机模拟出的流体粒子它的运动方向只允许四个，这个严重的缺点直接导致了应力张量的各向异性，其结果就是不能完全的体现出流体本身的特点，所以，由于这个缺陷的存在，导致了格子气自动机这个算法长期得不到足够的关注。直到1980年开始，在S.Wolrfma等人的研究下，使得元胞自动机理论长生了实质性的进步，这直接的带领了格子气自动机的飞速发展。到了1986年，法国科学家钱U.Frish、Y.pom
8、eau和美国科学家B.HaSSlaeher在前人J.Hardy、Y.Pomeau和0.Pazzis提出的HPP模型的基础上，共同开发出了一种具有很好的实际使用价值的并且基于六角形网络的LGA模型，他们把它称为FHP(Fritsch-HaS，lacher一Pomeau)模型，同时三个人论证出了基于这种模型的宏观行为与标准的Nvaier-Stokes方程得出的结论是相符合的。这种新的模型是第一个取得成功的LGA模型，同时，这种模型的成功提出，大大激发出了人们对LGA模型的研究热情。LGA自动机可以看成是一个扩展的LG模型。我们拿早期的LGA模型作为例子，进行其特征的概述 5：(1) 由于格子气自动
9、机自身的特点，因此LGA必须是一个可以逆向进行的CA模型，其中主要原因是流体粒子本身并不会轻易的消逝在模型空间内。(2) Margu1os类的邻居模型通常是被用作在LGA中，它的意思是在一个22的网格空间内，它的规格才可以有效的运行。它的规则可以用图1-1来进行简要的说明6:图 1-1 格子气自动机的规则如图所示，我们将图中的黑色小球定义为流体粒子，我们将图中的白色小球定义为元胞。这样定义以后，我们可以得出这样的结论，和其他的CA不同，LGA本身的研究对象不仅仅是单一的一个元胞，更多的是研究包含四个元胞的一个四方块，将其看成一个整体研究它的状态。(3)如果按照以上的规则和邻居模型进行一次完整的
10、计算后，还需要再依照另一种规则重新计算一次，我们把这种规则定义为将这个22的模板沿对角方向滑动。1.2.2人工生命研究1990年开始，人工生命开始兴起，并且逐渐发展成为一种复杂的，支柱性的研究学科。作为以一种可以通过科学研究来显示大自然里面各种和生命相关的系统行为特征的人工系统的复杂的科学研究，这种系统可以通过在计算机、机器人等一些人工的媒体上进行一系列的仿真、合成与生命有机体有关系的基本的现象，还可以通过来对“可能的生命现象”的相关的研究和观察，让人们对这些“已知的生命现象进行更好的理解 7。Christopher Langton等科学家们通过对CA的系统的复杂的研究，得出而且延续了人工生命
11、。反过来，人工生命的延续又给元胞自动机带来的新的意义和研究目标。这些使CA模型获得了大家的许可并且让人们重新认识到这项研究的意义。从而使人工生命的研究在上世纪90年代又一次成了科研的热门方向，也让研究的理论和研究的方法得到了更深层次的发展8。第二章 元胞自动机的简要介绍2.1元胞自动机的定义根据前人研究的经验，通常意义上我们把元胞自动机定义为两种方式：即物理学上的定义与数学上的定义。2.1.1物理学定义元胞自动机(CA)在实质上看来是一个元胞空间，这个空间被一些很有规则的网格分割成一系列的元胞，每一个被分割出来的单个元胞的状态属性都是有限而离散的，而每一个被分割出来的元胞它的演化的规则也都是局
12、部的，依照这些局部的规则，元胞都会在离散的时间维度上实时更新自身的状态属性，经过这一系列复杂的实时动态演化过程，元胞自动机形成一套完整的动力学系统循环。和一般意义上的动力模型不一样，CA将物理方程替换成为了演化规则9。2.1.2数学定义2.1.2.1集合论角度的定义假设CA的空间维数是d，SZ t是t时刻时在整数集Z上元胞状态的所有有限集。当d= 1时，即为一维元胞自动机时，CA的动态演化过程即为从t时刻开始的元胞状态组合依照演化规则F在t+1时刻时更新成了新的元胞状态组合，如式2.1所示。 F: SZ t SZ t+1 (2.1)CA的动态演化从本质上来说决定于局部规则本身，这种局部规则函数
13、其输入与输出集是有限的状态集合体。一维CA中，假设元胞的邻居半径是r，它的局部规则为f，在t时刻时元胞i状态为Si t，则局部规则F如式2.2所示。 F(Si t+1)=f(Si-r t, Si t, Si+r t) (2.2)2.1.2.2拓扑学角度的定义假设CA的空间维数是d，Sz是一个整数集Z到有限集S的映射，这种映射是元胞所有状态的集合。如a=(，a-1，a0，a1)是一维CA空间中的任意点，我们定义Sz中任意两个点x和点y之间的距离，由计算结果在Sz中可建立幵、闭、紧等一些拓扑方面的概念，用定义移位算子来进行构建CA的演化规则。2.2元胞自动机的组成部分CA的构成可以用图2.1来进行
14、表示，从图中我们可以看出其四个主要组成部分。(1)元胞：它是CA里面最基本的元素组成，具有状态属性。它在元胞空间的格点上分布着，并且会根据元胞空间划分的差异导致其具有不一样的形状，而且由于研究问题的差异也会导致其状态的差异。(2)元胞空间：它是指元胞分布的所有空间里的网格点的集合整体。依照CA维数的差异，元胞空间的划分方式也存在这诸多的不一样，例如一维CA是一条直线，二维以及二维以上的划分方法其划分的形式有很多种。(3)邻居：邻居指的是这个元胞在更新状态的时候所产生的所有可能影响到的空间范围，而且规定，所有邻居的大小都必须是一样的，而邻居里面的元胞的数量正比于规则的复杂性。一维CA的邻居可以用
15、邻居半径r来进行确定，二维CA的划分方式主要分为VonNemnann型、Moore型以及扩展Moore型这三种方式，如图2.2所示。由于位于边界的元胞和位于内部的元胞它的邻居并不相同，所以我们根据这些不同分为周期型边界、固定边界、绝热边界和映射边界等几种边界处理方式10。(4)规则：所谓的规则，首先应该做的是确认这个元胞现在的状态以及邻居的状态，然后由仿真要求可得出下一时间点这个元胞可能的状态，进而确定其状态转移函数，这个过程即被称作是演化规则，演化规则它是整个CA模型中的精髓部分。演化规则是否合理直接决定着仿真的结果是否可靠以及是否可信，而其灵活性与否也直接的决定了CA模型的适用的范围11。2.3元胞自动机的特征和分类通常来说，CA有下列的几种特性：(1)空间和时间离散：空间的离散具有两方面的含义，它既指元胞空间自身结构的离散，又指元胞在元胞空间里面分布的离散；而在时间上的离散则是指系统按照等时步长来演化，和微分方程里的连续时间不一样的是，它的时间的取值是与t、t+1、t+2等的这些时刻点相类似的时间点。(2)齐性和同质性：所谓齐性指的是元胞的大小相同、形状相
