元胞自动机简介.ppt
第二次大作业：元胞自动机,初等元胞自动机(Elementary Cellular Automata),一、元胞自动机概况20世纪50年代，John von Neumann 最早提出；(von Neumann,J.1963，collected works,edited by A.H.Taub)1970年，John Conway 提出生命游戏(Conway,J.(1970).In M.Gardner,(Ed.),Scientific American,223(4),pp.120-123.)1983年，Stephen Wolfram 初等元胞自动机(Stephen Wolfram.Reviews of Modern Physics,1983,Vol.55.Stephen Wolfram.Nature,1984,Vol.311)1986年至今，理论及应用,初等元胞自动机(Elementary Cellular Automata),二、格子及其状态任意格子i,有两种状态，且状态是随时间变化。,三、状态的演化 状态演化方程,周期边界,初等元胞自动机(Elementary Cellular Automata),四、映射的种类,初等元胞自动机(Elementary Cellular Automata),例题 按规则90 演化0011011010。,初等元胞自动机(Elementary Cellular Automata),五、时空图 0白色 1黑色 L=100初值取第50个格子为1，对每个规则演化100步。如下结构时空图,初等元胞自动机(Elementary Cellular Automata),六、时空图举例,rule 18,rule 57,rule 150,rule 30,rule 73,rule 126,rule 124,rule 169,初等元胞自动机(Elementary Cellular Automata),七、元胞自动机种类1983年，Stephen Wolfram 对初等元胞自动机的分类平稳型:自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。周期型:经过一定时间运行后，元胞空间趋于一系列简单的固定结构(Stable Paterns)或周期结构(Periodical Patterns)。混沌型:自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统计特征不再变止，通常表现为分形分维特征。复杂型:出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。,初等元胞自动机(Elementary Cellular Automata),八、元胞自动机应用在社会学中，元胞自动机用于研究经济危机的形成与爆发过程、个人行为的社会性，流行现象，如服装流行色的形成等。在生物学中，元胞自动机的设计思想本身就来源于生物学自繁殖的思想，因而它在生物学上的应用更为自然而广泛。例如：元胞自动机用于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索(Victor.Jonathan.D.1990)、爱滋病病毒HIV的感染过程(Sieburg.H.B.1990)、自组织、自繁殖等生命现象的研究以及最新流行的克隆(Clone)技术的研究等(ErmentroutG.B.1993)。应用领域涉及社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、歹境、军事学等。,初等元胞自动机(Elementary Cellular Automata),图为二维元胞自动机局部示意图，其中晶格1为对象元胞，2-9为对象元胞的邻居，设这些元胞在t时刻的状态为，则对象元胞1在t+1时刻的状态为：,15,元胞自动机 Cellular Automata邻居定义 Neighbor hood definitionsModels 模型Game of Life 生命游戏Highway Simulation 道路模拟Disease Spreading,revisited 疾病传播,初等元胞自动机(Elementary Cellular Automata),16,元胞自动机使用格子的方式定义:,一维 元胞自动机,二维 元胞自动机,初等元胞自动机(Elementary Cellular Automata),17,Moore Neighborhood,单个元胞仅仅与自己的邻居发生关联，邻居状态决定元胞的状态 二维空间上邻居的定义上的 the Moore neighborhood:,1st 阶 Moore 邻居 2nd order Moore邻居,初等元胞自动机(Elementary Cellular Automata),18,Von-Neumann Neighborhood,二维空间上邻居的定义Von-Neumann neighborhood:,1st 阶Von-Neumann neighborhood,2nd 阶 Von-Neumann neighborhood,初等元胞自动机(Elementary Cellular Automata),19,Game of Life 生命游戏,在二维空间中，建立 模型 Ni=1st order Moore neighbours 数量 对于目标元胞 i；.在每个元胞上循环，each cell i:不活动状态Deactivate:If Ni 3.活动状态Activate:if cell i is deactivated and Ni=3,20,Game of Life 生命游戏,在二维空间中，建立 模型 Ni=1st order Moore neighbours 数量 对于目标元胞 i；.在每个元胞上循环，each cell i:不活动状态Deactivate:If Ni 3.活动状态Activate:if cell i is deactivated and Ni=3,任何活着的元胞少于2个活着的邻居，要处于非激活状态，比拟人口过少的情况；Any live cell with fewer than two live neighbours dies,as if caused by under-population.任何活着的元胞有2个或者3个活着的邻居，将继续活到下一代（下一个时间节点）。Any live cell with two or three live neighbours lives on to the next generation.对于任何一个元胞，有多于3个活着的邻居；就会死去，模拟人口过多情况；Any live cell with more than three live neighbours dies,as if by overcrowding.一个死去的元胞，如果有3个活的邻居，就变成活的，模拟繁殖Any dead cell with exactly three live neighbours becomes a live cell,as if by reproduction.,Game of Life 生命游戏,22,路况模拟 Highway Simulation,作为一维元胞自动机的模拟，我们假设汽车在单元中，对于一个有汽车的单元，cell i:停下：如果这个单元直接的前面一个单元是被占用的，Stay:If the cell directly to the right is occupied.移动：否则就以概率p向前移动一个格子，；Move:Otherwise,move one step to the right,with probability p,Move to the next cell,with the probability p,23,Kermack-McKendrick 病毒传播模型中：S:易感人群 Susceptible personsI:被感染人群 Infected personsR:治愈人群 Removed(immune)persons:感染率 Infection rate:免疫率 Immunity rate,S,I,R,transmission,recovery,病毒传染Kermack-McKendrick 模型,24,Kermack-McKendrick 病毒传播模型中：S:易感人群 Susceptible personsI:被感染人群 Infected personsR:治愈人群 Removed(immune)persons:感染率 Infection rate:免疫率 Immunity rate,病毒传染Kermack-McKendrick 模型,25,病毒传染Kermack-McKendrick 模型,Kermack-McKendrick 病毒传播模型中：S:易感人群 Susceptible personsI:被感染人群 Infected personsR:治愈人群 Removed(immune)persons:感染率 Infection rate:免疫率 Immunity rate,26,Kermack-McKendrick 病毒传播模型中：S:易感人群 Susceptible personsI:被感染人群 Infected personsR:治愈人群 Removed(immune)persons:感染率 Infection rate:免疫率 Immunity rate,病毒传染Kermack-McKendrick 模型,27,Kermack-McKendrick 病毒传播模型的实现：在C+定义的一个二维矩阵中，需要把状态编码成如下状态：states S,I,R=0,1,20:易感人Susceptible；1:Infected 感染人；2:Recovered 治愈人,病毒传染Kermack-McKendrick 模型,28,对于每个时间步骤，元胞状态变化为在每个时间步骤，单个元胞的状态变化根据如下规则：元胞状态为易感人的种类，当他有一个邻居是已经感染的人，他将以概率被感染；元胞状态为已经感染的人，自己有一个概率恢复成免疫人群；,病毒传染Kermack-McKendrick 模型,以一个时间步长不断循环 the time variable,t,遍历所有的元胞 cells,i=1.N,j=1.N,遍历这个元胞所有的邻居neighbors,k=1.M,%元胞自动机：森林火灾模型规则：(1)正在燃烧的树变成空格位；(2)如果绿树格位的最近邻居中有一个树在燃烧，则它变成正在燃烧的树；(3)在空格位，森林树以概率p 生长；(4)在最近的邻居中没有正在燃烧的树的情况下树在每一时步以概率f(闪电)变为正在燃烧的树。,森林火灾模型,30,元胞自动机的实现,顺序更新,31,元胞自动机的实现,顺序更新,32,元胞自动机的实现,顺序更新,33,元胞自动机的实现,顺序更新,34,元胞自动机的实现,顺序更新,35,元胞自动机的实现,顺序更新,36,元胞自动机的实现,顺序更新,37,元胞自动机的实现,顺序更新,38,元胞自动机的实现,顺序更新,39,顺序更新,元胞自动机的实现,40,顺序更新,元胞自动机的实现,41,元胞自动机的实现,顺序更新,42,元胞自动机的实现,顺序更新,43,元胞自动机的实现,顺序更新,44,元胞自动机的实现,顺序更新,45,元胞自动机的实现,顺序更新,46,元胞自动机的实现,顺序更新,47,元胞自动机的实现,随机更新,48,随机更新,元胞自动机的实现,49,元胞自动机的实现,随机更新,50,元胞自动机的实现,随机更新,51,元胞自动机的实现,随机更新,52,元胞自动机的实现,随机更新,53,元胞自动机的实现,随机更新,54,元胞自动机的实现,随机更新,55,元胞自动机的实现,随机更新,56,元胞自动机边界条件,边界条件的定义:周期型：边界上得格子缠绕，让格子边界能够满足正常.固定型：边界是固定的.,57,边界条件的定义:固定边界 周期边界,元胞自动机边界条件,元胞自动机例子程序,一维元胞自动机；高速公路；2.疾病传播模型；3.森林大火；,
