元胞自动机简介

第二次大作业：元胞自动机初等元胞自动机(ElementaryCellularAutomata)一、元胞自动机概况•20世纪50年代，JohnvonNeumann最早提出；(vonNeumann,J.1963，collectedworks,editedbyA.H.Taub)•1970年，JohnConway提出生命游戏(Conway,J.(1970).InM.Gardner,(Ed.),ScientificAmerican,223(4),pp.120-123.)•1983年，StephenWolfram初等元胞自动机(StephenWolfram.ReviewsofModernPhysics,1983,Vol.55.StephenWolfram.Nature,1984,Vol.311)•1986年至今，理论及应用初等元胞自动机(ElementaryCellularAutomata)二、格子及其状态•任意格子i,有两种状态，且状态是随时间变化。三、状态的演化••状态演化方程•0:121ttiixitxiL格子时刻的状态,且,,,……,111()12ttttiiiixfxxxiL,,，,,……,周期边界初等元胞自动机(ElementaryCellularAutomata)四、映射的种类101tix101tix01tix101tix初等元胞自动机(ElementaryCellularAutomata)例题按规则90演化0011011010。初等元胞自动机(ElementaryCellularAutomata)五、时空图0——白色1——黑色L=100初值取第50个格子为1，对每个规则演化100步。如下结构时空图初等元胞自动机(ElementaryCellularAutomata)六、时空图举例rule18rule57rule150rule30rule73rule126rule124rule169初等元胞自动机(ElementaryCellularAutomata)七、元胞自动机种类1983年，StephenWolfram对初等元胞自动机的分类•平稳型:自任何初始状态开始,经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。•周期型:经过一定时间运行后，元胞空间趋于一系列简单的固定结构(StablePaterns)或周期结构(PeriodicalPatterns)。•混沌型:自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统计特征不再变止，通常表现为分形分维特征。•复杂型:出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。初等元胞自动机(ElementaryCellularAutomata)八、元胞自动机应用•在社会学中，元胞自动机用于研究经济危机的形成与爆发过程、个人行为的社会性，流行现象，如服装流行色的形成等。•在生物学中，元胞自动机的设计思想本身就来源于生物学自繁殖的思想，因而它在生物学上的应用更为自然而广泛。•例如：元胞自动机用于肿瘤细胞的增长机理和过程模拟、人类大脑的机理探索(Victor.Jonathan.D.1990)、爱滋病病毒HIV的感染过程(Sieburg.H.B.1990)、自组织、自繁殖等生命现象的研究以及最新流行的克隆(Clone)技术的研究等(ErmentroutG.B.1993)。•应用领域涉及社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、歹境、军事学等。初等元胞自动机(ElementaryCellularAutomata)•图为二维元胞自动机局部示意图，其中晶格1为对象元胞，2-9为对象元胞的邻居，设这些元胞在t时刻的状态为，则对象元胞1在t+1时刻的状态为：154362789(9)](8),S(7),S(6),S(5),S(4),S(3),S(2),Sf[S(1)Stttttttt1t15•元胞自动机CellularAutomata•邻居定义Neighborhooddefinitions•Models模型–GameofLife生命游戏–HighwaySimulation道路模拟–DiseaseSpreading,revisited疾病传播初等元胞自动机(ElementaryCellularAutomata)16•元胞自动机使用格子的方式定义:一维元胞自动机二维元胞自动机初等元胞自动机(ElementaryCellularAutomata)17MooreNeighborhood•单个元胞仅仅与自己的邻居发生关联，邻居状态决定元胞的状态二维空间上邻居的定义上的theMooreneighborhood:1st阶Moore邻居2ndorderMoore邻居初等元胞自动机(ElementaryCellularAutomata)18Von-NeumannNeighborhood•二维空间上邻居的定义Von-Neumannneighborhood:1st阶Von-Neumannneighborhood2nd阶Von-Neumannneighborhood初等元胞自动机(ElementaryCellularAutomata)19GameofLife生命游戏•在二维空间中，建立模型Ni=1storderMooreneighbours数量对于目标元胞i；.•在每个元胞上循环，eachcelli:1.不活动状态Deactivate:IfNi2orNi3.2.活动状态Activate:ifcelliisdeactivatedandNi=3生命游戏•在二维空间中，建立模型Ni=1storderMooreneighbours数量对于目标元胞i；.•在每个元胞上循环，eachcelli:1.不活动状态Deactivate:IfNi2orNi3.2.活动状态Activate:ifcelliisdeactivatedandNi=3•任何活着的元胞少于2个活着的邻居，要处于非激活状态，比拟人口过少的情况；•Anylivecellwithfewerthantwoliveneighboursdies,asifcausedbyunder-population.•任何活着的元胞有2个或者3个活着的邻居，将继续活到下一代（下一个时间节点）。Anylivecellwithtwoorthreeliveneighbourslivesontothenextgeneration.•对于任何一个元胞，有多于3个活着的邻居；就会死去，模拟人口过多情况；Anylivecellwithmorethanthreeliveneighboursdies,asifbyovercrowding.•一个死去的元胞，如果有3个活的邻居，就变成活的，模拟繁殖•Anydeadcellwithexactlythreeliveneighboursbecomesalivecell,asifbyreproduction.GameofLife生命游戏22路况模拟HighwaySimulation•作为一维元胞自动机的模拟，我们假设汽车在单元中，对于一个有汽车的单元，celli:1.停下：如果这个单元直接的前面一个单元是被占用的，Stay:Ifthecelldirectlytotherightisoccupied.2.移动：否则就以概率p向前移动一个格子，；Move:Otherwise,moveonesteptotheright,withprobabilitypMovetothenextcell,withtheprobabilityp23•Kermack-McKendrick病毒传播模型中：S:易感人群SusceptiblepersonsI:被感染人群InfectedpersonsR:治愈人群Removed(immune)personsβ:感染率Infectionrateγ:免疫率ImmunityrateSIRβtransmissionγrecovery病毒传染Kermack-McKendrick模型24•Kermack-McKendrick病毒传播模型中：S:易感人群SusceptiblepersonsI:被感染人群InfectedpersonsR:治愈人群Removed(immune)personsβ:感染率Infectionrateγ:免疫率Immunityrate病毒传染Kermack-McKendrick模型25)()()()()()(tIdtdRtItStIdtdItStIdtdS病毒传染Kermack-McKendrick模型•Kermack-McKendrick病毒传播模型中：S:易感人群SusceptiblepersonsI:被感染人群InfectedpersonsR:治愈人群Removed(immune)personsβ:感染率Infectionrateγ:免疫率Immunityrate26•Kermack-McKendrick病毒传播模型中：S:易感人群SusceptiblepersonsI:被感染人群InfectedpersonsR:治愈人群Removed(immune)personsβ:感染率Infectionrateγ:免疫率Immunityrate病毒传染Kermack-McKendrick模型27•Kermack-McKendrick病毒传播模型的实现：在C++定义的一个二维矩阵中，需要把状态编码成如下状态：states{S,I,R}={0,1,2}–0:易感人Susceptible；1:Infected感染人；2:Recovered治愈人SSSSSSSIIISSSSIIIISSSRIIISSSRIIISSSIIISSSSISSSSSS0000000111000011110002111000211100011100001000000病毒传染Kermack-McKendrick模型28•对于每个时间步骤，元胞状态变化为•在每个时间步骤，单个元胞的状态变化根据如下规则：–元胞状态为易感人的种类，当他有一个邻居是已经感染的人，他将以概率β被感染；–元胞状态为已经感染的人，自己有一个概率γ恢复成免疫人群；病毒传染Kermack-McKendrick模型以一个时间步长不断循环thetimevariable,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元胞自动机边界条件•边界条件的定义:•周期型：边界上得格子缠绕，让