元胞自动机元胞自动机 1612022102 陈锐1612022101 王荷丽1608524073 武改凤1608524068 王丹丹内容：起源与发展概念组成特征生命游戏应用领域道路交通仿真应用 元胞自动机是在40年代由Ulam首先提出,随后计算机之父冯.诺伊曼提出构造一个不确定的生命模型系统的设想，这个系统可以智能的自我进化。后来，冯.诺伊曼参照生物现象的自繁殖原理，将这个模型发展为一个网格状的自动机网络，每个网格为一个单元自动机，单元状态有生和死，相当于人体组织的存活和消亡。 Tobler在70年代,认识到元胞自动机在模拟复杂现象的优势,首先正式采用了元胞自动机的概念来模拟当时美国五大湖边底特律地区城市的迅速扩展。元胞自动机的起源与发展元胞自动机的起源与发展 20 世纪 70 年代，Conway 编制的“生命游戏”是最著名的元胞自动机模型，显示了元胞自动机在模拟复杂性系统的无穷潜力。引起了物理、数学、生物、计算机、地理等领域专家的兴趣，“生命游戏”被认为是元胞自动机研究的真正开始。 20 世纪 90 年代元胞自动机在各个领域得到了广泛的应用。此后元胞自动机主要应用在计算机图形学、生物学、复杂的社会经济现象如城市发展模拟与预测，热扩散，并行计算等领域。元胞自动机的起源与发展元胞自动机的起源与发展 元胞自动机（CA）是时间、空间、状态都离散,空间的相互作用及时间上因果关系皆局部的网格动力学模型。元胞自动机模型不同于一般的动力学模型,没有明确的方程形式,而是包含了一系列模型构造的规则,凡是满足这些规则的模型都可以算作是元胞自动机模型。因此,确切地说,元胞自动机是一类模型的总体、或者说是一个方法框架。元胞自动机的概念元胞自动机的概念 元胞自动机的组成元胞自动机的组成元胞自动机构成示意图元胞自动机构成示意图 元胞：又可称为单元或基元,是元胞自动机的最基本的组成部分。元胞分布在离散的一维、二维或多维欧几里德空间的晶格点上,具有离散、有限的状态。状态可以是 的二进制形式,或是s0,s1，s2sk整数形式的离散集。元胞自动机的组成元胞自动机的组成0，1 元胞空间：即元胞所分布的空间网点集合。元胞空间的划分在理论上可以是任意维数的欧几里德空间规则划分。目前研究主要集中在一维和二维元胞自动机上。对于一维元胞自动机,元胞空间的划分只有一种,而高维的元胞自动机,元胞空间的划分可有多种形式。最为常见的二维元胞自动机,其元胞空间通常可按三角、四方或六边形三种网格排列。元胞自动机的组成元胞自动机的组成 元胞自动机的组成元胞自动机的组成二维元胞自动机三种网格划分二维元胞自动机三种网格划分三类网格划分的优缺点对比:元胞自动机的组成元胞自动机的组成 邻居：以上的元胞及元胞空间只表示了系统的静态成分,为将“动态”引入系统,必须加入演化规则。在元胞自动机中,这些规则是定义在空间局部范围内的,即一个元胞下一时刻的状态决定于本身状态和它的邻居元胞状态。因而,在指定规则之前,必须定义一定的邻居规则,确定哪些元胞属于该元胞的邻居。元胞自动机的组成元胞自动机的组成元胞邻居冯.诺依曼型摩尔型扩展的摩尔型元胞自动机的组成元胞自动机的组成 规则：元胞自动机关于元胞的局部演化规则(即元胞状态转换规则)有一个通用的描述:中心元胞的下一个状态由中心元胞的当前状态和其邻居的当前状态按照一定的规则确定。可见,元胞状态转换规则是一个动力学函数,其实质是一个状态转移函数,这个函数构造了一种简单的、离散的空间和时间范围的局部物理成分。元胞自动机的组成元胞自动机的组成 时间：元胞自动机是一个动态系统,它在时间维上的变化是离散的,即时间是一个整数值,而且连续等间距。假设时间间距dt=1,若t=0为初始时刻,那么t=1为其下一时刻。在上述转换函数中,一个元胞在t+1的时刻直接决定于t时刻的该元胞及其邻居元胞的状态,虽然在t-1时刻的元胞及其邻居元胞的状态间接影响了元胞在t+1时刻的状态。元胞自动机的组成元胞自动机的组成 开放性和灵活性离散性和并行性空间性局部性高维性元胞自动机的特征元胞自动机的特征 生命游戏其实是一个零玩家游戏，它包括一个二维矩形世界，这个世界中的每个方格居住着一个活着的或死了的细胞。一个细胞在下一个时刻生死取决于相邻八个方格中活着的或死了的细胞的数量。如果相邻方格活着的细胞数量过多，这个细胞会因为资源匮乏而在下一个时刻死去；相反，如果周围活细胞过少，这个细胞会因太孤单而死去。生命游戏生命游戏 生命游戏生命游戏每个格子的生死遵循下面的原则：每个格子的生死遵循下面的原则：1 如果一个细胞周围有3个细胞为生（一个细胞周围共有8个细胞），则该细胞为生（即该细胞若原先为死，则转为生，若原先为生，则保持不变） 。2 如果一个细胞周围有2个细胞为生，则该细胞的生死状态保持不变；3 在其它情况下，该细胞为死（即该细胞若原先为生，则转为死，若原先为死，则保持不变设定图像中每个像素的初始状态后依据上述的游戏规则演绎生命的变化，由于初始状态和迭代次数不同，将会得到令人叹服的优美图案）。 生命游戏生命游戏 生命游戏生命游戏 生命游戏生命游戏 生命游戏是具有产生动态图案和动态结构能力的元胞自动机模型，它能产生丰富的、有趣的图案。生命游戏的优化与初始元胞状态值的分布有关，给定任意的初始状态分布。经过若干步的运算，有的图案会很快消失；而有的图案则固定不动，有的周而复始重复两个或几个图案，有的婉蜒而行；有的则保持图案定向移动，形似阅兵阵。 生命游戏生命游戏 最为著名的是“滑翔机 (叫Glider)”的图案，它可以周期性生产滑翔机发射器，每个发射器还能再发射滑翔机。 元胞自动机的应用领域元胞自动机的应用领域生物学领域： 肿瘤细胞的增长机理和过程模拟 人类大脑的机理探索 艾滋病病毒HIV的感染过程 自组织、自繁殖等生命现象的研究 克隆 (clone)技术的研究 模拟植物的生长过程 贝壳上的色素沉积图案 元胞自动机的应用领域元胞自动机的应用领域生态学领域： 兔子-草、鲨鱼-小鱼等生态系统动态变化过程的模拟 蚂蚁的行走路径，大雁、鱼类洄游等动物的群体行为的模拟 生物群落的扩散模拟 元胞自动机的应用领域元胞自动机的应用领域物理学领域： 磁场、电场、热扩散和热传导的模拟 模拟雪花等枝晶的形成 液态金属材料的凝固结晶过程 颗粒材料的垮塌现象 元胞自动机的应用领域元胞自动机的应用领域其他领域： 对城市道路交通流、交通网络的研究 城市扩展研究 模拟土地利用变化 火灾模拟 道路交通仿真的应用道路交通仿真的应用 将元胞自动机应用于道路交通仿真最早是受到了S.Wolfram 184号初等元胞自动机的启发。 在184号初等元胞自动机模型中,道路被划分为等距格子,每个格点表示一个元胞。元胞或者为空或者被一辆车占据。模型采用并行更新规则，每一个时间步内,若某车的前方元胞是空的,则该车可以向前行驶一步；若前面的元胞被另一辆车所占据,则该车停在原地不往前行驶。整个系统采用周期性边界条件以确保车辆数守恒。 道路交通仿真的应用道路交通仿真的应用tt+1t+2 道路交通仿真的应用道路交通仿真的应用 如果用“1”表示元胞被占据，“0”表示元胞为空，则184号模型的演化规则可以写成如下形式：T000001010011100101110111T+100011101 道路交通仿真的应用道路交通仿真的应用 研究意义：元胞自动机可以建立能够刻画实际交通特性的交通流模型，揭示交通系统的基本规律，从而在充分地利用现有的交通设施基础上解决交通拥堵问题、帮助完善现有的交通网络和控制系统。