1 / 8
文档名称:

元胞自动机.pdf

格式:pdf   大小:853KB   页数:8页
下载后只包含 1 个 PDF 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

元胞自动机.pdf

上传人:小辰GG1 2023/3/25 文件大小:853 KB

下载得到文件列表

元胞自动机.pdf

文档介绍

文档介绍:该【元胞自动机 】是由【小辰GG1】上传分享,文档一共【8】页,该文档可以免费在线阅读,需要了解更多关于【元胞自动机 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。元胞自动机(CellularAutomata),简称CA,也有人译为细胞自动机、点格自动
机、分子自动机或单元自动机)。是一时间和空间都离散的动力系统。散布在规
则格网(Lattice中的每一元胞Grid)(Cell)取有限的离散状态,遵循同样的作
用规则,依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成
动态系统的演化。不同于一般的动力学模型,元胞自动机不是由严格定义的物
理方程或函数确定,而是用一系列模型构造的规则构成。凡是满足这些规则的模
型都可以算作是元胞自动机模型。因此,元胞自动机是一类模型的总称,或者
说是一个方法框架。其特点是时间、空间、状态都离散,每个变量只取有限多个
状态,且其状态改变的规则在时间和空间上都是局部的。
元胞自动机的构建没有固定的数学公式,构成方式繁杂,变种很多,行为复杂。
故其分类难也度较大,自元胞自动机产生以来,对于元胞自动机分类的研究就是
元胞自动机的一个重要的研究课题和核心理论,在基于不同的出发点,元胞自
动机可有多种分类,其中,
动力学行为的元胞自动机分类,而基于维数的元胞自动机分类也是最简单和最常
用的划分。除此之外,在1990年,
行为的马尔科夫概率量测的层次化、参量化的分类体系(Gutowitz,H.
A.,1990)。下面就上述的前两种分类作进一步的介绍。同时就几种特殊类型的

化行为,并在大量的计算机实验的基础上,将所有元胞自动机的动力学行为归纳
为四大类(Wolfram.,1986):S.
(1)平稳型:自任何初始状态开始,经过一定时间运行后,元胞空间趋于一个空间
平稳的构形,这里空间平稳即指每一个元胞处于固定状态。不随时间变化而变化。
(2)周期型:经过一定时间运行后,元胞空间趋于一系列简单的固定结构(Stable
Paterns)或周期结构(Perlodical。由于这些Patterns)结构可看作是一种滤波
器(Filter),故可应用到图像处理的研究中。
(3)混沌型:自任何初始状态开始,经过一定时间运行后,元胞自动机表现出混沌
的非周期行为,所生成的结构的统汁特征不再变止,通常表现为分形分维特征。
(4)复杂型:出现复杂的局部结构,或者说是局部的混沌,其中有些会不断地传播。
从另一角度,元胞自动机可视为动力系统,因而可将初试点、轨道、不动点、周
期轨和终极轨等一系列概念用到元胞自动机的研究中,上述分类,又可以分别描
述为(谭跃进,1996;谢惠民,1994;李才伟、1997);
(1)均匀状态,即点态吸引子,或称不动点;
(2)简单的周期结构,即周期性吸引子,或称周期轨;
(3)混沌的非周期性模式,即混沌吸引子;
(4)这第四类行为可以与生命系统等复杂系统中的自组织现象相比拟,但在连续
系统中没有相对应的模式。但从研究元胞自动机的角度讲,最具研究价值的具有
第四类行为的元胞自动机,因为这类元胞自动机被认为具有"突现计算
"(EmergentComputation)功能,研究表明,可以用作广义计算机(Universal
Computer)以仿真任意复杂的计算过程。另外,此类元胞自动机在发展过程中还
表现出很强的不可逆(lrreversibility)特征,而且,这种元胞自动机在若干有
限循环后,有可能会死""掉,即所有元胞的状态变为零。
在元胞自动机是由空间上各项同性的一系列元胞所组成,是在有限元胞自动机基
础上发展起来的,用于模拟和分析几何空间内的各种现象。

初等元胞自动机(ElementaryCellular,简称ECA)是状态集AutomataS
只有两个元素{s1,s2},即状态个数k=2,邻居半径r=l的一维元胞自动机(谢
惠民,1994、李才伟,1997、Wolfram,S,1986)。它几乎是最简单的元胞自动
机模型。由于在S中具体采用什么符号并不重要,它可取{0,1},{-l,1},{静
止,运动},{黑,白},{生,死}等等,这里重要的是S所含的符号个数,通常
我们将其记为{0,1}。此时,邻居集N的个数2r=2,局部映射f:S→S可记为:
3
其中变量有三个,每个变量取两个状态值,那么就有2×2×2=8种组合,
只要给出在这八个自变量组合上的值,f就完全确定了。例如以下映射便是其中
的一个规则:
通常这种规则也可表示为以下图形方式(黑色方块代表l,白色方块代表0):
这样,对于任一个一维的何0,1序列,应用以上规则,可以产生下一时刻
的相应的序列。以下序列就是应用以上规则产生的:
t:010111110101011100010
t+1:10100010**********
以上八种组合分别对应0或1,因而这样的组合共有28=256种,即初等元
胞自动机只可能有256种不同规则。
个结果组成一个二进制(注意高低位顺序),如上可得01001100,然后计算它的
十进制值R:
在[0R,255]内,,则上面的
元胞自动机模型就是76号初等元胞自动机(谢惠民,1994;李才伟,1997)。
。研究表明,尽
管初等元胞自动机是如此简单,但它们表现出各种各样的高度复杂的空间形态。
经过一定时间,有些元胞自动机生成一种稳定状态,或静止,或产生周期性结
构,那么,有些产生自组织、自相似的分形结构。(1983)借用分形理
(Wolfram,S.,1983)。但256种元胞自
,所谓复杂型。
,尤其是初等元胞自动机的深入研究奠定了
元胞自动机理论的基石。对元胞自动机的理论研究,以及后来的人工生命研究和
近来兴起的复杂性科学(Scienceof研究作出了卓越的贡献。Complexity)
"生命游戏"
生命游戏()
种单人玩的计算机游戏(Garclner,M.,1970、1971)。他与现代的围棋游戏在某
些特征上略有相似:围棋中有黑白两种棋子。生命游戏中的元胞有{"生","死
"}两个状态{0,1};围棋的棋盘是规则划分的网格,黑白两子在空间的分布决定
双方的死活,而生命游戏也是规则划分的网格(元胞似国际象棋分布在网格内。
而不象围棋的棋子分布在格网交叉点上)。根据元胞的局部空间构形来决定生
死。只不过规则更为简单。下面介绍生命游戏的构成及规则:
(1)元胞分布在规则划分的网格上;
(2)元胞具有0,1两种状态,0代表"死",l代表"生";
(3)元胞以相邻的8个元胞为邻居。即Moore邻居形式;
(4)一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态(确切
讲是状态的和)决定:
·在当前时刻,如果一个元胞状态为"生",且八个相邻元胞中有两个或三个的状
态为"生",则在下--时刻该元胞继续保持为"生",否则"死"去;
·在当前时刻。如果一个元胞状态为"死"。且八个相邻元胞中正好有三个为"生"。
则该元胞在下一时刻"复活"。否则保持为"死"。
尽管它的规则看上去很简单。但生命游戏是具有产生动态图案和动态结构能力
的元胞自动机模型。它能产生丰富的、有趣的图案。生命游戏的优化与初始元胞
状态值的分布有关,给定任意的初始状态分布。经过若干步的运算,有的图案
会很快消失。而有的图案则固定不动,有的周而复始重复两个或几个图案,有的
婉蜒而行。有的则保持图案定向移动,形似阅兵阵„„,其中最为著名的是"
滑翔机(叫Glider)"的图案。
生命游戏模型已在多方面得到应用。他的演化规则近似地描述了生物群体的
生存繁殖规律:在生命密度过小(相邻元胞数之2)时,由于孤单、缺乏配种繁殖
机会、缺乏互助也会出现生命危机,元胞状态值由1变为0;在生命密度过大(相
邻元胞数>3)时,由于环境恶化、资源短缺以及相互竞争而出现生存危机,元胞
状态值由1变为0;只有处于个体适中(相邻元胞数为2或3)位置的生物才能生
存(保持元胞的状态值为1)和繁衍后代(元胞状态值由0变为1)。正由于它能够
模拟生命活动中的生存、灭绝、竞争等等复杂现象,因而得名"生命游戏"。
J·H·Conway还证明,这个元胞自动机具有通用图灵机的计算能力(谢惠民,
1994;李才伟,1997),与图灵机等价,也就是说给定适当的初始条件,生命游
戏模型能够模拟任何一种计算机。
从数学模型的角度看,该模型将平面划分成方格棋盘,每个方格代表一个
元胞。
元胞状态:0死亡,1-活着
领域半径:1
领域类型:Moore型
其中St表示t时刻元胞的状态,S为8个相邻元胞中活着的元胞数。
另外,需要指出的是,目前随着人们对"生命游戏"研究的深入,产生了许
多变种和扩展。在80年代末,A·K·Dewdney(Dewdney,A·K,1987)和C·Bays
(Bays,C,1987)Dewdney,A·K·,1990)将Conway的生命游戏扩展到了三维空
间上,构建了三维生命游戏,并对其规则作了具有普遍性的扩展(图2-3)。
C·Bays的学生LeeMeeker在此基础上进一步构建了四维的生命游戏。另外,
Gardner(Gardner,M·,1970、1971、1983)等人也曾在这方面作了很多迸一步
的研究工作。
对游戏规则的扩展主要是引入了4个参数EEFF,E表示对于一个"活"元
bkbkb
胞,在下一个时刻,继续保持其状态所需要的最少的"活"邻居的数目,而F则
b
表示对于一个"死"元胞,在下一时刻,"复活"所需要的最小的"活"邻居的数目,
E和F则分别表示上述情况的上限值。演化规则修改为
kk
格子气自动机
格子气自动机(Lattice一GasAutomata,LGA又称格气机),是元胞自动机
在流体力学与统计物理中的具体化,也是元胞自动机在科学研究领域成功应用的
范例李才伟,(1997)。相对于"生命游戏"来说,格子气自动机是个更注重于模
型的实用性。它利用元胞自动机的动态特征,来模拟流体粒子的运动。
第一个时空、速度等变量完全离散的格子气自动机是1973年由法国的
J·Hardy、Y·Pomeau和O·Pazzis提出的HPP模型,它的模拟结果已经很接
近流体力学中描述流体运动的Navier-Strokes方程。但模型中的流体粒子的运
动只允许有四个方向,造成应力张量各向异性的致命弱点,尚不能充分反映流
体的特征,因此在较长时间内没有受到足够的重视。直到20世纪80年代,
S·Wolfram等人的研究工作使得元胞自动机理论产生了质的飞跃,同时也带动
了格子气自动机的进一步发展。1986年,法国的U·Frish、Y·Pomeau和美国
的B·HassIacher在HPP模型的基础上提出了一个有实用价值的、基于六角形
网络的格子气自动机模型,得名为FHP(Fritsch-Has,lacher-Pomeau)模型,并
证明该模型的宏观行为符合标准的Navier-Stokes方程(李才伟,1997)。FHP
模型是第一个成功的格子气模型,并激发了研究格子气模型研究的热潮,人们在
几年内发表了数百篇论文,其中包括Gerhart(l995),Lim(1988),Xiao-Guang
Wu(1994),李元香(1991)等人的进一步工作。在90年代中后期,一种被称为格
点波尔兹曼方程(LatticeBolzmann)的改进模型逐步取代了原有的格气模型。
应当说,格子气自动机是一种特殊的元胞自动机模型,或者说是一个扩展
的元胞自动机模型(ExtendedCellularAutomata)。以早期的格子气模型为例,
描述其特征如下:
由于流体粒子不(1)会轻易从模型空间中消失,这个特征需要格子气自动机
是一个可逆元胞自动机模型。
格子气自动机的(2)邻居模型通常采用Margulos类型,即它的规则是基于
一个2X2的网格空间的。它的规则形似如下:
这里黑色球代表流体粒子,白色球代表空的元胞。可以看出,格子气自动
机不同于其它的元胞自动机模型,以一个元胞(常被称为中心元胞,为研究对象,
考虑其状态的转换,而是考虑包含四个元胞的一个四方块。
依照上(3)述规则和邻居模型在计算完一次后,需要将这个2X2的模板沿对
角方向滑动,再计算一次。那么,一个流体粒子的运动需要两步t-t+l-t+2才能
完成。
从时间和空间的角度看,格子气自动机相对其他的元胞自动机模型具有较
为独特的特征。格气自动机作为一种特殊类型的元胞自动机已成为流体动力学中
的一个重要领域,几乎独立于元胞自动机研究之外了。
Langton和“能自我复制的元胞自动机”
元胞自动机是一种离散的动态模型,由于它可以模拟自组织、自繁殖、信
息储存和传递等现象,因而,被广泛地应用于生命现象的研究中。目前兴起的
人工生命的研究就是来源于元胞自动机的深入研究,其主要论点是认为"自我复
制"乃生命的核心特征。聚集在美国新墨西哥州的圣塔费研究所(SantaFe
Institute)的科学家们在这方面作了很多深入的工作,最著名的成果之一就是
Christopher在二维元胞自动机中发现的一个能自我复制的Langton"圈"或称"
能自我复制的元胞自动机"(谭跃进等,1996;Longton,C·G·,1987)。当然,
他的研究是基于先前一系列研究的基础上的:
Langton在vonNeumann和Codd工作的基础上,设计了一个能自我复制的
"圈"。元胞状态在(0,1,2,3,4,5,6,7)中取值,其中,0,1,2,3构成
元胞自动机的基本结构,04,05,06,07代表信号。l代表"核"元胞;2代表"
壳"元胞,是边界;2包围的部分构成信息通道或称数据路径。邻居模型采用Von
Neumann的4邻居模型。
元胞自动机通过信号元胞替代相邻的元胞,如状态为1的元胞,而完成信
号传递。信号传播的过程可以通过下面的例子说明:
数据路径可以分支,在分支的节点处,信号在各个分支中复制本身,产生
多个复制品。
下图中,07信号在T形的交叉点处,复制自身:
这个元胞自动机模型的另外一个重要特征就是路径扩张。即一定的信号可以产生
数据路径的延伸,如下图所示:
有了上面的论述,下面的具有路径扩张的、能自我复制的"圈"的工作机理
应当容易理解了。