基于细胞自动机的生命活力模拟的实现

基于细胞自动机的生命活力模拟的实现
摘 要
在人类社会发展的早期，就有大批各领域的学者在积极地探索、思考生命的本质是什么？到了信息技术高速发展的阶段，不少人都希望用计算机来缔造人工生命。冯诺伊曼所提出细胞自动机便是这么一个模型。虽然这个模型很简单，但是，它展现出来的复杂的奇妙的现象却吸引了大量的研究人员。如今，它作为一个数学模型，在各行各业的应用领域发挥着巨大的作用。我们将对细胞自动机的构成、实现机制以及它产生的现象作一番简单的探讨。
第一章将详细介绍细胞自动机的概念、基本元素以及各类自动机的共同特征；第二章详细介绍一维细胞自动机和生命游戏的程序算法设计，分析算法的性能并给出了改进的方法；第三章结合自己对细胞自动机的一些理论知识，使用自己制作的细胞自动机进行实验操作，仔细分析细胞自动机产生的现象，以验证前人所提出的理论和观点，总结自己对这些现象和理论看法；第四章简单探讨了细胞自动机的长远意义和实际的应用。

关键词：细胞自动机；生命游戏；动力学模型

Based on Cellular Automaton Life Vigor Simulation Realization
Abstract
Early 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 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 domain 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 second 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 which 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 the cellular automaton long term and the actual application.

Key words: Cellular automaton; Life of game; Dynamics model

目  录
论文总页数：31页
引言    1
1 认识细胞自动机    1
1.1 细胞自动机概念的提出    1
1.2 细胞自动机的基本元素    1
1.3 细胞自动机的特征    5
1.4 生命游戏    7
2 细胞自动机的程序算法实现    8
2.1  通用模块的设计    8
2.2 生命游戏的实现    11
2.3 一维通用细胞自动机（CA）的实现    14
2.4 分子热运动模拟    15
3 细胞自动机的实验    17
3.1 一维细胞自动机分类    17
3.2 复杂系统相变的调节参数    23
4 细胞自动机的现实应用和长远意义    26
4.1 现实应用    26
4.3 长远意义    27
结论    29
参考文献    29
致谢    30
声明    31
 
引言
20世纪40年代晚期，天才科学家冯诺伊曼先生为了研究机器的自我复制过程而提出了一个著名的动力学模型：细胞自动机。数学家康维等人紧跟其后，继续发扬他的理论，实现了一个当时深受人们欢迎的模型：生命游戏。物理学家沃夫拉姆也针对冯诺伊曼提出的一维细胞自动机模型进行分析，把这个模型产生的四种现象分为四种类型。而被尊称为“人工生命之父”的兰顿对这四种类型进行了分析，认为这和物理学中的相变是同一种现象。目前，国内对一维细胞自动机也越来越关注。北京师范大学哲学与社会学学院李建会教授对细胞自动机进行了深入的研究，提出了“计算主义”的理论。这便是细胞自动机的来源背景和前人先辈做的工作。作为一个动力学模型，细胞自动机已经在各行各业得到了广泛的运用。
本文的目标就是依据前人提出的规则，设计出一维细胞自动机、生命游戏等程序，并详细阐述算法的复杂性以及不足，并针对这些问题提出改进的方法。然后使用这些程序对前人提出的一些基础性理论进行实验验证。比如沃夫拉姆提出的四种类型、兰顿提出的能调整系统状态的参数，以便加深自己对这方面理论的认识。在文章的最后，谈到了细胞自动机在个领域的应用以及所有的细胞自动机所共有的特征，并简单谈了它的长远意义。
程序的开发平台是.Net 2005，所使用的操作系统是Windows.XP。
1 认识细胞自动机
1.1 细胞自动机概念的提出
上世纪50 年代，在图灵提出人的大脑是一台离散态的计算机的思想几乎同一时期，计算机科学的另一个开创者冯•诺伊曼即开始从计算的视角思考生命的本质问题，他认为自我复制乃是有生命的物体的独一无二的特征，也是被称之为生命的必要条件。为了构造一个能够自我复制的机器，冯•诺伊曼提出了细胞自动机的概念。
冯•诺依曼在逝世前证明了起码有一种确实能够自我繁衍的细胞自动机模型的存在。这个模型极其复杂，要求大量的细胞格，而且每一个细胞有二十九种不同的状态，这是任何现有计算机的模仿功能都无法胜任的。但这种模型确实存在的事实回答了根本的原则问题。
从此，由细胞自动机来构造具有生命特征的机器成为科学界的一个新的方向，而对细胞自动机理论本身的研究开始逐步展开。
1.2 细胞自动机的基本元素
1.细胞
细胞又可称为单元、基元或元胞，是细胞自动机的最基本的组成部分。细胞分布在离散的一维、二维或多维欧几里德空间的网格上。
2.细胞状态
在实际应用中，细胞状态一般是{ s0,s1,……si……sn }整数形式的离散集。对于其它类型的取值，比如“红”“白”等颜色取值，可以映射到整数集上。
3.细胞空间
细胞所分布在的空间网格集合就是细胞空间。对于细胞空间，有几个特征需要注意。
(l)几何划分
理论上，细胞空间可以是任意维数的欧几里德空间，但目前研究多集中在一维和二维细胞自动机上。
对一维细胞自动机的系统研究最早，相对来讲，其状态、规则等较为简单，往往其所有可能的规则可以一一列出，易于处理，研究也最为深入。目前，对于细胞自动机的理论研究多集中在一维细胞自动机上。美国学者沃夫拉姆对细胞自动机的动力学分类也是基于对一维初等细胞自动机 (Elementary Cellular Automata，简称ECA)的分析研究得出的。它的最大的一个特征在于容易实现细胞自动机动态演化的可视化：在二维显示中，一维显示其空间构型，即空间维；另外一维显示其发展演化过程，即时间维。
二维细胞自动机是指细胞分布在二维欧几里德平面上规则划分的网格点上，通常为方格划分。以英国学者康维（John Horton Conway）的“生命游戏”（Game of Life）为代表，应用最为广泛。由于世界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法转换到二维空间上。所以，二维细胞自动机的应用最为广泛。
(2)边界类型
在理论上，细胞空间通常是在各维度上是无限延展的，这有利于在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此，我们需要定义细胞空间的边界。例如，可以定义如下几种边界:周期型、反射型、定值型、随机型。
周期型边界(Periodic Boundary)是指相对的边界连接起来的细胞空间。对于一维空间，细胞空间表现为一个首尾相接的“圈”。对于二维空间，上下相接、左右相连而形成一个拓扑圆环面 (Torus)。周期型空间与无限空间最为接近，因而在理论探讨时，常用此类边界来设计模型。
反射型边界(Reflective Boundary)指在边界外邻居的细胞状态是以边界为轴的镜面反射。对一维细胞自动机来说，如果最左边的那个细胞的状态是1 ，那么，他的左边邻居的状态我们看成和它是一致的，也是2。例如在一维空间中，当r=1时的边界情形:
 
图1 反射型边界示意图
定值型边界 (Constant Boundary)指所有边界外细胞均取某一固定常量，如0、1等。
有时，在应用中，为更加客观、自然地模拟实际现象，还有可能采用随机型边界(Random Boundary)，即在边界实时产生随机值。
需要指出的是，这几种边界类型在实际应用中，尤其是二维或更高维数的建模时，可以相互结合。如在二维空间中，上下边界采用反射型，左右边界可采用周期型。
(3)构型(Configuration)
在这个细胞、状态、细胞空间的概念基础上，我们引入另外一个非常重要的概念“构型”。构型是指在某个时刻，在细胞空间上所有细胞状态的空间分布组合。通常，在数学上，它可以表示为一个多维的整数矩阵。构型也被称为全局状态（global state）。
4.邻居
以上的细胞及细胞空间只表示了系统的静态成分，为将动态引入系统，必须加入演化规则。在细胞自动机中，这些规则是定义在空间局部范围内的，即一个细胞下一时刻的状态决定于本身状态和它的邻居细胞的状态。因而，在指定规则之前，必须明确哪些细胞是该细胞的邻居。
在一维细胞自动机中，通常以半径来确定邻居，与一个细胞相距在一个半径的距离之内的所有细胞均被认为是该细胞的邻居。
二维细胞自动机的邻居定义通常有以下几种形式，我们以最常用的规则四方网格划分为例。见下图，黑色细胞为中心细胞，灰色细胞为其邻居，它们的状态一起来计算中心细胞在下一时刻的状态。