《主题材料-元胞自动机》由会员分享，可在线阅读，更多相关《主题材料-元胞自动机（17页珍藏版）》请在金锄头文库上搜索。
1、.建模3群消息记录元胞自动机是一个在数学建模中有用的工具。在这里，我们打算通过一些模型，来初步介绍元胞自动机的应用。使用计算机进行模拟往往在建模过程中有很大的用途，但凭空说“模拟真实世界”往往让人觉得难以下手。而元胞自动机则往往能给模拟方法提供一个容易思考的框架。考虑到大家在建模中的实用性，所以在介绍当中，我会尽量多做直观的介绍，尽量避免数学计算。详细的数学内容大家可以参照相关书籍。讲解中有一些图片或说法来源于书籍或网络。我们在讲解当中，除了一些直接用到元胞自动机的模型，也介绍了在元胞自动机的发展过程当中一些比较有影响力的内容。它们不一定对建模有直接的用途，但我希望大家对它的了解能够更广泛一些
2、，这样可能对它进行更灵活地运用。它的提出，最早是冯诺依曼在研究能够自我复制的自动机时提出来的。其特点是，空间被分成离散的格子（可以是方形、三角形或六边形等），称之为元胞（Cell）。元胞处于若干可能的状态之一，而且随着时间，其状态可以演化。每个元胞状态的演化，往往要受到临近元胞的状态的影响。而且，在传统的元胞自动机中，每个元胞的变化都是同时进行的。最著名的元胞自动机的例子，应属Conway提出的“生命游戏”。它的提出并不是为了具体的应用，但其蕴含的丰富内容引起了许多人的兴趣。假设二维空间被划分成方形的格子，当然每个格子都是一个元胞。假设每个元胞只处于两种状态之一：死的与活的。死的可以记为0，活
3、的可以记为1。现在我们来考察每个元胞周围的“邻居”。“邻居”的定义当然并不唯一，有时考虑的是它的上下左右的邻居（如果是三维空间，则还有前后），这被称为“冯诺依曼邻居”；有时考虑的是包围在它周围的全部邻居，被称为Moore邻居。在更高维的空间也可以有类似的定义。当然，也完全可以考虑其它类型的邻居，也可以包括更广的范围。在生命游戏中，考察每个元胞的Moore邻居。如果邻居中只有1个或者没有活的元胞，或者有4个以上活的元胞，那么这个元胞如果是活的，就变成死的（由于孤独或拥挤），如果本来是死的就不用变了。若邻居中有2或3个活的元胞，那么如果这个元胞是活的，可以继续存活。如果邻居中有3个活的元胞，而中间
4、的元胞现在是死的，那么可以再生。整个空间的初始的状态可以人为设计，也可以随机设定。随着时间的推移，每个元胞都或死或生，然而空间的整体却出现了非常复杂的状态演化。有一些活元胞组成的形状会稳定不动（例如四个活元胞排成田字形），而有一些则会周期性变化（例如三个活元胞排成一字形）。有一些活的元胞可以排列成能够整体运动的形态（称之为Slider，我们暂时翻译成滑翔机。）这就是所谓的“滑翔机”，在若干步以后，整体推移了一段距离。而有一些元胞的组合可以在自己的周期变化当中不断地发射出滑翔机，有一些可以在自己的周期当中“吃掉”滑翔机。更多的则是体现出复杂而难以捉摸的演化状态。活元胞的总数随时间的变化，总的来说
5、也无规律可循。看左端发射出的滑翔机序列，其间隔是无规则的。我们来看看在生命游戏当中常见的一些样子：大家可以自己手动演示一下，这些样子都会如何继续发展下去。Conway证明，生命游戏事实上等价于一个通用图灵机。通过选择不同的初始条件，可以完成一切计算机能够完成的算法演算。在这个证明的思路当中，“传输信息”的工作，便是用滑翔机来进行的。这个结果，事实上意味着生命游戏可以产生几乎无数的复杂现象。对它也有许多有趣的研究。对元胞自动机的系统研究，其实还是Wolfram在1983年开始进行的。Wolfram就是著名软件Mathematica以及Wolfram公司的创始人。他开始的时候，研究的是最基本的一维
6、情况。也就是空间是一维的，也就是所有元胞排列成一维的链条。每个元胞i具有两种可能的状态，0或1。而i的状态变化取决于它的左右两个“邻居”。我们可以用刚才的这个图来描述演化的规则。中间的元胞将随着自己和左右情况的不同，而演化成a7，a0等不同状态。把a7到a0都指定一个0或1的数字，也就确定了一套完整的演化规则。我们等于是用穷举法，把在一切情况下的演化结果，全部列举清楚了，就算是把演化规则完整确定出来了。我们还可以用图示的方法，举一个演化规则的例子。这个图中，每种情况都指定好了演化的结果。用图画出来，绿色代表1，黑色代表0。把这个数字“10000111”看成二进制的数字，化成十进制其实是135。
7、所以我们可以把这个规则命名为规则135。对一个初始状态来说，使用规则135来演化，随着时间，会变成什么样子？这是很容易用计算机程序验证的。我们可以把每一个时间步得到的结果画在上一步的下面，可以看到一些有趣的图案。规则13（你可以自己把13化成二进制，填在刚才讲“规则”的那个示意图里，看看这个规则具体说的是什么）从一个随机的初始状态开始，逐渐演化成一个稳定的状态而不再变化。请看实际的图案：图中没有画出元胞的方格边界。显明的竖线，是由于那个位置的元胞一直处于0或1，而产生的现象。规则56则有所不同。它大概会生成这样的图案：看似斜线的图样，意味着每过一个时间步，处于1的元胞的位置，向右推移一格（其实
8、处于0的元胞的位置，也同样向右推移了一格）。如果空间是无限的，那这就类似一种无限的“匀速运动”，而如果空间的右侧和左侧连成一个环，那这可以看成是一种周期性的演化。规则18则产生了比较奇怪的图案：这看起来像分形几何里的图案。用动力系统的术语来说，这种演化类似混沌的状态。如果从只有一个1的初始状态开始，结果就更清晰一些：这是个非常类似Sierpinski三角形的图案。更复杂的是规则110。我们连续看两个图，第一个是它在只有一个1的初始状态开始的，第二个是它在随机初始状态开始的：它体现出比混沌更复杂的规律。里面呈现出几大块区域，像打碎的玻璃。据说，110号规则等价于一个通用图灵机。可以说，一切计算机
9、所能做的计算工作，都可以通过110号规则配合适当的初始条件来做到。这个证明曾是保密的（现在不知公开了没有），而且据说和Mathematica里的一些保密算法有关。Wolfram对不同的规则，分成了四个种类。1：不动点。在这类规则下，元胞自动机在有限步的演化中，几乎全部的初始状态都会演化成稳定而不会改变的状态。 2：周期环：在这类规则下，几乎全部初始状态都演化成周期性改变的图形。 3：混沌：几乎全部的初始状态都演化成混沌的，非周期性的图形，而且往往具有自相似性。初始条件的微小变化往往导致若干步后的结果的显著不同。 4：复杂：可以产生持续不断的复杂结构，难以描述和预测。这个分类是经验的，并不能严格
10、地证明。对这种一维的元胞自动机有许多推广的研究，譬如可以考察更广范围的邻居，或者依某种概率参数来随机地决定演化结果。但是几乎所有的演化结果，都可以分到这四类的某一类之中。 这个分类是经验的，并不能严格地证明。对这种一维的元胞自动机有许多推广的研究，譬如可以考察更广范围的邻居，或者依某种概率参数来随机地决定演化结果。但是几乎所有的演化结果，都可以分到这四类的某一类之中。比如下面的图就是一个复杂一些的规则，考虑了距离为2的邻居。生成的结果也很有趣。图片14a下面这个图演示了更复杂一些的规则，不仅考虑了距离为2的邻居，而且元胞可以处于三种状态（用不同颜色区分）。对一些呈现出“复杂”状态的规则而言，甚
11、至人们并不能确信，是否在足够多步以后，它们会变成别的状态，例如不动点？Wolfram写了一本书，叫做ANewKindofScience。是专讲元胞自动机的各种应用。里面的研究包括海螺的花纹，包括交通流的性质，包括金融市场的“内在”随机性，等等。大家有兴趣可以去看，有专门的网站，可以看电子版。也可以下载得到。在此我们还可以专门提一下，二维的元胞自动机，更可能在很简单的规则下，产生出奇怪的结果来。最简单的恐怕就是ChrisLangton和GregTurk提出的“蚂蚁”了。顺便说一下，他是SFI（SantaFeInstitute）的成员。SFI是对研究复杂系统的很领先的研究机构，包括复杂系统的动力学
12、，对社会和金融市场的模拟和研究、人工智能等问题都有很前沿的研究工作。官方网站是www.santafe.edu，大家有兴趣的话可以去看。我们来看这个最简单的蚂蚁自动机。曾有篇著名论文，题目叫做二维图灵机，专门讲了这个例子。假设一个“蚂蚁”在平面的方形网格中爬行，每个格子有两个状态：白色或黑色。蚂蚁爬进一个白色的格子时，就左转90度，并且把这个格子改成黑色。蚂蚁爬进一个黑色的格子时，就右转90度，并且把这个格子改成白色。最初时，整个“世界”都是白色的。我们可以预测一下，这个蚂蚁会如何运动？很简单的规则，很简单的初始条件。但情况却是意想不到的复杂。这个图是不到100步的时候，蚂蚁留下的图案：图里红色
13、箭头就是蚂蚁。黑白色的格子是现在的世界的样子。下面是接近400步的时候，蚂蚁留下的图案（没有画元胞的边界线）：这个蚂蚁画得太大了，挡住了中间的几个元胞，不过不影响大局。在大概500步以内，它不时地回到原点，留下中心对称的图案。但随后开始出现奇怪的现象，请看下图，大概是四千步的状态：在从500步左右开始，直到接近11000步，它的图案完全失去了对称性，并且变得乱七八糟。再看继续的图，大约10000步的时候：我们看到，在10000步左右，它的运动突然开始出现了规律。再往下：每过104步，蚂蚁的位置向左下方推移一“节”。这种现象有时被叫做“公路”。其实可以通过一个很简单而巧妙的分析，证明蚂蚁的轨道必
14、然是无界的。这个证明我这次不多说了，大家也可以试试（提示：反证法）。而且蚂蚁的轨道无论多么复杂，把时间倒转过来，都是完全可逆的。在平面上如果存在两只或多只蚂蚁，情况会变得非常复杂。随着两只蚂蚁的初始位置不同，情况会不同，但多数情况下，蚂蚁都会通过建造“公路”的方式远离，但有时也会出现周期很大的周期轨道。也就是过几万步之后，居然能够完全回到初始状态。对此类问题的研究也有很多。以上讲的是比较传统的元胞自动机例子。对它的研究虽然有许多，但总的来说，如果直接用它来对付实际问题，其思路不是很容易理解，也不是很容易推广。即使是Wolfram的那本A New Kind of Science，也有许多批评的声
15、音。但元胞自动机的计算机实验非常好做，有一个开源软件Netlogo，也可以简单地做一些可视化的演示。我在上面的蚂蚁等图案都是用Netlogo生成的。而下面我们要讲的，则是一种容易理解的元胞自动机。它来源于对实际问题的模拟，有时被称为格子气自动机，LGA（Lattice Gas Automata）。LGA是为了进行流体力学的计算而发展的离散方法。假设流体是由许多颗粒组成的，而不是连续的。再假设每个颗粒都在网格上运动，而不是在连续的空间中。而且时间也是离散的。如图20所示。粒子就从一个格点运动（其实说成跳跃也可以）到另一个格点，其间它们可能碰撞。从这个角度上看，这个设定完全符合元胞自动机的定义。每
16、个元胞就是空间的网格，状态有“被粒子占据”或“不被粒子占据”两种（其实更精确地说，粒子的运动方向也是要说到的）。这里的关键是粒子的运动规则。在简单的问题中（譬如静态气体中的扩散），甚至完全不需要考虑粒子的速度，只需要考虑运动方向就够了。首先，其碰撞的规则必须是一种“变换”。如果所有粒子匀速运动并可以互相穿过，这就体现不出来流体的“流动”了。所以在粒子碰撞的时候，其运动方向应发生变化。但这同时要保持质量守恒和动量守恒。在正方形网格的假设下，最简单的规则就是HPP规则：如果还要考虑到气体是在容器里的，容器壁对气体分子还要有一个反射的规则。这就不赘述了。HPP规则已经能体现出和真实气流很类似的运动趋势了。譬
