元胞自动机方法的研究进展(本科毕业论文)

毕业论文（2013届）题目：元胞自动机方法的研究进展学院：物理电气信息学院专业：物理学（师范）年级：2009级学生学号：12009243981学生姓名：任治安指导教师：马治完成时间：2013/5/5摘要随着科学技术的飞速发展，复杂性问题已经深入到科学研究的各个层面上。近年来关于复杂性和复杂系统中涌现、自组织特征的探讨使生命和非生命之间的界限越来越模糊。为了研究由大量个体相互作用所形成的复杂现象，如自组织现象、耗散结构、合作效应，计算机专家和物理学家从20世纪80年代开始对元胞自动机（CellularAutomata，简称CA）进行了深入研究。元胞自动机模型具有时间离散、空间离散、状态离散、元胞相互作用局部化和动力学演化同步性等特点。元胞自动机是一种时间、空间、状态都离散的动力学模型，是非线性科学的一种重要研究方法。元胞自动机具有计算的完备性特征,可以模拟复杂系统的突现、混沌等特征，是模拟生态、环境、微观组织演变(金属凝固、再结晶、晶粒长大等)高度复杂现象的有力工具。特别适合于复杂系统时空演化过程的动态模拟研究，它用简单的规则在计算机上模拟各种复杂系统和物理过程。元胞自动机引起了许多研究者的关注，相关研究工作已经广泛展开，论文综述了元胞自动机的研究进展及在不同领域的一些应用。关键词：元胞自动机元胞空间复杂系统AbstractWiththerapiddevelopmentofscienceandtechnology,theproblemofcomplexityhasalreadypenetratedintoallaspectsofscientificresearch,theemergenceofcomplexityandcomplexsysteminrecentyears,theexplorationoftheselforganizingfeaturehasbecomeincreasinglyblurredtheboundariesbetweenlivingandnonliving.Inordertostudybyalargenumberofindividualsformedbytheinteractionofcomplexphenomena,suchasself-organizingphenomenon,dissipativestructure,cooperationeffect,computerexpertandphysicistsstartsfromthe1980stotheCellularAutomata,(CellularAutomata,CAforshort)werestudied.Becausethecellularautomatamodelwithdiscretetimediscretespace,stateofdiscreteandcellularlocalizationofinteractionanddynamicevolutionofsynchronicityetc.Thecellularautomatonisdynamicsmodelwhichonekindoftime,thespace,theconditionallareseparated,isthenon-linearscienceimportantresearchmethod,Thecellularautomatonhasthecomputationcompletecharacteristiccanbeusedtosimulatetheemergence,chaoticcharacteristicsofcomplexsystemistosimulatemicrostructureevolutionecology,environmentand(metalsolidification,recrystallizationandgraingrowthandsoon),apowerfultoolforhighlycomplexphenomenon,suchasparticularlysuitedtothetimeandspaceevolutionofcomplexsystemsimulationresearch,itusesthesimpleruletosimulateeachkindofcomplexsystemandthephysicalprocessonthecomputer.Cellularautomatahasattractedtheattentionofmanyresearchers,andrelatedresearchworkhasbeenwidelyspread,thepapersummarizedthecellularautomata(CA)researchprogressandsomeapplicationsindifferentareas.KeyWords:CellularautomataCellularspacesComplexsystems目录第一章绪论.........................................................11.1研究背景与意义..............................................11.2元胞自动机方法的研究历史与现状..............................21.2.1元胞自动机的诞生.......................................21.2.2元胞自动机发展的三个重要阶段...........................21.3本文的组织结构...............................................4第二章元胞自动方法的基本理论.......................................52.1引言.........................................................52.2元胞自动机定义...............................................52.3元胞自动机的组成.............................................62.3.1元胞(Cell)..............................................62.3.2状态(State)..............................................62.3.3元胞空间(CellSpaces)....................................72.3.4邻域(Neighborhood)......................................92.3.5规则(Rule).............................................102.4元胞自动机特征..............................................112.5元胞自动机的动力学分类......................................12第三章元胞自动机方法的应用........................................143.1概论.......................................................143.2元胞自动机方法的应用.......................................143.2.1元胞自动机方法在社会学中的应用........................143.2.2元胞自动机方法在生物学和医学中的应用..................153.2.3元胞自动机方法在生态学中的应用........................163.2.4元胞自动机方法在计算机科学中的应用....................173.2.5元胞自动机方法在物理学中的应用........................183.2.6元胞自动机方法在化学中的应用..........................183.2.7元胞自动机方法在环境科学中的应用......................193.2.8元胞自动机方法在军事科学中的应用......................20第四章总结与展望..................................................22参考文献...........................................................23致谢...............................................................26物理电气信息学院本科毕业论文1第一章绪论1.1研究背景与意义古代科学方法论本质上是整体论，强调由整体把握对象。近代以来，还原论发挥了重要的作用并且在自然科学领域取得了巨大的成功。它遵循将事物分解为局部或低层次来研究，以局部或低层次问题的解决为基础，向整体或高层次的问题推进。如果局部或低层次的问题无法解决，就将其继续分解下去，直至将问题弄清楚。物理学、化学、生物学基本上按照这种方法论发展起来并获得了成功，但现代科学研究表明，宇宙的许多奥秘来自整体性。例如为什么单个的分子没有温度和压强，而大量的分子聚集起来却有温度和压强？为什么氢元素有易燃性，氧元素有助燃性，而水分子却失去了易燃性和助燃性？为什么上海、北京这样的大城市可以能够不间断的保障食品、医疗、服饰和数千万居民的必需品供应？为什么艾滋病毒能摧毁人类免疫系统？诸如此类复杂问题向还原论提出了挑战[1]因此，许多科学家认为还原论不能全面解决复杂性问题，进而提出了复杂性研究。钱学森先生早在80年代就指出：凡现在不能用还原论方法处理的，或不宜用还原论方法处理的问题，而要用或宜用新的科学方法处理的问题，都是复杂性问题，复杂巨系统就是这类问题。现代科学家通过运用自组织、混沌、涌现、复杂自适应系统等来研究复杂性，而且很重视计算机技术在复杂性研究中的应用，相继提出了演化算法，元胞自动机等模型[2]。元胞自动机作为复杂系统的离散模型，是研究动力学相互作用与时空演化过程的重要实验数学方法。它开创了基础科学研究与复杂性探索的新途径，是一类获得迅速发展的新的并行计算机，又是计算机、信息和智能应用等高科技的热点之一。与传统的方法相比，元胞自动机能更好的模拟化学过程、雪花形成、流体以及湍流形成等难以解释的复杂现象，甚至能逼真的反映大量个体相互作用的细致结构模式。因此，元胞自动机是描述复杂性的比较有效的方法之一，也是复杂系统建模的一种重要方法[3]。总之，研究表明，计算机实验是发现新问题、新方法和新结果的重要手段，元胞自动机是研究复杂系统和复杂性的有效工具。物理电气信息学院本科毕业论文21.2元胞自动机方法的研究历史与现状1.2.1元胞自动机的诞生元胞自动机(CellularAutomata，简称CA)的概念最早是由数学家StanislawUlam和JohnvonNeumann在20世纪50年代提出来的。它的诞生可以说是两种思想的结合，其中“元胞”的思想来源于Ulam，而“自动机”的思想来源于VonNeumann早在20世纪40年代，VonNeumann就对人造机器能否自我复制的问题产生了浓厚的兴趣，并试图构造一个具有自我复制特性和通用计算能力的简单机器。但由于当时人造机器部件昂贵以及计算技术的限制，他不得不寻求一种数学抽象来完成自己的设想。在Ulam的建议下VonNeumann开始从元胞的视角考虑这个问题，他引入元胞以代替“机器部件