元胞自动机的演化行为研究

2020-04-12 来源：飒榕旅游知识分享网

第24卷第8期2007年8月

计算机应用研究

ApplicationResearchofComputersVol.24No.8Aug.2007

元胞自动机的演化行为研究

王仲君

1,2

,王能超,冯　飞,田武峰

122

(1.华中科技大学计算机科学与技术学院,武汉430071;2.武汉理工大学统计学系,武汉430063)

摘　要:基于元胞自动机演化行为研究与仿真系统,通过对元胞自动机的一、二、三维演化行为的研究,从统计和渐进的角度对元胞自动机进行了分类,将元胞自动机的演化行为动态统计图与沃尔弗拉姆对于元胞自动机的分类对应起来研究。这些从不同视角得到的结果有助于对元胞自动机的演化行为进行深入研究;但从统计和渐进的角度对元胞自动机进行分类是否具有普适性,是需要进一步研究探讨的问题。关键词:元胞自动机;演化行为;统计;渐进;复杂系统

中图分类号:TP391.41　　　文献标志码:A　　　文章编号:100123695(2007)0820038204ResearchonevolvedbehaviorofcellularautomataWANGZhong2jun

1,2

,WANGNeng2chao,FENGFei,TIANWu2feng

122

(1.CollegeofComputerScience&Technology,HuazhongUniversityofScience&Technology,Wuhan430071,China;2.Dept.ofStatistics,WuhanUniversityofTechnology,Wuhan430063,China)

Abstract:Thepaperstudiedevolvedbehaviorofcellularautomatononone2dimension,two2dimension,andthree2dimension,

basedonthedevelopedcellularautomatonsystemaboutevolvedbehaviorresearchandsimulation.Fromtheviewpointofstatis2tics,cellularautomatawasstudiedbystatisticscharacteristic,classifiedaccordingtoitsevolvedbehavior,andcomparedtoWorfram’sclassification.Whetherornottheseresultshavegottenareuniversal,thisisanimportantquestionthatneedfurthertostudy.

Keywords:cellularautomaton;evolvedbehavior;statistics;advancesgradually;complexsystem

　　元胞自动机是21世纪科学研究中一个异常活跃的前沿领域,是复杂性科学的核心技术之一。元胞自动机是一种时间、空间、状态均离散,具有时空计算特征的网格动力学模型,是一个集数学、物理学、计算机科学、生物学和系统科学等多学科交叉的边缘领域,有广泛应用前景的研究方法[1]。当前,其应用领域广泛涉及到社会学、生物学、生态学、信息科学、计算机科学、数学、物理学、化学、地理、环境、军事学等,并取得了丰硕成果,如用于肿瘤细胞的增长机理、人类大脑的机理探索、航天军事作战模拟以及地理信息系统的开发等。但是,元胞自动机作为一种全新的方法,目前的研究仍然不完整。无论是对元胞自动机本身的演化行为及相关理论的研究,还是应用元胞自动机机理来研究其他学科,都成为研究的前沿与热点[2]。近年来,国内也有一些相关的应用性研究,但要么停留在理论上,要么仅仅是某方面的应用仿真[3]。因此,对元胞自动机的演化行为进行研究与仿真,并设计一个元胞自动机的演化行为仿真与应用系统是非常有必要的。本文在此基础上,开发出了元胞自动机演化行为研究与仿真系统软件,对元胞自动机的演化行为机理进行了深刻刻画。该软件可广泛地应用于社会学、生物学、信息科学、数学、物理、化学等领域,将为这些学科的科学研究提供一种全新的研究技术。

　元胞自动机的演化行为统计特征

1　一维元胞自动机的演化行为

元胞自动机是探讨复杂系统中局部—整体互动关系最简单的模式,可视为演化分析的基本计算模型。通常用两种方法来了解元胞自动机的演化行为,即计算机仿真及数学推演。元胞自动机体现了整体辩证思想:用简单的局域相互作用表现复杂系统的整体行为及其时间演化。它有三个显著的特点,即大规模同步并行、局域相互作用和简单结构。这些特点使其能高效地模拟许多复杂现象[5,6]。由于在元胞自动机中选择不同的规则能产生各种不同的演化模式,通过对其演化规则和演化行为的研究来探索复杂系统的演化过程。

沃尔弗拉姆(S.Wolfram)在详细分析研究了一维元胞自动机的演化行为,并在大量计算机仿真的基础上,将所有元胞自动机的演化行为归纳为四类[1]:

a)Ⅰ平稳型(homogeneous)。自任何初始状态开始,经过

一定时间演化和若干步运算后便停留在一个固定的状态。

b)Ⅱ周期型(periodic)。经过一定时间演化后,在几种状

态之间周期循环。

c)Ⅲ混沌型(chaos)。自任何初始状态开始,经过一定时

　　收稿日期:2006205222;修返日期:2006207228　　基金项目:国家自然科学基金资助项目(70371063)

　　作者简介:王仲君(19642),女,湖北武汉人,教授,硕导,主要研究方向为计算数学、生物信息学及复杂性研究(wangzj3000@gmail.com);王能超(19372),男,江苏盐城人,教授,博导,主要研究方向为并行算法、快速算法、复杂系统演化分析等;冯飞(19832),湖北松滋人,硕士研究生,主要研究方向为统计学、复杂性研究;田武峰,湖北荆州人,硕士研究生,主要研究方向为统计学、复杂性研究.

第8期王仲君,等:元胞自动机的演化行为研究　　　・39・

间演化后,处于一种完全无序随机的状态,几乎找不到任何规律。

d)Ⅳ复杂型(edgeofchaos)。在演化过程中可能产生复

元胞自动机属于第四类即复杂型。随着λ的增长,复杂结构的维持时间会变得越来越大。

d)λ≥0.6时,复杂结构消失,系统将被吸引到一种完全随

杂的结构。这种结构既不是完全的随机混乱,又没有固定的周期和状态。

在元胞自动机的演化行为研究与仿真系统中观察分析元胞自动机的演化行为,如图1(a)～(d)所示。

机的混沌状态。

综上所述,随着λ的增大,元胞自动机展现出来的结构将逐渐变得复杂。当λ介于一个中间值时,演化行为会达到最大的复杂性;随着λ的进一步增大,复杂结构会逐渐被随机结构所取代。

根据λ的连续变化,能够得到四种元胞自动机之间的过渡转换形态:Ⅰ2>Ⅱ2>Ⅳ2>Ⅲ,即固定点2>周期2>复杂2>混沌。

元胞自动机的第Ⅲ类型是完全随机、无序,这类系统过于松散,不可能产生有价值的结构。第Ⅳ类元胞自动机刚好存在在一维最简元胞自动机的情况下(状态数是2,半径是

1),从图1(a)观察132号元胞自动机变成了一条竖线,表明132号规则的元胞自动机被吸引到了一个固定的状态。图1(b)中208号元胞自动机是若干条斜线。由于边界是循环的,

于从有序到无序之间一个狭小的空间中。在这里,复杂结构形成了神奇的王国,会不断地看到若干局部结合成有趣的结构与秩序,但同时这些结构和秩序永远不会被冻结,它们偶尔会被破坏,但新的结构马上又会生成。这样的状态被人工生命之父郎顿称为混沌与秩序的边缘。科学家们已经对有序、随机的性质有了清楚的研究,然而对于从有序到无序转变的过程则仍然没有足够认识。原因在于这样的状态具有太多复杂的结构,很难预言它的具体性质。第Ⅳ类元胞自动机也是这样,下一时刻元胞自动机会是怎样的情况?除了按照其物理规律运行外别无他法,因为复杂的元胞自动机的行为不能预言。

复杂的结构诞生于混沌的边缘。把混沌边缘的概念推广,也就是把秩序、周期这些动态情况看做是一种凝固的吸引力,它保证了系统能够固定于某一种结构;另一方面,随机、混沌形成了另一种张力,使得系统趋于不稳定,但同时为系统提供了创新的动力。仅仅当这两种力处于一种恰到好处的平衡态时,也就是系统处于混沌的边缘条件下,该系统才会更加有活力,并且演变得越来越复杂。

1　二维及多维元胞自动机的演化行为

通过前面对一维元胞自动机机理的分析,可见元胞自动机是通过简单的规则进行演化,产生复杂的行为,并在大量的计算机仿真基础上,将所有元胞自动机的演化行为归纳为平稳型、周期型、混沌型和复杂型四大类。

对最简单的初等元胞自动机的分类尚且如此困难,而二维以至三维的规则更多,演化行为更为复杂,对二维或三维元胞自动机进行系统分类就更是难以进行。目前,国内外还没有相关的较好的研究成果。下面将对二、三维元胞自动机的分类从统计和渐进的角度进行探索。

1)统计渐进分类的原理

可以预言,经过若干个时间周期的运行后,元胞自动机将回复到原来的状态,这样的元胞自动机是循环的。两个相同状态之间经历的时间步长为这种元胞自动机的周期。图1(c)中203号元胞自动机既没有固定的周期也没有被吸引到一个点,它们处于一种混乱的、无序的状态,称这种状态为混沌状态。通过反复运行最简元胞自动机程序可见,所有的256种元胞自动机都能被归为固定值、周期循环、混沌三类。

是不是所有元胞自动机的演化行为只有这三种类型呢?考虑稍微复杂一点的情况,状态数为2,邻居半径为2的一维元胞自动机的情况。在这样的元胞自动机中,除了上面叙述的三种类别依然存在外,还发现了另一种类型,如图1(d)所示。其运行图好像一棵倒挂的葡萄藤。这种葡萄藤是一种复杂的结构,它既不等同于完全的随机,又没有固定的循环迹象。这种复杂结构正是笔者感兴趣的一种类型。因为它既没有被吸引到固定的点或周期状态而变得死板,又没有因为随机而过于活跃;它既保证了一定的流动活性,同时又能产生具有记忆性的结构。该运行情况显然不同于前面叙述的三种类别,称其为复杂型。几乎所有的一维元胞自动机运行的演化行为都能归到沃尔弗拉姆所划分的四类之中。

经过沃尔弗拉姆研究,发现可用参数λ来划分元胞自动机的类型。定义参数λ=(m2r+1-nq)/m2r+1。其中:m为状态集

S={s1,…,sm}中的状态数;r为邻居半径;nq是所有输出项为

0的个数。因此,λ参数反映了一组规则中转换成非零状态的

比例。

根据参数λ的取值不同,分析元胞自动机的演化行为:

a)当λ=0～0.1,所有的元胞被吸引到一种固定的状态,

在理论上,元胞自动机的演化空间通常在各维上是无限延展的,这有利于在理论上的推理和研究。在实际应用过程中,无法在计算机上实现这一理想条件,因此,需要定义不同的边界条件。归纳起来,边界条件主要有三种类型,即周期型、反射型和定值型。在应用中,这三种边界条件为更加客观、自然地模拟实际现象,还有可能采用随机型,即在边界实时产生随机值。

即为第一类元胞自动机。

b)λ=0.2附近,系统在一些固定状态之间周期循环,这相

当于第二类元胞自动机。λ=013的元胞自动机相比λ=0.2的在开始时具有更复杂的结构。

c)λ在0.3～0.6时,会出现相当复杂的结构。这些结构

既不属于固定周期或固定值,也不属于完全的随机。因此这些

・40・计算机应用研究2007年

a)周期型(periodicboundary)是指相对边界连接起来的元心一个元胞状态是生时,在经过有限步演化后,生的元胞比率趋于某一周期性的变化。

图4是在第1步后就开始周期性变化。其规则是

S=i

胞空间。对于一维空间,元胞空间表现为一个首尾相接的圈;对于二维空间,上下相接、左右相接,形成一个拓扑圆环面(to2

rus)。周期型空间与无限空间最为接近,因而在理论探讨时,

1　f(8)=0或8时,Si+1=1;否则Si+1=00　f(8)=1或7时,Si+1=1;否则Si+1=0

常以此类空间型作为试验。本文以周期型边界为前提来进行讨论。

b)反射型(reflectiveboundary)是指在边界外,邻居的元胞

图5是其演化到第10步和15步时的图像,其周期为57,这个规则的图像非常奇特有趣。对应地,在沃尔弗拉姆的分类中,表示稳定型演化行为。

状态是以边界为轴的镜面反射。

c)定值型(constantboundary)是指所有边界外,元胞均取

某一固定常量,如0、1等。

d)随机型(randomboundary)是指边界元胞取实时产生的

随机值。

在进行统计渐进分类时有三个前提:边界条件是周期型;元胞状态是两状态的,即生和死;初始条件是一个中心元胞状态为生,其他元胞状态为死。

在上述前提下,某一规则的元胞自动机演化到一定步数后,若其生的元胞比例趋于稳定,则为稳定型;若出现周期性的变化,则为周期型;若无明显规律,则为复杂型。可以看到,这种分类方法是根据元胞演化过程中的统计性质来分类的,并且是一种渐进(极限)情况下的统计性质。在具体判断某一规则是否为稳定型时,本文使用元胞自动机演化行为仿真系统。

2)二维演化行为的渐进统计分析

(1)稳定型　某一规则是稳定型是指当其初始条件为一

从演化行为的仿真例子可以看到周期型的两种类型:a)演化到一定步数后,生的元胞比例是一种简单周期,即周期为几类图案交替出现;b)演化到一定步数后也出现周期,但周期较长,且每一个周期内部还存在小周期(部分周期)。

(3)复杂型　不属于以上两种类型的统称为复杂型,即其

个中心元胞状态是生时,在经过有限步演化后,生的元胞比率趋于平稳(或不变)。

图2是能够生成自相似图形的规则动态统计图。其规则是

Si=动态统计图是无规则波动的曲线。

图6是复杂型规则的动态统计图。其规则是

S=i

1　f(8)=2、4、6、8时,Si+1=1;否则Si+1=00　f(8)=1、3、5、7时,Si+1=1;否则Si+1=0

1　Si+1=1

0　f(4)=1或4时,Si+1=1;否则Si+1=0

图7是演化到第154步和155步时的图像。这类情形仅从统计图上来看还不是太复杂,虽然波动幅度稍微有点大,但还算是比较稳定。由于其演化图非常复杂,没有什么规律,归为复杂类。对应的λ=0.468,在沃尔弗拉姆的分类中,表示复杂型演化行为。

其中:Si表示元胞在i时刻的状态;Si+1表示元胞在i+1时刻即下一时刻的状态;f(4)中的4表示邻居类型为4邻胞,其取值表示邻居状态为生的元胞数目之和。图3是演化到第26步时的行为,可以看到明显的自相似现象。当演化到第64步时就已经稳定(不变)了,这时元胞为生的比例为λ=016352,在沃尔弗拉姆的分类中,表示复杂型演化行为。

3)三维演化行为的渐进统计分类探索(1)三维元胞自动机统计渐进分类的原理

从演化行为的仿真例子可以看到稳定型的两种类型:a)演化到一定步数后生的元胞比例恒为某一个常数不变;b)演化到一定步数后趋于稳定,但不是常数,有一定的上下波动,但波动幅度非常小。

(2)周期型　某一规则是周期型是指当其初始条件为中

类似于二维元胞自动机统计渐进分类的原理,可以给出三维元胞自动机统计渐进分类的原理。三个前提是:边界条件是定值型;元胞状态是两状态的,即生和死;初始条件是各元胞状态以0.5的概率为生。

与二维元胞自动机统计渐进分类的前提相比:a)条件变

第8期王仲君,等:元胞自动机的演化行为研究　　　・41・

成了定值型。这是因为周期型的三维边界在计算机上实现比较困难(包括算法和运算速度两个困难),但这个对分类来说并没有太大影响。b)初始条件变成了随机型的初始条件。这个对于对初始条件特别敏感的规则来说影响较大,但可以通过多次重复进行仿真实验来消除影响。

在上述前提下,某一规则的元胞自动机演化到一定步数后,若其生的元胞比例趋于稳定,则为稳定型;若出现周期性的变化,则为周期型;若无明显规律,则为复杂型。

(2)三维演化行为的渐进统计分析

动态统计图如图12所示,演化到第14步时的图像如图13所示。其演化行为呈无规则状态,为复杂型演化行为。

从图12可见,此演化规则对应于三维复杂型的演化行为。对应地,λ=0116,在沃尔弗拉姆的分类中,表示周期型演化行为。

①稳定型演化规则

1　f(26)=0、1、4、5、6、8、9、12、13、16、17、20、21、25、26时,

Si=　Si+1=1;否则Si+1=0

0　f(26)=1、5、9、13、17、21、25时,Si+1=1;否则Si+1=0

动态统计图如图8所示,演化到第118步时的图像如图9所示。

　结束语综上所述,沃尔弗拉姆对于元胞自动机的分类以及混沌边缘的概念,不仅仅适用于一维元胞自动机,对于二维甚至多维元胞自动机仍然适用。本文从统计和渐进的角度对元胞自动机进行了分类,从实际仿真情况来看,大多数属于稳定型和周期型,复杂型比较少。在实际仿真时发现,在统计上有规律的在其演化行为上可能表现得非常凌乱和无规律;而有些在演化图形上非常有规律的,在统计上局部却看不到什么规律,但从长期来看,却是周期的或是稳定的。可以认为这些是局部复杂

从动态统计图可见,此演化规则对应于三维渐进稳定型的演化行为。对应地,λ=01259,在沃尔弗拉姆的分类中,表示周期型演化行为。

②周期型演化规则

S=i

的,但全局服从一定的统计规律。

本文对于二维和三维元胞自动机分类的探讨只是初步的。本文最有意义的工作是开发出了一个完整的元胞自动机演化行为研究与仿真系统。元胞自动机演化行为的仿真是进行元胞自动机演化行为研究及应用的必要手段,本系统可以提供一个很好的平台。参考文献:

[1]WOLFRAMS.Anewkindofscience[M].

Media,Inc.,2002:2312249.

[2]WOLFRAMS.Theoryandapplicationsofcellularautomata[M].

[S.l.]:WorldScientificPublishingCo.PTELtd,1986:2032220.[3]周成虎,孙战利,谢一春.地理元胞自动机研究[M].北京:科学出

[S.l.]:Wolfram

1　f(26)=0、1、25、26时,Si+1=1;否则Si+1=00　f(26)=5、8、20、23时,Si+1=1;否则Si+1=0

动态统计图如图10所示,演化到第20步时的图形如图11所示。其演化行为呈渐进周期状态。

版社,1999:26250.

[4]WEISBUCHG.Complexsystemdynamics:anintroductiontoauto2

matanetworks[M].[S.l.]:Addison2WesleyPublishingCompany,1991:1132140.[5]

PLATEAUB,ATIFK.

Stochasticautomatanetworkformodeling

parallelsystems[J].IEEETransonSoftware,Engineering,1991,

从图10可见,此演化规则对应于三维渐进周期型的演化行为。对应地,λ=01307,在沃尔弗拉姆的分类中,表示周期型演化行为。

③复杂型演化规则

S=i

17(10),108321108.

[6]PALADINE.变异和演化———演化理论简述[EB/OL].http://

www2.hkedcity.net/citizen_files/aa/bs/fy1379/public_html/e2volve.htm.

[7]邓黎,王仲君.扩展奇偶规则的元胞自动机模型和分析[J].武汉

1　f(26)=1、12、13、23时,Si+1=1;否则Si+1=00　f(26)=0、4、24、26时,Si+1=1;否则Si+1=0

理工大学学报:交通科学与工程版,2004,28(6):9362938.

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

元胞自动机的演化行为研究