元胞自动机简史 元胞自动机的诞生是人类探索人的认识本质的结果，也是计算技术巨大进步推动的结果。自古以来，人类认识一般问题的根本方法就是，建模和计算（推演）。模型是人类智力能理解自然世界的唯一方式。而元胞自动机正是一种可以用来建模也非常容易进行计算的理论框架和模型工具。最早从计算的视角审视问题的是关心人的认识本质的哲学家。笛卡尔认为, 人的理解就是形成和操作恰当的表述方式。洛克认为, 我们对世界的认识都要经过观念这个中介, 思维事实上不过是人类大脑对这些观念进行组合或分解的过程。霍布斯更是明确提出, 推理的本质就是计算。莱布尼兹也认为, 一切思维都可以看作是符号的形式操作的过程。进入20 世纪, 弗雷格, 怀特海、罗素等人通过数理逻辑把人类的思维进一步形式化, 形成了所谓的命题逻辑及一阶和高阶逻辑。在他们看来, 逻辑和数学, 都是根据特定的纯句法规则运作的。在这里, 所有的意义都被清除出去而不予考虑。在弗雷格和罗素的基础上, 维特根斯坦在他的早期哲学中把哲学史上自笛卡尔以来的原子论的理性主义传统发展到了一个新的高度。在维特根斯坦看来, 世界是逻辑上独立的原子事实的总和, 而不是事物的总和; 原子事实是一些客体的结合, 这些事实和它们的逻辑关系都在心灵中得到表达: 我们在心灵中为自己建造了事实的形象。人工智能事实上就是试图在机器中实现这种理性主义理想的一门学科。 在计算理论发展过程中, 阿兰·图灵(A. Turing) 的思想可以说是最关键的。在1936 年发表的论文中, 图灵提出了著名的图灵机概念。图灵机的核心部分有三: 一条带子、一个读写头、一个控制装置。带子分成许多小格, 每小格存一位数; 读写头受制于控制装置, 以一小格为移动量相对于带子左右移动, 或读小格内的数, 或写符号于其上。可以把程序和数据都以数码的形式存储在带子上。这就是“通用图灵机”原理。图灵在不考虑硬件的前提下, 严格描述了计算机的逻辑构造。这个理论不仅解决了纯数学基础理论问题, 而且从理论上证明了研制通用数字计算机的可行性。 图灵认为, 人的大脑应当被看作是一台离散态机器。尽管大脑的物质组成与计算机的物质组成完全不同, 但它们的本质则是相同。。离散态机器的行为原则上能够被写在一张行为表上, 因此与思想有关的大脑的每个特征也可以被写在一张行为表上, 从而能被一台计算机所仿效。1950 年, 图灵发表了《计算机器和智能》的论文, 对智能问题从行为主义的角度给出了定义, 设计出著名的“图灵测验,论证了心灵的计算本质, 并反驳了反对机器能够思维的9 种可能的意见。 与图灵提出人的大脑是一台离散态的计算机的思想几乎同一时期, 计算机科学的另一个 开创者冯·诺伊曼(J . von Neumann) 则开始从计算的视角思考生命的本质问题。一个人工的机器能够繁殖它自己吗? 当年笛卡尔在声称动物是机器的时候, 就曾被这个问题所难住。但冯·诺伊曼要回答这个问题, 他要找到自动机产生后代的条件, 他要证明机器可以繁殖! 为此, 冯·诺伊曼作了一个思想实验。他想象一台机器漂浮在一个池塘的上面, 这个池塘里有许多机器的零部件。这台机器是一台通用的建造器: 只要给出任何一台机器的描述,这台机器就会在池塘中寻找合适的部件, 然后再制造出这台机器。如果能够给出它自身的描述, 它就可以创造出它本身。不过, 这还不是完全的自我繁殖, 因为后代机器还没有对自身的描述, 它们因此不能复制自己。所以, 冯·诺伊曼继续假定最初的机器还必须包含一个描述复制器, 一旦后代机器产生出来, 它也从亲代那里复制一份关于自身的描述, 这样, 后代机器就可以无穷无尽地繁殖下去。 冯·诺伊曼的试验揭示了一个深刻的问题：任何自我繁殖的系统的基因材料, 无论是自然的还是人工的, 都必须具有两个不同的基本功能: 一方面它必须起到计算机程序的作用, 是一种在繁殖下一代时能够运行的算法, 另一方面它必须起到被动数据的作用, 是一个能够复制和传给下一代的描述。1953 年沃森和克里克揭示的DNA 结构和自我复制的机理。DNA 的特性正好具备冯·诺伊曼所指出的两个要求。 然而, 冯·诺伊曼对他自己的动力学模型并不十分满意。他不能充分地获得最小的逻辑前提, 因为该模型仍然以具体的原材料的吸收为前提。冯·诺伊曼感到, 该模型没有很好地把过程的
收稿日期:2003 01 09;修订日期:2003 04 23 基金项目:本项研究得到国家自然科学基金项目(No.40072030)、教育部博士点基金(20010491007)和国土资源部科研项目(B1 9)共同资助。作者简介:陈建平(1959 ),男,教授,博士导师,1995年毕业于成都理工学院,获博士学位,主要从事资源评价和 3S !技术应用的教学与科研工作,已发表文章80余篇,专著7部。E mail:3s@https://www.doczj.com/doc/543123870.html, 文章编号:1007 4619(2004) 03 0254 07基于GIS 和元胞自动机的荒漠化演化预测模型 陈建平,丁火平,王功文,厉 青,冯 春 (中国地质大学,北京 100083) 摘 要: 荒漠化是当今全球最严重的环境与社会经济问题之一,荒漠化以其发展速度和严重的灾害性而引起国际学术界的广泛关注。开展荒漠化变化的驱动因素及其作用机制研究,尤其是在此基础上对荒漠化与其驱动因素之间的关系进行量化及动态模拟模型研究,对荒漠化的防治和治理具有十分重要的意义。尝试利用3S 技术,结合元胞自动机理论架构出一套荒漠化动态模拟模型,进而对北京及邻区荒漠化的发展趋势进行预测。实验证明,这套系统是对荒漠化演化机制从宏观和微观角度进行模拟的有效方法。关键词: 荒漠化;元胞自动机;驱动因素;动态模拟中图分类号: P208/XB7 文献标识码: A 1 引 言 荒漠化是指包括气候变异和人类活动在内的种种因素造成的干旱、半干旱、亚湿润干旱区的土地退 化。荒漠化已经演变为全球性的环境问题之一,对人类的生存发展构成严重威胁 [1] 。据资料显示:全 球陆地面积的1/4受荒漠化威胁,9亿多人口受到荒漠化影响;全球荒漠化正以每年约50000 70000km 2的速度扩展;全球荒漠化造成的直接经济损失每年达423亿美元。中国是世界上受荒漠化影响最严重的国家之一。目前,中国的荒漠化土地约为261万km 2,并有更多的土地正面临着荒漠化的潜在威胁;荒漠化土地从东北经华北到西北形成一条不连续的弧形分布带。荒漠化土地不仅面积广大,而且其发展速率仍在加大,在20世纪60 70年代为1560km 2 /a,80年代为2100km 2 /a,90年代已经达到2460km 2 /a [2]。荒漠化的不断发展,已经严重地影响了中国北方地区生态环境建设和社会经济的可持续发展。荒漠化以其发展速度和严重的灾害性而引起国际学术界的广泛关注和重视。中国在荒漠化治理研究方面进行了大量的工作,取得了一系列成果。近几年来,遥感(RS)、地理信息系统(GIS)和全球定位系统(GPS)及其集成技术迅速发展,大量应 用于灾害监测、资源监测等方面,在多元数据定量分析与综合研究方面取得了很好的效果,不足之处在于动态模拟演化研究。本文基于元胞自动机理论将荒漠化动态演化规律与其空间分布特征相结合,利用3S 技术的集成技术,结合数学模型探讨荒漠化时空动态演变规律,并预测其未来发展趋势。 C A 模型(Cellular Automaton Model)又叫元胞(细胞,元胞,分子或点格)自动机模型。最初是由John Von Neumann 40年代末提出来的,用于研究自复制系统的逻辑特性。C A 理论在地学中的应用最早可追溯到20世纪60年代。美国北卡来罗那州大学的Chapin 和Weiss(1968)在土地利用变化研究中采用了离散动态模型,十分接近CA 模型。Tobler 在70年代,认识到C A 理论在模拟复杂地学现象中的优势,首先正式采用了C A 概念模型来模拟当时美国五大湖边底特律地区城市的迅速扩展。进入80年代后,伴随着C A 理论的深入和发展,CA 在地学中的应用和理论研究也取得了长足的进步,成为地学研究的热点。Yong 和Wadge 用C A 模拟了火山爆发时,火山熔岩在重力作用下的漫流扩散过程。Simth 设计了一个简单地学元胞自动机模型模拟了地形侵蚀的过程。Flavio B onfatti 等人,用C A 模型对意大利威尼斯泻湖在周期性潮汐作用下的动态变化进行了生动的模拟和预测。CA 在地学中的许多邻域都已 第8卷第3期遥 感 学 报 Vol.8,No.32004年5月 JOURNAL OF REMOTE SENSING May,2004
元胞自动机与MATLAB 引言 元胞自动机（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); ●加入一个简单的图形用户界面是很容易的。在下面这个例子中，应用了三个 按钮和一个文本框。三个按钮，作用分别是运行，停止，程序退出按钮。文框是用来显示的仿真运算的次数。
元胞自动机 元胞自动机的概念 元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。 具体讲,构成元胞自动机的部件被称为"元胞"，每个元胞具有一个状态。这个状态只琵取某个有限状态集中的一个，例如或"生"或"死"，或者是256中颜色中的一种，等等;这些元胞规则地排列在被你为"元胞空间"的空间格网上;它们各自的状态随着时间变化。而根据一个局部规则来进行更新，也就是说，一个元胞在某时刻的状态取决于、而且仅仅家决于上一时刻该元胞的状态以及该元胞的所有邻居元胞的状态;元胞空间内的元胞依照这样的局部规则进行同步的状态更新，整个元胞空间则表现为在离散的时间维上的变化。 元胞自动机的构成 元胞自动机最基本的组成元胞、元胞空间、邻居及规则四部分。简单讲，元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。 1.元胞 元胞又可称为单元。或基元，是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上。 2.状态 状态可以是{0,1}的二进制形式。或是{s0,s2,……s i……s k}整数形式的离散集，严格意义上。元胞自动机的元胞只能有一个犬态变量。但在实际应用中，往往将其进行了扩展。例如每个元胞可以拥有多个状态变量。李才伟(1997)在其博士论文工作中，就设计实现了这样一种称之为"多元随机元胞自动机"模型。并且定义了元胞空间的邻居(Neighbor)关系。由于邻居关系，每个元胞有有限个元胞作为它的邻居; 3.元胞空间(Lattice)
元胞所分布在的空间网点集合就是这里的元胞空间。 (l)元胞空间的几何划分:理论上，它可以是任意维数的欧几里德空间规则划分。目前研究多集中在一维和二维元胞自动机上。对于一维元抱自动机。元胞空间的划分只有一种。而高维的元胞自动机。元胞空间的划分则可能有多种形式。对于最为常见的二维元胞自动机。二维元胞空间通常可按三角、四万或六边形三种网格排列(图2-5)。 这三种规则的元胞空间划分在构模时各有优缺点: 三角网格的优点是拥有相对较少的邻居数目，这在某些时候很有用;其缺点是在计算机的表达与显示不方便，需要转换为四方网格。 四方网格的优点是直观而简单，而且特别适合于在现有计算机环境下进行表达显示;其缺点是不能较好地模拟各向同性的现象，例如后面提到的格子气模型中的HPP模型。 六边形网格的优点是能较好地模拟各向同性的现象，因此，模型能更加自然而真实，如格气模型中的FHP模型;其缺点同三角网格一样，在表达显示上较为困难、复杂。 (2)边界条件:在理论上，元胞空间通常是在各维向上是无限延展的，这有利于在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理想条件，因此，我们需要定义不同的边界条件。归纳起来，边界条件主要有三种类型:周期型、反射型和定值型。有时，在应用中，为更加客观、自然地模拟实际现象，还有可能采用随机型，即在边界实时产生随机值。 周期型(Pehodic Boundary)是指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的"圈"。对于二维空间，上下相接，左右相接。而形成一个拓扑圆环面(Torus)，形似车胎或甜点圈。周期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间型作为试验。 反射型(Reflective Boundary)指在边界外邻居的元胞状态是以边界为轴的镜面反射。例如在一维空间中，当r=1时的边界情形: 定值型(Constant Boundary)指所有边界外元胞均取某一固定常量，如0，1等。需要指出的是，这三种边界类型在实际应用中，尤其是二维或更高维数的构模时，可以相互结合。如在二维空间中，上下边界采用反射型，左右边界可采用周期型(相对边界中。不能一方单方面采用周期型)。
2014美赛A题元胞自动机完整代码,做出来了有木有~ 2014美赛相关MATLAB程序(基于NS模型) 主程序:NaSch_3.m程序代码 % 单车道最大速度3个元胞开口边界条件加速减速随机慢化 clf clear all %build the GUI %define the plot button plotbutton=uicontrol('style','pushbutton',... 'string','Run', ... 'fontsize',12, ... 'position',[100,400,50,20], ... 'callback', 'run=1;'); %define the stop button erasebutton=uicontrol('style','pushbutton',... 'string','Stop', ... 'fontsize',12, ... 'position',[200,400,50,20], ... 'callback','freeze=1;'); %define the Quit button quitbutton=uicontrol('style','pushbutton',... 'string','Quit', ... 'fontsize',12, ... 'position',[300,400,50,20], ... 'callback','stop=1;close;'); number = uicontrol('style','text', ... 'string','1', ... 'fontsize',12, ...
元胞自动机理论基础 https://www.doczj.com/doc/543123870.html,/complex/models/ca/ca1.htm 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)
浙江理工大学 毕业论文(设计)诚信声明 我谨在此保证：本人所写的毕业论文(设计)，凡引用他人的研究成果均已在参考文献或注释中列出。论文(设计)主体均由本人独立完成，没有抄袭、剽窃他人已经发表或未发表的研究成果行为。如出现以上违反知识产权的情况，本人愿意承担相应的责任。
声明人(签名)： 年月日
摘要 本文利用Java 作为编程语言，Java swing编写图形界面实现了生命游戏的可视化编程，并且在生命游戏的基础上进行了一定的扩展，增加了系统复杂性,给定了简单的初始状态以此进一步研究细胞自动机在复杂系统中所表现的能力，为细胞自动机及生命游戏的后续研究奠定基础。结论：计算机实现的细胞自动机在计算机模拟的复杂系统中确实拥有复杂系统所表现出来的自适应性，不确定性等特性 关键词：生命游戏；细胞自动机；复杂系统 ABSTRACT Using Java as a programming language, Java Swing as graphical interface to achieve a visual programming of the Game of Life. Expand the basis of the game of life, increased system complexity, given the simple initial state in order to further studythe demonstrated ability of cellular automata in a complex system, lay the foundation for the follow-up study of cellular automata and the Game of Life. Conclusion: The computer-implemented cellular automaton computer simulation of complex systems do .FOODMULTIPLE*getWeakPercentByAge()*beEatedToMeat()*(0.3+speed70. 0bodySize+strength30.0bodySize); LifeGameCommon.FOODMULTIPLE为程序设定的倍数，用于控制个体所需食物量从而达到控制个体数量的效果。 getWeakPercentByAge()返回的是一个削弱值，表现为个体在寿命的前20%以及后20%竞争力会按一定比例上升下降. beEatedToMeat()返回该生物被吃掉时产生的肉食数量，与个体体积成正比 (0.3+speed70.0bodySize+strength30.0bodySize)表示个体需要的食物量至少需要自身体型的0.3倍，当速度力量高时，也会提高这个数值，显然速度的提升对食物的消耗更少。 3.7 环境规则 根据LifeGameCommon中定义的环境自增长比率（下一节中有介绍），每一个周期每一格环境自增长，每当比率达到下一个等级，曾颜色变深一级，土地，草地，每当比率达到100%，则环境变换成下一种类型（土->草，草->树），草地，树林，每
数学建模讲座：元胞自动机 aqua2001 数学中国超级版主 September4,2010 大家好，我是数学中国超级版主aqua2001。我们这次做元胞自动机的讲座。 元胞自动机是一个在数学建模中有用的工具。在这里，我们打算通过一些模型，来初步介绍元胞自动机的应用。使用计算机进行模拟往往在建模过程中有很大的用途，但凭空说“模拟真实世界”往往让人觉得难以下手。而元胞自动机则往往能给模拟方法提供一个容易思考的框架。 考虑到大家在建模中的实用性，所以在介绍当中，我会尽量多做直观的介绍，尽量避免数学计算。详细的数学内容大家可以参照相关书籍。讲解中有一些图片或说法来源于书籍或网络。 我们在讲解当中，除了一些直接用到元胞自动机的模型，也介绍了在元胞自动机的发展过程当中一些比较有影响力的内容。它们不一定对建模有直接的用途，但我希望大家对它的了解能够更广泛一些，这样可能对它进行更灵活地运用。 元胞自动机（Cellular Automata或Cellular Automaton,CA）是空间和时间都离散，物理参量只取有限数值集的物理系统的理想化模型。 它的提出，最早是冯?诺依曼在研究能够自我复制的自动机时提出来的。其特点是，空间被分成离散的格子（可以是方形、三角形或六边形等），称之为元胞（Cell）。元胞处于若干可能的状态之一，而且随着时间，其状态可以演化。每个元胞状态的演化，往往要受到临近元胞的状态的影响。而且，在传统的元胞自动机中，每个元胞的变化都是同时进行的。 最著名的元胞自动机的例子，应属Conway提出的“生命游戏”。它的提出并不是为了具体的应用，但其蕴含的丰富内容引起了许多人的兴趣。假设二维空间被划分成方形的格子，当然每个格子都是一个元胞。假设每个元胞只处于两种状态之一：死的与活的。死的可以记为0，活的可以记为1。 现在我们来考察每个元胞周围的“邻居”。“邻居”的定义当然并不唯一， 1