元胞自动机简介

1、第二次大作业：元胞自动机一、元胞自动机概况一、元胞自动机概况 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 Wolf

2、ram. Reviews of Modern Physics,1983,Vol.55. Stephen Wolfram. Nature,1984,Vol.311) 1986年至今，理论及应用年至今，理论及应用 )二、格子及其状态 任意格子i,有两种状态，且状态是随时间变化。三、状态的演化 状态演化方程 0:121ttiixitxiL格子 时刻的状态,且,111()12ttttiiiixf xx xiL, ,，,周期边界)四、映射的种类101tix101tix01tix101tix)例题 按规则90 演化0011011010。)五、时空图 0白色 1黑色 L=100初值取第50个格子为1，对每个

3、规则演化100步。 如下结构时空图)六、时空图举例rule 18rule 57rule 150rule 30rule 73rule 126rule 124rule 169)七、元胞自动机种类1983年，Stephen Wolfram 对初等元胞自动机的分类 平稳型:自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。 周期型:经过一定时间运行后，元胞空间趋于一系列简单的固定结构(Stable Paterns)或周期结构(Periodical Patterns)。 混沌型:自任何初始状态开始，经过一定时间运行后，元胞

4、自动机表现出混沌的非周期行为，所生成的结构的统计特征不再变止，通常表现为分形分维特征。 复杂型:出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。)八、元胞自动机应用 在社会学中，元胞自动机用于研究经济危机的形成与爆发过程、个人行为的社会性，流行现象，如服装流行色的形成等。 在生物学中，元胞自动机的设计思想本身就来源于生物学自繁殖的思想，因而它在生物学上的应用更为自然而广泛。 例如：元胞自动机用于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索(Victor.Jonathan.D. 1990)、爱滋病病毒HIV的感染过程(Sieburg.H.B.1990)、自组织、自繁殖等生命现象

5、的研究以及最新流行的克隆 (Clone)技术的研究等 (ErmentroutG.B.1993)。 应用领域涉及社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、歹境、军事学等。) 图为二维元胞自动机局部示意图，其中晶格1为对象元胞，2-9为对象元胞的邻居，设这些元胞在t时刻的状态为，则对象元胞1在t+1时刻的状态为：154362789(9)(8),S(7),S(6),S(5),S(4),S(3),S(2),SfS(1)Stttttttt1t15 元胞自动机 Cellular Automata 邻居定义 Neighbor hood definitions Models 模型

6、Game of Life 生命游戏Highway Simulation 道路模拟Disease Spreading, revisited 疾病传播 )16 元胞自动机使用格子的方式定义:一维一维 元胞自动机元胞自动机二维二维 元胞自动机元胞自动机)17Moore Neighborhood 单个元胞仅仅与自己的邻居发生关联，邻居状态决定元胞的状态 二维空间上邻居的定义上的 the Moore neighborhood:1st 阶 Moore 邻居 2nd order Moore邻居 )18Von-Neumann Neighborhood 二维空间上邻居的定义Von-Neumann neighbo

7、rhood:1st 阶Von-Neumann neighborhood2nd 阶 Von-Neumann neighborhood)19 在二维空间中，建立 模型 Ni = 1st order Moore neighbours 数量 对于目标元胞 i；. 在每个元胞上循环， each cell i:1. 不活动状态不活动状态Deactivate: If Ni 3.2. 活动状态活动状态Activate: if cell i is deactivated and Ni = 在二维空间中，建立 模型 Ni = 1st order Moore neighbours 数量 对于目标元胞 i；. 在每个

8、元胞上循环， each cell i:1. 不活动状态不活动状态Deactivate: If Ni 3.2. 活动状态活动状态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

9、 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. 22路况模拟 H

10、ighway Simulation 作为一维元胞自动机的模拟，我们假设汽车在单元中，对于一个有汽车的单元，cell i:1. 停下：停下： 如果这个单元直接的前面一个单元是被占用的，如果这个单元直接的前面一个单元是被占用的， Stay: If the cell directly to the right is occupied.2. 移动：否则就以概率移动：否则就以概率p向前移动一个格子，；向前移动一个格子，； Move: Otherwise, move one step to the right, with probability pMove to the next cell, with t

11、he probability p23 Kermack-McKendrick 病毒传播模型中： S: 易感人群 Susceptible personsI: 被感染人群 Infected personsR: 治愈人群 Removed (immune) persons: 感染率 Infection rate: 免疫率 Immunity rateSIR transmission recovery24 Kermack-McKendrick 病毒传播模型中： S: 易感人群 Susceptible personsI: 被感染人群 Infected personsR: 治愈人群 Removed (immun

12、e) persons: 感染率 Infection rate: 免疫率 Immunity rate25)( )( )()( )()( tIdtdRtItStIdtdItStIdtdS Kermack-McKendrick 病毒传播模型中： S: 易感人群 Susceptible personsI: 被感染人群 Infected personsR: 治愈人群 Removed (immune) persons: 感染率 Infection rate: 免疫率 Immunity rate26 Kermack-McKendrick 病毒传播模型中： S: 易感人群 Susceptible person

13、sI: 被感染人群 Infected personsR: 治愈人群 Removed (immune) persons: 感染率 Infection rate: 免疫率 Immunity rate27 Kermack-McKendrick 病毒传播模型的实现：在C+定义的一个二维矩阵中，需要把状态编码成如下状态：states S, I, R=0, 1, 2 0:易感人Susceptible；1: Infected 感染人； 2: Recovered 治愈人SSSSSSSIIISSSSIIIISSSRIIISSSRIIISSSIIISSSSISSSSSS0000000111000011110002

14、11100021110001110000100000028 对于每个时间步骤，元胞状态变化为 在每个时间步骤，单个元胞的状态变化根据如下规则： 元胞状态为易感人的种类，当他有一个邻居是已经感染的人，他将以概率被感染； 元胞状态为已经感染的人，自己有一个概率恢复成免疫人群； 以一个时间步长不断循环 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 顺序更