专题：元胞自动机.docVIP

建模3群消息记录 元胞自动机是一个在数学建模中有用的工具。在这里，我们打算通过一些模型，来初步介绍元胞自动机的应用。使用计算机进行模拟往往在建模过程中有很大的用途，但凭空说“模拟真实世界”往往让人觉得难以下手。而元胞自动机则往往能给模拟方法提供一个容易思考的框架。 考虑到大家在建模中的实用性，所以在介绍当中，我会尽量多做直观的介绍，尽量避免数学计算。详细的数学内容大家可以参照相关书籍。讲解中有一些图片或说法来源于书籍或网络。 我们在讲解当中，除了一些直接用到元胞自动机的模型，也介绍了在元胞自动机的发展过程当中一些比较有影响力的内容。它们不一定对建模有直接的用途，但我希望大家对它的了解能够更广泛一些，这样可能对它进行更灵活地运用。 它的提出，最早是冯?诺依曼在研究能够自我复制的自动机时提出来的。其特点是，空间被分成离散的格子（可以是方形、三角形或六边形等），称之为元胞（Cell）。元胞处于若干可能的状态之一，而且随着时间，其状态可以演化。每个元胞状态的演化，往往要受到临近元胞的状态的影响。而且，在传统的元胞自动机中，每个元胞的变化都是同时进行的。 最著名的元胞自动机的例子，应属Conway提出的“生命游戏”。它的提出并不是为了具体的应用，但其蕴含的丰富内容引起了许多人的兴趣。假设二维空间被划分成方形的格子，当然每个格子都是一个元胞。假设每个元胞只处于两种状态之一：死的与活的。死的可以记为0，活的可以记为1。 现在我们来考察每个元胞周围的“邻居”。“邻居”的定义当然并不唯一，有时考虑的是它的上下左右的邻居（如果是三维空间，则还有前后），这被称为“冯?诺依曼邻居”；有时考虑的是包围在它周围的全部邻居，被称为Moore邻居。在更高维的空间也可以有类似的定义。当然，也完全可以考虑其它类型的邻居，也可以包括更广的范围。 在生命游戏中，考察每个元胞的Moore邻居。如果邻居中只有1个或者没有活的元胞，或者有4个以上活的元胞，那么这个元胞如果是活的，就变成死的（由于孤独或拥挤），如果本来是死的就不用变了。若邻居中有2或3个活的元胞，那么如果这个元胞是活的，可以继续存活。如果邻居中有3个活的元胞，而中间的元胞现在是死的，那么可以再生。 整个空间的初始的状态可以人为设计，也可以随机设定。随着时间的推移，每个元胞都或死或生，然而空间的整体却出现了非常复杂的状态演化。有一些活元胞组成的形状会稳定不动（例如四个活元胞排成田字形），而有一些则会周期性变化（例如三个活元胞排成一字形）。有一些活的元胞可以排列成能够整体运动的形态（称之为Slider，我们暂时翻译成滑翔机。） 这就是所谓的“滑翔机”，在若干步以后，整体推移了一段距离。而有一些元胞的组合可以在自己的周期变化当中不断地发射出滑翔机，有一些可以在自己的周期当中“吃掉”滑翔机。更多的则是体现出复杂而难以捉摸的演化状态。活元胞的总数随时间的变化，总的来说也无规律可循。看左端发射出的滑翔机序列，其间隔是无规则的。我们来看看在生命游戏当中常见的一些样子： 大家可以自己手动演示一下，这些样子都会如何继续发展下去。Conway证明，生命游戏事实上等价于一个通用图灵机。通过选择不同的初始条件，可以完成一切计算机能够完成的算法演算。在这个证明的思路当中，“传输信息”的工作，便是用滑翔机来进行的。这个结果，事实上意味着生命游戏可以产生几乎无数的复杂现象。对它也有许多有趣的研究。对元胞自动机的系统研究，其实还是Wolfram在1983年开始进行的。Wolfram就是著名软件Mathematica以及Wolfram公司的创始人。他开始的时候，研究的是最基本的一维情况。也就是空间是一维的，也就是所有元胞排列成一维的链条。每个元胞i具有两种可能的状态，0或1。而i的状态变化取决于它的左右两个“邻居”。我们可以用刚才的这个图来描述演化的规则。中间的元胞将随着自己和左右情况的不同，而演化成a7，…，a0等不同状态。把a7到a0都指定一个0或1的数字，也就确定了一套完整的演化规则。我们等于是用穷举法，把在一切情况下的演化结果，全部列举清楚了，就算是把演化规则完整确定出来了。我们还可以用图示的方法，举一个演化规则的例子。这个图中，每种情况都指定好了演化的结果。用图画出来，绿色代表1，黑色代表0。把这个数字看成二进制的数字，化成十进制其实是135。所以我们可以把这个规则命名为规则135。对一个初始状态来说，使用规则135来演化，随着时间，会变成什么样子？这是很容易用计算机程序验证的。我们可以把每一个时间步得到的结果画在上一步的下面，可以看到一些有趣的图案。规则13（你可以自己把13化成二进制，填在刚才讲“规则”的那个示意图里，看看这个规则具体说的是什么）从一个随机的初始状态开始，逐渐演化成一个