7月18日元胞自动机解析

元胞自动机简介及其应用0.绪论关于《一种新科学》元胞自动机本来是现代计算机之父--冯·诺伊曼（VonNeumann）及其追随者提出的想法，但是沃尔弗拉姆却将这种带有强烈的纯游戏色彩的原始想法从学术上加以分类整理，并使之最终上升到了科学方法论。元胞自动机的基础就在于“如果让计算机反复地计算极其简单的运算法则，那么就可以使之发展成为异常复杂的模型，并可以解释自然界中的所有现象”的观点。八十年代这一理论成了人们议论的话题，比如“雪花的结晶”、“海螺的图案”或者“基于相对论的扭曲时空”等自然界的各种各样的模型都确实可以由这种“反复计算”而生成，这一切不断地证明了沃尔弗拉姆的观点。但是他的观点当时却被科学界中的主流斥为“异端”。根据《一种新科学》中的观点，认为截止到目前数千年来发展而成的全部科学，从某种意义上讲，依赖的是一种完全无法预测的方法。从物理学、化学、生物学到心理学，甚至各种社会学等现有学术领域本来就不应该进行如此分类。这些科学领域中的各种各样的现象，说到底实际上都在受同一种运算法则的支配，利用各种方法对此反复计算就可以生成各种领域的复杂现象。沃尔弗拉姆认为“支持整个宇宙的原理无非就是区区几行程序代码”。从“完全打破现有的学术体系，按照完全不同的原理来理解自然界”的意义出发，新作被命名为《一种新科学》。也可以把沃尔弗拉姆的观点称作是计算机万能理论。以物理学和数学为中心的传统科学是以方程式为基础而演绎推导出来的，但是在元胞自动机方面，则是通过反复计算单纯的程序代码，也可以说是递归推导而出的。在牛顿生活的17世纪的时候，由于还没有像现在一样的先进计算机，因此当时的科学家还不得不依赖于演绎的方法（算式计算）。这一切也可以说是历史上的必然、科学上的偶然。沃尔弗拉姆认为：真正意义上的正确的科学方法是利用像现有那样的计算机来进行的算法运算元胞自动机元胞自动机是探索复杂系统中局部—整体互动关系的最简单模式，视为演化分析的基本计算模型；物理学：一个离散的无穷维的动力学系统数学：一个时空离散的数学模型，描述连续对象的偏微分方程的对立体计算机科学：新兴的人工智能、人工生命的分支生物学：生命现象的一种描述元胞自动机是一种复杂的动力学系统。利用其简单、局部的规则可以模拟复杂的现象以及一些非线性系统的动力演化过程。Mirek’sCellebration软件，是一个功能很强的元胞自动机模拟软件。但它不能很方便的对用户自定义的规则进行模拟，并分析自定义规则的演化过程。元胞自动机应用•应用范围：•元胞自动机应用于人工生命研究、•混沌的边缘、•微分方程、•分形分维、•马尔科夫(链)过程、•随机行走模型、•凝聚扩散模型、•多主体系统、•系统动力学模型等。一.元胞自动机的定义及构成元胞自动机定义•元胞自动机(CellularAutomata，简称CA，也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。•元胞自动机是21世纪科学研究中一个异常活跃的前沿领域,是复杂性科学的核心技术之一。它体现了整体辩证思想:用简单的局域相互作用表现复杂系统的整体行为及其时间演化。•元胞自动机有三个显著的特点,即大规模同步并行、局域相互作用和结构简单。这些特点使其能高效地模拟许多复杂现象。元胞自动机的构成元胞自动机最基本的组成:元胞、元胞空间、邻居及规则四部分。简单讲，元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。元胞自动机的构成1.元胞元胞自动机的最基本组成部分。它分布在离散的一维、二维或多维欧几里德空间的晶格点上。2.状态状态可以是{0,1}的二进制形式，或是{s0,s1,s2,…，si}整数形式的离散集。严格意义上，元胞只能有一个状态变量，但在实际应用中，往往将其进行扩展。3.元胞空间元胞所分布在的空间网点集合就是元胞空间A、元胞空间的几何划分任意维数的欧几里德空间规则划分。对于一维元胞自动机，元胞空间划分只有一种。而高维的元胞自动机，元胞空间的划分则可能有多种形式。对于常见的二维自动机，元胞空间通常可按三角形、四边形或六边形三种网格排列。TriangleSquareHexagon三角网格拥有较少的邻居数目，这在某些时候很有用。缺点是计算机的表达与显示不方便。四边形网格直观简单，特别适合于计算机环境下进行表达显示。六边形网格能较好的模拟各向同性的现象，因此，模型能更加自然而真实。其缺点同正三角网格一样，在表达显示上较为困难和复杂。B、边界条件理论上，元胞空间在各个维向上是无限延展的。实际应用过程中，无法在计算机上实现这一理想条件。C、构形在某个时刻，在元胞空间上所有元胞状态的空间分布组合。在数学上，它通常可以表示为一个多维的整数矩阵。邻居、元胞和元胞空间只表示了系统的静态成分，为了将动态引入系统，必须加入演化规则。这些规则是定义在局部空间范围内的，即一个元胞下一时刻的状态决定于本身的状态和它的邻居元胞的状态。因此，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。一维元胞自动机中，通常以半径r来确定邻居，距离一个元胞r内的所有元胞都属于该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有以下几种（以正方形网格为例）规则根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是状态转移函数。这个函数构造了一种简单的离散的时间和空间范围的局部物理成分。状态的变化可以由状态转移函数表示：f:stt+1=f(sit,……，stN)stN为t时刻的邻居状态组合时间元胞自动机是一个动态系统，它在时间维上的变化是离散的，即时间t是一个整数值，而且连续且等间距。在上述转换函数中，一个元胞在t+1时刻的状态只直接决定于t时刻的该元胞及其邻居的状态。元胞自动机特性•把一个空间划分成网络，每一个点表示一个元胞，它们的状态赋值，在网格中用颜色的变化来表示，在事先设定的规则下，元胞的演化就用网格颜色的变化来描述，这样的模型就是元胞自动机。•通过对元胞自动机这些网络中的格点的不同定义，以及初始条件的不同，可以模拟出不同的现象和过程。•元胞自动机的基本特征：离散性：元胞自动机是高度离散的。它不仅仅空间离散时间离散，而且在函数值，即元胞的状态值也是离散的。动力学演化的同步性：元胞自动机具有利用简单的，局部规则的和离散的方法，描述复杂的，全部的和连续系统的能力。相互作用的局部性：元胞自动机的规则是局部的，而动力学行为规则是全局的，在模拟的过程中，具体的演化过程也是局部的，即仅同周围的元胞有关系。元胞自动机应用的思想复杂系统又称为非线性系统。如城市的发展与演化、城市人流与交通流以及交通堵塞的形成、自然环境下的动物的空间分布、河网的形成、疾病的传播等。传统的自顶向下的分析方法是把系统分割成几个部分，对每一个部分逐个进行研究。而目前提出来的分析复杂动态系统的思想：自底向上的研究方法。基于个体的自底向上的研究方法：程序的行为完全由它的内部机制决定，通常将个体与程序相连，所模拟的复杂现象包括许多个体。在计算机里生成一个与真实世界对等的虚拟的人工世界，通常这个虚拟的世界包括许多个体，而这许多个体的行为呈现为复杂性。以此来探讨微观的个体行为和宏观复杂性之间的关系。二.常用元胞自动机1.初等元胞自动机初等元胞自动机(ElementaryCellularAutomata，简称ECA)。其状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径r=l的一维元胞自动机(谢惠民，1994、李才伟，1997、Wolfram，S，1986)。它几乎是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要，它可取{0，1}，{-l，1}，{静止，运动}，{黑，白}，{生，死}等等，这里重要的是S所含的符号个数，通常我们将其记为{0，1}。此时，邻居集N的个数2r=2，局部映射f:S3→S可记为:其中变量有三个，每个变量取两个状态值，那么就有2×2×2=8种组合，只要给出在这八个自变量组合上的值，f就完全确定了。例如以下映射便是其中的一个规则:规则:01001100通常这种规则也可表示为以下图形方式(黑色方块代表l，白色方块代表0):——简单的演化算法演示现假设有一个一维元胞自动机(由25个格点组成)的初始状态为：0000000000001000000000000演化规则:Si(t+1)=Si-1(t)+Si+1(t)，则：模拟20步后模拟40步后模拟80步后2.二维元胞自动机2.1J.Conway和生命游戏下面介绍生命游戏的构成及规则:(1)元胞分布在规则划分的网格上；(2)元胞具有0，1两种状态，0代表“死”，1代表“生”；(3)元胞以相邻的8个元胞为邻居。即Moore邻居形式；(4)一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态(确切讲是状态的和)决定:在当前时刻，如果一个元胞状态为“生”，且八个相邻元胞中有两个或三个的状态为“生”，则在下--时刻该元胞继续保持为“生”，否则“死”去；在当前时刻，如果一个元胞状态为“死”，且八个相邻元胞中正好有三个为“生”，则该元胞在下一时刻复活。否则保持为死。从数学模型的角度看，该模型将平面划分成方格棋盘，每个方格代表一个元胞。元胞状态:0-死亡，1-活着领域半径:1领域类型：Moore型演化规则修改为:元胞自动机是一个不可逆的离散动力系统2.2元胞自动机模拟软件简介状况：由于元胞自动机的鲜明特点，现在，对元胞自动的研究越来越广泛，并在这方面做了大量的工作。但有的是针对某一个CA规则和模型而研究；有的是针对某一个特殊的应用领域所做的研究。特别是Mirek’sCellebration软件，是一个功能很强的元胞自动机模拟软件。在这个模拟软件中，包容了很多的CA规则，并通过程序对这些规则进行了模拟，可以设置模拟的视屏，选择模拟时的颜色，查看规则的定义，观察运行时0和1的变化等等。缺陷：但这个软件是用程序来定义规则，一个模型规则就有一个程序，然后选择这些规则并进行模拟。如果要对CA规则进行修改、添加等操作，就必须去修改添加程序。2.3一些常见的应用元胞自动机对交通流的模拟城市动态演化模拟材料组织结构变化模拟元胞自动机在地理时空动态模拟元胞自动机对网络流的模拟元胞自动机对森林火灾模拟元胞空间:正方形网格元胞状态:0代表无森林覆盖；1代表未燃森林；21代表刚刚点燃的森林；22代表正在燃烧并且火势旺盛的森林；23代表正在燃烧但是已经接近熄灭的森林3代表已经燃烧过的森林。邻居:采用标准的Moore邻居类型，即每个元胞以其8个相邻元胞作为邻居元胞。转换函数A.ifni,j(t)=0or3,thenni,j(t+1)=ni,j(t);B.Ifni,j(t)=21,thenifRti,j=Rt1i,j,thenni,j(t+1)=22;otherwiseni,j(t+1)=21,Rti,j=Rti,j+1ifni,j(t)=22,thenifRti,j=Rt1i,j+Rt2i,j,thenni,j(t+1)=23;otherwiseni,j(t+1)=22,Rti,j=Rti,j+1ifni,j(t)=23,thenifRti,j=Rt1i,j+Rt2i,j+Rt3i,jthenni,j(t+1)=3;otherwiseni,j(t+1)=23,Rti,j=Rti,j+1ifni,j(t)=1,n’(t)=22,n’€Ω,Ω为元胞的邻居集合计算该单元被邻居火点点燃的可能性：即计算当前单元邻居中，元胞状态为22的各个元胞（共k个，1=k=8）点燃周围森林的可能性矢量Pk。3元胞自动机的演化行为的统计特征3元胞自动机的演化行为的统计特征•Wolfram将元胞自动机的演化行为归纳为四大类：I、平稳型（homogeneous）：自任何初始状态开始，经过一定时间演化后，经过若干步运算便停留在一个固定的状态。II、周期型(periodic)：经过一定时间演化后，在几种状态之间周期循环。III、混沌型(chaos)：自任何初始状态开始，经过一定时间演化后，处于一种完全无序随机的状态，几