（课程与教学论专业论文）螺旋元胞自动机的生长、时间演化行为及其应用.pdf

螺旋元胞自动机的生长、时间演化行为及其应用 摘要 非线性现象的研究是当前科学家重点关注的领域，其中元胞自动机是非线性 研究的一个重要手段和工具。 本文综述了元胞自动机的基本原理和几种典型的元胞自动机的构造方法。并 通过大量的计算机模拟研究螺旋元胞自动机中的图形构成，发现螺旋元胞自动机 的生长不仅仅依赖于螺旋的周长，而且对初始化种子的配置也十分敏感，其中周 长决定了模型的长期生长行为，而种子的配置对局域生长的影响较为显著。此模 型可以产生一系列的规则生长图案，包括s i e r p i n s k i 三角毯、紧凑结构、复合 图形阵列、层状结构、二相结构等图案。随着图形生长高度的增加，模型在不同 的周长和种子配置条件下展现了周期的、突变的和缓慢的生长行为。文章通过分 形维数和占有率计算定量分析了不同的生长过程。另外，研究发现，经过剧烈的 振荡螺旋元胞自动机的时间演化最终都呈现出占有率趋近0 3 3 4 的结果。 文中对螺旋元胞自动机的应用进行了探讨，发现其中周长为2 的n 次方的占 有率随时间的演化可以描述环境污染与经济增长关系中的威布尔函数分布曲线。 最后利用螺旋元胞自动机生长的混沌特征构造了一种简便的随机数发生器。 关键词：元胞自动机；模拟；螺旋生长：分形；时间演化 g r o w t ha n dt i m ee v o l u t i o nb e h a v i o ro fh e l i c a lc e l l u l a r a u t o m a t aa n di t sa p p l i c a t i o n a b s t r a c t i np r e s e n t ，t h es t u d yo fn o n l i n e a rp h e n o m e n ai saf o c a lf i e l d ，w h i c hs c i e n t i s t sp a y c l o s ea t t e n t i o nt o ，a n dc e l l u l a ra u t o m a t a ( c a ) i sa ni m p o r t a n tm e a n sa n dt o o lo f s t u d i n gn o n l i n e a r i t y i nt h i st h e s i s ，t h em a i np r i n c i p l eo fc aa n dt h ec o n s t r u c tm o t h o do fs e v e r a l t a p i c a lc a h a v eb e e nr e v i e w e d t h e p a t t e r nf o r m a t i o ni nah e l i c a lc e l l u l a ra u t o m a t o n ( h c a ) m o d e li ss t u d i e db yc o m p u t e rs i m u l a t i o n s i ti sf o u n dt h a tt h ee v o l u t i o n so ft h e h c aa r es e n s i t i v en o to n l yt ot h ec i r c u m f e r e n c eo ft h eh e l i xb u ta l s ot ot h ei n i t i a l s e e d s t h el o n g t e r mg r o w t hb e h a v i o ri sd e t e r m i n e db yt h ec i r c u m u l a t eo fh e l i xw h i l e t h el o c a lb e h a v i o ri sd e t e r m i n e db yt h ep e r i o d i cs e e d c o n f i g u r a t i o nw i t hf i x e d c i r c u m f e r e n c e t h em o d e lg e n e r a t e sas e r i e so fn o v e lp a t t e r n s ，i n c l u d i n gs i e r p i n s k i t r i a n g l eg a s k e t ，c o m p o u n dp a t t e r n sc o n s i s t i n go fr e g u l a ra n dr a n d o ms t r u c t u r e s ， c o m p o u n dp a t t e r na r r a y , l a y e rp a t t e r n , t w o p h a s e ，a n ds oo n w i t hi n c r e a s i n gh e i g h to f t h ep a t t e r n s ( i n c r e a s i n gg r o w t ht i m e ) ，t h em o d e la l s oe x h i b i t sp e r i o d i c ，a b r u p t ，a n d g r a d u a lg r o w t hb e h a v i o r sf o rd i f f e r e n t s e e dc o n f i g u r a t i o n s ，r e s p e c t i v e l y f r a c t a l d i m e n s i o na n a l y s i si su s e dt oc h a r a c t e r i z et h e s ed i f f e r e n te v o l u t i o n p r o c e s s e s q u a n t i t a t i v e l y s u b s e q u e n t l y , t h eo c c u p a n c yv a l u eo ft i m e e v o l u t i o nb e h a v i o ri s c a l c u l a t e da n df o u n dt ob ec l o s et oo 3 3 4a f t e ra b r u p to s c i l l a t i o n s o m ea p p l i c a t i o n so fh c ah a v eb e e ns t u d i e da l s oi nt h i sp a p e r i ti sf o u n dt h a t t h ec u r v eo ft i m ee v o l u t i o nw h e r epi se q u a lt oap o s i t i v ei n t e g e rp o w e ro f2i ss i m i l a r t ow e i b u l ld i s t r i b u t i o nc u r v e ，w h i c hu s e dt od e s c r i b et h er e l a t i o n s h i po fe n v i r o n m e n t a l p u l l u t i o na n de c o n o m i cg r o w t h f i n a l l y , a c c o r d i n gt ot h ec h n o sb e h a v i o ri no u r h c a m o d e l ，as a m p l eo fp s e u d o r a n d o mn u m b e rg e n e r a t o rw a sd e s i g n e da s a n o t h e r e x a m p l eo fa p p l i c a t i o n so f t h eh c a k e yw o r d s ：c e l l u l a ra u t o m a t a ；s i m u l a t i o n ；h e l i c a lg r o w t h ；t i m ee v o l u t i o n 插图清单 图2 1 三种典型的二维网格结构4 图2 2 一维线形元胞自动机的邻居模型5 图2 3 几种典型的邻居结构。5 图2 4 典型的边界条件6 图3 1s i e r p i n s k i 三角毯和s i e r p i n s k i 海绵8 图3 2s i e r p i n s k i 三角毯的构造过程1 0 图3 3 盒计数法计算分维1o 图3 4 采用最小二乘法的拟合曲线( 斜率= 1 9 2 6 7 3 ) 。1 1 图4 1l c a 的四类演化行为。1 3 图4 2 森林火灾的二维结果临界状态的快照。1 4 图4 3c c a 生长演化的模型( a ) 仁1 ( b ) t = 2 15 图4 4c c a 在不同时间步骤的演化结果1 6 图4 5 人口比率随时间的变化( 万= 0 ，万= 0 6 ) 1 7 图5 1 螺旋元胞自动机的立体结构。1 9 图5 2 周期性种子设置( a ) t = 1 ( b ) t = 2 ( c ) t = 3 ( d ) t - ：4 1 9 图5 3 螺旋元胞自动机的平面展开结构2 0 图6 1 偶数p 和奇数p 序列在n = 6 时的前三个图形，偶数p 序列：2 l 图6 2 螺旋元胞自动机的生长图形( t = 1 ) 。2 2 图6 3 对应于不同螺旋周长p 的占有率r ( t _ 1 ) 2 3 图6 4 图形在竖直方向上的生长( a ) p = 2 5 7 ，c o ) p = 2 5 8 ，( c ) p = 3 8 4 2 4 图6 5 分形维数随块序数的变化( a ) p - 2 5 7 ，( b ) p = 2 5 8 ，( c ) p = 3 8 4 2 5 图6 6 周期t - - 3 时，螺旋元胞自动机的生长图形2 6 图6 7 对应于不同螺旋周长p 的占有率1 7 ( t = 3 ) 。2 7 图6 8 图形在竖直方向上的生长( p = 3 2 1 ，t - 3 ) 2 7 图6 9 分形维数随块序数的变化( 9 = 3 2 1 ，t _ 3 ) 2 8 图6 1 0 螺旋元胞自动机的生长图2 9 图6 1 1 分形维数随块序数的变化( p = 2 5 6 ) 3 0 图6 1 2 周长为2 5 6 ，种子周期为4 3 的生长情况3 0 图6 1 3 螺旋元胞自动机在p = 2 5 8 时不同种子周期的演化行为3 1 图6 1 4 分形维数随种子周期的变化( p = 2 5 6 ) 3 2 图6 1 5 分形维数随块序数的变化( 9 = 2 5 8 ) ( a ) t = 3 2 ，( b ) t = 1 3 1 ，( c ) t = 1 5 。3 4 图6 1 6 分形维数随块序数的变化( a ) t = 3 2 ，( b ) t 1 3 1 ，( a ) t = 1 5 。3 5 图7 1 螺旋元胞自动机( p = 2 5 6 ，t - 1 ) 的时间演化图：3 7 图7 2 小区域的放大图形3 7 图7 3 占有率随时间变化曲线( t = 1 ) 3 8 图7 4 螺旋元胞自动机( p = 2 5 7 ，t - 1 ) 的时间演化图3 8 图7 5 占有率随时间变化曲线( t = 1 ) 3 9 图7 6 螺旋元胞自动机( p = 2 5 8 ，t 1 ) 的时间演化图4 0 图7 7 占有率随时间变化曲线( t = 1 ) 4 1 图8 1 威布尔拟合得结果( a ) p = 3 2 ，( o ) p = 6 4 ，( c ) p = 1 2 8 ，( d ) p = 2 5 6 ，( e ) p = 5 1 2 4 3 图8 21 0 0 0 个( 左) 和3 0 0 0 个( 右) 随机数的频数直方图4 5 图8 3 硬币投掷的3 种情况4 7 图8 4 硬币投掷的三种情况对应的轮次4 7 表格清单 表2 1 一维和二维元胞自动机的数目5 表4 1 万= 0 时拟合l o g i s t i c 曲线的参数1 7 表8 1 威布尔分布拟合结果表4 2 表8 21 0 0 0 个随机数的均值4 4 表8 31 0 0 0 个【0 ，1 1 域数字的频数统计4 6 表8 - 4 轮次检验结果4 7 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外。论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金胆王些盔堂 或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：肆窆 签字日期：一芬 学位论文版权使用授权书 年p 厶矿产 本学位论文作者完全了解金胆王些盔堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金世 王业太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：痒蒸事 签字日期：驴习年口石月6 7 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 翩撇吗吁 签字日期：年 月日 电话： 邮编： 致谢 本人在三年的硕士研究生课程学习和撰写学位论文的过程中，自始至终得到 了我的导师马力平副教授的悉心指导，无论从课程学习、论文选题，还是到收集 资料、论文成稿都倾注了马力平老师的心血，由衷感谢马老师在学业指导及各个 方面所给予我的关心，老师严谨的治学作风、诲人不倦的教育情怀，将使我终身 受益。特别感谢阜阳师范学院物电学院的王戴木教授在我做课题期间给予的各种 指导和论文期间提供的大力支持。王老师对待科学的严谨态度，对待学生的宽厚 耐心令我终生难忘。 特别感谢何晓雄、邓铁如教授在我学习和生活上的无私帮助和支持，他们宽 厚的胸怀和广博的学识令我终生难忘，在此谨向两位老师表示衷心感谢。 感谢邓小玖教授、罗乐副教授、梅忠义副教授、高峰副教授等老师的热情指 导和帮助。 同时感谢我的同学王勇、万宝礼、徐迪、赵永礼、王超群、王东、符晓四、 李姗姗、王钰、张云丽、袁润、王星烁、李怀龙等同学在硕士期间给我的关心和 帮助! 特别感谢阜阳师范学院给我读研深造的机会。特别感谢我的亲人们，如果没 有他们的无私付出和支持，就没有我的一切。感谢我的爱人和儿子从我考研到现 在对我始终不变的支持。 感谢所有帮助过我的领导、师长、朋友和同学。 i u 作者：朱辉 2 0 0 8 年4 月2 0 日 第一章导论 1 1 概述 自然界常常呈现出复杂而又有序的结构和行为，追根究底是由大量基本组 成单元的简单相互作用引起的，m 但是由于理论和实验技术等方面的限制，科学 家们尚无法对其进行完美的描述。自从2 0 世纪5 0 年代以来，对于这些现象的 研究促使非线性科学及其相对应的复杂性成为研究的前沿领域。 对于一个非线性系统而言，虽然由大量的个体构成，但是在行为上并非表 现出个体效应的简单累加，而往往呈现出个体的集体的效应：如自组织行为、 耗散结构和合作行为等，都显现出典型的集体效应。多年以来，人们用名为元 胞自动机( c e l l u l l t l a u t o m a t a ) 的模型来模拟研究这些复杂行为。 元胞自动机是在空间和时间离散并且物理量是有限的离散序列值的物理系 统理想化的数学模型乜1 。在计算机模拟非线性系统的方法中，由于计算机基本结 构的特征，决定了元胞自动机是一个行之有效的模拟方法。元胞自动机的模型 最早是由著名的科学家冯诺依曼( y o n n e u m a n n ) 在应用计算机研究生物系统的 局域生命行为自繁殖行为时提出的。在此模型中，冯诺依曼把一个平面 分成若干个网格，每一个格点表示一个细胞或系统的基元，它们的状态赋值为o 或1 ，分别用空格和实格来表示。当演化的规则决定以后，这些细胞或基元就开 始了自我繁殖的过程。此模型开创了用元胞自动机的方法研究复杂系统的先河。 在冯诺依曼提出元胞自动机理论以后，由于计算条件等等的限制，元胞 自动机的研究沉寂了一段时间。直到上世纪6 0 年代末期，英国科学家约翰康 卫( j o h nc o n w a y ) 设计的一个生命游戏( g a m e “l i f e ”) 模型口1 ，即在一个二维的棋 盘方格中，每格均由两种状态组成，分别是“活着的 的黑方块和“死了的 白方块，每个方格有八个邻格，游戏的规则包括3 个：生存规则，对于生存的 格点而言如果邻居的数目为2 个或者3 个，这一代存活的状态就能保持下去； 死亡规则，同样对于生存的格点如果邻居数目超过4 个，会因为拥挤造成下一 代死亡，假如邻居的数目为1 个或者o 个，下一代会因为孤独而死亡；生长规 则，对于死亡的格点，8 个邻近的格点中有3 个处于生存状态，则此点会转化成 一个新的生长格点。g a m e “l i f e ”的初始图案可以由游戏者任意摆布。但运行这 个游戏后，这些方块就会根据很少几条简单规则活过来或死过去。尽管它的规 则看上去很简单，但生命游戏是具有产生动态图案和动态结构能力的元胞自动 机模型。它能产生丰富的、有趣的图案。生命游戏的演化与初始元胞状态值的 分布有关，给定任意的初始状态分布，经过若干步的运算，有的图案会很快消 失，有的图案则固定不动，有的周而复始重复两个或几个图案，有的婉蜒而行， 而有的则保持图案定向移动，形似阅兵阵，其中最为著名的是“滑翔机 ( g l i d e r ) 的图案。g a m e “l i f e ”模型取得了元胞自动机理论提出以来的重大成功， 吸引许多的科学家投入到元胞自动机理论和模型的研究中。 上世纪8 0 年代掀起了股研究元胞自动机的热潮，人们通过计算机模拟得 到各种奇妙的图案，如奇怪吸引子、混沌、自组织以及经典的分形图形等。其 中对元胞自动机作出杰出贡献的是s w o l f r a m 。他通过统计物理的方法对最简单 的一维线性元胞自动机( l i n ec e l l u l a ra u t o m a t a ) 的模型进行全面的研究，揭示了 元胞自动机的基本特征，并把元胞自动机的理论进一步推广到动力学系统的研 究中。h 1 此后，在数学家、物理学家、计算机学家和生物学家等共同努力下，构 造了一系列的元胞自动机模型- - w i l l s o n 的一维分形元胞自动机嵋1 、随机元胞 自动机嘲、循环元胞自动机盯1 、i s i n g 模型阻1 、格子气自动机四1 、交通流模型n 们、 量子元胞自动机叫和圆周元胞自动机n 2 ，等。 这些模型和改进的模型现已被广泛地应用于自然科学的各个领域，如物理 学中的晶体生长、悬浮体的聚集、缺陷的产生、i s i n g 模型、各种流体的流动、 扩散、热传导、机械波、光的传播以及场的模拟等hn 3 】- 【1 ；计算机科学中，由 于元胞自动机先天的性质决定其不仅是研究并行计算的有力工具n 射，也广泛地 应用到计算机图形学等各个领域n 町吨2 ：生命科学中元胞自动机可以模拟心脏的 颤动、肿瘤的生长、贝壳或者毛皮上色素的沉淀、生物及人口增长的l o g i s t i c 模型等方面；嘲吖2 钔在其他自然科学领域中还可以用来模拟地震的成因、森林火 灾等各方面口鄙1 2 刀。 随着元胞自动机理论的不断发展，其进一步应用到社会科学的各个领域， 如犯罪问题、舆论和疾病等的传播汹h 3 、股票市场中的羊群效应口幻“3 朝、交通流 问题的研究n 们、教育科学m h 汹1 、经济危机的形成与爆发、人类大脑的机理探索、 历史问题、土地利用、管理科学以及城市规划等方面。跚叫3 钔虽然元胞自动机在 社会科学中的应用尚不及其在自然科学中的应用广泛和深入，但随着时间的推 移和人类对社会科学规律的进一步认识，元胞自动机在社会科学中的应用也逐 渐表现出了强大的生命力。 1 2 本论文的研究内容及创新之处 1 2 1 研究内容 在2 0 0 5 年度安徽省自然科学基金项目“纳米团簇自组装生长动力学的蒙特 卡罗模拟”的基础上，考虑到柱状螺旋是自然界中一个基本结构，而且人类社 会的演化发展也遵循螺旋发展的规律，因此本论文旨在将螺旋元胞自动机的理 论作进一步的拓展，研究其在不同初始条件下的生长行为和时间演化规律， 并给出了螺旋元胞自动机的几个具体应用实例。主要包括以下内容： 1 ) 元胞自动机特征和元胞自动机的基本组成单元； 2 ) 元胞自动机和分形； 3 ) 从不同的角度探讨了几种典型的元胞自动机的构造方法及其典型的应 用，分别是从图形演化和统计分析的角度研究的l i n e a rc e l l u l a ra u t o m a t a ( l c a ) ； 2 从概率规则上研究的p r o b a b i l i s t i cc e l l u l a ra u t o m a t a ( p c a ) 及其在火灾问题 上的典型应用；以及采用顺序扫描方式生长和时间演化的c i r c u l a rc e l l u l a r a u t o m a t a ( c c a ) 模型及其演化图形分析。 4 ) 探讨了螺旋元胞自动机的构造方法； 5 ) 在现有的螺旋元胞自动机的模型基础上，研究种子初始化条件的改变对 其生长行为的影响，并利用盒计数方法对这些生长结果进行分形维数分析和采 用占有率对生长结果进行统计分析； 。 6 ) 研究螺旋元胞自动机时间演化的结果，通过分形维数分析的方法和占有 率的方法对其时间演化行为进行统计分析； 7 ) 探讨了螺旋元胞自动机的应用； 8 ) 结论。 1 2 2 本论文的创新之处 1 ) 对螺旋元胞自动机的理论作了进一步的拓展，在周长对螺旋元胞自动机 生长影响的基础上提出了影响其生长新条件一种子的配置方式。并在其两个 初始条件的影响下，系统地研究了螺旋元胞自动机的生长行为，得到了一些新 的结果，如：复合图形阵列、层状结构、二相结构等。通过统计分析总结了不 同初始条件对生长行为的影响。 2 ) 研究了螺旋元胞自动机的演化行为。重点研究了在不同周长下，生长点 的占有率随时间的变化趋势。揭示了不同周长下，螺旋元胞自动机从规则图形 向混沌图演化过程中的变化行为。 3 ) 通过威布尔分布对周长为2 的n 次方的演化曲线的拟合，并把拟合结果 和环境污染与经济发展关系曲线比较，得到了相近的形状参数。 4 ) 利用螺旋元胞自动机特定周长混沌的特点设计了一个伪随机数发生器， 并对其产生的随机数进行统计检验，能符合伪随机数的均匀性和随机性的特征。 3 第二章元胞自动机的基本理论 元胞自动机，又称点格自动机、细胞自动机、单元自动机等，1 9 8 4 年p h y s i e a d 出版了二- 期元胞自动机研究专辑( 第一期) 。在序言中，s w o l f r a m 总结了元胞 自动机具有的五个基本的特征h ： 从几何学上来看其是由分离的元胞空间组成： 每个元胞的状态的取值都是有限的值； 元胞自动机的演化在时间上分离： 元胞自动机模型中的每个元胞的演化所遵从相同的规则： 每个元胞的都拥有邻居，而且其值的变化仅仅依赖于它周围局域邻居的作 用。 这些特征充分体现了元胞自动机的离散性、齐质性、局部性、动态性和简 单性的特点及元胞自动机的构成要素，具体可以表现为元胞空间、邻居、边界 条件、演化方式和规则。 2 1 元胞空间 元胞空间是一个d 维的网格，在特殊的情况下也可能是无限维的。在研究 物理系统和社会行为时，考虑到计算的复杂性和区域有限的限制，这些研究大 多采用二维网格。 由于空间对称性的限制，二维网格可以采用的网格空间有正方网格、三角 网格和六角网格三种常见的方式h 幻，分别对应图2 1 ( a ) 一( c ) 。这三种网格划分 的元胞空间在构模时各有优缺点，其中正方网格简单直观，非常适合计算机编 程。现在绝大多数的元胞自动机的模型都是构建在正方网格上面，即使是新构 造的元胞自动机的网格空间仍多以正方网格为基础或者利用等效变换转换到正 方网格中计算，但正方网格在斜方向的限制，使其难以应用到各向同性的模拟 中。相对正方网格而言，三角网格的优点是拥有相对较少的邻居数目，特别对 一些三角结构，能表现出强大的优越性，其缺点是在计算机上的表达与显示不 方便，在计算的过程中仍需转化为正方网格进行计算。六边形网格的优点是能 较好地模拟各向同性的现象，因此，模拟能更加自然而真实，如格气模型中的 f h p 模型，其缺点同三角网格一样，在表达显示上较为困难、复杂。 ( a ) 四方网格( b ) 三角网格( c ) 六角网格 图2 1 三种典型的二维网格结构 4 2 2 邻居 元胞自动机的邻居指在所研究的元胞点( 中心元胞) 搜索空间域内的元胞。 图2 2 显示的一维线性元胞自动机的邻居示意图，其中黑色的格点对应的是中 心元胞，浅灰色的格点表示搜索空间域内的元胞( 邻居) ，从图中可以看出搜索 的区域为左右各2 个格点，也可以称之为搜索半径r 为2 。 i j 豳鍪匿蠢一j 二一 圈中心元胞围邻居 图2 2 一维线形元胞自动机的邻居模型 原则上对邻居的大小没有限制，但实际运用上由于最近邻对中心元胞的影 响较大，而远离被研究的元胞点的邻居对研究点产生的影响较小，加之计算机 速度、内存等的限制，不可能采用较多的邻居数目参加运算，所以在实际应用 中往往只需考虑邻接的元胞。同理，如果邻居的状态过多，演化规则的复杂程 度的增长变得不可以接受，以一维元胞自动机和二维元胞自动机为例，它们的 复杂性通常随邻居元胞的数目成指数增长( 表2 - 1 ) 。 表2 - i 一维和二维元胞自动机的数目 一维元胞自动机二维元胞自动机 r七 元胞自动机数目网格形状 z七 元胞自动机数目 l22 r ：2 8 ：2 5 6 正方 522 r ：2 3 2 4 3 1 0 9 222 f ：2 3 2 4 3 1 0 9 六角 722 2 7 ：2 , 2 8 1 0 3 8 表中r 为搜索半径，k 为元胞可能取值数目，z 为参与规则演化的格点数目。 对于二维元胞自动机，为了简化计算的复杂度，在应用中多采用下面三种 常用的邻居：h 3 1 1 ) v o nn e u m a n n 邻居 中心元胞的最近邻，又称为y o nn e u m a n n 邻居( 图2 3 ( a ) ) ，是由中心元胞 的邻接元胞构成，对于正方网格，分别是其上下左右方位的四个元胞。 2 ) m o o r e 邻居 在最近邻的基础上，增加考虑次近邻，称为m o o r e 邻居( 图2 3 ( b ) ) ，共有 九个元胞组成。如果进一步考虑到二级邻居，如图2 3 ( c ) ，此种邻居类型，称 之为扩展m o o r e 型邻居。 f 1 翁_ t j 翻瞄j 幢一l 阂r j l 卜卜il ll j ( a )( b ) ( c ) 图2 3 几种典型的邻居结构 雕 口二 二妇二 二 ( d ) 鬻蕾j ；j | | 3 ) m a r g o l u s 邻居 研究格子气体的时候，通常采用m a r g o l u s 类型，它是基于一个2 2 的网 格空间，以包含四个方块为基本单元进行研究。这个规则对左上佃) 、右上( u r ) 、 左下( 1 1 ) 和右下( h ) 很敏感。如图2 3 ( d ) 所示，在此种网格的条件下，可以有两 种可能的分块形式：奇数分块和偶数分块，分别以实线和虚线界定的单元块。 邻居分别在偶数时步和奇数时步在这两种情况之间交替变化。在进行下一次迭 代时，分块替换，l r 元胞将转化为u l 。 此外，可以根据具体模型所敏感的区域来定义不同形式的邻居，如扩展的 m o o r e 邻居等。 2 3 边界条件 实际上，利用元胞自动机进行模拟的时候，由元胞自动机的局域性特点， 决定系统必须是有限的、有边界的。这样属于网络边界的格点就不具有与其它 格点一样的邻居，为了确定边界格点的行为，可以制定不同的边界条件，为边 界上的格点制定不同的邻居。一般来说可有下面几种典型的边界条件，分别是： 周期条件、固定边界、绝热边界和映射边界( 图2 4 ( a ) 一( d ) ) 。在特殊的应用中 也可以采用其他的边界条件，如开放性边界条件，此时需要考虑在边界流入和 流出的概率，能成功地应用到交通流问题的研究中k “钔，模拟的结果更符合 真实的交通情况。 如二二二二二二二二回 周期边界 细二二二二二二二二口 固定边界 团二二二二二二二二口国二二二二二二二二口 绝热边界 映射边界 图2 4 典型的边界条件 2 4 元胞更新方法 元胞的更新次序中，考虑到微观系统的变化规律，如在扩散过程、疾病传 播等物理和社会的动力学过程中，所有的元胞的下一时刻的变化可以看作是同 时完成。此类型的问题的研究中，元胞自动机的每个元胞的演化多采用平行更 新方法，让所有的元胞在下一时刻( + 1 ) 同时改变自己的状态。 但真实世界中并不是所有的过程中所有的元胞都同时更新，如晶体生长过 程等。为了模拟此种类型的演化，吴自勤等在通过数值模拟的方法研究金属半 导体晶体薄膜的生长过程中提出了顺序生长的方法，此模型中，所有的格点 按照一定的扫描次序进行生长，每一次仅仅研究一个格点的变化，当前格点生 长完毕后，再研究下一个格点的演化行为。 6 2 5 规则 规则是根据元胞当前的状态即邻居状态确定下一时刻该元胞状态的动力函 数，中心元胞的演化可以使用下式来表示，定义为： s + 。( f ) = r ( s ( f ) ，墨o + 磊) ，s ，o + 磊) ，s ( f + 8 q ” ( 2 1 ) 其中s ( f ，f ) 为第j 个元胞在t 时刻的状态，f + 瓯为元胞自动机的第k 个指 定邻居。 元胞自动机的生长、演化规则很多，其中常用的有： 1 ) 奇偶规则：是定义在二维方形网格上，网格的每一个格子是一个元胞，用 它的位置( ，) 来表示，其中f 、，为行和列的标号，函数以五j f ) 描述元胞( f j j f ) 在时刻芒的状态，其值为0 或1 ，元胞( 五，) 在下一时刻的状态转移函数可以 表示为 墨+ l ( f ，) = 墨( f + 1 ，力。墨( f - 1 ，_ ，) o 墨( f ，j + 1 ) 0 s ( f ，j f 一1 ) ( 2 2 ) 式中0 为“异或 逻辑运算，即模2 加法。 2 ) 表决规则：初始状态在正方网格上随机分布的一些白点和黑点，邻居选 择最近邻和次近邻及其本身共9 个网格点，采用少数服从多数的原则来决定下 一时刻是白点还是黑点，即5 个或者5 个以上的白点，中心元胞下一时刻即为 白点，5 个或者5 个以上的黑点下一时刻中心元胞为黑点。 3 ) 中间拥挤度规则：二维网格的4 个最近的v o n n e u m a n n 邻居中有且仅有 一个位置是生长点时，中央元胞才会变成生长点，如果最近邻的生长点为o 个( 太 孤独) 或有2 个以上( 太拥挤) ，中心元胞都会变成死亡点( 白点) 。 此外还有一些针对所研究问题的具体模型而提出的规则，譬如蚁行规则、 沙堆规则和q 2 r 规则等。 2 6 本章小结 本章概述了元胞自动机的基本理论和元胞自动机的构成要素，并指出了这 些要素在元胞自动机模型中的典型应用。 7 第三章元胞自动机与分形 元胞自动机与相关理论和方法的发展有着千丝万缕的联系。一方面，元胞 自动机的发展得益于相关理论的研究，如逻辑数学、离散数学、计算机中的自 动机理论和图灵机思想等等；另一方面，元胞自动机的发展也促进了一些相关 学科和理论( 如人工智能、非线性科学、复杂性科学) 的发展，甚至还直接导致 了人工生命科学的产生。另外，在表现上，元胞自动机模型还与一些理论方法 存在着较大的相似性，或者相对性，如：人工生命研究、“混沌的边缘”、微分 方程、马尔科夫( 链) 过程、随机行走模型和凝聚扩散模型等相关的理论方法。 其中元胞自动机与分形理论有着密切的联系，也是本文采用的重要研究方 法之一。元胞自动机的自复制、混沌等特征，往往导致元胞自动机模型在空间 构形上表现出自相似的分形特征，即元胞自动机的模拟结果通常可以用分形理 论来进行定量的描述。分形维数的计算是最基本分形图像分析方法，为了研究 这些特征，我们采用分形维数的方法来研究元胞自动机的统计属性。 3 1 分形的定义 1 9 7 3 年，曼德勃罗( b b m a n d e l b r o t ) 在法兰西学院讲课时，为了表征自然 科学领域的复杂图形和复杂过程，首次提出了分维和分形几何的设想，它的原 意是不规则的、支离破碎的物体。h 刀由于不规则现象在自然界是普遍存在的， 因此分形几何又称为描述大自然的几何学。 分形可以分为规则分形和不规则分形。规则分形指的是具有严格自相似的 结构。例如：c a n t o r 集、k o c h 曲线、s i e r p i n s k i 垫片、地毯和海绵等。图3 1 中的( a ) 和( b ) 分别对应s i e r p i n s k i 三角毯和s i e r p i n s k i 海绵。 不规则分形指自相似是近似的或统计的结果。如：蜿蜒曲折的海岸线、变 换无穷的布朗运动、闪电放电通道、胶体气溶胶聚合体的有限扩散凝聚等。这 些图形自相似性只存在于标度不变区域内，超过标度不变区域，自相似性不复 存在。 然而，分形及其度量分形维数的确切严格定义至今尚未解决。h l 引分 形几何学的奠基人m a n d e l b r o t 曾经给出两个定义： a af r a c t a li s b yd e f m i f i o n as e tf o rw h i c ht h eh a u s d o r f f - b e s i c o v i t c h d i m e n s i o ns t r i c t l ye x c e e d st h et o p o l o g i c a ld i m e n s i o n ( 1 9 8 2 年) b af r a e t a li sas h a p em a d eo fp a r t ss i m i l a rt ot h ew h o l ei ns o m ew a y ( 19 8 6 年) 两个定义中前者不能很好的反映自相似性，而后者虽然能反映自相似性， 但自相似性并不能代表分形的全部。 著名的分形几何学家f a l c o n e r 也回避分形的精确定义，仅仅给出五条用不 确定语言描述的分形特征 a 一个细微的结构； b 非常不规则； c 部分的自相似； d 一般来说，分形维数是主要的； e 大部分规则的定义都是相当简单的，也可以是重复的。 两者在定义中都表明了分形的自相似性。 3 2 几何图形的维数 3 2 1 分维 在欧氏空间中，人们一般理解维数是描述空间中一个点的坐标数目，例如 习惯把空间看成三维的，平面或球面看成二维，而把直线或曲线看成一维。也 可以稍加推广，认为点是零维的，还可以引入高维空间，但通常人们习惯于整 数的维数。分形理论则把维数视为分数，这类维数是物理学家在研究混沌吸引 子等理论时需要引入的重要概念。为了定量地描述客观事物的“非规则 程度， 1 9 1 9 年，数学家从测度的角度引入了维数概念，将维数从整数扩大到分数，从 而突破了一般拓扑集维数为整数的界限。郝柏林在从抛物线谈起混沌动 力学引论一书中通过对一维分形的研究，给出了规则图形的维数( d ) 的确定公 式： d = m ( s ) 砌( 1 占) ( s - - - 1o ) ( 3 1 ) 式中的是测量单元的尺寸，可以是尺子( 一维) 、正方形或者圆( 二维) 和 立方体和球( 三维) ，也可以根据具体的图形选择不同的测量单元。 3 2 2s i e r p i n s k i 三角毯的维数 1 9 1 5 年，波兰数学家谢尔宾斯基( w s i e r p i n s k i ) 设计了像地毯和海绵一样的 几何图形。这些都是为解决分析拓朴学中的问题而提出的反例，但它们正是分 形几何思想的源泉。 1 ) s i e r p i n s k i 三角毯的构造 如图3 2 所示嘲，把正三角形四等分成四个小三角形，挖去中间的一个， 把剩下的三个小三角形四等分后再挖去中间的一个，如此无限地进行下去，每 9 一次迭代后整个图形的面积都会减小到原来的3 4 ，因此最终得到的图形面积为 0 、由无穷多线段组成的s i e r p i n s k i 三角毯。它的h a u s d o r f f 维度介于1 和2 之间。 aaaa 图3 2s i e r p i n s k i 三角毯的构造过程 2 ) s i e r p i n s k i 三角毯的分维 根据上述定义，用边长为( 1 2 ) “的正三角形测量，得到的图形有3 ”个单元， 可以得到标准s i e r p i n s k i 三角毯的分维为： d = i n 3 1 i n 2 = 1 5 8 5 ( 3 2 ) s i e r p i n s k i 三角毯也可以不是等边三角形，也可以是直角三角形，分维计算 结果仍然是1 5 8 5 。 3 3 不规则分形的分维计算方法一盒计数方法 由于多数情况下计算分形集合的h a u s d o r f f 维数复杂而困难，导致实际应 用的不便。根据基于尺度测量的思想定义的分形维数，人们经常用实验的方法 算出分形的近似维数。目前测定不规则分形维数的方法很多，如求粗糙曲线的 圆规维数、从周长一面积关系或表面积一体积关系求分形维数、s a n d b o x 方法、 面积一回转半径方法、变换法、密度一密度相关方法及盒计数方法等。其中盒 计数方法是针对连续模型提出最为简单的计算分形维数的方法。咖3 二维图像的盒计数方法的实现如图3 3 ，将尺寸为占= l 8 和s = l 1 6 的网 格覆盖在分形图形上，计数网格中有图形象素( 不管有很多还是很少象素) 的方 格数目，例如得到n ( 1 8 ) = 6 1 和n ( 1 1 6 ) = 2 0 5 ( 增大不到4 倍) 。不断减小网格 尺寸继续计数含图形象素的网格数n ( e ) ，直至最小的网格尺寸达到象素为 止。为了减少误差，应该使不同尺寸的网格能覆盖相同大小的图形，如2 5 6 2 5 6 象素的图形的应当是1 ，1 2 ，1 4 ，1 8 ，1 1 6 ，直到降到1 2 5 6 ，而3 6 0 3 6 0 象素的图形的应当是1 ，1 2 ，1 3 ，1 4 ，t 5 ，1 6 ，直到降到1 3 6 0 。 图3 3 盒计数法计算分维 将一系列 ，f ，占夕、占数据作l n n ( ) - l n f 夕图，如能得到一条直线，它 1 0 说明j v ( e 夕和有如下关系 n ( s ) a c ( 1 f ) d ( 3 3 ) 图3 4 采用最小二乘法的拟合曲线( 斜率= 1 9 2 6 7 3 ) 图3 4 中离散点的经过线性拟合得出直线的斜率d 即为图形的分维，从结 果可以得到直线的斜率为1 6 6 7 9 8 ，也就表明图3 3 的分形维数为1 6 6 7 9 8 。如 果i n n ( e 夕_ 1 n 占) 图上只有一部分是直线时，则此图形的自相似性( 标度不变 性) 只存在于直线部分的测度范围内。这是由于实际分形和理想规则分形不同， 它只存在于有限的范围之内。 3 4 本章小结 本章简述了元胞自动机的理论方法之一分形分维方法。通过分形的定 义和分维的基本概念后，给出了分形维数的一种简便的测量方法一盒计数方 法。 第四章几种典型的元胞自动机 根据第二章元胞自动机的特征，许多不同种类、不同用途的元胞自动机被 构造出来并应用到科学研究的各个领域。如生命游戏、量子元胞自动机( q c a ) 、 线性元胞自动机( l c a ) 、概率元胞自动机( p c a ) 、圆周元胞自动机( c c a ) 、i s i n g 模型等不同类型的元胞自动机，本章就研究其中具有典型结构和规则的元胞自 动机。 4 1 线性元胞自动机( l c a ) s