元胞自动机

2013年数模,有一道题是关于道路故障占用车道的规划和预测分析,其中有一篇优秀论文用到了元胞自动机分析方法.元胞自动机解决复杂的模型系统的重要研究方法被广泛关注.它通过简单的微观机制就能产生宏观整体的复杂行为,在最简单的元胞自动机(Cellular Automata,即ECA)里,状态集S只有两个两个元素{s1,s2 },通常记为{0,1},也可以记为黑与白.邻居半径r=1.

此时：邻居的个数为2r=2，局部映射f：S^3->S:

其中有三个变量,每个变量有两个状态,那么就会有2*2*2=8种组合,只有确定这8种值,f就可以确定了.在这8种组合中,就会产生2^8=256种规则(局部映射),也就是对应于256种初代元胞自动机.所以这看起来很简单.但是当你将它们不断变换时,你就会发现它解决了很多复杂的问题.

S. Wolfrarm在做了大量的推演和计算机实验,将元胞自动机大致分为四大类:

⑴平稳型:自任何初始状态开始，经过一定时间运行后，元胞空间趋于一个空间平稳的构形，这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。

⑵周期型：经过一定时间运行后，元胞空间趋于一系列简单的固定结构（Stable Patterns）或周期结构（Perlodical Patterns)。由于这些结构可看作是一种滤波器（Filter），故可应用到图像处理的研究中。

⑶混沌型：自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌的非周期行为，所生成的结构的统计特征不再变止，通常表现为分形分维特征。

⑷复杂型：出现复杂的局部结构，或者说是局部的混沌，其中有些会不断地传播。

进一步,我们可以看到它所具有的特点:

①离散(高度):不仅空间离散,时间离散,状态也是离散的,这个特征极大的简化了计算和处理过程.作为一个全离散的局部动力学模型,很容易描写单元间的相互作用,只需要确定局部演化规则.

②齐性:就是说在元胞空间中每个元胞都服从相同的规律,元胞自动机转换规则或转换函数是相同的.

③并行运算:由于规律相同,就有理由让他们一起运算,元胞自动机的结构变化可以看成是对数据和信息的计算和处理.

④时空局限性:每一个元胞的下一时刻t+1的状态,都取决于其周围半径为r的领域(或者其他形式邻居规则定义下的领域)中的元胞当前状态t时刻的状态,这就是时间空间的局限性,从信息传输的角度来说,信息传输速度是有限的.

⑤维数高:在动力系统中一般将变量的个数看成维数,在元胞空间中,每个元胞被看成是系统的一个变量,由于任何完备的元胞自动机的元胞空间都是定义在一维、二维或多维空间上的无限集, 因此, 元胞自动机是一类无穷维动力系统.

简单说就是将一片区域（系统）分成很多个给定运动规则的单元格（可以说方形、六边形等），用单元格整体趋势来表示这片区域（系统）的演化趋势。散布在规则格网 (Lattice Grid)中的每一元胞(Cell)取有限的离散状态，遵循同样的作用规则，依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成精态系统的演化。'它没有严格意义的函数限制,没有公式,行为复杂,是用一系列模型构造的规则构成的,所以只要满足这些规则的都可以使用这个模型.在实际应用过程中，有的元胞自动机模型对其中的某些特征进行了扩展，有的在规则设计中引入随机因素，如：森林火灾模型。 又如，在交通、通讯发达的今天， 研究流行病或计算机病毒的传播问题时， 我们还可以将空间背景换成复杂网络的结点，用网络邻接点作为邻居。这样的调整显然比仍旧使用二维欧氏空间、采用欧氏距离的模型更加符合实际情况。 在大型场所人群紧急疏散问题模拟研究中，可以考虑年龄、性别等因素，即元胞不是同质的，更加有利于使模拟系统接近真实系统。一般定义微观规则模拟交通堵塞和疏通的具体情况啊啥的，用matlab仿真可以得到具体问题的解，比如排队时间是多少，一个周期能排多少辆车，多长时间疏通都可以解。元胞自动机的方法比较新，大约90年代后通用，传统的有交通波和排队论.

链接：https://www.zhihu.com/question/21929655/answer/54098966

应尚军, 魏一鸣, 蔡嗣经. 元胞自动机及其在经济学中的应用[J]. 中国管理科学, 2000(s1):272-278.