元胞自动机简介


本文转自： http://www.sciencenet.cn/m/user_content.aspx?id=41096

元胞自动机

元胞自动机(Cellular Automata，简称CA)是 一种时空离散的局部动力学模型，是复杂系统研究的一个典型方法，特别适合用于空间复杂系统的时空动态模拟研究。不同于一般的动力学模型，元胞自动机不是由 严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总 称，或者说是一个方法框架。在这一模型中，散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。

上世纪50 年代，冯·诺伊曼提出了元胞自动机的概念。从此，由元胞自动机来构造具有生命特征的机器成为科学界的一个新的方向，而对元胞自动机理论本身的研究开始逐步展开。 从不同领域的视角来看，元胞自动机有着不同的定义。

从物理学视角来看：元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上进行演化的动力学系统。

      从生物学视角来看：以生物学或者人工生命的角度来看，元胞自动机可以视为一个让许多单细胞生物生活的世界，在我们设定好这个世界的初始状态和进化规则之后，这些单细胞生物便依据规则在离散的时间步上进行演化。

从数学视角来看：标准的元胞自动机是一个四元组 : A=(L, S, N, f)，这里A代表一个元胞自动机系统；L表示元胞空间，d是一正整数，表示元胞空间的维数；S是元胞的有限的、离散的状态集合；N表示一个邻域内所有元胞的组合，即包含n个不同元胞状态的一个空间矢量，记为:N=(s₁,s₂,...,s_n)，其中 s_i∈S，i∈{1，...,n}；f 表示将 S 映射到 S 上的一个局部转换函数。所有的元胞位于d维空间上，其位置可用一个d元的整数矩阵Z 来确定。

从 计算视角来看：显然，元胞自动机每一个元胞的状态变化都是一种计算。我们可以把每一个元胞都看作一台计算机，这样元胞自动机就是一种计算模型。元胞自动机 每个元胞的变化是同步进行的，也就是对信息的处理是同步进行的，特别适合于并行计算。元胞自动机可能是下一代并行计算机的雏形。

从 动力学视角来看：元胞自动机可以视为离散动力系统中的一种自动器网络模型。离散动态系统中自动器网络模型的基本结构可用图论中的图来表示，它由若干结点及 连接这些结点的边而构成，但在自动器组成的复杂网络模型中，我们还可引入不同层次的动力学，即每个结点表示一个子系统，它们有各自的动态行为，结点之间的 连接强度也可能发生变化，由此反映元素间作用关系的变化。每个结点（或元素）都可以看作是一个自动器，这些连接起来的自动器组成了自动器网络。若干自动器 （automation）叫作自动机（automata）。                如果一个自动器网络具有规则的晶格结构，每个元素是完全一样的有限自动器（相同的局部连接即输入集和输出函数相同），且元素间的联接强度为常数，这样的自动器网络称为“元胞自动机”。 若自动器网络的元素是一布尔自动器（状态为0和1）且状态函数为布尔开关函数，元素间联接强度不变，则我们得到“布尔网络”。 当元素间联接强度可随时间变化时，网络的行为就变得更复杂，这将是“神经网络”要讨论的问题。复杂系统理论中研究的这些自动器网络模型的共同特点在于： 涉及的元素数量较大；元素间局部联接；系统总体体现了鲜明的涌现性。

标准元胞自动机具有如下特征：

1、同质性：在元胞空间内的每个元胞的变化都服从相同的规律，所有元胞均受同样的规则所支配。

2、齐性：元胞的分布方式相同，大小、形状相同，地位平等，空间分布规则整齐。

空间离散:元胞分布在按照一定规则划分的离散的元胞空间上。

3、时间离散:系统的演化是按照等间隔时间分步进行的，时间变量t只能取等步长的时刻点。

4、状态离散且有限：元胞自动器的状态只能取有限个离散值，在实际应用中，往往需要将有些连续变量进行离散化，如分类、分级，以便于建立元胞自动机模型。

5、并行性：各个元胞的在每个时刻的状态变化是独立的行为，相互没有任何影响。

6、时空局部性:每一个元胞的下一时刻的状态，取决于其邻域中所有元胞的状态，而不是全体元胞。从信息传输的角度来看，元胞自动机中信息的传递速度是有限的。

7、维数高:在 动力系统中一般将变量的个数成为维数。例如，将区间映射生成的动力系统称为一维动力系统；将平面映射生成的动力系统称为二维动力系统；对于偏微分方程描述 的动力系统则称为无穷维动力系统。从这个角度来看，由于任何完备元胞自动机的元胞空间是定义在一维、二维或多维空间上的无限集，每个元胞的状态便是这个动 力学系统的变量。因此，元胞自动机是一类无穷维动力系统。在具体应用中或计算机模拟时当然不可能处理无限个变量，但一般也总是处理数量很大的元胞组成的系 统。因此可以说维数高是元胞自动机研究中的一个特点。

在上述特征中，同质性、并行性、局部性是元胞自动机的核心特征，任何对元胞自动机的扩展应当尽量保持这些核心特征，尤其是局部性特征。

魏一鸣和范英研究员，他们是我的博士论文指导老师，在CA领域做了不少工作。其中魏一鸣老师是国内较早地将CA应用于自然灾害和金融市场领域研究的研究 者；范英老师在金融市场的元胞自动机仿真方面做得非常出色，她的相应研究课题在自然科学基金委结题拿到了“特优”的评价，这是非常不简单的。

如果进一步对于CA理论发生了兴趣，可以检索STEPHEN WOLFRAM的工作，他是CA理论研究的集大成者，是自VON NEUMANN以来在CA领域最重要的理论奠基人。他有相应的官方学术网页：

http://www.stephenwolfram.com/publications/articles/ca/

上面有很多论文可供下载学习。

CA是时间、空间和状态都离散的一种经典动力学模型，自Von Neumann和Wolfram后，一直在物理、数学、计算机算法、自动机理论乃至社会经济领域的研究产生重大的作用。您所说的“发酵罐中微生物群体生命 活动的动力学”我不懂，不敢置评。但就我所读的一些文献看，在很多领域如城市增长、交通流、自然灾害、金融市场等等领域都有很多很好的研究。

吴裕祥的相关论述，生动，有启发。介绍Wolfram。

http://blog.china.com.cn/yuxiangwu/art/126171.html

http://blog.china.com.cn/yuxiangwu/art/126424.html

转载本文请联系原作者获取授权，同时请注明本文来自任鹏举科学网博客。
链接地址：https://blog.sciencenet.cn/blog-111458-281154.html

上一篇：audacity使用小结
下一篇：linux 配置 gview