元胞自动机模型.ppt

《元胞自动机模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、元胞自动机模型元胞自动机(cellularautomata，CA)模型是最具代表性的微观离散模型，最早由VonNeumann和Ulam提出。22011122王东岩22011223王果22011323王语海22011326周崎轩22011328宋国强东南大学元胞自动机（CellularAutomata，简称CA）实质上是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定的局部规则，在离散的时间维度上演化的动力学系统。1.CA之所以是离散系统，是因为元胞是定义在有限的时间和空间上的，并且元胞的状态是有限。2.CA被认为是动

2、力学模型，是因为它的举止行为具有动力学特征什么是元胞（CA）自动机元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元胞自动机是一类模型的总称，或者说是一个方法框架初等元胞自动机初等元胞自动机是状态集S只有两个元素{s1，s2}，即状态个数k=2，邻居半径r=1的一维元胞自动机。由于在S中具体采用什么符号并不重要，它可取{0，1}，{-1，1}，{静止，运动}等等，重要的是S所含的符号个数，通常我们将其记为{0，1}。此时，邻居集N的个数2·r=2，

3、局部映射f：S3→S可记为:.Wolfram的初等元胞自动机由于只有0、1两种状态，所以函数f共有28=256种状态256种初等CA规则元胞自动机的构成元胞自动机最基本的组成：元胞、元胞空间、邻居及规则四部分。另外，还应包含状态和时间。可以视为由一个元胞空间和定义于该空间的变换函数所组成。元胞自动机的构成示意图元胞:元胞又可称为单元、细胞或基元，是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上。具有以下特点：1.元胞自动机最基本的单元.2.元胞有记忆贮存状态的功能.3.所有元胞状态都安照元胞规则

4、不断更新元胞状态元胞的状态可以是二进制形式，如：（0，1），（生，死），（黑、白）等；也可以在一个有限整数集内S内取值：如交通领域的CA模型中，有时元胞状态可在[-(Vmax+1)～Vmax+1)]之间取值。状态参量：严格意义上的CA只能有一个状态参量；但是，在实际应用中，可以具有多个状态参量。元胞空间元胞在空间中分布的空间格点的集合就是元胞空间。A元胞空间的几何划分B元胞空间的边界条件A元胞空间的几何划分理论上，它可以是任意维数的欧几里德空间规则划分。常用的元胞自动机一般是一维和二维的。A一维元胞自动机的元胞空间只有一种划分B二维

5、元胞自动机通常有三种划分方式:三角形,正方形,正六边形三类网格划分的优缺点对比:B元胞空间边界条件理论上，元胞空间是无限的；实际应用中无法达到这一理想条件。常用的边界条件如下*周期型*定值型*绝热型*反射型周期型边界条件：定义：周期型是指相对边界连接起来的元胞空间*对一维空间，首尾相接形成一个圆环*对二维空间，上下相接，左右相接，而形成一个拓*扑圆环面，形似车胎或甜点圈*周期型空间与无限空间最为接近，因而在理论探讨时，常以此类空间作为试验定值型边界条件定义：所有边界外元胞均取某一固定常量绝热型边界条件定义：在指边界外邻居元胞的状态始

6、终和边界元胞的状态保持一致，即具有状态的零梯度*反射型边界条件定义：在边界外邻居的元胞状态是以边界元胞为轴的镜面反射。邻居:冯-诺依曼(Von.Neumann)型定义如下：摩尔(Moore)型规则:根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单讲，就是一个状态转移函数。根据上面对元胞自动机的组成分析，我们可以更加深入地理解元胞自动机的概念。可以将元胞自动机概括为一个用数学符号来表示的四元组。A:代表一个元胞自动机系统；Ld：代表元胞空间；d：为空间维数；S：是元胞有限的离散的状态集合；N：表示邻域内所有元胞的组

7、合（包括中心元胞在内）；f：是局部转换函数，也就是规则。元胞行为局部变化引起全局变化*可以简单认为元胞自动机在运动上类似于波.*无胞的状态变化依赖于自身状态和邻居的状态元胞自动机的规则某元胞下时刻的状态只决定于邻居的状态以及自身的初始状态．元胞行为元胞网格元胞行为元胞邻居经典元胞生命游戏生命游戏(CameofLife)是J.H.Conway在2世纪6年代末设计的一种单人玩的计算机游戏(Garclner，M.，97、97)。他与现代的围棋游戏在某些特征上略有相似：围棋中有黑白两种棋子。生命游戏中的元胞有{"生"，"死"}两个状态{，}

8、;围棋的棋盘是规则划分的网格，黑白两子在空间的分布决定双方的死活，而生命游戏也是规则划分的网格(元胞似国际象棋分布在网格内。而不象围棋的棋子分布在格网交叉点上)。根据元胞的局部空间构形来决定生死。只不过规则更为简单。生命游戏的构成及规