论文 元胞自动机的研究进展

摘要：元胞自动机是一种利用简单编码与仿细胞繁殖机制的非数值算法空间分析模式，可以说是一种动态模型，也可以说是一种算法。它可以演示出许多纷繁复杂的行为。元胞自动机近年来引起了研究者们的追捧，元胞自动机算法由于其优点已成为目前世界上备受关注的算法之一。本文综述了元胞自动机的研究进展，相关研究理论方法及其在不同领域的广泛应用。 关键词：元胞自动机 MATLAB实现 相关理论方法 元胞自动机的应用

1.引言

元胞自动机(cellular automaton)简称CA，也有人译为细胞自动机、点格自动机、分子自动机或格子气自动机。不同的领域翻译出来的名称都带有各自领域的特色。

元胞自动机可以说是由许许多多网格组成的，每一个网格中的一个单元就代表着一个元胞，而这些元胞遵循同样的转换规则，所有的元胞进行同步转换，同步更新。大量元胞通过彼此之间的相互作用，形成动态系统，进行复杂的演化状态。所以我们简单的说元胞自动机模型就是在一定的转换规则下的动态系统。本文主要讲到元胞自动机的研究进展，相关研究理论方法及其的应用。

2.元胞自动机的研究及其组成

元胞自动机的起源需要追溯到上世纪40年代，计算机之父-----约翰·冯·诺依曼（John Von Neumann）在设计可以自我进行复制的自动机时，他参照了生物体细胞的自我繁殖机制，提出来元胞自动机的概念及计算机模型。20世纪70年代，Conway 的“生命”游戏引发了元胞自动机的研究热潮。在此期间，人们发现了元胞自动机的自组织机制。在众多研究者的努力下，到目前随着元胞自动机及其相关的研究不断深入，从简单到复杂，从一维元胞自动机到二维、三维元胞自动机，从计算机对一定规则的游戏的实现，到现实生活中实例的模拟，元胞自动机为实际问题的分析研究提供了很好的工具。元胞自动机是由元胞，元胞空间，邻居及转换规则组成。其中最基本的单位也就是元胞，元胞位于一维，二维及多维的网格点上，元胞所分布的网格点的集合就成为元胞空间。其中一维空间和二维空间是目前研究的重点。 一维空间只有一种形式，我们称为一维状态链。对于二维空间可以有很多种形式，可以有三角形，四边形等多种网格排列。由于元胞空间理论上是无限的，但是实际应用当中我们就要定义不同的边界条件。根据不同的情况我们定义不同的边界条件，一般有：定值型，反射型和周期型三种，当然有时候我们也需要定义随机型边界。

在演化规则加入静态系统后就开始动态演化，那么一个元胞的状态和其邻居元胞的状态根据演化规则就决定了其下一时刻的状态。所以说定义邻居规则同样重要，我们必须搞清楚一个元胞的邻居是怎样的。一维的

在一维元胞自动机的研究方面，Wolfram和Willson等人作出了杰出的贡献。Wolfram详细研究了r=1,k=2（r表示步长， k表示状态数）的256种一维元胞自动机。这种元胞自动机是在一维状态链上，将演化规则的半径取为r，对包括自身共3个近邻的每个近邻的状态数设为2，得到这3个近邻可取的23=8种排列，下一时刻，每一种排列又可取2个不同的值，于是得到28=256个不同的元胞自动机。从随机初试状态出发，Wolfram通过计算机对所有的256种一维元胞自动机进行研究发现，这些元胞自动机长期演化后，得到下列四种状态：均匀、循环、混沌和更为复杂的结构 。Wolfram还发现了当k取定值2时，元胞自动机的数目随r（一维情况）和z（二维情况）的增大而急剧增大，其中r为一维情况下的半径，z为二维情况下的邻域中格座数。Willson则构造了这样一个一维分形元胞自动机，即令多项式qt (s)=(1+s)t（系数数目随t不断增大）的系数取0或1（系数为偶数取0，为奇数取1），且用空白表示0，用黑点表示1，得到了Sierpinski分形三角地毯。另外，Fehsenfeld等研究了生命游戏相关构形的演化中的标度律，Botelho等研究了基于一维元胞自动机演化图形的随机行走。

二维或三维元胞自动机可以用来模拟实际中的生存和流动等过程，如晶体生长、颗粒凝聚、湍流形成等。

对于圆周元胞自动机的研究，一般的文献中仅对步长为1的情况进行了研究。本文对圆周元胞自动机进行了扩展，在此基础上，提出了方形元胞自动机的概念并对其进行一定的分析和计算，得出一些结论。