1、基于细胞自动机的生命活力模拟的实现毕业设计论文毕业设计(论文) 基于细胞自动机的生命活力模拟的实现 论文作者姓名: 申请学位专业: 申请学位类别: 指导教师姓名,职称,: 论文提交日期: 基于细胞自动机的生命活力模拟的实现 摘 要 在人类社会发展的早期，就有大批各领域的学者在积极地探索、思考生命的本质是什么,到了信息技术高速发展的阶段，不少人都希望用计算机来缔造人工生命。冯诺伊曼所提出细胞自动机便是这么一个模型。虽然这个模型很简单，但是，它展现出来的复杂的奇妙的现象却吸引了大量的研究人员。如今，它作为一个数学模型，在各行各业的应用领域发挥着巨大的作用。我们将对细胞自动机的构成、实现机制以及它产
2、生的现象作一番简单的探讨。 第一章将详细介绍细胞自动机的概念、基本元素以及各类自动机的共同特征;第二章详细介绍一维细胞自动机和生命游戏的程序算法设计，分析算法的性能并给出了改进的方法;第三章结合自己对细胞自动机的一些理论知识，使用自己制作的细胞自动机进行实验操作，仔细分析细胞自动机产生的现象，以验证前人所提出的理论和观点，总结自己对这些现象和理论看法;第四章简单探讨了细胞自动机的长远意义和实际的应用。 关键词:细胞自动机;生命游戏;动力学模型 Based on Cellular Automaton Life Vigor Simulation Realization Abstract Early
3、 time develops which in the human society, has the large quantities of various domains the scholar positively is exploring, what is the ponder life essence? Told the development to the information technology the stage, many people all hoped creates the artificial life with the computer. Von Neumann
4、proposed the cellular automaton then is such a model. Although this model is very simple, but, it unfolds the complex marvelous phenomenon has actually attracted the massive researcher. Now, it took a number study model, plays this huge role in the entire various trades and occupations application d
5、omain we to the cellular automaton constitution, the phenomenon which the realization as well as it will produce make a simple discussion. First chapter in detail will introduce the cellular automaton the concept, fundamental element as well as each kind of automaton common characteristic; The secon
6、d chapter detailed introduction unit dimensional cellular automaton and the life game procedure algorithm design, the parsing algorithm performance and has produced the improvement method; Third chapter unifies oneself to the cellular automaton some theory knowledge, uses the cellular automaton whic
7、h oneself manufactures to carry on the experiment to operate, carefully analyzes the phenomenon which the cellular automaton produces, confirms the theory and the viewpoint which the predecessor proposed, summarizes oneself to these phenomena and the theory view; Fourth chapter simply has discussed
8、the cellular automaton long term and the actual application. Key words: Cellular automaton; Life of game; Dynamics model 目 录 论文总页数:31页 引言 - 3 1 认识细胞自动机 - 3 1.1 细胞自动机概念的提出 - 3 1.2 细胞自动机的基本元素 - 3 1.3 细胞自动机的特征 - 7 生命游戏 - 9 1.42 细胞自动机的程序算法实现 - 10 2.1 通用模块的设计 - 10 2.2 生命游戏的实现 - 13 2.3 一维通用细胞自动机(CA)的实现 -
9、16 2.4 分子热运动模拟 - 17 3 细胞自动机的实验 - 19 3.1 一维细胞自动机分类 - 19 3.2 复杂系统相变的调节参数 - 25 4 细胞自动机的现实应用和长远意义 - 28 4.1 现实应用 - 28 4.3 长远意义 - 29 结论 - 31 参考文献 - 31 致谢 - 32 声明 - 33 引言 20世纪40年代晚期，天才科学家冯诺伊曼先生为了研究机器的自我复制过程而提出了一个著名的动力学模型:细胞自动机。数学家康维等人紧跟其后，继续发扬他的理论，实现了一个当时深受人们欢迎的模型:生命游戏。物理学家沃夫拉姆也针对冯诺伊曼提出的一维细胞自动机模型进行分析，把这个模型
10、产生的四种现象分为四种类型。而被尊称为“人工生命之父”的兰顿对这四种类型进行了分析，认为这和物理学中的相变是同一种现象。目前，国内对一维细胞自动机也越来越关注。北京师范大学哲学与社会学学院李建会教授对细胞自动机进行了深入的研究，提出了“计算主义”的理论。这便是细胞自动机的来源背景和前人先辈做的工作。作为一个动力学模型，细胞自动机已经在各行各业得到了广泛的运用。 本文的目标就是依据前人提出的规则，设计出一维细胞自动机、生命游戏等程序，并详细阐述算法的复杂性以及不足，并针对这些问题提出改进的方法。然后使用这些程序对前人提出的一些基础性理论进行实验验证。比如沃夫拉姆提出的四种类型、兰顿提出的能调整系
11、统状态的参数，以便加深自己对这方面理论的认识。在文章的最后，谈到了细胞自动机在个领域的应用以及所有的细胞自动机所共有的特征，并简单谈了它的长远意义。 程序的开发平台是.Net 2005，所使用的操作系统是Windows.XP。 1 认识细胞自动机 1.1 细胞自动机概念的提出 上世纪50 年代，在图灵提出人的大脑是一台离散态的计算机的思想几乎同一时期，计算机科学的另一个开创者冯?诺伊曼即开始从计算的视角思考生命的本质问题，他认为自我复制乃是有生命的物体的独一无二的特征，也是被称之为生命的必要条件。为了构造一个能够自我复制的机器，冯?诺伊曼提出了细胞自动机的概念。 冯?诺依曼在逝世前证明了起码有
12、一种确实能够自我繁衍的细胞自动机模型的存在。这个模型极其复杂，要求大量的细胞格，而且每一个细胞有二十九种不同的状态，这是任何现有计算机的模仿功能都无法胜任的。但这种模型确实存在的事实回答了根本的原则问题。 从此，由细胞自动机来构造具有生命特征的机器成为科学界的一个新的方向，而对细胞自动机理论本身的研究开始逐步展开。 1.2 细胞自动机的基本元素 1.细胞 细胞又可称为单元、基元或元胞，是细胞自动机的最基本的组成部分。细胞分布在离散的一维、二维或多维欧几里德空间的网格上。 2.细胞状态 在实际应用中，细胞状态一般是 s,s,ss 整数形式的离散集。01in对于其它类型的取值，比如“红”“白”等颜
13、色取值，可以映射到整数集上。 3.细胞空间 细胞所分布在的空间网格集合就是细胞空间。对于细胞空间，有几个特征需要注意。 (l)几何划分 理论上，细胞空间可以是任意维数的欧几里德空间，但目前研究多集中在一维和二维细胞自动机上。 对一维细胞自动机的系统研究最早，相对来讲，其状态、规则等较为简单，往往其所有可能的规则可以一一列出，易于处理，研究也最为深入。目前，对于细胞自动机的理论研究多集中在一维细胞自动机上。美国学者沃夫拉姆对细胞自动机的动力学分类也是基于对一维初等细胞自动机 (Elementary Cellular Automata，简称ECA)的分析研究得出的。它的最大的一个特征在于容易实现细
14、胞自动机动态演化的可视化:在二维显示中，一维显示其空间构型，即空间维;另外一维显示其发展演化过程，即时间维。 二维细胞自动机是指细胞分布在二维欧几里德平面上规则划分的网格点上，通常为方格划分。以英国学者康维(John Horton Conway)的“生命游戏”(Game of Life)为代表，应用最为广泛。由于世界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法转换到二维空间上。所以，二维细胞自动机的应用最为广泛。 (2)边界类型 在理论上，细胞空间通常是在各维度上是无限延展的，这有利于在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此，我们需要
15、定义细胞空间的边界。例如，可以定义如下几种边界:周期型、反射型、定值型、随机型。 周期型边界(Periodic Boundary)是指相对的边界连接起来的细胞空间。对于一维空间，细胞空间表现为一个首尾相接的“圈”。对于二维空间，上下相接、左右相连而形成一个拓扑圆环面 (Torus)。周期型空间与无限空间最为接近，因而在理论探讨时，常用此类边界来设计模型。 反射型边界(Reflective Boundary)指在边界外邻居的细胞状态是以边界为轴的镜面反射。对一维细胞自动机来说，如果最左边的那个细胞的状态是1 ，那么，他的左边邻居的状态我们看成和它是一致的，也是2。例如在一维空间中，当r=1时的边
16、界情形: 图1 反射型边界示意图 定值型边界 (Constant Boundary)指所有边界外细胞均取某一固定常量，如0、1等。 有时，在应用中，为更加客观、自然地模拟实际现象，还有可能采用随机型边界(Random Boundary)，即在边界实时产生随机值。 需要指出的是，这几种边界类型在实际应用中，尤其是二维或更高维数的建可以相互结合。如在二维空间中，上下边界采用反射型，左右边界可采用模时，周期型。 (3)构型(Configuration) 在这个细胞、状态、细胞空间的概念基础上，我们引入另外一个非常重要的概念“构型”。构型是指在某个时刻，在细胞空间上所有细胞状态的空间分布组合。通常，在
17、数学上，它可以表示为一个多维的整数矩阵。构型也被称为全局状态(global state)。 4.邻居 以上的细胞及细胞空间只表示了系统的静态成分，为将动态引入系统，必须加入演化规则。在细胞自动机中，这些规则是定义在空间局部范围内的，即一个细胞下一时刻的状态决定于本身状态和它的邻居细胞的状态。因而，在指定规则之前，必须明确哪些细胞是该细胞的邻居。 在一维细胞自动机中，通常以半径来确定邻居，与一个细胞相距在一个半径的距离之内的所有细胞均被认为是该细胞的邻居。 二维细胞自动机的邻居定义通常有以下几种形式，我们以最常用的规则四方网格划分为例。见下图，黑色细胞为中心细胞，灰色细胞为其邻居，它们的状态一起
18、来计算中心细胞在下一时刻的状态。 图2 细胞自动机的邻居模型 (1)冯?诺依曼型 一个细胞的上、下、左、右相邻四个细胞为该细胞的邻居。这里，邻居半径r为1。 (2)摩尔型 一个细胞的上、下、左、右、左上、右上、右下、左下相邻八个细胞为该细胞的邻居。 (3)扩展的摩尔型 将以上的邻居半径r扩展为2或者更大，即得到所谓扩展的摩尔型邻居。 (4)马哥勒斯型 这是一种同以上邻居类型迥然不同的形式，它是每次将一个2x2的细胞块做统一处理，而上述前三种邻居模型中，每个细胞是分别处理的。这种邻居类型因为格子气自动机而得到关注。 有了邻居的定义，我们可以得到引入邻域的概念。邻域就是一个细胞及其所有邻居的集合。
19、 有必要说明的是，邻居并不一定要去“最邻近”的，但是这些“最邻近”的邻居较为符合现实，而且已经足可以代表了所有的细胞自动机。 5.规则 根据细胞当前状态及其邻居状况确定下一时刻该细胞状态的动力学函数就是规则。 k这里我们遇到一个典型的组合爆炸问题。假设细胞自动机中每个细胞存在nk种状态，其邻域拥有的细胞个数是n，那么邻域存在种状态。细胞的规则，或nnkkk称细胞自动机的转换函数，要将种状态映射为种状态的一种，则共有k种5转换函数存在。 非常重要的一点就是，沃夫拉姆(Wolfram)证明了，总和规则描述的细胞自动机可以展现所有细胞自动机可能表现的动态行为。 6.时间 细胞自动机是一个动态系统，它
20、在时间维上的变化是离散的，即时间t是一个整数值，而且连续等间距。假设时间间距dt=1，若t=i为某一时刻，那么，t=i+1为其下一时刻。 1.3 细胞自动机的特征 细胞自动机内所有的细胞都受相同规则的约束。它们大小相等、形状相同，地位平等，按一定的规则分布在离散的细胞空间上。系统的演化是按照等间隔时间分步进行的，时间变量t只能取等步长的时刻点。同时，由每个细胞演化到下一代都只受邻近的细胞影响，具有空间局部性。除此之外，细胞自动机还有如下重要特征: 1) 随机性和确定性 确定性和随机性是客观事物的两个方面。科学家们早就发现，确定性和不确定性之间并没有不可逾越的鸿沟，二者是辨证统一的关系。细胞自动
21、机的行为提供了一个绝好的佐证。 我们观察大自然的时候，觉得有很多随机现象，这些现象我们认为都是不可预测的。但这并不等于这些现象没有内在的确定性规则约束。比如，著名的“蝴蝶效应” 。据说，在北京的一只蝴蝶扇了一下翅膀，有可能引起太平洋的一次龙卷风。就是说，初始状态轻微的，不明显变化能引起整个系统翻天覆地的改变。这些不明显的变化经过系统的演变时被无限放大了。正如我前面所分析的，如果一维细胞自动机的细胞个数只有5的话，那么不管什么规则，最多演化2的5次方也就是32次以后，它必然呈现出重复的现象来。由于现实世界是个近乎无限的离散动力系统，这使得宏观现象看起来非常的随机化。所以，计算主义认为，它仅仅只有
22、几条简单的规则约束着，这是可确定的一部分。 2) 过程与状态 在近代科学中，早已破除了那种以状态为主看待事物的思维方法，而逐步树立了以过程为视角的思维方法。这种视角认为，我们应该首先考虑系统的演化行为，而不是此时的状态。在许多情况下，终极状态是什么并不知道，甚至是否存在这样的终极状态也并不是明确的。哲学家黑格尔曾说过，了解一门科学的历史，也就了解了这门科学本身。朗顿也曾经说过这样一句话:“你应该观察系统是如何运作的，而不是观察它是由什么组成的”。 同样的道理，在对细胞自动机进行分析的时候，必须看它的动态过程。单单看一过静态的状态是没有任何意义的。 3) 集中控制与自组织 就像自然界是大量的原子
23、和分子组成并在某种规则约束之下运动一样。研究单个原子的运动很难得出有意义的结论。但是，在大量的原子和分子在相互作用之后，复杂的现象就会突现出来。这说明，大自然没有“中央电脑”的控制。集中控制并不是操纵系统实现某一目的的唯一手段。 4) 简单与复杂 细胞自动机让我们很惊讶的发现，一些简单的东西却可以产生如此复杂的现象。细胞状态是如此简单，规则是如此简单，然而它竟然可以“模拟整个宇宙”，从生物进化，到股市涨落，到雪花形成，到铁钉生锈，等等一切。这更加深了我们“表面上看起来复杂的事物其本质可能很简单”这一信念，从而激发我们为从复杂性中发现简单性而锲而不舍。 5) 连续与离散 微分方程有着三百多年的发
24、展历史，它已经成为现代科学的语言，也是科学研究中最为重要的研究工具之一，一大批重要的科学规律就是利用微分方程来推理和表达的。 微分方程的主要特点是时间、空间均连续(如果方程中有空间因子的话)，这是建立在时空连续的哲学认识基础上的。而细胞自动机则是完全的空间离散、时间离散，在这个意义上，微分方程和细胞自动机一对相对的计算方法。 在人工计算的情况下，由符号组成的(偏)微分方程可以灵活地进行约简等符号运算，而得到精确的定量解，这是其优势。但在现代计算机日益发展，已成为我们科学研究的重要工具时，微分方程却遇到了一个尴尬的问题，即计算机是建立在离散的基础上的，微分方程在计算时不得不对自身进行时空离散化，
25、建立差分方程等;或者展开成幂系列方程，截取部分展开式;或者采用某种转换用离散结构来表示连续变量。这个改造过程不仅是繁杂的，甚至是不可能解决的，但最重要的是在这个过程中，微分方程也失去了它的自身最重要的特性精确性、连续性。甚至，我们可能因变数太多而根本无法得到合适的方程式，要么方程式本身极其复杂难以求解。 而对于细胞自动机来讲，脱离计算机环境来进行运算几乎是不可能的，但是借助计算机进行计算，却非常自然而合理，甚至它还是下一代并行计算机的原型。因此，在现代计算机的计算环境下，以细胞自动机为代表的离散计算方式在求解方面，尤其是动态系统模拟方面有着更大的优势。 因为细胞自动机的计算能力等价于图灵机，所
26、以细胞自动机在理论上具备计算的完备性。但是，其满足特定目的的构模尚无完备的理论支持，其构造往往是一个直觉过程。用细胞自动机得到一个定量的结果非常困难，即便是可能的话，细胞自动机也将陷入一个尴尬，细胞自动机的状态、规则等构成必然会复杂化，从而不可避免地失去其简单、生动的特性。 然而，诚如物理学家玻尔所说，“相对的并不一定是矛盾的，有可能是相互补充和相互完善的”。二者互有优缺点，相互补充，都有其存在的理由。在现代计算机环境下，对于细胞自动机这一类相对来讲还处于幼年阶段的离散计算方式，需要予以更多的关注和支持。 6) 并行与串行 前面说过，若从计算视角理解细胞自动机，则细胞自动机可能是下一代并行计算
27、机的雏形。细胞自动机的出现，让人们更好的展望并行计算的前景。 生命游戏是一维细胞自动机的一个特例。它之所以能展现出这么复杂美妙的图形，是因为它的规则使他恰恰处于一个“混沌边缘”(一个介于周期状态和复杂随机状态的边界，下面还要详细论述这个现象)的状态。所以，下面，我们来介绍一下生命游戏。 1.4 生命游戏 生命游戏是由剑桥大学的数学家康维于 1970 年发表于科学美国人上的论文所提出的。理论上，它是一个二维细胞自动机。在这个细胞自动机中，细胞空间是一个分割成很多四方格子(类似棋盘)的平面，初始状态时，某些方格上存活着单个细胞。播种可以是随机的，也可以指定确定的模式，以便考察一些特殊的行为。每一个
28、细胞有八个邻居，即采用摩尔邻居形式。这些细胞有两种状态:“生”或“死”，存活的细胞我们在方格内涂上特定单一的颜色，而死亡的细胞我们则不涂色。一个细胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态决定，更确切的讲是周围八个邻居的状态的和决定。其规则叙述如下: 1 对于存活的细胞(涂色的方格):当八个邻近细胞中只有零个或一个是活细胞时，则该细胞会因孤独而死亡;当八个邻近细胞中，恰有二或三个是活细胞时，则该细胞继续存活;当八个邻近细胞中，有四个或超过四个是活细胞时，则该细胞会因拥挤而死亡 2 对于死亡的细胞(未涂色的空方格):当八个邻近细胞中，恰有三个是活细胞时，则该处诞生一个活细胞 生命游戏
29、的演化规则近似地描述了生物群体的生存繁殖规律:在生命密度过小(相邻细胞数3)时，由于环境恶化、资源短缺以及相互竞争而出现生存危机，细胞状态值由“生”变为“死”;只有处于个体适中(相邻细胞数为2或3)位置的生物才能生存(保持细胞的状态值为“生”)和繁衍后代(细胞状态值由“死”变为“生”)。正由于它能够模拟生命活动中的生存、灭绝、竞争等等复杂现象，因而得名“生命游戏”。 尽管生命游戏的规则看上去很简单，但是它具有产生动态图案和动态结构的能力。它能产生丰富的、有趣的图案。生命游戏的游戏截图图3如下: 图3 生命游戏模拟图 运行这个程序的时候，我们发现，透过不同的设计，生命游戏可以展现无限的多样性。其
30、演化结果与初始细胞状态值的分布有关，给定某个的初始状态分布，即随意的设置一些活着的细胞，经过若干步的运算，有时候它们会全部死亡，即变成全黑的图案，有时候则生成固定不动的图案，有时候生成翻滚不已的图案，有时候则得到周而复始重复的几个图案，更多的时候，是得到沸腾着的各种结构，有的图案蜿蜒而行，有的则保持图案定向移动，形似阅兵阵，其中最为著名的是“滑翔机”的图案，即一小簇以常速滑过屏幕的活细胞，在四个世代的一个循环中，它沿着对角线的方向在方格上爬行，转换自己的位置，一个正方形向右，一个正方形向下，直到与其它结构相撞，产生出新的结构。 1970年康维在科学美国人杂志上发表了关于生命游戏的文章，并利用细
31、胞自动机的一些现象，成功了构造了与、或、非等逻辑门，然后更进一步证明了生命游戏足以支持通用的计算，即这个细胞自动机具有通用图灵机的计算能力，与图灵机计算等价。也就是说给定适当的初始条件，生命游戏模型能够模拟任何一种计算机。 2 细胞自动机的程序算法实现 2.1 通用模块的设计 由于下面这几个算法的实现都有一些共同的特点: 1 需要一个二维的空间 2 在程序运行时，需要频繁的刷新绘图区域 3 运动的个体都是一些离散的个体 所以，我设计了一个通用的模块，实现下面的功能的时候，都是调用了这个模块。这个模块包含了两个部分: (1)在二维空间上绘制离散的个体 (2)对这些离散个体的存储 另外，为了证明这
32、个模块通用的程度，我利用这个模块轻易实现了贪吃蛇、五子棋等小游戏，证明了这个模块的功能确实超出了预期的设想。 下面介绍一下这个模块的组成。先看图4: 图4 生命游戏模拟图 观察黑色的绘图区域，我们就可以发现，要实现各种功能，我们首先要用一个数据结构来记录各种离散个体的信息，也就是布局，然后把这些离散信息绘制出来。 1) 布局 布局相对来说比较简单。因为绘图区域是个二维图形。我们可以先创建一个int类型的二维数组cell，然后使二维数组的元素和对上面的每一个小区域一一对应起来。比如，某一个元素数值是 1 的话，那么就代表这个相应的区域存在0 的话，就说明这块区域没有个体。我们可以先对这个一个个体
33、，如果数值是 数组进行处理，然后再一次性绘制出来。实践证明，这样的方法是可行的。由于程序是动态运行，也就是说，当前的数组状态须根据相应的规则，产生下一代的状态。所以，单单只有一个数组，没办法实现这个功能。所以，我定义了另外一个数组:workcopy 。这个数组保存的就是cell状态的一个备份。当需要演化时，我们逐个对cell上的个体进行判断，邻居在workcopy 上判断。修改直接体现在cell数组上。 2) 绘制离散个体 离散的个体我们可以调用图形来，然后把它画在黑色的画布上。由于画布是个二维的矩阵，所以，要规整的在画布上布局这些个体，我们使用的图形必须是正方形的，并且，图形的背景要透明，看
34、起来才比较自然。至于个体在画布上的擦除，我们可以采用对整个画布进行刷新的办法。但是这个方法不仅低效，而且程序运行的时候，整个画面非常闪烁，令人很不愉快。我采取了一个小技巧，由于画布是黑色的，我们可以制作一个尺寸和个体图片尺寸一样大小的的黑色图片，把它覆盖在原来的区域，就等于把这个个体擦除了。这个方法不需要刷新整个屏幕，而且，只对小区域的图形进行操作，大大提高了系统的性能。下面是这个想法的算法实现(为了提高系统的性能，我使用了双缓冲技术): 3) 算法描述: Begin (1)首先把cell里的信息复制到workcopy里。 (2)载入你想在屏幕上显示的图片，建立虚拟画布。 (3)对绘画区域上的
35、位置逐个进行判断。如果这个位置下一代有而上一代没有的话，就绘制一个图形;如果这个位置下一代没有而上一代有的话，就擦除上面的图形。 End 请看通用模块显示部分算法流程图5 图5 通用模块显示部分算法流程图 4) 总结 这个模块之所以有一定的通用性是因为它的显示不受任何规则的影响，也就是说它是一个独立的函数。绘制的个体也可以多种多样，不一定非要是一个小球，你甚至可以定义一个坦克的小图品，没有问题，只要您的图片是正方形的，而且图片的长度能满足下面这个公式: 600 % 图片长度(像素点) = 0 (因为绘图区域的长度是600个像素点)。这就说明了它的两个组成部分都是独立的。如果您要实现的算法满足我
36、上面列出的三个特征，您可以使用这个通用模块，并添加一些辅助的规则，轻易实现这个算法。 2.2 生命游戏的实现 算法描述(这里，离散个体这个称呼我们改成细胞):; Begin (1)初始化。把cell 数组的每一个元素都设置成0.设置相关的变量，如临时变量、记录坐标的变量等。 (2)对cell 数组进行随机赋值，只能是0和1. (3)备份cell 数组的信息到workcopy 数组里。 (4)对cell 数组的每个元素逐个计算。取得这个细胞上、下、左、右的坐标值。如果数组元素已遍历完，则直接到End. (5)利用这些坐标值求出生存邻居的个数 (6)结合邻居个数和约束条件，如果细胞是活的，那么当它
37、有2到3个邻居时就可以继续生存下去. 否则只能死亡或者当原来没有细胞生存时，当它的邻居是3时，也可以产生出一个细胞.其他情况一律死亡。把这些信息记录到cell数组上。返回到(4)。 End 1) 收集邻居个数 图6 生命游戏中收集邻居个数的算法流程图 2) 按规则演化 图7 生命游戏中细胞按规则演化的算法流程图 注意:算法流程图中出现的变量名解释: h_i 是二维矩阵的行号;h_j是二维矩阵的列号; top 存储当前细胞上一行的行号坐标; bottom 存储当前细胞下一行的行号坐标; left 存储当前细胞前一列的列号坐标; right 存储当前细胞后一列的列号坐标;z是矩阵的边界 处理了ce
38、ll数组以后，我们就可以使用通用模块中的Display函数把它的: 状态绘制出来。至此，完成了生命游戏的程序设计。请看程序运行的截图 图8图8 生命游戏 2.3 一维通用细胞自动机(CA)的实现 生命游戏其实是一维细胞自动机的一个特殊的例子。它能实现比一维细胞自动机更生动直观和奇幻的图形。但是，由于一维细胞自动机规则简单、现象直观，故而人们对它进行了深入的研究，而且，沃夫拉姆的四种分类也是建立在一维细胞自动机的基础之上。它的理论基础可参照本论文第一章第二节。所以，有必要实现一维细胞自动机模型。 一维细胞自动机的算法描述: Begin (1)随机生成第一代的细胞:先在绘制区域的最后一行，也就是矩
39、阵数组的最后一行进行一次随机生成细胞操作。 (2)从第二行开始，把整个区域往上挪一行 (3)根据一维细胞自动机的规则和上一代的细胞状态，计算出下一代的细胞状态。并放置在cell数组的最后一行里。 根据cell数组的信息，绘制出相应的图形并返回到(2)步骤。 End 在这里，我们有必要对一维细胞自动机的规则作出解释，请先参看第一章第三节对规则的解释，上面是以一维细胞自动机为例的，也详细阐述了其规则的原理。下面简单其规则产生的算法: 一维细胞自动机规则生成算法描述: Begin (1)取得使用者给出规则的十进制表达形式。 (2)使用相关的函数把十进制值转化成二进制(具体语言不一样，可参照本毕业设计
40、源程序的trun_this_on() 函数)。 (3)把这个二进制值每一位分别拆开，放到数组里以便使用。 End 图9 一维细胞自动机演化规则号转化为二进制值的算法流程图 图10 一维细胞自动机算法流程图 注意:算法流程图中出现的变量名解释:f、k、a和b 是临时变量 ，abc是存放二进制位的一个数组。 完成程序设计工作，请看程序运行截图 图11: 图11 一维细胞自动机 2.4 分子热运动模拟 由于上面的章节没有提到分子热运动，所以这里需要解释一下。我们还是使用原来的通用模块来对分子热运动这个物理现象进行模拟。这里，离散个体的称呼改成小分子。因为分子运动性质和上面的细胞有点区别，每个分子都必
41、须有自己的运动方向和当前以及下一步的坐标，所以使用了一个结构体来存储这些信息。当然，我们对这群分子的状态的显示离不开cell数组，cell 属于通用模块的第一个组成部分。我们可以这样定义这个数据结构: public struct qiuti public int x; /这个小分子当前的坐标值 public int y; public int fang; /指示这个小分子当前的的运动方向 我们用上面的结构体定义一个结构体数组，来存储所产生的分子的信息(信息指这个分子下一步的坐标和方向)。 public qiuti fenzi = new qiuti15000; 分子随机热运动模拟程序算法描述:
42、 (1)在cell数组上随机生成小分子的坐标和方向。 (2)把这些信息记录在我们定义的结构体数组里。 (3)把 cell 数组的信息复制到 workcopy 数组里去。 (4)对结构体数组的每一个数据项都进行计算，给出分子下一步的方向和坐标。 (5)调用通用模块显示出所有分子的状态，并返回(3)步骤。 图12 分子热运动模拟算法流程图 注意:算法流程图中出现的变量名解释:fenzi是结构体数组，fenzi_count是存储分子个数的变量，qq是临时变量。 至此，分子热运动的程序设计完成，请看程序运行的截图: 图13 分子热运动模拟 3 细胞自动机的实验 3.1 一维细胞自动机分类 20世纪 8
43、0年代 ，物理学家斯蒂芬.沃夫拉姆对细胞自动机(CA)进行了分类，做了全面研究(1984)。他认为细胞自动机是个真实的复杂系统，有一些系统非常有趣，可以展现出和真实世界类似的现象。从大气现象到生物体甚至是经济系统，莫不如此。因此，有可能利用细胞自动机发现复杂系统的一般规律。更为有意义的是:复杂的系统可以从简单的行为中突现出来。 其次， 他相信，科学正处在一种新型研究方法变革的重大时期。这就是计算机实验。对自然界的一些对象，特别是复杂对象的研究，很难进行直接的实验。比如遥远星系中旋转的巨大的气体云，据说，它们往往在引力的作用下收缩成高密度的集结物，并最终成为恒星的中心团块，其周围绕着它旋转的较小
44、的团块最后变成伴随该恒星的行星系统。这种说法，很显然没有人能用实际的实验来检验一下。又假如有人说通过提高利率，比如说在很短的时间内提升500个基点，以检验关于货币和股票的价格波动的某个新理论。可以肯定，任何一个国家的金融机构都不会同意，因为这种系统对人们的生活太重要了，任何人都不敢贸然作这类实验。但是，利用计算机进行模拟实验，同样也可以得出有意义的结果。而细胞自动机是利用这种新型研究方法进行研究的最好的对象。 沃夫拉姆所研究的细胞自动机是一维的，而康维和冯。诺伊曼的细胞自动机都是二维的，它们是在二维的平面上运行的。沃夫拉姆的一维细胞自动机是在一条直线上运行。每一个细胞只有左右两个邻居。一维细胞自动机的一个优点是:因为每一代细胞的状态都可以表示在一条直线上，因此，我们可以把不同时代的细胞状态从上到下
