【最新版】计算机毕业论文55323

第2章

2.1 元胞自动机 2.1.1 元胞自动机

元胞自动机和Swarm技术

上世纪50 年代，图灵提出人的大脑是一台离散态的计算机的思想。几乎同一时期，计算机科学的另一个开创者冯·诺伊曼即开始从计算的视角思考生命的本质问题，他认为自我复制乃是有生命的物体的独一无二的特征。为了构造一个能够自我复制的机器，冯·诺伊曼提出了元胞自动机的概念。每一个元胞的状态变化都是一种计算。我们可以把每一个元胞都看作一台计算机，这样元胞自动机就是一种计算模型。元胞自动机每个元胞的变化是同步进行的，也就是对信息的处理是同步进行的，特别适合于并行计算。

冯·诺依曼在逝世前证明了起码有一种确实能够自我繁衍的元胞自动机模型的存在。这个模型极其复杂，要求大量的细胞格，而且每一个细胞有二十九种不同的状态，这是任何现有计算机的模仿功能都无法胜任的。但这种模型确实存在的事实回答了根本的原则问题。

离散时间集规则/变换函数元胞及状态邻居元胞空间

图 - 元胞自动机(Cellular Automata,简称CA)的组成

是一个时间和空间都离散的动力系统。散布在规则格网 (Lattice Grid)中的每一

元胞(cell)取某个有限状态集中的一个离散状态。一个元胞在某时刻的状态取决于而且仅仅取决于上一时刻该元胞的状态以及该元胞的所有邻居元胞的状态。元胞空间内的元胞依照局部规则进行同步的状态更新，整个元胞空间则表现为在离散的时间维上的变化。大量元胞通过简单的规则相互作用而构成动态的系统演化。

与一般的动力学模型不同的是，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。

元胞自动机由元胞、元胞的状态空间、邻居及局部规则四部分组成，可用一个四元组表示：

说明：其中A为一个元胞自动机；为元胞空间，为元胞空间的维数；为元胞的有限状态集；表示一个所有邻域内元胞的组合，为包含个不同元胞的空间矢量，表示为 ，是邻居元胞个数，（整数集），；表示将映射到上的一个状态转换函数。

1) 元胞和元胞空间

元胞又可称为基元，是元胞自动机的最基本的组成部分，分布在离散的一维、二维或多维欧几里德空间的格点上。而元胞所分布在的空间网格集合就是元胞空间，它可以是任意维数欧几里德空间的规则划分。由于计算机显示的原因，目前研究集中在一维和二维，对于一维元胞自动机，元胞空间的划分只有一种，而二维元胞自动机，二维元胞空间通常可以按三角、正方形或六边形三种网格排列。三种元胞空间划分在模拟时各有优缺点，三角网格和六边形网格在计算机的表达和显示不方便，通常都要都借助影射转换正方形网格处理。另一个需要考虑的问题是，理论上的元胞空间通常是在各维上是无限的，但却无法在计算机上实现，因此，我们需要定义不同的边界条件。归纳起来，边界条件主要有三种类型：周期型、反射型和定值型，这三种边界类型在实际应用中，尤其是二维或更高维数的构模时，可以相互结合。

2) 状态（State）

取值于一个有限的离散集。严格意义上，元胞自动机的元胞只能有一个状态变量，但在实际应用中，往往将其进行了扩展。

3) 邻居（Neighbor）

在给出规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。在一维元胞自动机中，通常以半径r来确定邻居，距离一个元胞r内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有Von.Neumann型、Moore型及扩展Moore型等（图）。

■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ （a）

Von.Neumann型 (b) Moore型 扩展Moore 型

（图中，黑色的元胞为中心元胞，灰色元胞为其邻居）

4) 局部规则（Local Rule）

(c)

根据元胞当前状态以及邻居状况确定下一时刻该元胞状态的函数，也称为状态转移函数。这个函数构造了一种简单的、离散的空间时间的局部物理成分。

2.1.2 元胞自动机的应用

元胞自动机自产生以来，被广泛地应用于各个领域的研究。在社会学中，元胞自动机用于研究个人行为的社会性，流行现象。在经济学中，是实验经济学的一个很好的工具，可以研究个体行为造成的整体性现象，更可以加入博弈论来考察均衡状态形成。而由于元胞自动机的设计思想本身就有很大部分来源于生物学的自繁殖思想，因而它在生物学上的应用更为自然而广泛。例如元胞自动机用于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索(Victor Jonathan.D., 1990)、爱滋病病毒HIV的感染过程(Sieburg, H.B., 1990)、自组织、自繁殖等生命现象的研究以及最新流行的克隆技术的研究等 (Ermentrout G..B., 1993)。 在信息学中，元胞自动机被用于研究信息的保存、传递、扩散的过程。Deutsch(1972)、Sternberg(1980)和Rosenfeld(1979)等人还将二维元胞自动机应用到图像处理和模式识别中 (WoIfram.S.，1983)。在计算机科学中。元胞自动机可以被看作是并行计算机而用于并行计算的研究(Wolfram.S.1983;Bandini,S.,2001)，还被用于计算机图形学的研究。

在算法研究中我们已经知道著名的遗传算法、神经网络算法等，并且元胞自动机的规则进化性甚至可以自我产生出优化算法，而机器学习中的一些算法已被运用于人工智能的研究。在数学中，元胞自动机可用来研究数论和并行计算。例如Fischer(1965)设计的素数过滤器(Prime Number Sieves)(Wolfram,S.1983)。而元胞自动机通过降低复杂性，来解决一些复杂性问题，如研究Langton的蚂蚁所表现的无法判定的复杂性问题(Gajardo, A., et al, 2002)。在物理学中。除了格子气元胞自动机在流体力学上的成功应用，它还被应用于磁场、电场等场的模拟，以及热扩散、热传导和机械波的模拟。在化学中，元胞自动机可用来通过模拟原子、分子等各种微观粒子在化学反应中的相互作用，从而研究化学反应的过程。在环境科学上，应用元胞自动机来模拟海上石油泄露后的油污扩散、工厂周围废水、废气的扩散等过程的模拟。在城市学上，元胞自动机也常被用来模拟城市变迁(Elena Besussi et al, 1998)。 在生态学中，元胞自动机成功地应用于蚂蚁、大雁、鱼类洄游等动物的群体行为的模拟，而基于元胞自动机模型的生物群落的扩散模拟也是当前的一个应用热点。

2.2 Swarm介绍 2.2.1 Swarm的背景

Swarm是复杂适应系统建立模型而设计的软件平台。1995 年SFI 发布了Swarm 的beta 版，此后，大约30个用户团体已经安装了Swarm并用它积极地开展建模工作，并完成了一定的论文。Swarm已经帮助提供了讨论模拟技术和方法论的焦点，还提供在特定的研究团体中模型组件和库的共享，这是智力交换的一个重要形式。最终，建立一个用于模型定义的形式化框架建立一个特定的用于实验科学工具的计算机程序的必要标准。 开发Swarm 的目的就是通过科学家和软件工程师的合作制造一个高效率的可信的可重用的软件实验仪器，它能给予科学家们一个标准的软件工具集，就象提供了一个设备精良的软件实验室帮助人们集中精力于研究工作而非制造工具。

Swarm 实际上是一组用Objective-C 语言写成的类库，这是一种面向对象的C 语言。一部分图形界面，如图表、按钮和窗口，是用TCLTK 描述的。Swarm 最初只能在Unix 操作系统和X Windows 界面下运行，1998 年四月伴随着 1 .1版的发