元胞

元胞自动机仿真苏永孟大连大学数学建模工作室2016年9月5号•元胞自动机的规则非常简单，甚至用一句话就可以描述，但是他却是万能的。——冯.诺依曼•GivemespaceandmotionandIwillgiveyoutheworld元胞自动机•元胞自动机简介•元胞自动机理论•经典例子•作业1.发展历史2.应用领域元胞自动机简介发展历史•元胞自动机（CellularAutomata，简称CA）最初的元胞自动机是由冯.诺依曼在1950年代为模拟生物细胞的自我复制提出的。•1970年，剑桥大学的约翰.何顿.康威设计了“生命游戏”的电脑游戏后，元胞自动机吸引了科学家的注意。•1983年斯蒂芬·沃尔夫勒姆发表一系列的论文，对初等元胞自动机的模型进行了深入研究，并且用熵来描述其演变行为，将元胞自动机分为平稳型，周期型，混沌型和复杂型。应用领域•生物领域：肿瘤的增长机理和过程模拟、艾滋病毒的感染过程等•生态学领域：生态系统的动态变化过程的模拟、生物群落的扩散模型等•物理领域：流体力学领域，磁场、电场、热扩散和热传导的模拟等•化学领域：通过模拟原子、分子等各种微观粒子在化学反应中的相互作用，进而研究化学反应的过程•其它领域：交通科学领域、计算机科学与信息学领域、环境科学领域、社会学领域、军事科学领域1.定义2.元胞自动机的构成元胞网格规则元胞的边界元胞的邻居元胞的状态3.元胞自动机的分类元胞自动机理论什么是元胞自动机•元胞自动机是离散动力学系统，用简单的规则控制相互作用的元胞模拟复杂世界。•元胞自动机之所以是离散系统，是因为元胞是定义在有限的时间和空间上，而元胞的状态是无限的。•元胞自动机被认为是动力学模型，是因为他的举止行动具有动力学特征。元胞自动机的构成1.元胞元胞是元胞自动机基本单元元胞有记忆贮存状态的功能所有元胞状态都安照元胞规则不断更新2.网格•所有的元胞被放置在一个网格中：一维网格二维网格三维网格常见的二维网格正方型网格三角型网格六边型网格3.规则•局部变化引起全局变化可以简单认为元胞自动机在运动上类似于波.元胞的状态变化依赖于自身状态和邻居的状态某元胞下时刻的状态只决定于邻居的状态以及自身的初始状态．4.元胞的邻居冯.诺伊曼型摩尔型扩展摩尔型5.元胞的边界•理论上的元胞空间通常是在各维上是无限的,但却无法在计算机上实现,因此,我们需要定义不同的边界条件。有周期边界（在2维中主要指上下连接，左右连接）、固定边界、绝热边界、映射边界•周期边界：是指相对边界连接起来的元胞空间。对于一维空间，元胞空间表现为一个首尾相接的“圈”。对于二维空间，上下相接，左右相接。而形成一个拓扑圆环面，形似车胎或甜点圈。周期型空间与无限空间最为接近，在理论探讨时，常以此类空间型作为试验。•绝热边界：使虚元胞赋相邻元胞的位置的元胞值。•固定边界：对虚元胞用预先赋值的方法使其邻居完整。•映射边界：相当于在虚元胞中复制其他邻居的值。abbabbaaab1周期边界固定边界绝热边界映射边界周期边界6.元胞的状态•取值于一个有限的离散集。严格意义上,元胞自动机的元胞只能有一个状态变量,但在实际应用中,往往将其进行了扩展。元胞自动机的分类•一维元胞自动机•二维元胞自动机•多维元胞自动机一维元胞•初等元胞自动机(ECA)是状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径为r的一维元胞自动机。二维元胞•元胞分布在二维欧几里德平面上规则划分的网格点上，通常为方格划分。以J.H.Conway的“生命游戏”为代表，“深林火灾”，应用最为广泛。由于，世界上很多现象是二维分布的，还有一些现象可以通过抽象或映射等方法，转换到二维空间上，所以，二维元胞自动机的应用最为广泛，多数应用模型都是二维元胞自动机模型。多维元胞示例生命游戏森林火灾生命游戏•生命游戏是Conway在20世纪60年代末设计的,其元胞分布在二维正方型网格上;元胞具有“生”和“死”两种状态;一个元胞的生死由该时刻本身的生死状态和周围八个邻居(Moore邻居)的状态决定。•规则：（1）在当前时刻，如果一个元胞状态为“生”，且八个相邻元胞中有两个或三个的状态为“生”，则在下--时刻该元胞继续保持为“生”，否则“死”去。（2）在当前时刻。如果一个元胞状态为死。且八个相邻元胞中正好有三个为生。则该元胞在下一时刻复活。否则保持为死游戏规则1代表生0代表死除八个顶点元胞之外的元胞求状态和求和如果总和为2的话，则下一时刻的状态不改变如果总和为3，则下一时刻的状态为1否则状态=0MATLAB的编程考虑(y+1,x)(y,x-1)(y,x)(y,x+1)(y-1,x)(y+1,x-1)(y-1,x+1)(y-1,x-1)(y+1,x+1)核心代码•x=2:n-1;•y=2:n-1;•fori=1:100•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);•set(imh,'CData',cat(3,cells,z,z))•end森林火灾规则：元胞有3个不同的状态。状态为0是树木，状态=1是空地，状态=5是燃烧着的树木。如果4个邻居中有一个或一个以上的是燃烧着的并且自身是树木，那么该元胞下一时刻的状态是燃烧。森林元胞（状态为0）以一个低概率（例如0.000005）开始烧（因为闪电）。一个燃烧着的元胞（状态为5）在下一时刻（时间步长可以控制）变成空位的（状态为0）。空元胞以一个低概率（例如0.01）变为森林以模拟生长核心代码•Ca=ca;•zuo=ca(:,[n1:n-1]);you=ca(:,[2:n1]);•shang=ca([n1:n-1],:);xia=ca([2:n1],:);•su=zuo+you+shang+xia;•ca(Ca==0&(su=5|(rand(n)Plighting)))=5;•ca(Ca==5&time=3)=1;•ca(Ca==1&rand(n)Pgrowth)=0;•set(h,'cdata',cat(3,(ca==5),(ca==0),zeros(n)))•time(ca~=Ca)=0;•time=time+1;RGB图像•RGB模式是基于自然界中3种基色光的混合原理，将红（R），绿（G）和蓝（B）3种基色按照0（黑）到255（白色）的亮度值在每个色阶中分配，从而指定其色彩。•当三种基色的亮度值相等时，产生灰色。•当三种基色的亮度值都是0时，产生纯黑色。•当三种基色的亮度值都是255时，产生纯白色。•Set：设置函数，一般调整图的属性。Cat：用来联结数组。用法：C=cat(dim,A,B)按dim来联结A和B两个数组。C=cat(dim,A1,A2,A3,...)按dim联结所有输入的数组。e.g.a=cat(3,A,B)左括号后的3表示构造出的矩阵维数；在新的矩阵中第1、2维就是A和B这两个矩阵的行数和列数，第3维是A和B这两个矩阵的矩阵个数，即为2；•Image:把三维数据组合成图像。与上面的cat组合的三维数据对应。合成后图像中的颜色代表元胞的状态。作业•今年假期的暑假作业•要求：•男生每人交一份；•女生尽量交一份•9月30号前交到[e-mail]谢谢聆听