科研成果课论文.doc

科研成果课论文
论文题目: 元胞自动机的简单认识
学院: 金山学院专业年级:
学号:
姓名:
指导教师、职称: 程丽、副教授
2013年 12 月5日
I
元胞自动机的简单认识
摘要:元胞自动机(Cellular Aumatomata,简称 CA)又称细胞自动机或单元自动机,是由号称“现代计算机之父“的冯·诺依曼
(Von Neumann)在上世纪40年代首先提出的一种离散模型,它是描述自然界复杂现象的常用工具,最初被用于模拟生命统特有的自复制现象。元胞自动机在模拟空间复杂系统的时空演变方面具有很强的能力,所以经常用于复杂系统的建模与模拟。元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上,按照一定局部规则,在离散的时间维上演化的动力学系统。元胞自动机的部件被称为“元胞(Cell)”,每个元胞具有一个状态,这个状态只能取某个有限状态集中的一个,例如“生”或“死”,或者256种颜色中的一种等等。这些元胞规则地排列在被称为“元胞空间”的空间格网上,它们各自的状态随着时间变化,根据一个局部的规则来进行更新
,即一个元胞在某时刻的状态取决于且只取决于该元胞周围邻域元胞的状态。
关键词:元胞;自动机;时间;空间;模型
一、元胞自动机的概述
不同于一般的动力学模型,元胞自动机不是由严格定义的物理方程或函数确定,而是用一系列模型构造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此,元胞自动机是一类模型的总称,或者说是一个方法框架。其特点是时间、空间、状态都离散,每个变量只取有限多个状态,且其状态改变的规则在时间和空间上都是局部的。
元胞自动机的构建没有固定的数学公式,构成方式繁杂,变种很多,行为复杂。故其分类难度也较大,自元胞自动机产生以来,对于元胞自动机分类的研究就是元胞自动机的一个重要的研究课题和核心理论,在基于不同的出发点,元胞自动机可有多种分类,其中,最具影响力的当属S. Wolfram在80年代初做的基于动力学行为的元胞自动机分类,而基于维数的元胞自动机分类也是最简单和最常用的划分。除此之外,在1990年, Howard 、参量化的分类体系(Gutowitz, H. A. ,1990)。
二、元胞自动机的动力学行的分类
下面就上述的前两种分类作进一步的介绍。同时就几种特殊类型的元胞自动机进行介绍和探讨S. Wolfrarm在详细分忻研究了一维元胞自动机的演化行为,并在大量的计算机实验的基础上,将所有元胞自动机的动力学行为归纳为四大类
(Wolfram. S.,1986):
(1)平稳型:自任何初始状态开始,经过一定时间运行后,元胞空间趋于一个空间平稳的构形,这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。
(2)周期型:经过一定时间运行后,元胞空间趋于一系列简单的固定结构(Stable Paterns)或周期结构(Perlodical Patterns)。由于这些结构可看作是一种滤波器(Filter),故可应用到图像处理的研究中。
(3)混沌型:自任何初始状态开始,经过一定时间运行后,元胞自动机表现出混沌的非周期行为,所生成的结构的统汁特征不再变止,通常表现为分