元胞自动机简介元胞自动机简介（CellularAutomata）元胞自动机元胞自动机(Cellular Automata)(Cellular Automata)简要发展历程简要发展历程元胞自动机是定义在一个由离散、有限状态的元胞组成的元胞空间上，按照元胞自动机是定义在一个由离散、有限状态的元胞组成的元胞空间上，按照一定的局部规则，在离散时间维度上演化的动力学系统。一定的局部规则，在离散时间维度上演化的动力学系统。冯诺依曼提出模仿人脑的行为，人脑包含自控制和自维护机理。考虑在完全冯诺依曼提出模仿人脑的行为，人脑包含自控制和自维护机理。考虑在完全离散的框架下处理，每个元胞都具有内在的状态，由有限数量的信息为组成；离散的框架下处理，每个元胞都具有内在的状态，由有限数量的信息为组成；这个元胞系统按照离散时间进行演化这个元胞系统按照离散时间进行演化19701970年数学家年数学家ConwayConway提出了著名的生命游戏提出了著名的生命游戏(Game of life)(Game of life)。尽管生命游戏。尽管生命游戏的规则简单，但具有出乎预料的复杂行为的规则简单，但具有出乎预料的复杂行为WolframWolfram著名的物理学家，他在研究一维和二维元胞自动机，注意到，元胞著名的物理学家，他在研究一维和二维元胞自动机，注意到，元胞自动机是一个离散的动力学系统，但显现出许多连续系统中遇到的行为。自动机是一个离散的动力学系统，但显现出许多连续系统中遇到的行为。20022002年年一种新科学一种新科学，对自然选择提出挑战，对时间单向流逝，怎样制造，对自然选择提出挑战，对时间单向流逝，怎样制造人造生命，股市如何涨落给出了解释；探索了树叶、数目、贝壳为什么是其人造生命，股市如何涨落给出了解释；探索了树叶、数目、贝壳为什么是其形状；在其新科学的到统一解释，即元胞自动机形状；在其新科学的到统一解释，即元胞自动机生物学、生态学（兔子生物学、生态学（兔子- -草），物理学（流体力学、场的模拟）、化学（各草），物理学（流体力学、场的模拟）、化学（各种粒子在化学反应中的相互作用）、交通科学等种粒子在化学反应中的相互作用）、交通科学等一、元胞自动机的定义、构成和特征一、元胞自动机的定义、构成和特征1 1 定义定义 (1) (1) 物理学的定义物理学的定义元胞自动机是定义在一个由具有离散、有限状态的元胞组元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。化的动力学系统。一、元胞自动机的定义、构成和特征一、元胞自动机的定义、构成和特征1 1 元胞自动机的定义元胞自动机的定义 (2)(2)数学定义数学定义( (基于集合论的定义基于集合论的定义)设设d代表空间维数，代表空间维数，k代表元胞的状态，并在一个有限集合代表元胞的状态，并在一个有限集合S中取值，中取值，r表元胞的邻居半径。表元胞的邻居半径。Z是整数集，表示一维空间，是整数集，表示一维空间，t代表时间。代表时间。为叙述和理解上简单起见，在一维空间上考虑元胞自动机，为叙述和理解上简单起见，在一维空间上考虑元胞自动机，即假定即假定d=1。那么整个元胞空间就是在一维空间，将整数集。那么整个元胞空间就是在一维空间，将整数集Z上的状态集上的状态集S的分布，记为的分布，记为SZ。元胞自动机的动态演化就是在。元胞自动机的动态演化就是在时间上状态组合的变化，可以记为时间上状态组合的变化，可以记为:这个动态演化又由各个元胞的局部演化规则这个动态演化又由各个元胞的局部演化规则f所决定的。这所决定的。这个局部函数个局部函数f通常又常常被称为局部规则。对于一维空间，元通常又常常被称为局部规则。对于一维空间，元胞及其邻居可以记为胞及其邻居可以记为S2r+1，局部函数则可以记为，局部函数则可以记为:F(Sit+1)=f(sti-r,sti,sti+r)sti表示在表示在t时刻位置时刻位置i处的元胞，至此，我们就得到了一个处的元胞，至此，我们就得到了一个元胞自动机模型元胞自动机模型对于局部规则对于局部规则f来讲，函数的输入、输出集均为有限集合，来讲，函数的输入、输出集均为有限集合，实际上。它是一个有限的参照表。例如，实际上。它是一个有限的参照表。例如，r=1，f的形式则形似的形式则形似如下如下:0,0,0-O;0,0,1-0;0,1,0-1;1,0,0-0;0,1,1-1;1,0,1-0;1,1,0-0;1,1,1-0对元胞空间内的元胞，独立对元胞空间内的元胞，独立施加上述局部函数，则可得到全局的演化。施加上述局部函数，则可得到全局的演化。2 2 元胞自动机的构成元胞自动机的构成1)元胞元胞元胞又可称为单元。或基元，是元胞自动机的最基本的组成元胞又可称为单元。或基元，是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的晶部分。元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上。格点上。状态可以是状态可以是0,1的二进制形式。或是的二进制形式。或是s0,s2,sisk整数形式的离散集，严格意义上。元胞自动机的元胞只能有一整数形式的离散集，严格意义上。元胞自动机的元胞只能有一个个状状态变量态变量。但在实际应用中，往往将其进行了扩展。例如每。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量。就设计实现了这样一种称之为个元胞可以拥有多个状态变量。就设计实现了这样一种称之为“多元随机元胞自动机多元随机元胞自动机”模型。在车辆交通元胞自动机模型中，模型。在车辆交通元胞自动机模型中，对车辆占用的元胞，元胞中含有车辆的位置和速度等对车辆占用的元胞，元胞中含有车辆的位置和速度等2)元胞空间元胞空间元胞所分布在的空间网点集合就是这里的元胞空间。元胞所分布在的空间网点集合就是这里的元胞空间。理论上，它可以是任意维数的欧几里德空间规则划分。目理论上，它可以是任意维数的欧几里德空间规则划分。目前研究多集中在一维和二维元胞自动机上。对于一维元抱自前研究多集中在一维和二维元胞自动机上。对于一维元抱自动机。元胞空间的划分只有一种。而高维的元胞自动机。元动机。元胞空间的划分只有一种。而高维的元胞自动机。元胞空间的划分则可能有多种形式。对于最为常见的二维元胞胞空间的划分则可能有多种形式。对于最为常见的二维元胞自动机。二维元胞空间通常可按三角、四万或六边形三种网自动机。二维元胞空间通常可按三角、四万或六边形三种网格排列。格排列。三角网格的优点是拥有相对较少的邻居数目，这在某些时候很有用;其缺点是在计算机的表达与显示不方便，需要转换为四方网格。四方网格的优点是直观而简单，而且特别适合于在现有计算机环境下进行表达显示;其缺点是不能较好地模拟各向同性的现象，例如后面提到的格子气模型中的HPP模型。 六边形网格的优点是能较好地模拟各向同性的现象，因此，模型能更加自然而真实，如格气模型中的FHP模型;其缺点同三角网格一样，在表达显示上较为困难、复杂。 3)邻居邻居元胞及元胞空间只表示了系统的静态成分，为将元胞及元胞空间只表示了系统的静态成分，为将动态动态引入系引入系统，必须加入演化规则。在元胞自动机中，这些规则是定义在统，必须加入演化规则。在元胞自动机中，这些规则是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于本身状空间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞的状态。因而，在指定规则之前，必须定义态和它的邻居元胞的状态。因而，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于该元胞的邻居。在一维元一定的邻居规则，明确哪些元胞属于该元胞的邻居。在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞，内的胞自动机中，通常以半径，来确定邻居，距离一个元胞，内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有以下几种形式义较为复杂，但通常有以下几种形式(我们以最常用的规则四方我们以最常用的规则四方网格划分为例网格划分为例)(1)(1)冯冯- -诺依曼诺依曼(Von Neumann)(Von Neumann)：上下左右：上下左右 4 4个个(2)(2)摩尔型摩尔型(Moore)(Moore)：上下左右；左上、左下、右上、右下；：上下左右；左上、左下、右上、右下；8 8个个(3)(3)扩展摩尔扩展摩尔(Moore)(Moore)型：型：r r 扩展为扩展为2 2或更多或更多(4)(4)马哥勒斯马哥勒斯(Margolus)(Margolus)型：它是每次将一个型：它是每次将一个2x22x2的元胞块做统的元胞块做统一处理，而上述前三种邻居模型中，每个元胞是分别处理的一处理，而上述前三种邻居模型中，每个元胞是分别处理的 边界条件边界条件在理论上，元胞空间通常是在各维向上是无限延展的，这有利于在理论上，元胞空间通常是在各维向上是无限延展的，这有利于在理论上的推理和研究。但是在实际应用过程中，我们无法在计在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此，需要定义不同的边界条件。算机上实现这一理想条件，因此，需要定义不同的边界条件。三种类型三种类型:周期型、反射型和定值型。周期型、反射型和定值型。周期型周期型：是指相对边界连接起来的元胞空间。对于一维空间，元胞：是指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的空间表现为一个首尾相接的“圈圈”。对于二维空间，上下相接，。对于二维空间，上下相接，左右相接。而形成一个拓扑圆环面左右相接。而形成一个拓扑圆环面，形似车胎或甜点圈。周期型，形似车胎或甜点圈。周期型空间与无限空间最为接近，在理论探讨时，常以此类空间型作为空间与无限空间最为接近，在理论探讨时，常以此类空间型作为试验。试验。反射型反射型：指在边界外邻居的元胞状态是以边界为轴的镜面反射。：指在边界外邻居的元胞状态是以边界为轴的镜面反射。定值型定值型：指所有边界外元胞均取某一固定常量，如：指所有边界外元胞均取某一固定常量，如0，1等。等。在实际应用中在实际应用中，尤其是二维或更高维数的构模时，尤其是二维或更高维数的构模时，可以相互结合可以相互结合。如在二维空间中，上下边界采用反射型，左右边界可采用周期型如在二维空间中，上下边界采用反射型，左右边界可采用周期型4)4)规则规则(Rule)(Rule)根据元胞当前状态及其邻居状况确定下一时刻该元胞状根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。态的动力学函数，简单讲，就是一个状态转移函数。记为记为f:sit+1=f(sit,sNt)，sNt为为t时刻的邻居状态组合，我们称时刻的邻居状态组合，我们称f为元胞自动机的局部映射或局部规则为元胞自动机的局部映射或局部规则3 3 元胞自动机的特征元胞自动机的特征1)同质性、齐性:同质性，每个元胞的变化服从相同的规律；齐性，元胞的分布方式相同，大小形状相同，空间分布规则整齐2)时间离散:元胞按一定规律分布在离散的元胞空间上3)空间离散:演化按等间隔时间分步进行,时间只取等步长的时刻点4)状态离散有限：5)同步计算:元胞自动机的处理同步进行，适合并行计算6)时空局域性:元胞在t+1时刻的状态，取决于其周围半径r的邻域中的元胞在t时刻的状态，及所谓的时间、空间局限性7)维数高:在动力系统中一般讲变量的个数称为维数。由于任何完备元胞自动机的元胞空间是定义在一维、二维或多维空间上的无限集，每个元胞的状态便是这个动力学系统的变量。因此，元胞自动机是一类无穷维动力系统。二、经典的元胞自动机模型二、经典的元胞自动机模型1 Conway1 Conway和他的和他的“生命游戏生命游戏” 1)“生命游戏”的构成及演化规则(1)”生命游戏”的构成：元胞分布在规则换分的二维方形网格上；元胞具有0、1两种状态，0代表死，1代表生；元胞以相邻的上下左右好对焦线上的8个元胞维邻居；一个元胞的生死有其在该时刻本身的生死状态和周围8个邻居的状态决定。(2)“生命游戏生命游戏”的演化规则：的演化规则：生存生存：对一个活的元胞，如果它的邻居中有2个或3个元胞是活的，那么该元胞将继续生存；死死亡亡：对于一个活的元胞，如果它的邻居中有4个或4个以上的元胞是活的，该元胞死亡；如果它的邻居中只有1个或没有活的元胞，那么死亡；繁殖：对1个空的元胞，如果它的邻居中有3个活的，那么该元胞将成为活的元胞二、经典的元胞自动机模型二、经典的元胞自动机模型2)“生命游戏”中一些演化形态二、经典的元胞自动机模型二、经典的元胞自动机模型2 Wolfram2 Wolfram和他的初等元胞自动机和他的初等元胞自动机 1)初等元胞自动机 初等元胞自动机是状态集初等元胞自动机是状态集S S只有两个元素，即只有两个元素，即k=2k=2，邻，邻居半径居半径r=1r=1的一维元胞自动机的一维元胞自动机。初等一维元胞自动机可能的初等一维元胞自动机可能的8 8种输入状态组合种输入状态组合111 110 101 100 011 010 001 000111 110 101 100 011 010 001 000rule 18rule 57rule 150rule 30rule 73rule 126rule 124rule 1692）典型的Wolfram规则3)元胞自动机种类Stephen Wolfram Stephen Wolfram 对初等元胞自动机的分类对初等元胞自动机的分类平稳型平稳型: :自任何初始状态开始自任何初始状态开始, ,经过一定时间运行后，元胞空间经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。于固定状态。不随时间变化而变化。周期型周期型: :经过一定时间运行后，元胞空间趋于一系列简单的固定经过一定时间运行后，元胞空间趋于一系列简单的固定结构结构(Stable Paterns)(Stable Paterns)或周期结构或周期结构(Perlodical Patterns)(Perlodical Patterns)。混沌型混沌型: :自任何初始状态开始，经过一定时间运行后，元胞自动自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统计特征不再机表现出混沌的非周期行为，所生成的结构的统计特征不再变变化化，通常表现为分形分维特征。通常表现为分形分维特征。复杂型复杂型: :出现复杂的局部结构，或者说是局部的混沌，其中有些出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。会不断地传播。三、元胞自动机应用三、元胞自动机应用 在社会学中，元胞自动机用于研究经济危机的形成与爆发过在社会学中，元胞自动机用于研究经济危机的形成与爆发过程、个人行为的社会性，流行现象，如服装流行色的形成等。程、个人行为的社会性，流行现象，如服装流行色的形成等。 在生物学中，元胞自动机的设计思想本身就来源于生物学自在生物学中，元胞自动机的设计思想本身就来源于生物学自繁殖的思想，因而它在生物学上的应用更为自然而广泛。繁殖的思想，因而它在生物学上的应用更为自然而广泛。 例如：元胞自动机用于肿瘤细胞的增长机理和过程模拟、人类例如：元胞自动机用于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索大脑的机理探索(Victor.Jonathan.D. 1990)(Victor.Jonathan.D. 1990)、爱滋病病毒、爱滋病病毒HIVHIV的感染过程的感染过程(Sieburg(Sieburg. .H.B.1990)H.B.1990)、自组织、自繁殖等生命现象、自组织、自繁殖等生命现象的研究以及最新流行的克隆的研究以及最新流行的克隆 (Clone)(Clone)技术的研究等技术的研究等 (ErmentroutG(ErmentroutG. .B B. .1993)1993)。应用领域涉及社会学、生物学、生态学、信息科学、计算机科应用领域涉及社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、歹境、军事学等。学、数学、物理学、化学、地理、歹境、军事学等。四、基于元胞自动机的基本交通模型四、基于元胞自动机的基本交通模型1.11.1模型的建立模型的建立 考虑一个有等长的L个格子的线段，每个格子可有一个向右行驶的车或为空。行驶规则为：若前方格子有车，则停止。若前方为空，则前进一格，不能跟驰。采用周期边界，此即为NS模型即：f为：T111110101100011010001000T+1101110001 1一维模型一维模型1.2结果时空分布图时空分布图横轴：空间纵轴：时间2 2 二维基本模型二维基本模型2.1模型的建立考虑一个L*L的网格，对任一格子(i,j),共有三种状态，即有一个向右行驶的车、有一个向上行驶的车和空。行驶规则为奇数时间向右行驶的车可以前进，且一辆车只有前方格子里空时可前进一格。不能跟驰，偶数时间步向上的车可以行驶，规则同右行。2.2结果平均速度和平均车流密度的关系平均速度和平均车流密度的关系快照3 3 基本模型的改进基本模型的改进3.1一维变速模型 在NS模型的基础上，考虑车可有不同的速度，并制定相应的运行规则，最大速度为Vmax为正整数，这样，每个格子的状态为空，或具有一个小于等于Vmax的非负整数的车。运行规则考虑加速、减速、随机事件等因素。3.1模型3.2结果3.2二维双向模型 在原二维的元胞自动机基础上，考虑双向行驶机制，则每个格子有七中状态：空，右行，上行，左行，下行，左右，上下。 运行规则类似于原二维模型。3.2.1模型3.2.2结果平均速度和平均车流密度的关系平均速度和平均车流密度的关系3.2.3快照