https://www.doczj.com/doc/0a13258836.html, 元胞自动机及其在土壤侵蚀中的应用现状评述*
原立峰1，2，3
（1.中科院成都山地灾害与环境研究所，成都 610041；
（2.中科院地理科学与资源研究所，北京 100101；3.中国科学院研究生院，北京 100039
E－mail：yuanlf@https://www.doczj.com/doc/0a13258836.html,
摘 要：动态模拟和预测土壤侵蚀的发育及演化过程具有十分重要的意义。元胞自动机(Cellular Automata ,简称“CA”) 是一种“自下而上”的动态模拟建模框架，具有模拟地理复杂系统时空演化过程的能力。从元胞自动机的概念、构成和原理入手，分析总结了元胞自动机的基本特征，介绍了元胞自动机模型在土壤侵蚀学科中的应用情况和存在问题，对CA模型应用于土壤侵蚀过程模拟和预测的可行性进行了探讨，提出了将CA应用于土壤侵蚀过程模拟的基本思想。
关 键 词：土壤侵蚀；元胞自动机；动态模拟；地理模型
1引言
钱学森院士曾多次指出，作为地理学的基本研究对象，地理系统是一个由多要素共同作用的、自然、社会和经济复合的、开放的复杂巨系统[1]。许多地理现象都具有非平衡性、多尺度性、不确定性、自相似性、层次性、随机性和交互性等复杂性现象的特征[2]。正是由于地理系统是一个典型的非线性耗散系统，所以研究复杂的地理现象只有应用复杂系统的理论，结合地理学的本质，采用适当的研究方法，才有可能建立空间复杂系统的科学模型[3]。
元胞自动机作为研究空间复杂性现象的一种方法工具，近年来受到地理学界的普遍重视。它是由号称“现代计算机之父”的冯?诺伊曼（V on Neumann）在上个世纪40年代末首先提出的一种离散模型，往往可以将其看作是描述连续现象微分方程的对立体[4]。CA模型是定义在一个由离散、有限状态的元胞所组成的元胞空间上，按照一定的局部规则，在离散时间维上演化的动力学系统[5]。由于CA模型“自下而上”的研究思路、强大的复杂计算功能、固有的并行计算能力和鲜明的时空耦合特征使得它特别适合于地理空间系统的动态模拟研究[6]。
目前，CA 已经逐渐成为一个国际前沿的研究领域。CA 的应用范围非常广泛，从物理、生物现象的微观模拟[7]到地理、社会进程的宏观模拟[8]，几乎无所不包，应用的领域涉及社会学、生物学、信息科学、计算机科学、数学、物理、化学、军事等许多学科。CA在地理学中的应用主要包括：城市地理学、交通流、森林火灾、城市热岛效应、以及土地利用/覆盖变化（LUCC）等方面。例如：20世纪70年代，Tobler认识到CA在模拟地理复杂现象方面的优势，首次正式采用CA的概念来模拟当时美国五大湖区底特律城市用地的迅速扩张[9]。20世纪80年代，美国圣巴巴
作者简介：原立峰，男，1978年生，山西太原人，博士研究生。主要从事土壤侵蚀和GIS应用方面的研究。通讯地址：北京市朝阳区大屯路甲11号 中科院地理所2415# 邮编：100101
拉加州大学地理系的Helen Couclelis对于CA在城市发展动态模拟中的应用作了开创性的研究工作，奠定了CA在地理学中应用的理论框架[10,11]。交通流CA模型中最具代表性的工作是Nagel和Schreckenberg（1992）提出的用于描述高速公路交通流的一维随机元胞自动机模型（即“NS”模型），该模型考虑到车辆加速和不完善驾驶的影响，首次揭示了车辆从自由运动相到局部阻塞相的相变，引起学术界的广泛注意[12]。Green和他的同事（1990）基于CA设计了灌木丛林的野火扩散模型[13]。Embuts和Goodchild（1994）等人基于CA模型成功模拟了城市热岛效应[14]。M.Batty & Yichun Xie（1999）等人利用CA，结合地理信息系统（GIS）技术对城市的动态演化作了深入细致的研究[15]。White（1993）等人应用CA模型对美国辛辛那提（Cincinnati）市的城市增长、全球气候变化对加勒比（Caribbean）岛土地利用构成变化的影响进行了系列研究[16]。
随着复杂系统理论、计算机技术以及其它一些相关学科的发展，元胞自动机模型在地理学中的应用逐渐倾向于模拟和预测复杂的地理过程。CA在我国的研究才刚刚起步，在土壤侵蚀学科领域中，人们对CA 还比较陌生。然而，对土壤侵蚀的发育和演化过程进行模拟和预测显然是CA 应用的又一个潜在领域，具有广阔的应用前景。我们希望在这方面进行一些初步探讨，以推动CA 模型在该领域内的研究和发展。
2元胞自动机理论
2.1元胞自动机的概念
元胞自动机（Cellular Automata，又称细胞自动机，分子自动机或者点格自动机，简称“CA”），是一种在时间、空间和状态上都离散的网格动力学模型[17]。元胞自动机的基本原理是利用大量元胞在简单规则下的并行演化来模拟复杂而丰富的宏观现象[18]。散布在规则格网（Lattice Grid）中的每一个元胞取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量的元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数来确定，而是由一系列简单的规则构成。凡是满足这些规则的模型都可以看作是CA模型。因此，确切的讲，元胞自动机是一类模型的总称，或者说是一个方法框架[6,19]。
2.2元胞自动机的构成
元胞自动机的最基本的组成单元就是元胞（cell）、元胞空间（lattice）、邻居（neighbor）及规则（rule）。元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。标准元胞自动机是一个四元组，其可表示为：A={d,S,N,f}。这里A代表一个元胞自动机系统；d是一个正整数，表示元胞自动机的维数；S是元胞有限离散的状态集合；N表示一个所有邻居内元胞的组合（包括中心元胞），即包含n个不同元胞状态的一个空间矢量，记为： N={s1,s2,s3,…,s n},n是元胞的邻居个数，S i∈z(整数集合)，i∈(1,…,n)；f表示将S n映射到S上的一个局部转换函数。所有的元胞位于d维空间上，其位置可用一个d元的整数矢量Z d来确
定[1]。
2.2.1 元胞空间
元胞空间可以是一维、二维或多维的。元胞空间的划分可以有多种形式。最为常见的二维CA 网络通常可以按照三角、四方或六边形排列。如图1
2.2.2 邻居类型
[21]
（1）冯?诺依曼（Von Neumann）型
其邻居定义如下：
}),(,1|||||),({2Z v v v v v v v v v N iy ix oy iy ox ix iy ix i Neumann ∈≤?+?==
v ix , v iy 表示邻居元胞的行列坐标值，v ox 表示中心元胞的行列坐标值。如图2-a
（2）摩尔（Moore ）型
其邻居定义如下：
}),(,1||,1|||),({2Z v v v v v v v v v N iy ix oy iy ox ix iy ix i Moore ∈≤?≤?==
此时，对于四方网格，在维数为d 时，一个元胞的邻居个数为（3 d-1）。如图2-b
（3）扩展的摩尔（Moore ）型
其邻居定义如下：
}),(,|||||),(
{2'Z v v r v v v v v v v N iy ix oy iy ox ix iy ix i Moore ∈≤?+?==
此时，对于四方网格，在维数为d 时，一个元胞的邻居个数为（（2r+1）d-1）。如图2-c
（4）马哥勒斯（Margolus ）型
[22]
这是一种同以上邻居模型迥然不同的邻居类型，它是每次将一个2×2的元胞块做统一处 （a ）三角网格 （b ）四方网格 （c ）六边网格 图1 二维元胞自动机的三种网格划分（据李才伟，1997[20]） Fig. 1 The Three Lattice Types of 2-Dimension Cellular Automata （a ） V on.Neumann 型 （b ）Moore 型 （c ）扩展的Moore 型
图2 元胞自动机的邻居模型
Fig. 2 Neighbor Models of Cellular Automata
理，以包含四个元胞的四方块为基本单位进行研究，如图3
图3马哥勒斯（Margolus）型
Fig. 3 Margolus Neighbor Model
2.2.3 转换规则/函数
转换规则是CA的核心，它表述被模拟过程的逻辑关系，决定空间变化的结果。根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。我们将一个元胞的所有可能状态连同负责该元胞状态变换的规则一起称为一个变换函数[21]。CA 的转换规则可以下概括为以下几种[23]：
(1) 直接确定。对于给定的元胞和邻居情况，直接确定转换结果，即元胞下一时刻的状态。
(2) 隐含确定。通过一些公式的计算和推导，进行转换。
(3) 多步计算。把CA 的转换规则分解成几步，既清楚明了，又便于运算。
(4) 概率性计算。对于一个给定的元胞和邻居，没有一个确切的惟一结果。这种转换规则给出可能的几种转换结果和相应的转换概率，所有转换概率的和是1。
2.3元胞自动机的特征分析
传统的建模基于人为给定的一个方程，通过模型迭代运行确定参数，这种模型可称为“刚性”模型。CA 则是强调局部元素、组分之间的相互作用，由局部的变化耦合形成系统整体的宏观变化和特征。CA 模型以其框架的简单、开放和可以模拟十分复杂的系统行为而具有很强的生命力，从目前的研究看，它具有以下特点[22,24,25]
（1）空间性，反映在以栅格单元空间来定义元胞自动机，因而能很好地和许多空间数据集相互兼容。
（2）离散性，即空间的离散性、时间的离散性、状态的离散性，因此具有良好的计算机接口。
（3）同步性，可以将元胞自动机的状态变化看成是对数据或信息的计算或处理，这时的重要特征是计算的并行性，各个元胞在时间上遵循不同的演化规则同步运行。
（4）简单性，通过元胞的初始状态、周围元胞的状态就可以确定该元胞在下一时刻的状态，不需要构建复杂的偏微分方程。
（5）时空动态性，可以用来模拟复杂系统的时空动态，弥补了传统模型把系统的时间、空间特性孤立考虑的不足。
（6）局部性，每一个元胞的状态，只对其周围半径为R邻域内的元胞在下一时刻的状态有影响。
（7）高维数，在动力系统中一般将变量的个数称为维数，从这个角度看，元胞自动机的维数是无穷的。
3元胞自动机在土壤侵蚀学科中的应用
3.1元胞自动机模型在土壤侵蚀学科中的应用现状
上个世纪九十年代以来，国外科学家对于将元胞自动机应用于土壤侵蚀学科领域进行了大量的研究工作。Simth（1991）等人设计了一个元胞自动机模型模拟了地形侵蚀的过程，并把结果同其他模型作了对比，展示了简单元胞自动机强大的模拟功能[26]。Chase（1992）开发了一个元胞自动机模型，利用简单的元胞规则定义，模拟了降雨溅蚀和坡面径流侵蚀的过程[27]。Murray 和Paola（1994，1997）建立了一个用来模拟汇流过程的CA模型，在模拟现象的主要特征方面取得了成功[28]。Pilotti 和 Menduni（1997）利用二维格子气模型模拟了面蚀及侵蚀物质的输移过程[29]。Favis-Mortlock（1998）利用元胞自动机模拟了坡面细沟侵蚀发生、演化的基本形态和细沟间侵蚀演化所形成的地表几何形态，避免了传统坡面模型需要的大量参数标定[30]。D.D’Ambrosio （1999）等人基于元胞自动机开发了“SCA V ATU”模型模拟了土壤水蚀过程，并将其应用于意大利南部卡拉布里亚区Fiumara Armaconi 的一个小流域，取得了令人满意的效果[31]。Bastien Chopard（2000）等人利用标准的格子Boltzmann方法模拟了水力侵蚀中发生的泥沙沉积和输移现象，并用元胞自动机来模拟水流中土壤分子的悬移状态，模拟结果与野外实测能够很好的吻合[32]。Wei Lou（2001）等人利用CA模型模拟了降雨、入渗、侵蚀等地形演变过程，并开发了“LANDSAP”软件对侵蚀过程做了动态模拟[33]。N.Imbroinise、P.Aucelli和D. D’Ambrosio（2003）等人继续完善了“SCA V ATU”模型，提出了改进后的“SCA V ATU-hex”模型，该模型基于六边形元胞形状建立，能够更加真实的模拟现实情况，将其应用于意大利Molise地区的Morgiapietravalle盆地的一次真实的侵蚀性降雨过程，取得了良好的效果 [34]。Gino Mirocle Crisci （2004）等人开发了一个用于模拟由于火山喷发时形成火成碎屑流的元胞自动机模型—“PYR”，并将它成功的运用于1991年菲律宾群岛的Pinatubo火山爆发模拟[35]。Uri Wilensky（2004）等人利用NetLogo元胞自动机设计软件建立了一个土壤侵蚀模型，形象生动地表达了不同地表粗糙度下的地形侵蚀情况[36]。除此之外，还有很多国外科学家对CA应用于模拟侵蚀现象作了大量的研究工作（D.Barca et al，1994；J.Adinarayana et al，1999；J.P. Nunes et al，2001等等）[37,38,39]，并取得了丰硕的成果。
近几年来，受国际研究的影响和推动，国内也有人开始了这方面的研究。周成虎（1999）等人在总结前人工作的基础上，提出了地理元胞自动机（GeoCA）模型，推动了CA模型在地学中的发展。马力（2003）等人利用CA模型，在GIS的技术支持下，分析了不同土地利用模式下土壤侵蚀的空间演化状况，预测了不同土地利用模式中以地块为单元的土壤侵蚀的发展方向，取得了
一定的效果[40]。陈建平（2004）等人利用GeoCA，建立了土地荒漠化动态演化预测模型，并对北京及邻区的土地荒漠化情况做出了对比分析，并提出了一些有益的建议[41]。史晓霞（2004）等人以吉林省西部盐碱化土地为研究区，在GIS 的支持下系统分析了土壤盐碱化的特征及其影响因子，建立了基于GeoCA 的土壤盐碱化动态模型，模拟了吉林省西部土地盐碱化发生发展的时空动态规律[42]。
总体上来说，国内将CA模型应用于土壤侵蚀学科方面的研究才刚刚起步，应用程度还比较浅，需要侵蚀学科领域内的专家给予必要的重视。
3.2元胞自动机模拟土壤侵蚀时空演化过程的可行性
土壤侵蚀发育及演化过程的模拟是一项十分复杂的系统工程。由于土壤侵蚀过程是随时间发展不断变化的瞬态过程，传统的土壤侵蚀模型，无论是基于统计资料的经验模型，还是基于物理过程的理论模型[43]，从本质上来说，都属于一种稳态模型，仅仅能够做一些事后的预报，或者说预测的范围极其有限，并不能实现真正意义上的土壤侵蚀预报。除此之外，传统基于统计数据的侵蚀经验模型不能回答侵蚀的时空分布规律[44]，很难直观地反映土壤侵蚀的发生、发育和演化的全过程。所以从土壤侵蚀模型研究的角度来说，呼唤研究方法的创新和突破。于是，CA以其方法的灵活性和新颖性进入人们的视野。
首先，CA方法本身就是从微观物理过程的角度来分析问题并建立模型的，所以较之传统的经验方法更有利于对土壤侵蚀机理的分析研究，从而有利于进一步揭示侵蚀过程的内在机制。其次，CA 模型的特点决定了它适合于土壤侵蚀过程的时空动态分析及模拟。这是因为[45,46]：
(1) CA模型采用“自下而上”的构模方式，而且没有一个既定的数学方程，只是一个建模原则，因此具有很好的开放性和灵活性，更符合人们认识复杂事物的思维方式。
(2) CA模型是一个基于微观个体相互作用的时空动态模拟模型，将地理实体的空间和时间特性统一在模型中，通过划分研究对象的元胞空间和研究初始状态及状态转换规则，CA模型就可以自行迭代运算，模拟系统演化过程。
(3) CA模型将空间和时间离散化，适合于建立计算机模型，具有并行计算特征，因为计算机对客观世界的表示是离散的。
(4) CA模型具有不依赖比例尺的概念，元胞只是提供了一个行为空间，本身不受元胞空间测度和时间测度的影响，时空测度的影响通过转换规则体现。因此CA模型可以用来模拟不同时空尺度的土壤侵蚀过程。
(5)从数据模型的角度看，CA模型中的元胞和基于栅格GIS中的栅格一样，所以CA模型易于和GIS、遥感数据处理等系统集成。
由以上CA模型具有的特点可以看出，将其应用于土壤侵蚀发生、发育和演化过程的模拟不但是可行的，而且有利于对土壤侵蚀内在机理的理解，并且基于对演化规则的调控，能够在一定程度上实现土壤侵蚀模型时空尺度转换。
3.3标准CA模型在模拟土壤侵蚀过程中的扩展
虽然利用CA来模拟土壤侵蚀过程的动态演化具有很大的吸引力，但是由于土壤侵蚀发育机理及演化过程的复杂性，必须对标准的CA模型进行拓展，才能满足其进行时空模拟的需要，真实准确地模拟和预测土壤侵蚀的演化过程。
(1) 元胞与元胞空间的扩展。元胞空间不再是抽象的空间，而是与笛卡儿坐标下的实际地理空间相对应，并可以抽象为二维的地块或研究区。每一个元胞具有明确的地理含义，如可以代表遥感影像上的栅格单元、地块或精细尺度下一定大小的地表单元等等。当然，不同空间尺度元胞单元的地理定义会直接影响建模的复杂程度。
(2) 元胞状态的扩展。地理元胞可以有多种状态，其状态集合可以定义为表征地理单元的自然属性（如地形、海拔、土壤可蚀性等），或者是影响侵蚀的相关指标（降雨量、雨强、植被覆盖度、耕作措施）等等。
(3) 元胞状态转换规则的扩展。转换规则可以视为宏观土壤侵蚀发育机理在微观个体变化规律的体现，表现土壤侵蚀过程的动态演化十分复杂，排除人为因素以外，还受各种区域自然条件的影响。因此，CA 模型中状态转换规则必须兼顾微观地形单元和宏观区域自然条件。而且，元胞的转换规则在地理时空上是不同构的，应该随区域差异和时间而调整，只有这样才能更为真实的展现连续的、动态的侵蚀过程。
(4) 时间概念的扩展。 CA 模型中的模拟时间必须和土壤侵蚀过程中的真实时间建立对应关系，将系统运行时间映射到真是时间。否则，建模就失去了利用价值。一般可以采用多年的土壤侵蚀观测数据来建立两者之间的对应关系。
4存在的问题
CA模型是一种模拟土壤侵蚀时空动态演化过程很有前景的方法框架，但是由于CA模型框架的简单性与土壤侵蚀机理、演化过程复杂性之间存在的矛盾，用CA来模拟土壤侵蚀的时空动态演化过程也面临以下的问题和挑战。
（1）CA 空间尺度的划分问题。不同的空间尺度下，由于模型的表现效果以及影响模型的各种外在因素作用程度的差异，系统单元表现的规律也不相同，因此，根据研究的需要，如何确定合适的空间分辨率是一个需要考虑的问题[46]。
（2）CA 转换规则体系的建立问题。建立合理的转换规则是CA模型取得成效的关键，在CA模型中，转换规则反映了地理单元间的局部相互作用。这个局部规则与传统的宏观规律，既有联系，又存在较大的差别。它的产生有时靠的是直觉和经验，而且找到一个确切规则的难度是比较大的，这也是CA模型应用于模拟土壤侵蚀过程能否成功的重要因素。
（3）CA 模型的时间校准问题。标准CA 模型的时间是一个抽象的概念，那么它的模拟结果如何与实际的时间尺度如年、月、日相对应，是CA 模型面临的一个难题。一般可以利用已有的历史数据来校准模型的时间概念，即用某时段观测到的土壤侵蚀结果数据与现有CA模型计
https://www.doczj.com/doc/0a13258836.html, 算运行的结果相拟合，得到一个时间对应关系。但这种方法的局限性在于一般只适用于有关测站点的地区或流域，并且已经积累了大量的野外观测历史数据。
（4）CA模型与GIS集成的问题。GIS系统的支撑已经成为地理系统建模的必要条件。虽然CA模型与栅格模型GIS在空间数据结构上存在较大的相似性，然而CA模型是一个时空动态模型。传统的GIS并不能完整的表示地理实体的时态信息和时空关系，时空分析能力很弱[47]。如何将二者动态的紧密集成，也是阻碍CA模型在模拟土壤侵蚀动态演化过程中的一个障碍[6]。
由以上CA模型在具体应用中存在的问题可以看出，如何建立CA模型的转换规则及校准CA模型的时间直接关系到模型模拟结果的真实性和准确性，所以是模拟土壤侵蚀时空演化过程所必须解决的核心与关键问题。
5结论与展望
土壤侵蚀的发生、发育及演化过程是一个非常复杂的现象，具有极大的不确定性和混沌特征，虽然存在一定的规律，但要通过数学模型精确预测它们的发展变化则是非常困难的。CA提供了研究这一现象的有力工具。但是，CA在土壤侵蚀学科领域内的应用在我国才刚刚起步，将CA 应用于模拟土壤侵蚀过程的动态演化研究还有待进一步深化。例如：如何使CA在模拟侵蚀过程中由系统自动调整模型参数和演化规则，实现侵蚀模型在时空尺度上的自由转换；如何将CA 模型与GIS、模糊推理、多智能体（Muti-Agents）、土壤侵蚀专业模型紧密集成，建立基于GIS和CA 集成的智能化土壤侵蚀过程模拟及侵蚀评价专家系统；以及如何利用计算机技术实现土壤侵蚀演化过程的三维动态CA模拟，使其既能展现土壤侵蚀的时空分布情况，又可以直观地展示土壤侵蚀的形成和发展过程，从而进一步深化人们对侵蚀内在机理的认识，也为水土保持工程措施的优化布置提供有力支撑。以上问题的深入研究与解决，将使CA模型在土壤侵蚀领域中发挥更大的作用。
参考文献
[1]孙战利.空间复杂性与地理元胞自动机模拟研究[J].地球信息科学,1999,32～37
[2]钱学森,于录元,戴汝为. 一个新的学科领域——开放的复杂巨系统及其方法论[J].自然杂志, 1990,1:3～
10
[3]罗平,杜清运,何素芳,黄耀丽. 基于关系数据库的CA模型扩展和时空模拟实验研究[J]. 地理学与国土研
究,2002,18(3):8～12
[4]Wolfram S. Cellular Automata as Model of Complexity [J]. Nature, 1984, 311:419～424
[5]谢惠民. 非线性科学丛书:复杂性与动力系统[M].上海科技教育出版社,1994
[6]周成虎,孙战利,谢一春. 地理元胞自动机研究[M]. 北京:科学出版社,1999.23～26
[7]Gutowitz.H.(ed.), Cellular automata theory and theory and experiment [M]. 1st MIT Press
edition,Boston,MA,1991
[8]Weimar.J., Simuluation with Cellular Automata[M].Logos Verlag,Berlin,Germany,1998
[9]Tobler WD., A Computer Movie Simulating Urban Growth in the Detroit Region[J].Economic
Geography,46:234～240 1970
[10]Couclelis,H., Cellular Worlds:a Framework for Modeling Micro-Macro Dynamics[J].Environment and
Planning A,17,585～596,1985
[11]Couclelis,H., From Cellular Automata to Urban Model: News Principles for Model Development and
Implementation[J],Environment and Planning B,24,165～174, 1997
[12]Nagel K., Schreckenberg M., A cellular automaton model for freeway traffic[J]. J. Physique I2,
2221–2229,1992
[13]Green DG, Tridgell A., Interactive Simulation of Bushfires in Heterogeneous Fuels[J].Mathematical
Computation and Modeling,13(12):57～59,1990
[14]Embutsu I., Goodchild M. F., et al., A Cellular Automata Modeling for Urban Heat Island Mitigation,
Proceeding of GIS/LIS’94,262-271,1994
[15]M.Batty,Yichun Xie,Zhanli Sun.,Modeling urban dynamics through GIS-based cellular
automata[J].Computers, Environment and Urban Systems 23,205～233,1999
[16]White RW., Cellular automata and fractal urban form: a cellular modeling approach to the evolution
of urban land use patterns[J]. Environment and Planning A,25:1175～1189,1993
[17]黎夏.主成分分析与CA在空间决策与城市模拟中的应用[J].中国科学D辑,2001,31(8):683～690
[18]应尚军,魏一鸣,蔡嗣经.元胞自动机及其在经济学中的应用[J].中国管理科学,2000,8:272～278
[19]汤君友,杨桂山.试论元胞自动机模型与LUCC时空模拟[J].土壤,2003,35(6):456～460
[20]Buchendorfer, T., Bifurcation Properties of Dynamics, Ph.D. thesis of Cranfiels University, 1997
[21]孙战利.基于元胞自动机的地理时空动态模拟研究[D].中科院地理科学与资源研究所博士论文,1999
[22]赵文杰,刘兆理.元胞自动机在环境科学中的应用[J].东北师范大学学报(自然科学版),2003,35(2):87～92
[23]Jose Andres Moreno Ruiz,Cesar Carmona Moreno ,Manuel Cruz Martinez ,et al. New Cellular Automata
Applications on Multi-Temporal and Spatial Analysis of NOAA - NVHRR Images[M] . Florence :Society of Photo-Optical Instrumentation Engineers,1～382,1999
[24]何宜柱,余亮,陈大宏,雷廷权.元胞自动机仿真技术[J].华东冶金学院学报,1998,15(4):309～313
[25]杜宁睿,邓冰. 细胞自动机及其在模拟城市时空演化过程中的应用[J].武汉大学学报(工学
版),2001,34(6):9～11
[26]Smith.R., The application of cellular automata to the erosion of landforms[J].Earth Surface
Processes and Landforms[J],16,273～281,1991
[27]Chase,C.G., Fluvial landsculpting and the fractal dimension of topography[J].Geomorphology
5,39～57,1992
[28]Murrayc A. B., Paola C., A cellular model of braided rivers [J]. Nature,371, 54～57, 1994
[29]Pilotti M. and Menduni, G., Application of lattice gas techniques to the study of sediment erosion
and transport caused by laminar sheetflow[J].Earth Surface Processes and Landforms[J], 22(9), 885～893, 1997
[30]Favis-Mortlock,D., A self-organizing dynamic systems approach to the simulation of rill
initiation and development on hillslopes[J].Computer & Geosciences 24,353～372,1998
[31]D.D’Ambrosio, S.Di Gregorio, S.Gabriele and R.Gaudio. A Cellular Automata Model for Soil Erosion
by Water[J].Phys. Chem. Earth(B).Vol.26 No.1,pp.33～39,2001
[32]B.Chopard,P.O.Luthi, Lattice Boltzmann Computations and Application to Physics[J].Theoretical
Computer Science,Vol.217,115～130,1999
[33]Wei https://www.doczj.com/doc/0a13258836.html,NDSAP: a coupled surface and subsurface cellular automata model for landform
simulation[J].Computer and Geoscience 27(2001) 363-367.
[34]N.Imbroinise,P.Aucelli,D.D’Amvrosio,T.Caloiero,S.Gabriele,R.Gaudio.A Hexagonal Cellular
Automata for Modeling Soil Erosion by Water: A Application to A Real Event. Geophysical Research Abstracts[J],Vol.5,04124,2003.
[35]Gino Mirocle Crisci,Salvatore Di Gregorio,Rocco Rongo,William Spataro. PYR: A Cellular Automata
model for pyroclastic flows and application to the 1991 Mt. Pinatubo eruption[J].Future Generation Computer System,2004.
[36]Wilensky,U.(2004).NetLogo Erosion model.https://www.doczj.com/doc/0a13258836.html,/netlogo/models/Erosion.
Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.
[37]D.Barca,G.M.Crisci,S.Di Gregorio,F.P.Nicoletta., Cellular Automata for simulating lava flows:
a method and examples of the Etnean eruptions[J].Transport Theroy and Statistical
Physics,Vol23,195～232,1994
[38]J.Adinarayana,K.Gopal Rao,N.Rama Krishna,P.Venkatachalam,J.K.Suri., A rule-based soil erosion
model for a hilly catchment[J].Catena 37,309～318,1999
[39]J.P.Nunes,G.Vieira,P.Goncalves,J.Seixas,N.Carvalhais., Runoff and erosion modeling: a new
approach driven by small-scale variability[J].Proceedings of the 2001 International Symposium on Envirnmental Hydranlics
[40]马力,杨新民,吴照柏,杨世伟. 不同土地利用模式下土壤侵蚀空间演化模拟[J].水土保持通
报,2003,23(1):49～51
[41]陈建平,丁火平,王功文,厉青,冯春. 基于GIS 和元胞自动机的荒漠化演化预测模型[J].遥感学
报,2004,8(3):254～260
[42]史晓霞,王静,任春颖,刘湘南. 基于GIS 与GeoCA 模型的半干旱区土壤盐碱化动态模拟研究[J].东北师大
学报,2004,36(2):88～94
[43]吕喜玺,史德明.土壤侵蚀模型研究进展[J].土壤学进展,1994,22(2):9～14
[44]雷廷武,邵明安,李占斌,王全九.土壤侵蚀预报模型及其在中国发展的考虑[J].水土保持研
究,1999,6(2):162～166
[45]张显峰. 基于CA的城市扩展动态模拟与预测[J].中国科学院研究生院学报,2000,17(1):70～79
[46]崔伟宏, 张显峰. 土地资源的动态监测和动态模拟研究[J].地球信息科学,2002,3(1):79～85
[47]Goodchild M., Geographical Information Science[J]. Journal of International Geographical
Information Systems.1992 ,6(1):31～45
https://www.doczj.com/doc/0a13258836.html, Cellular Automata and Its Applications to Soil Erosion
YUAN Lifeng1,2,3
(1.Institute of Mountain Hazards and Environment, CAS, Chengdu 610041;
2. LREIS, Institute of Geographic Sciences and Natural Resources, CAS, Beijing 100101;
3. Graduate School of the Chinese Academy of Sciences, Beijing 100039;
Abstract: It is very important to dynamically simulate and forecast the development and evolutionary process of soil erosion. Cellular Automata (simply named “CA”) is a dynamic modeling framework, and is capable to simulate the spatial-temporal evolutionary process of geographical complex system. It was introduced that the concept and the character of CA theory and its application to soil erosion. Some present problems were discussed. The feasibility was proved and the basic idea was put forward while CA model was applied to simulate and forecast the process of soil erosion.
Key Word: soil erosion; cellular automata; spatial-temporal simulation; Geo-model
元胞自动机(CA)代码及应用 引言 元胞自动机（CA）是一种用来仿真局部规则和局部联系的方法。典型的元胞自动机是定义在网格上的，每一个点上的网格代表一个元胞与一种有限的状态。变化规则适用于每一个元胞并且同时进行。典型的变化规则，决定于元胞的状态，以及其（4或8 ）邻居的状态。元胞自动机已被应用于物理模拟，生物模拟等领域。本文就一些有趣的规则，考虑如何编写有效的MATLAB的程序来实现这些元胞自动机。 MATLAB的编程考虑 元胞自动机需要考虑到下列因素，下面分别说明如何用MATLAB实现这些部分。并以Conway的生命游戏机的程序为例，说明怎样实现一个元胞自动机。 ●矩阵和图像可以相互转化，所以矩阵的显示是可以真接实现的。如果矩阵 cells的所有元素只包含两种状态且矩阵Z含有零，那么用image函数来显示cat命令建的RGB图像，并且能够返回句柄。 imh = image(cat(3,cells,z,z)); set(imh, 'erasemode', 'none') axis equal axis tight ●矩阵和图像可以相互转化，所以初始条件可以是矩阵，也可以是图形。以下 代码生成一个零矩阵，初始化元胞状态为零，然后使得中心十字形的元胞状态= 1。 z = zeros(n,n); cells = z; cells(n/2,.25*n:.75*n) = 1; cells(.25*n:.75*n,n/2) = 1; ●Matlab的代码应尽量简洁以减小运算量。以下程序计算了最近邻居总和，并 按照CA规则进行了计算。本段Matlab代码非常灵活的表示了相邻邻居。 x = 2:n-1; y = 2:n-1; sum(x,y) = cells(x,y-1) + cells(x,y+1) + ... cells(x-1, y) + cells(x+1,y) + ... cells(x-1,y-1) + cells(x-1,y+1) + ... cells(x+1,y-1) + cells(x+1,y+1); cells = (sum==3) | (sum==2 & cells); ●加入一个简单的图形用户界面是很容易的。在下面这个例子中，应用了三个 按钮和一个文本框。三个按钮，作用分别是运行，停止，程序退出按钮。文框是用来显示的仿真运算的次数。 %build the GUI %define the plot button plotbutton=uicontrol('style','pushbutton',...
元胞自动机简史 元胞自动机的诞生是人类探索人的认识本质的结果，也是计算技术巨大进步推动的结果。自古以来，人类认识一般问题的根本方法就是，建模和计算（推演）。模型是人类智力能理解自然世界的唯一方式。而元胞自动机正是一种可以用来建模也非常容易进行计算的理论框架和模型工具。最早从计算的视角审视问题的是关心人的认识本质的哲学家。笛卡尔认为, 人的理解就是形成和操作恰当的表述方式。洛克认为, 我们对世界的认识都要经过观念这个中介, 思维事实上不过是人类大脑对这些观念进行组合或分解的过程。霍布斯更是明确提出, 推理的本质就是计算。莱布尼兹也认为, 一切思维都可以看作是符号的形式操作的过程。进入20 世纪, 弗雷格, 怀特海、罗素等人通过数理逻辑把人类的思维进一步形式化, 形成了所谓的命题逻辑及一阶和高阶逻辑。在他们看来, 逻辑和数学, 都是根据特定的纯句法规则运作的。在这里, 所有的意义都被清除出去而不予考虑。在弗雷格和罗素的基础上, 维特根斯坦在他的早期哲学中把哲学史上自笛卡尔以来的原子论的理性主义传统发展到了一个新的高度。在维特根斯坦看来, 世界是逻辑上独立的原子事实的总和, 而不是事物的总和; 原子事实是一些客体的结合, 这些事实和它们的逻辑关系都在心灵中得到表达: 我们在心灵中为自己建造了事实的形象。人工智能事实上就是试图在机器中实现这种理性主义理想的一门学科。 在计算理论发展过程中, 阿兰·图灵(A. Turing) 的思想可以说是最关键的。在1936 年发表的论文中, 图灵提出了著名的图灵机概念。图灵机的核心部分有三: 一条带子、一个读写头、一个控制装置。带子分成许多小格, 每小格存一位数; 读写头受制于控制装置, 以一小格为移动量相对于带子左右移动, 或读小格内的数, 或写符号于其上。可以把程序和数据都以数码的形式存储在带子上。这就是“通用图灵机”原理。图灵在不考虑硬件的前提下, 严格描述了计算机的逻辑构造。这个理论不仅解决了纯数学基础理论问题, 而且从理论上证明了研制通用数字计算机的可行性。 图灵认为, 人的大脑应当被看作是一台离散态机器。尽管大脑的物质组成与计算机的物质组成完全不同, 但它们的本质则是相同。。离散态机器的行为原则上能够被写在一张行为表上, 因此与思想有关的大脑的每个特征也可以被写在一张行为表上, 从而能被一台计算机所仿效。1950 年, 图灵发表了《计算机器和智能》的论文, 对智能问题从行为主义的角度给出了定义, 设计出著名的“图灵测验,论证了心灵的计算本质, 并反驳了反对机器能够思维的9 种可能的意见。 与图灵提出人的大脑是一台离散态的计算机的思想几乎同一时期, 计算机科学的另一个 开创者冯·诺伊曼(J . von Neumann) 则开始从计算的视角思考生命的本质问题。一个人工的机器能够繁殖它自己吗? 当年笛卡尔在声称动物是机器的时候, 就曾被这个问题所难住。但冯·诺伊曼要回答这个问题, 他要找到自动机产生后代的条件, 他要证明机器可以繁殖! 为此, 冯·诺伊曼作了一个思想实验。他想象一台机器漂浮在一个池塘的上面, 这个池塘里有许多机器的零部件。这台机器是一台通用的建造器: 只要给出任何一台机器的描述,这台机器就会在池塘中寻找合适的部件, 然后再制造出这台机器。如果能够给出它自身的描述, 它就可以创造出它本身。不过, 这还不是完全的自我繁殖, 因为后代机器还没有对自身的描述, 它们因此不能复制自己。所以, 冯·诺伊曼继续假定最初的机器还必须包含一个描述复制器, 一旦后代机器产生出来, 它也从亲代那里复制一份关于自身的描述, 这样, 后代机器就可以无穷无尽地繁殖下去。 冯·诺伊曼的试验揭示了一个深刻的问题：任何自我繁殖的系统的基因材料, 无论是自然的还是人工的, 都必须具有两个不同的基本功能: 一方面它必须起到计算机程序的作用, 是一种在繁殖下一代时能够运行的算法, 另一方面它必须起到被动数据的作用, 是一个能够复制和传给下一代的描述。1953 年沃森和克里克揭示的DNA 结构和自我复制的机理。DNA 的特性正好具备冯·诺伊曼所指出的两个要求。 然而, 冯·诺伊曼对他自己的动力学模型并不十分满意。他不能充分地获得最小的逻辑前提, 因为该模型仍然以具体的原材料的吸收为前提。冯·诺伊曼感到, 该模型没有很好地把过程的
第23卷第1期2011年3月河南工程学院学报(自然科学版)J OURNA L O F HENAN I N ST ITUTE OF ENG I N EER I NG V o l 23,N o 1M ar .2011 扩散过程的元胞自动机模拟 李延升1,2,侯珂珂1,张保林2 (1.许昌学院化学化工学院,河南许昌461000; 2.郑州大学化工与能源学院,河南郑州450007)摘 要:以元胞自动机为研究方法,通过编写M atlab 程序,以演化示意图的形式,模拟了圆域内的扩散过程,给出了 累积演化率曲线.同时,用微积分的方法,解析了该扩散过程,并结合实例与元胞自动机方法对比.研究证 明,元胞自动机可以生动形象地模拟扩散过程,且与微积分得到的结论一致. 关键词:扩散;元胞自动机;扩散方程;模拟 中图分类号:TQ019 文献标识码:A 文章编号:1674-330X (2011)01-0001-04 收稿日期:2011-02-11 作者简介:李延升(1971-),男,山东章丘人,讲师,博士,主要从事化工传递过程与精细化工的教学研究工作.通讯作者:张保林(1947-),男,河南西平人,教授,博士生导师,主要从事化工传递过程与精细化工的教学研究工作. 扩散过程是重要的质量传递方式之一,元胞自动机则是近年来新兴的仿真模拟方法.但是,将两者结合,即用元胞自动机研究扩散过程的文献却相对较少.有关此类的报道,多是和反应过程相关联且研究的侧重点放在后者[1],很少见到用元胞自动机专门研究扩散过程的报道.另外,在有关的报道中,元胞自动机模型的参数往往过多且相互之间的关系复杂,分析时需要综合多门学科的理论,这限制了它的实际应用.作为一种新兴的研究手段,元胞自动机的意图是以极其简单的规则解释或模拟复杂的现象,而有关的报道多数违背了这一意图,无法体现元胞自动机的优越性.本文即从此方面入手,将元胞自动机方法与数学分析方法相对比,给出了生动形象的扩散过程动态画面,为进一步的研究奠定了基础. 1 元胞自动机简介 元胞自动机有时也被称为细胞自动机、点格自动机、分子自动机或单元自动机,它是现代计算机之父N eum ann 及其追随者提出的想法.20世纪末21世纪初,Stephen 将这种带有强烈的纯游戏色彩的原始想法从学术上加以分类整理,最终使之上升到了科学方法论[2]. 元胞自动机是一时间和空间都离散的动力系统,散布在规则格网(Lattice Grid)中的每一元胞(Ce ll)取有限的离散状态,遵循同样的演化规则,依据确定的局部规则同步更新,大量元胞通过简单的相互作用而构成动态系统的演化.不同于一般的动力学模型,元胞自动机不是由严格定义的物理方程或函数确定,而是由一系列模型构造的规则构成,凡是满足这些规则的模型都可以算作元胞自动机模型.因此,元胞自动机是一类模型的总称,或者说是一个方法框架[1-2].元胞自动机最基本的组成为元胞、元胞空间、邻居及规则这4部 分.简单来讲,元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成[1-3]. 2 扩散过程元胞自动机模型的提出 同普通的元胞自动机一样,本文的元胞自动机也是采用等间隔的点作为元胞.不失一般性,以二维的圆形区域为离散域,以处于中心的某个元胞为圆心,取适当长度的半径,在圆域内的元胞即为该元胞自动机的元胞,正好在圆上的交叉点也看作圆域内的元胞,见图1.以纵横方向上均匀分布的点为元胞,圆域内外的元胞区分非常明确.为了让画面清晰,该图的元胞较少,在实际应用时,元胞数量要比该图多得多.
元胞自动机简史元胞自动机的诞生是人类探索人的认识本质的结果，也是计算技术巨大进步推动的结果。自古以来，人类认识一般问题的根本方法就是，建模和计算（推演）。模型是人类智力能理解自然世界的唯一方式。而元胞自动机正是一种可以用来建模也非常容易进行计算的理论框架和模型工具。最早从计算的视角审视问题的是关心人的认识本质的哲学家。笛卡尔认为, 人的理解就是形成 和操作恰当的表述方式。洛克认为, 我们对世界的认识都要经过观念这个中介, 思维事实上不过是 人类大脑对这些观念进行组合或分解的过程。霍布斯更是明确提出, 推理的本质就是计算。莱布尼兹也认为, 一切思维都可以看作是符号的形式操作的过程。进入20 世纪, 弗雷格, 怀特海、罗素等人通过数理逻辑把人类的思维进一步形式化, 形成了所谓的命题逻辑及一阶和高阶逻辑。在他们看来, 逻辑和数学, 都是根据特定的纯句法规则运作的。在这里, 所有的意义都被清除出去而不 予考虑。在弗雷格和罗素的基础上, 维特根斯坦在他的早期哲学中把哲学史上自笛卡尔以来的原 子论的理性主义传统发展到了一个新的高度。在维特根斯坦看来, 世界是逻辑上独立的原子事实 的总和, 而不是事物的总和; 原子事实是一些客体的结合, 这些事实和它们的逻辑关系都在心灵中得到表达: 我们在心灵中为自己建造了事实的形象。人工智能事实上就是试图在机器中实现这种理性主义理想的一门学科。 在计算理论发展过程中，阿兰图灵（A. Turing）的思想可以说是最关键的。在1936年发表的论 文中, 图灵提出了著名的图灵机概念。图灵机的核心部分有三: 一条带子、一个读写头、一个控制装置。带子分成许多小格, 每小格存一位数; 读写头受制于控制装置, 以一小格为移动量相对于带子左右移动, 或读小格内的数, 或写符号于其上。可以把程序和数据都以数码的形式存储在带子上。这就是“通用图灵机”原理。图灵在不考虑硬件的前提下, 严格描述了计算机的逻辑构造。这个理论不仅解决了纯数学基础理论问题, 而且从理论上证明了研制通用数字计算机的可行性。 图灵认为, 人的大脑应当被看作是一台离散态机器。尽管大脑的物质组成与计算机的物质组成完全不同, 但它们的本质则是相同。。离散态机器的行为原则上能够被写在一张行为表上, 因此与思想有关的大脑的每个特征也可以被写在一张行为表上, 从而能被一台计算机所仿效。1950 年, 图灵发表了《计算机器和智能》的论文, 对智能问题从行为主义的角度给出了定义, 设计出著名的“图灵测验,论证了心灵的计算本质, 并反驳了反对机器能够思维的9 种可能的意见。 与图灵提出人的大脑是一台离散态的计算机的思想几乎同一时期, 计算机科学的另一个 开创者冯诺伊曼J . von Neumann）则开始从计算的视角思考生命的本质问题。一个人工的机器能 够繁殖它自己吗？当年笛卡尔在声称动物是机器的时候，就曾被这个问题所难住。但冯诺伊曼要回答这个问题, 他要找到自动机产生后代的条件, 他要证明机器可以繁殖! 为此，冯诺伊曼作了一个思想实验。他想象一台机器漂浮在一个池塘的上面，这个池塘里有许多机器的零部件。这台机器是一台通用的建造器: 只要给出任何一台机器的描述,这台机器就会在 池塘中寻找合适的部件, 然后再制造出这台机器。如果能够给出它自身的描述, 它就可以创造出它本身。不过, 这还不是完全的自我繁殖, 因为后代机器还没有对自身的描述, 它们因此不能复制自己。所以，冯诺伊曼继续假定最初的机器还必须包含一个描述复制器，一旦后代机器产生岀来，它也从亲代那里复制一份关于自身的描述, 这样, 后代机器就可以无穷无尽地繁殖下去。 冯诺伊曼的试验揭示了一个深刻的问题：任何自我繁殖的系统的基因材料，无论是自然的还是人工的, 都必须具有两个不同的基本功能: 一方面它必须起到计算机程序的作用, 是一种在繁殖下一代时能够运行的算法, 另一方面它必须起到被动数据的作用, 是一个能够复制和传给下一代的描述。1953 年沃森和克里克揭示的DNA 结构和自我复制的机理。DNA 的特性正好具备冯诺伊曼所指岀的两个要求。 然而, 冯诺伊曼对他自己的动力学模型并不十分满意。他不能充分地获得最小的逻辑前提, 因为该模型仍然以具体的原材料的吸收为前提。冯诺伊曼感到, 该模型没有很好地把过程的 逻辑形式和过程的物质结构区分开。作为一个数学家，冯诺伊曼需要的是完全形式化的抽象理
元胞自动机的定义与构成及其特征 https://www.doczj.com/doc/0a13258836.html, 2005-4-17 15:05:00 来源：生命经纬 尽管元胞自动机有着较为宽松，甚至近乎模糊的构成条件。但作为一个数理模型，元胞自动机有着严格的科学定义。同时，元胞自动机是一个地地道道的"混血儿"。是物理学家、数学家，计算机科学家和生物学家共同工作的结晶。因此。对元胞自动机的含义也存在不同的解释，物理学家将其视为离散的、无穷维的动力学系统;数学家将其视为描述连续现象的偏微分方程的对立体，是一个时空离散的数学模型;计算机科学家将其视为新兴的人工智能、人工生命的分支;而生物学家则将其视为生命现象的一种抽象。下面给出几种常见的定义: 1.元胞自动机的物理学定义 元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。 具体讲,构成元胞自动机的部件被称为"元胞"，每个元胞具有一个状态。这个状态只琵取某个有限状态集中的一个，例如或"生"或"死"，或者是256中颜色中的一种，等等;这些元胞规则地排列在被你为"元胞空间"的空间格网上;它们各自的状态随着时间变化。而根据一个局部规则来进行更新，也就是说，一个元胞在某时刻的状态取决于、而且仅仅家决于上一时刻该元胞的状态以及该元胞的所有邻居元胞的状态;元胞空间内的元胞依照这样的局部规则进行同步的状态更新，整个元胞空间则表现为在离散的时间维上的变化。 2.元胞自动机的数学定义 美国数学家L.P.Hurd和K·Culik等人在90年代初，对元胞自动机分别从集合论和拓扑学等角度进行了严格地描述和定义 (谢惠民，1994; Culik,II K，1990;李才伟,1997) 1)基于集合论的定义 设d代表空间维数，k代表元胞的状态，并在一个有限集合S中取值，r表元胞的邻居半径。Z是整数集，表示一维空间，t代表时间。 为叙述和理解上简单起见，在一维空间上考虑元胞自动机，即假定d=1。那么整个元胞空间就是在一维空间，将整数集Z上的状态集S的分布，记为S Z。元胞自动机的动
[1] Zhou W H, Lee J, Li G L, et al. Embedding Game of Life into a Simple Asynchronous Cellular Automaton[C]. Computing and Networking (CANDAR), 2014 Second International Symposium on IEEE, 2014: 503-506. [2]Tian J, Treiber M, Zhu C, et al. Cellular Automaton Model with Non-hypothetical Congested Steady State Reproducing the Three-Phase Traffic Flow Theory[M]. Cellular Automata. Springer International Publishing, 2014: 610-619. [3]Delivorias S, Hatzikirou H, Penaloza R, et al. Detecting Emergent Phenomena in Cellular Automata Using Temporal Description Logics[M]. Cellular Automata. Springer International Publishing, 2014: 357-366. [4] D'Ariano G M, Mosco N, Perinotti P, et al. Path-integral solution of the one-dimensional Dirac quantum cellular automaton[J]. Physics Letters A, 2014, 378(43): 3165-3168. [5] Bisio A, D’Ariano G M, Tosini A. Quantum field as a quantum cellular automaton: The Dirac free evolution in one dimension[J]. Annals of Physics, 2015, 354: 244-264. [6] Masuda T, Nishinari K, Schadschneider A. Cellular Automaton Approach to Arching in Two-Dimensional Granular Media[M]. Cellular Automata. Springer International Publishing, 2014: 310-319. [7] Takada K, Namiki T. on Limit Set of Two-Dimensional Two-State Linear Cellular Automaton Rules[C]. Computing and Networking (CANDAR), 2014 Second International Symposium on. IEEE, 2014: 470-475. [8] Al-Mamun M A, Srisukkham W, Fall C, et al. A cellular automaton model for hypoxia effects on tumour growth dynamics[C].Software, Knowledge, Information Management and Applications (SKIMA), 2014 8th International Conference on. IEEE, 2014: 1-8. [9] Hu M L, Sun J. Sudden change of geometric quantum discord in finite temperature reservoirs[J]. Annals of Physics, 2015, 354: 265-273. [10] Bure? M, Siegl P. Hydrogen atom in space with a compactified extra dimension and potential defined by Gauss’ law [J]. Annals of Physics, 2015, 354: 316-327. [11] Terrier V. Recognition of linear-slender context-free languages by real time one-way cellular automata[C]. AUTOMATA 2015. 2015, 9099: 251-262. [12] Fuentes M L, Klimchuk J A. Two-dimensional cellular automaton model for the evolution of active region coronal plasmas[J]. The Astrophysical Journal, 2015, 799(2): 128. [13] Tucker G E, Hobley D E J, Hutton E, et al. CellLab-CTS 2015: a Python library for continuous-time stochastic cellular automaton modeling using Landlab[J]. Geoscientific Model Development Discussions, 2015, 8: 9507-9552.
冯诺依曼元胞自动机（John V on Neumann’s Cellular Automaton） 冯诺依曼元胞自动机是由计算机科学家约翰冯诺依曼发明的一种图灵完备的元胞自动机。目前它还有三种不同的规则，分别名叫：JvN29，Nobili32,Hutton32.可以模拟许多“机器”，比如自我复制机（Replicator）就是其中最重要的一种。 目前几乎没有介绍冯诺依曼元胞自动机的中文网站，所以我在此给大家比较详细地介绍一下它。 一、JvN29 这是由John Von Neumann在1940年发明的自动机。由于其上的活细胞共有29种状态，故名JvN29，29种状态分别为： 前8种和后3种是激发态（不稳定），不用记。 其中4个蓝箭头和4个红箭头相当于“导线”，4个绿箭头和4个紫箭头分别是两种电线中的“电流”。 紫箭头可以eat（即将其变为死细胞，下同）蓝箭头，绿箭头可以eat 红箭头。不过紫箭头权限更高，它还可以eat掉4种菱形。 当一串绿箭头或紫箭头到达“导线”最前端时，前端前的死细胞就会根据绿箭头或紫箭头的不同序列而变成不同的稳定活细胞，这个过程叫做翻译，需要用到前8种激发态作为桥梁。8种激发态间有一个转化关系，如图： 我们一般采用所谓“密码子”的箭头序列。在JvN29中，每种稳定细胞都对应一个密码子，即一个可以产生此种细胞的箭头序列。从上图可以总结出JvN29的密码子如下：
这个表同样适用于红箭头和紫箭头。 菱形是种重要的状态，根据“导线”的不同接法它可以发挥不同的作用。 1）当接为一入多出时，菱形充当信号分路器： 当单独信号输入时： 当两个信号输入时： 可见，在分路时信号会延迟，菱形的三种激发态充当了桥梁的作用， 2）接入为三入一出或二入二出时，菱形充当“与门”，当且仅当发输入端全都有信号来时，菱形才进入激发态 3）特殊地，若接入一入一出，就构成信号延迟器：
按模型的数学方法分： 几何模型、图论模型、微分方程模型、概率模型、最优控制模型、规划论模型、马氏链模型等 按模型的特征分： 静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型等 按模型的应用领域分： 人口模型、交通模型、经济模型、生态模型、资源模型、环境模型等。 按建模的目的分： 预测模型、优化模型、决策模型、控制模型等 一般研究数学建模论文的时候，是按照建模的目的去分类的，并且是算法往往也和建模的目的对应 按对模型结构的了解程度分： 有白箱模型、灰箱模型、黑箱模型等 比赛尽量避免使用，黑箱模型、灰箱模型，以及一些主观性模型。 按比赛命题方向分： 国赛一般是离散模型和连续模型各一个，2016美赛六个题目（离散、连续、运筹学/复杂网络、大数据、环境科学、政策） 数学建模十大算法 1、蒙特卡罗算法 （该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法） 2、数据拟合、参数估计、插值等数据处理算法 （比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具）
3、线性规划、整数规划、多元规划、二次规划等规划类问题 （建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法 （这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法 （这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法 （这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法 （当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法 （很多问题都是从实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法 （如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）10、图象处理算法 （赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的这些图形如何展示，以及如何处理就是需要解决的问题，通常使用Matlab进行处理） 算法简介 1、灰色预测模型（必掌握）
https://www.doczj.com/doc/0a13258836.html, 1 元胞自动机方法及其在材料介观模拟中的应用 何燕，张立文，牛静 大连理工大学材料系（１１６０２３） E-mail ： commat ＠https://www.doczj.com/doc/0a13258836.html, 摘 要：元胞自动机（ＣＡ）是复杂体系的一种理想化模型，适合于处理难以用数学公式定量描 述的复杂动态物理体系问题，如材料的组织演变等。本文概述了元胞自动机方法的基本思想 及原理，介绍了ＣＡ的基本组成及特征，综述了ＣＡ方法在材料介观模拟研究中的应用。研究表 明ＣＡ法在对金属凝固结晶、再结晶、及相变现象等材料介观尺度的组织模拟中表现出特有的 优越性。 关键词：元胞自动机，组织演变，介观模拟，动态再结晶 １． 引 言 自２０世纪计算机问世以来，用计算机建立模型来模拟材料行为的方法在材料设计中的 应用越来越广泛，此方法既可节省大量的人力物力和实验资金，又能为实验提供巨大的灵活 性和方便性，因而已经引起了各界科学家的高度重视和极大兴趣。计算机对材料行为的模拟 主要有三个方面：材料微观行为、介观行为和宏观行为的模拟。材料的微观行为是指在电子、原子尺度上的材料行为，如模拟离子实（原子）体系行为，在这方面主要应用分子动力学、分子力学等理论方法；材料的介观行为是指材料显微组织结构的转变，包括金属凝固结晶、再结晶及相变过程，在这方面的模拟主要应用Ｍｏｎｔｅ Ｃａｒｌｏ（ＭＣ）方法和Ｃｅｌｌｕｌａｒ Ａｕｔｏｍａｔａ（ＣＡ）方法；材料的宏观行为主要指材料加工方面，如材料加工中的塑性变形，应力 应变场及温度场的变化等，在这方面的模拟工作主要应用大型有限元软件Ｍａｒｃ， Ａｎｓｙｓ等。大量实验研究表明，材料的微观组织结构决定了其宏观行为及特征。因此，对材料介观行为 的模拟显得尤为重要。传统的数学建模方法是建立描述体系行为的偏微分方程，它依赖于对 体系的成熟定量理论，而对大多数体系来说这种理论是缺乏的；从微观入手的Ｍｏｎｔｅ Ｃａｒｌｏ 方法主要依赖于体系内部自由能的计算，由于其运算量大，需要大量的数据，运算速度慢，为模拟工作带来了诸多不便；而ＣＡ方法则另辟蹊径，通过直接考察体系的局部相互作用， 再借助计算机模拟这种作用导致的总体行为，从而得到其组态变化，并体现出宏观上的金属 性能。由于ＣＡ的结构简单，便于计算，允许考虑数量极大的元胞，并且在空间和时间的尺 度上都不受限制，出于以上特点，元胞自动机方法已经受到越来越多研究工作者的青睐。本 文概述了元胞自动机方法的基本思想及原理，介绍了ＣＡ的基本组成及特征，对ＣＡ法在模拟 介观组织行为方面的应用进行了综述。
2005年5月重庆大学学报(自然科学版)May2005第28卷第5期Journal of Chongqing University(Natural Science Editi on)Vol.28 No.5 文章编号:1000-582X(2005)05-0086-04 基于元胞自动机原理的微观交通仿真模型3 孙 跃,余 嘉,胡友强,莫智锋 (重庆大学自动化学院,重庆 400030) 摘 要:描述了一种对高速路上的交通流仿真和预测的模型。该模型应用了元胞自动机原理对复杂的交通行为进行建模。这种基于元胞自动机的方法是将模拟的道路量离散为均匀的格子,时间也采用离散量,并采用有限的数字集。同时,在每个时间步长,每个格子通过车辆跟新算法来变换状态,车辆根据自定义的规则确定移动格子的数量。该方法使得在计算机上进行仿真运算更为可行。同时建立了跟车模型、车道变换的超车模型,并根据流程对新建的VP算法绘出时空图。提出了一个设想:将具备自学习的神经网络和仿真系统相结合,再根据安装在高速路上的传感器所获得的统计数据,系统能对几分钟以后的交通状态进行预测。 关键词:元胞自动机;交通仿真;数学模型 中图分类号:TP15;TP391.9文献标识码:A 1 元胞自动机 生物体的发育过程本质上是单细胞的自我复制过程,50年代初,计算机创始人著名数学家冯?诺依曼(Von Neu mann)曾希望通过特定的程序在计算机上实现类似于生物体发育中细胞的自我复制[1],为了避免当时电子管计算机技术的限制,提出了一个简单的模式。把一个长方形平面分成若干个网格,每一个格点表示一个细胞或系统的基元,它们的状态赋值为0或1,在网格中用空格或实格表示,在事先设定的规则下,细胞或基元的演化就用网格中的空格与实格的变动来描述。这样的模型就是元胞自动机(cellular aut omata)。 80年代,元胞自动机以其简单的模型方便地复制出复杂的现象或动态演化过程中的吸引子、自组织和混沌现象而引起了物理学家、计算机科学家对元胞自动机模型的极大兴趣[1]。一般来说,复杂系统由许多基本单元组成,当这些子系统或基元相互作用时,主要是邻近基元之间的相互作用,一个基元的状态演化受周围少数几个基元状态的影响。在相应的空间尺度上,基元间的相互作用往往是比较简单的确定性过程。用元胞自动机来模拟一个复杂系统时,时间被分成一系列离散的瞬间,空间被分成一种规则的格子,每个格子在简单情况下可取0或1状态,复杂一些的情况可以取多值。在每一个时间间隔,网格中的格点按照一定的规则同步地更新它的状态,这个规则由所模拟的实际系统的真实物理机制来确定。格点状态的更新由其自身和四周邻近格点在前一时刻的状态共同决定。不同的格子形状、不同的状态集和不同的操作规则将构成不同的元胞自动机。由于格子之间在空间关系不同,元胞自动机模型分为一维、二维、多维模型。在一维模型中,是把直线分成相等的许多等分,分别代表元胞或基元;二维模型是把平面分成许多正方形或六边形网格;三维是把空间划分出许多立体网格。一维模型是最简单的,也是最适合描述交通流在公路上的状态。 2 基于元胞自动机的交通仿真模型的优点目前,交通模型主要分为3类: 1)流体模型(Hydr odyna m ic Model),在宏观上,以流体的方式来描述交通状态; 2)跟车模型(Car-f oll owing Model),在微观上,描述单一车辆运动行为而建立的运动模型; 3)元胞自动机模型(Cellular Aut omat on),在微观 3收稿日期:2005-01-04 基金项目:重庆市自然科学基金项目(6972) 作者简介:孙跃(1960-),浙江温州人,重庆大学教授,博士,研究方向:微观交通仿真、电力电子技术、运动控制技术及系统。
元胞自动机理论基础 Chapter1 元胞自动机(Cellular Automata，简称CA，也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。是一时间和空间都离散的动力系统。散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架。其特点是时间、空间、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时间和空间上都是局部的。 1. 自动机 自动机(Automaton)通常指不需要人们逐步进行操作指导的设备(夏培肃，1984)。例如，全自动洗衣机可按照预先安排好的操作步骤作自动地运行;现代计算机能自动地响应人工编制的各种编码指令。完成各种复杂的分析与计算;机器人则将自动控制系统和人工智能结合，实现类人的一系列活动。另一方面，自动机也可被看作为一种离散数字动态系统的数学模型。例如，英国数学家A.M.Turing于1936年提出的图灵机就是一个描述计算过程的数学模型(TuringA M.，1936)。它是由一个有限控制器、一条无限长存储带和一个读写头构成的抽象的机器，并可执行如下操作: ·读写头在存储带上向左移动一格; ·读写头在存储带上向右移动一格; ·在存储的某一格内写下或清除一符号; ·条件转移。 图灵机在理论上能模拟现代数字计算机的一切运算，可视为现代数字计算机的数学模型。实际上，一切"可计算"函数都等价于图灵机可计算函数，而图灵机可计算函数类又等价于一般递归函数类。 根据存储带是否有限，可将自动机划分为有限带自动机(Finite Automaton)和无限带自动机(Infinite Automaton)。由于图灵机有无限长的存储带，所以为一种无限带自动机。有限带自动机常用作数字电路的数学模型，也用来描述神经系统和算法;而无限带自动机主要用来描述算法，也用来描述繁殖过程 (如细胞型自动机和网络型自动机)。 有限自动机是一种控制状态有限、符号集有限的自动机，是一种离散输入输出系统的数学模型。可将有限自动机设想成由一条划分为许多方格的输入带和一个控制器组成的机器:在输入带的每一个小格中可以容 纳一个符号，这些符号取自一个有限符号集S-控制器具有有限个可能状态(构成集合Q)。并在每一时刻仅处于其中的一个状态q;控制器有一个读入头，可以从输入带中读入符号;时间是离散的，初始时控制器处在状态;控制器的功能是根据其当前状态g和读入头从输入带上得到的符号a,来确定控制器的下一时刻的状态实现从状态q到状态q'，实现从状态q到状态铲q'的转移，并将读入头右移一格。控制器另一功能是识别终止状态(它们构成Q的一个子集F)，也可将该识别功能视为有限自动机的输出。 从数学上来定义，有限自动机是一个五元组: FA=(Q，S，δ，q0，F) 其中，Q是控制器的有限状态集、S是输入符号约有限集、δ是控制状态转移规律的Q×S到Q的映射(可用状态转移图或状态转移表表示)，q0是初始状态、F是终止状态集。若δ是单值映射，则称M为确定性有限自动机;若δ是多值映射，则称M为非确定性有限自动机。
第24卷 第5期 自 然 资 源 学 报V ol 24N o 5 2009年5月J OURNAL OF NATURAL RESOURCES M ay ,2009 收稿日期:2008-08-22;修订日期:2008-12-02。 基金项目:国家自然科学基金重点资助项目(40830532);国家自然科学基金资助项目(40801236);国家杰出青年基金资助项目(40525002);国家高技术研究发展计划资助项目(2006AA12Z206)。 作者简介:杨青生(1974-),男,青海乐都人,讲师,博士,主要研究遥感与地理信息模型及应用。E m ai :l qs y ang2002@https://www.doczj.com/doc/0a13258836.html, 基于元胞自动机的土地资源节约利用模拟 杨青生1,2 (1 广东商学院资源环境学院,广州510230;2 中山大学地理科学与规划学院,广州510275) 摘要:为模拟节约土地资源的城市可持续发展形态,以珠江三角洲城市快速发展的东莞市为 例,运用元胞自动机(C A )、地理信息系统(G IS)和遥感(RS)从历史数据中建立城市空间扩展的 C A,将土地资源节约利用程度与城市用地空间聚集程度相结合,在评价城市用地空间聚集程度 的基础上,通过不断增加离市中心距离权重和离公路距离权重,调整CA 的参数,模拟节约土地 资源,城市用地在空间上紧凑布局的城市形态,并以调整参数的模型(离市中心距离权重为 -0 006,离公路权重为-0 024)模拟结果为基础,分析了实现城市用地空间上紧凑发展,土地 资源节约利用的政策:到2010年,东莞市离市中心27k m 范围内的适宜地区可规定为鼓励城市 发展区,27~34k m 范围内的适宜地区可规定为限制性城市发展区,其它地区为非城市发展区。 关 键 词:土地资源;节约利用;紧凑;元胞自动机 中图分类号:F301 24;P208 文献标识码:A 文章编号:1000-3037(2009)05-0753-10 1 引言 元胞自动机(C ellular Auto m ata ,简称CA )具有强大的空间运算能力,可以有效地模拟复杂的动态系统。近年来,CA 已被越来越多地运用在城市模拟中,取得了许多有意义的研究成果[1~3]。CA 可以模拟虚拟城市,验证城市发展的相关理论,也可以模拟真实城市的发展, 如W u 等模拟了广州市的城市扩展 [4];黎夏和叶嘉安模拟了东莞市的城市扩张[5]。同时,用CA 可以模拟未来的城市规划景观,如黎夏等模拟了珠江三角洲地区城市不同发展条件下的规划景观[6,7]。这些研究表明,C A 能模拟出与实际城市非常接近的特征,可以由此预测未来城市的发展及土地利用变化,为城市和土地利用规划提供决策依据。 CA 的特点是通过一些简单的局部转换规则,模拟出全局的、复杂的空间模式。为了模拟城市,除了运用CA 的局部转换规则外,还要在转换规则中引入影响城市扩展的区域变量和全局变量。转换规则中的这些变量对应着很多参数,这些参数值反映了不同变量对模型的 贡献 程度。研究表明,这些参数值对模拟的结果影响很大。目前,C A 主要通过多准则判断(MCE ) [8]、层次分析法(AH P)[9]和主成分分析[10]、自适应模型[11]、人工神经网络模型 [5]、决策树[12]等方法确定模型的参数值。笔者也采用粗集[13]、支持向量机[14]、贝叶斯分类[15]、空间动态转换规则[16]等方法研究了非线性、动态转换规则模拟城市发展。目前,采用CA 模拟虚拟城市系统和真实城市系统已经非常成熟,模型的精度也越来越高,而模拟可
元胞自动机N a S c h模型 及其M A T L A B代码 This manuscript was revised by the office on December 22, 2012
元胞自动机N a S c h模型及其M A T L A B代码 作业要求 根据前面的介绍，对NaSch模型编程并进行数值模拟： 模型参数取值：Lroad=1000，p=0.3，Vmax=5。 边界条件：周期性边界。 数据统计：扔掉前50000个时间步，对后50000个时间步进行统计,需给出的结果。 基本图（流量-密度关系）：需整个密度范围内的。 时空图（横坐标为空间，纵坐标为时间，密度和文献中时空图保持一致,画500个时间步即可）。 指出NaSch模型的创新之处，找出NaSch模型的不足，并给出自己的改进思路。 流量计算方法： 密度＝车辆数/路长； 流量flux=density×V_ave。 在道路的某处设置虚拟探测计算统计时间T内通过的车辆数N； 流量flux=N/T。 在计算过程中可都使用无量纲的变量。 1、NaSch模型的介绍 作为对184号规则的推广，Nagel和Schreckberg在1992年提出了一个模拟车辆交通的元胞自动机模型，即NaSch模型（也有人称它为NaSch模型）。 时间、空间和车辆速度都被整数离散化。道路被划分为等距离的离散的格子，即元胞。 每个元胞或者是空的，或者被一辆车所占据。 车辆的速度可以在（0～Vmax）之间取值。 2、NaSch模型运行规则 在时刻t到时刻t+1的过程中按照下面的规则进行更新： （1）加速：vnmin(vn1,vmax) 规则（1）反映了司机倾向于以尽可能大的速度行驶的特点。 （2）减速：vnmin(vn,dn) 规则(2)确保车辆不会与前车发生碰撞。 （3）随机慢化：以随机概率p进行慢化，令：vnmin(vn-1,0) 规则(3)引入随机慢化来体现驾驶员的行为差异，这样既可以反映随机加速行为，又可以反映减速过程中的过度反应行为。这一规则也是堵塞自发产生的至关重要因素。 （4）位置更新：vnxnvn，车辆按照更新后的速度向前运动。其中vn，xn分别表示第n辆车位置和速度；l（l≥1）为车辆长度； p表示随机慢化概率；dnxn1xn1表示n车和前车n+1之间空的元胞数； vmax为最大速度。 3、NaSch模型实例