第七讲-元胞自动机及应用

2020/1/251元胞自动机及其在城市模拟中的应用2020/1/252基于CA的真实城市模拟其他城市CA模拟应用存在的问题logisticCA的具体实现内容如下：元胞自动机（CA）和地理元胞自动机元胞自动机及其在城市模拟中的应用研究背景城市化作为土地利用／土地覆被变化(LUCC)的重要驱动机制日益引起广泛的关注，而我国正进入城市化的加速发展阶段城市空间模拟日益成为城市规划者、经济学家、生态学家、和致力于可持续发展的资源管理者的重要工具研究背景城市模型发展阶段静态的、均衡的、宏观模型（20世纪50，60年代）动态的、微观模型（20世纪80年代以后）城市增长动态模型分类宏观系统动力学模型：着眼于宏观变量相互关系微观系统动力学模型：宏观现象的微观作用机制CellarAutomataBasedModelMulti-AgentBasedModel研究背景主要的模拟方法及模型基于细胞自动机（CA)的动态模拟基于主体的动态模拟TranSims模型空间统计学模拟马尔可夫链(Lopezetal.,2001)和逻辑斯蒂回归(WuandYeh,1997)基于人工神经网络的模拟格局分析(Shmueli,1998;Pijanowskiaetal.2002)基于分形的形态模拟扩散聚合模型（DLA）(BattyandLongley,1994)；渗透模型(Makseetal.,1998)混沌和灾变模拟自组织临界值（SOC）(Batty1998；Wu1999)研究背景2020/1/256元胞自动机元胞自动机（CellularAutomata）是一种时间、空间、状态都离散的模型，具有强大的空间建模和计算能力，能够模拟具有时空特征的复杂动态系统。元胞自动机的基础就在于“如果让计算机反复地计算极其简单的运算法则，那么就可以使之发展成为异常复杂的模型，并可以解释自然界中的所有现象”的观点。细胞自动机的特点简单性和直观性complexity≠complication离散性；灵活性与开放性易于与GIS、遥感数据处理等系统结合细胞自动机的扩展细胞空间：从无限到有限；从同质到非同质；从规则到不规则细胞状态：表征地理实体或现象的指标、编码或等级的集合邻域：从固定性到非固定性多种多样转换规则：从普遍到非普遍（分区）；从恒定性到变动性；从确定性到随机性，局部个体间相互作用-综合的多层次规则时间概念与地理实体演化相一致，从规律性到不规律性系统从闭合到开放元胞自动机城市增长模型（SLEUTH）的发展与应用2020/1/258CA大力发展考虑自我复制的可能性引入其他领域不断改进、优化20世纪50年代20世纪8、90年代现在•美国数学家vonneumann(冯·诺依曼,计算机之父)；•用CA演示了机器能够模拟自身的现象；•Wolfram等；•对CA的发展起了极大的推动作用，提出CA的五个基本特征；•生命游戏；•对各种复杂现象进行模拟•模型进一步发展•元胞自动机（CA）与计算机科学的发展有密切的关系，元胞自动机的出现为早期计算机的设计提供了依据。元胞自动机的发展历史20世纪90年代–S.Wolfram的研究(1984,Nature)，发现了110规则，对元胞自动机理论作出了巨大贡献。•沃尔夫勒姆1959年出生于伦敦，父亲是相当成功的作家，母亲是牛津大学的哲学教授。他幼年聪慧，13岁入伊顿（Eton）公学，15岁发表首篇粒子物理方面的学术论文，到17岁，他的科学论文发到了《核物理》（TheNuclearPhysics）杂志上。•1978年19岁的沃尔夫勒姆受著名物理学家穆雷·盖尔曼之邀去到加州理工学院（theCaliforniaInstituteofTechnology），从事基本粒子物理学方面的研究，取得显著成就，一年内获得理论物理学博士学位。1980年沃尔夫勒姆成为加州理工学院一员，与费曼（RichardFeynman）共事。1981年被授予麦克阿瑟“天才人物”奖（MacArthurGeniusFellowship），并成为该奖最年轻的获得者。之后他又到了爱因斯坦度过后半生的普林斯顿高级研究所（theInstituteforAdvancedStudy）工作，再后来又成为伊利诺斯大学（theUniversityofIllinois）的物理学、数学和计算机科学教授。•1986年27岁的沃尔夫勒姆创立了以他的姓氏命名的沃尔夫勒姆研究公司（WolframResearch,Inc）后，离开了学术界，成为一位企业家。1988年6月23日他的公司发布了一种著名的数学软件――“数学”（Mathematica），该软件使得人们可以随心所欲地进行各种复杂的数学运算，解方程、求导数、求积分、求矩阵的逆、画三维图形等等不再是一件烦人的苦差事。•加州大学圣迪亚哥分校通讯和信息技术研究所主任拉雷·斯马尔把该软件称作有史以来最重要的科学软件。沃尔夫勒姆本人则因发明该软件被认为是“人类的伟大赞助者”。目前该软件在科学家、工程师以及其他各种职业中有大量的使用者，其数目超过一百万，沃尔夫勒姆因此也成为千万富翁。•1991年“数学”软件第二版发行之后，沃尔夫勒姆开始抽出一部分时间来继续先前的研究。他一般在晚上10点整坐到他的电脑前开始他的科学工作，直到天亮，再睡到中午，然后与他的前数学家妻子和三个孩子度过下午。沃尔夫勒姆就这样在几乎隐居的状态下进行他的科学研究，按照他的说法，牛顿和达尔文在发表他们的惊人之作前，都是单打独斗了好几年的。•在总共4000多个漆黑的夜晚里，沃尔夫勒姆敲击了一亿次键盘，移动了一百多英里的鼠标，作了上万页的笔记，产生的研究结果占了10G的硬盘空间，编制了近一百万行的“数学”软件命令，运行了一千万亿次的电脑运算。最后形成了一本1200多页、5磅重的大部头。《一种新科学》《一种新科学》•从“完全打破现有的学术体系，按照完全不同的原理来理解自然界”的意义出发，新作被命名为《一种新科学》。•《一种新科学》以如下惊人之言开始它的鸿篇巨制：“三个世纪以前，人们发现建立在数学方程基础上的规律能够用于对自然界的描述，伴随着这种新观念，科学发生了转变。在此书中我的目的是将要用简单的电脑程序来表达更为一般类型的规律，并在此种规律基础上建立一种新的科学，从而启动另一场科学变革。”•“与牛顿发现的万有引力基本原理相媲美的科学金字塔”《一种新科学》•沃尔夫勒姆声称此书是科学史上最为重要的一部著作，而他所做的一切不亚于牛顿的贡献。早在该书面世以前，沃尔夫勒姆在接受《福布斯》杂志记者采访时就夸耀了他将在书中给出的几个主要发现，譬如，向自然选择学说作出挑战；时间为什么单向流逝；怎样制造人造生物；解释股市涨落；诸如从雷电到星系的复杂系统如何蕴藏着智能；树叶、树木、贝壳、雪花和几乎所有其他东西的形状为什么是那个样子的等•《新科学》首先用元胞自动机完成了乘法、除法运算，和求素数、求平方根、求π值，甚至解偏微分方程。并把一维元胞自动机扩展到多维元胞自动机，产生更高的复杂程度，模拟了雪花、生物细胞等等。•沃尔夫勒姆的“新科学革命”波及了如此广泛的专业领域，他的一些“过激”言论自然遭到了来自传统科学界的猛烈反击。《一种新科学》•沃尔夫勒姆的“计算等价原理”是一条让人褒贬不一的大胆设想。他认为，所有过程，无论是由人力产生的还是自然界中自发的，都可以视作一种计算过程。在他看来，从山顶滚下的岩石也是计算机，因为这个系统每一步都有输入，按照固定的规则更新系统，就如PC机一样。沃尔夫勒姆之所以产生这样的观点，是因为按照他的定义，宇宙就是一台电脑。在接受《纽约时报》的一次采访中，沃尔夫勒姆承认在角落里静静地生锈的一桶铁钉也是一台普适计算机，其相关特征与人的智能是可有一比的•在接受《福布斯》记者采访时沃尔夫勒姆倒是作出了他的大胆预言：“50年内，更多的技术，将基于我的科学而不是传统科学，被创造出来。人们在学习代数之前将先学元胞自动机理论”。•我们这个时代真的有幸产生一位可以与牛顿比肩的划时代科学伟人？一场新的科学革命真的已悄然发生？好在50年不长，我们走着瞧。2020/1/2515基本特点（wolfram，1984）：•元胞分布在按照一定规则划分的离散的元胞空间上；•系统的演化按照等间隔时间分布进行，时间变量取等长的时刻点；•每个元胞都有明确的状态，并且元胞的状态只能取有限个离散值；•元胞的下一时刻演化的状态值是由确定的转换规则所决定的；•每个元胞的转换规则只由局部领域内的元胞状态所决定。2020/1/2516CA的核心是确定其转换规则，根据具体的需要解决的问题，转换规则的类型、结构等都有很大的不同。邻域的类型主要有摩尔邻域和冯诺伊曼邻域两种，其半径的大小也需根据实际问题而定。传统CA模型中状态是离散的，但有学者也开始将其扩展为连续的（黎夏，叶嘉安，1999），以体现元胞的持续变化过程。2020/1/2517说明：冯诺伊曼领域、摩尔邻域、扩展的摩尔领域2020/1/2518CA的组成元胞（cell）和元胞空间（Lattice）1状态（state）和初始状态（initialconfiguration）2领域（Neighborhood）3转换规则（TransitionRule）42020/1/2519离散时间集元胞及状态领域规则/演变函数元胞空间2020/1/2520元胞（Cell）•元胞是元胞自动机最基本的组成部分；•一个元胞就是一个存储元件，可以记录状态；•元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上的。2020/1/2521元胞空间•一维元胞空间Cell2020/1/2522元胞空间•2维元胞空间2020/1/2523元胞空间•三维元胞空间：2020/1/2524状态（state）•状态的数目是有限的（Numberofstatesshouldbefinite）•初始形态决定了各个元胞的初始状态onoff1232020/1/2525离散时间维上演化•所有的元胞都在离散时间上进行变化t=1t=22020/1/2526领域（Neighborhood）•一个元胞的领域由其周围的元胞组成•冯诺依曼领域（vonNeumannNeighborhood）•摩尔领域（MooreNeighborhood）2020/1/2527转换规则（TransitionRule）•转换规则决定了元胞在下一个时刻的状态；•简单讲，就是一个状态转移函数。CTRBLS…2020/1/2528•与传统的建模方法相比，元胞自动机直接模拟系统各组元之间的相互作用，因此能够通过一些简单的规则产生出高度复杂的演化结果。该方法现在已经成功地运用于对诸如交通系统、经济系统、火灾系统等复杂系统的研究中。2020/1/2529生命游戏模型－最经典的CA模型•1970年前后，英国数学家JohnConway和他的学生在“细胞自动装置”的研究过程中提出生命游戏。它在70年代曾一度使许多人着迷，无论学生、教师，也不分从事何种专业工作的人，都在计算机上做大量的试验。[它的规则很简单：假设平面上画好了方形网格，这个世界中的每个方格居住着一个活着的或死了的细胞。一个细胞在下一个时刻生死取决于相邻八个方格中活着的或死了的细胞的数量。如果相邻方格活着的细胞数量过多，这个细胞会因为资源匮乏而在下一个时刻死去；相反，如果周围活细胞过少，这个细胞会因太孤单而死去。生命游戏•实际中，可以设定周围活细胞的数目怎样时才适宜该细胞的生存。如果这个数目设定过高，世界中的大部分细胞会因为找不到太多的活的邻居而死去，直到整个世界都没有生命；如果这个数目设定过低，世界中又会被生命充满而没有什么变化。实际中，这个数目一般选取2或者3；这样整个生命世界才不至于太过荒凉或拥挤，而是一种动态的平衡。这样的话，游戏的规则就是：当一个方格周围有2或3个或细胞时，方格中的活细胞在下一个时刻继续存活；即使这个时刻方格中没有活细胞，在下一个时刻也会“诞生”活细胞。在这个游戏中，还可以设定一些更加复杂的规则，例如当前方格的状况不仅由父一代决定，而且还考虑祖父一代的情况。你还可以作为这个世界的God，随意设