元胞自动机在数学模型中的应用.ppt

元胞自动机在数学模型中的应用January 2, 28“Give me space and motion and I will give you the world“Application Of Cellular Automata In Mathematical Modeling应当 尽可能简单 而不是 比较简单地 做每一件事.——A.爱因斯坦提要元 胞 简 介 元 胞 构 成元 胞 行 为元 胞 特 征元 胞 分 类经 典 元 胞应 用 举 例程 序 实 现参 考 文 献元胞简介 （Introduction）元胞自动机是离散（discrete）动力学系统（ dynamic ）l CA之所以是离散系统，是因为元胞是定义在有限的时间和 空间上的，并且元胞的状态是有限l CA被认为是动力学模型，是因为它的举止行为具有动力学 特征什么是元胞（CA）自动机To put it another way“Not to describe a complex system with complex equations, but let the complexity emerge by interaction of simple individuals following simple rules.”Ｂasic IdeaSimulate complex systems by interaction of cells following easy rules.元胞简介 （Introduction）l Original concept of CA is most strongly associated with John von Neumann.l von Neumann was interested in the connections between biology and the then new study of automata theory.l Stanislaw Ulam suggested that von Neumann use a cellular automata as a framework for researching these connections.l The original concept of CA can be credited to Ulam, while the early development of the concept is credited to von Neumann.l Ironically, although von Neumann made many contributions and developments in CA, they are commonly referred to as “non-von Neumann style”, while the standard model of computation (CPU, globally addressable memory, serial processing) is know as “von Neumann style”.元胞自动机的历史（History）元胞构成（Components）元胞（Cell）l 元胞自动机最基本的单元.l 元胞有记忆贮存状态的功能.l 所有元胞状态都安照元胞规则不断更新格子 (Lattice)l 元胞的网格空间.Cell and lattice元胞行为 (Behavior)局部变化引起全局变化l 可以简单认为元胞自动机在运动上类似于波.l 无胞的状态变化依赖于自身状态和邻居的状态元胞自动机的规则(Rule)某元胞下时刻的状态只决定于邻居的状态以及自身的 初始状态．元胞行为 (Behavior)元胞网格(Lattice)Square Triangle Hexagon元胞行为 (Behavior)VonNeumann Neighborhood Moore neighborhoodExtended Moore neighborhood元胞邻居(Neighborhood)元胞行为 (Behavior)其它元胞网格(Neighborhood)元胞行为 (Behavior)边界条件(boundary)元胞行为 (Behavior)元胞自动机的规则决定了元胞的行为征.l 即使一个简单的系统, 也有很多种规则决定下一时刻的状态.——Could base the next state of the cell off of the sum of the states of your neighbors (Game of Life).——Could modify the scope of the neighborhood, so the resulting neighbors could be local (touching), close (neighbor’s neighbors) or global (anywhere in the system) or possibly use random neighbors——Could allow the cells to grow and die.规则系统元胞特征 (Characteristics)离散的网格元胞的同质 离散的状态 局部的作用离散的时间元胞分类 (Classes)空间上元胞可分为三类l 一维元胞自动机l 二维元胞自动机l 三维元胞自动机不同的分类方式概率机与非概率机典型概率机：森林火灾经典元胞生命游戏 生命游戏 (Came of Life)是J. H. Conway在2世纪6年代末设计的一 种单人玩的计算机游戏(Garclner，M.，97、97)。

他与现代的围棋游戏 在某些特征上略有相似：围棋中有黑白两种棋子生命游戏中的元胞有 {“生“，“死“}两个状态 {，};围棋的棋盘是规则划分的网格，黑白两子在空 间的分布决定双方的死活，而生命游戏也是规则划分的网格(元胞似国际 象棋分布在网格内而不象围棋的棋子分布在格网交叉点上)根据元胞 的局部空间构形来决定生死只不过规则更为简单经典元胞生命游戏的构成及规则:l元胞分布在规则划分的网格上；l元胞具有，两种状态，代表“死”，l代表“生”；l元胞以相邻的8个元胞为邻居即Moore邻居形式；l一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状 态 (确切讲是状态的和)决定:在当前时刻，如果一个元胞状态为“生”，且八个相邻元胞中有两个或三 个的状态为“生”，则在下--时刻该元胞继续保持为“生”，否则“死”去；在当前时刻如果一个元胞状态为“死“且八个相邻元胞中正好有三个 为“生“则该元胞在下一时刻 “复活“否则保持为“死“生命游戏经典元胞l 元胞有3个不同的状态.状态为 0是空位,状态= 1是燃烧着的树木, 状态= 2是树木. l 如果4个邻居中有一个或一个以上的是燃烧着的并且自身是树木(状态为2 ),那么该元胞下一时刻的状态是燃烧(状态为1).l 森林元胞(状态为2 )以一个低概率(例如.5 )开始烧(因为闪电). l 一个燃烧着的元胞(状态为1)在下一时时刻变成空位的(状态为 ).l 空元胞以一个低概率(例如. )变为森林以模拟生长. l 出于矩阵边界连接的考虑,如果左边界开始着火,火势将向右蔓延,右边界同理.同样适用于顶部和底部.森林火灾森林火灾的构成及规则:应用举例数学建模中的应用The Booth Tolls for Thee应用举例数学建模中的应用Modeling Flooding from a Dam Failure in South CarolinaCell 0xCell 2xCell 0yCell 2yCell 1FgxFgyYxFpyNet FpFpx程序实现MATLAB的编程考虑矩阵和图形的相互转化ImageImshowpcolor imread1 1 0 1 10 1 1 1 0•0 1 0 11 1 1 1 0 程序实现MATLAB的编程考虑初始化元胞状态 z = zeros(n,n); cells = z; cells(n/2, .25*n:.75*n) =1 ; cells(.25*n:.75*n, n/2) =1;程序实现MATLAB的编程考虑简单的实现规则y=2:n-1; x=2:n-1; sum = veg(y, x+1)+…veg(y, x -1)+ ...veg(y+1, x )+…veg(y -1, x ) ;(y+1,x)(y,x-1) (y,x)(y,x-1)(y-1,x)程序实现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 程序实现典型元胞程序精讲森林火灾sum = (veg(1:n,[n 1:n-1])==1) + (veg(1:n,[2:n 1])==1) + ...(veg([n 1:n-1], 1:n)==1) + (veg([2:n 1],1:n)==1) ; veg = ... 2*(veg==2) - ((veg==2) 程序实现典型元胞程序精讲交通流参考文献（References）l物理系统的元胞自动机模拟(Cellular Automata Modeling of Physical Systems). Bastien Chopard, Michel Droz 祝玉学 赵学龙译lIntroduction to the Theory of Cellular Automata and One- Dimensional Traffic Simulation. Cochinos, Richard.lCellular Automata: A Discrete Universe. Ilachinski.lIntroduction to Cellular Automata. Rennard, Jean-Philepe.lhttp://cell- in Cellular Automata: A Selected Review. Mitchell, Melanie.lRucker R., Walker J., Introduction to CelLab, http://www.fourmilab.ch/cellab/THE END。