元胞自动机仿真与实现

《元胞自动机仿真与实现》由会员分享，可在线阅读，更多相关《元胞自动机仿真与实现（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 Mat lab实验模拟11第五章 Game Of Life 的实现17结 论20参考文献21致 谢23第一章 绪 论1.1 元胞自动机的历史进程元胞自动机(CellularAutomata,简称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 格子气自动机格子气自动机(LattIce Gas Autmoata,简称LGA),是由CA演变而来，它 主要是元胞自动机具体应用在流体力学和统计物理中而演变的一种算法，其更是 CA的科学研究方向应用成功的典型代表。它不同于“生命游戏”，LGA会在模型 的实用性方面更加加以注重。LGA可以很好的用来模拟流体粒子的运动，在其利 用了 CA的动态特征的条件下20世纪70年代初，法国的三位科学家J.Hard

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

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

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

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

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

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

13、照演化规则F在t+1时刻时更新成了新的元胞状态组合，如式 2.1 所示。F: SZ SZ+1(2.1)CA 的动态演化从本质上来说决定于局部规则本身，这种局部规则函数其输入与 输出集是有限的状态集合体。一维CA中，假设元胞的邻居半径是r,它的局部 规则为f,在t时刻时元胞i状态为SZ，则局部规则F如式2.2所示。F(SZ+1)=f(SZ-r，,Si，,SLr)(2.2)2.1.2.2 拓扑学角度的定义假设CA的空间维数是d，S是一个整数集Z到有限集S的映射，这种映射z是元胞所有状态的集合。如a=(，a，a，a)是一维CA空间中的任意点，-1 0 1我们定义 S 中任意两个点 x 和点 y 之间

14、的距离，由计算结果在 S 中可建立幵、 zz闭、紧等一些拓扑方面的概念，用定义移位算子来进行构建CA的演化规则。2.2 元胞自动机的组成部分CA 的构成可以用图 2.1 来进行表示，从图中我们可以看出其四个主要组成部分。Ug胞及状奄元胞动机的构成图规则/变换函数元煦空问(1)元胞：它是CA里面最基本的元素组成，具有状态属性。它在元胞空间的格点上分布着，并且会根据元胞空间划分的差异导致其具有不一样的形状，而且 由于研究问题的差异也会导致其状态的差异。(2) 元胞空间：它是指元胞分布的所有空间里的网格点的集合整体。依照CA 维数的差异，元胞空间的划分方式也存在这诸多的不一样，例如一维CA是一条 直线，二维以及二维以上的划分方法其划分的形式有很多种。(3) 邻居：邻居指的是这个元胞在更新状态的时候所产生的所有可能影响到 的空间范围，而且规定，所有邻居的大小都必须是一样的，而邻居里面的元胞的 数量正比于规则的复杂性。一维CA的邻居可以用邻居半径r来进行确定，二维CA的划分方式主要分为VonNemnann型、Moore型以及扩展Moore型这三种方式， 如图2.2所示。由于位于边界的元胞和位于内部的元胞它的邻居并不相同，所以 我们根据这些不同分为周期型边界、固定边界、绝热边界和映射边界等几种边界 处理方式10。単力能呦他口型_Mg圧型扩展Moore型口=1 - I1