初等元胞自动机的界面设计及稳定性分析

《初等元胞自动机的界面设计及稳定性分析》由会员分享，可在线阅读，更多相关《初等元胞自动机的界面设计及稳定性分析（5页珍藏版）》请在装配图网上搜索。

1、第26卷第7期计算机仿真2009年7月文章编号：1006- 9348( 2009) 07- 0178- 04初等元胞自动机的界面设计及稳定性分析郭娟,吴迪,赵宪明(东北大学轧制技术及连轧自动化国家重点实验室，辽宁沈阳110004)摘要:建立了所有规则下的初等元胞自动机的可视化模型及界面，设计了用于判断初等元胞自动机稳定性的应用程序,并可直接计算得到演化类型及周期。在此基础上，模拟得到了不同元胞数m,随机产生的不同的初始状态,不同规则数 R以及各种边界条件下初等元胞自动机的演化结果，并分析了以上因素对稳定性的影响。结 果表明：元胞数m,初始状态,规则数 R以及边界条件，均对初等元胞自动机的演化类

2、型，演化周期产生较大影响。充分反映了元胞自动机的复 杂性。模型从 模拟的角度出发，为元胞自动机的复杂性研究提供了一个简单的、可视的计算机仿真工具，并可为复杂的理论推导提供参考或验证。关键词:元胞自动机；界面；稳定性；边界条件 中图分类号：TP181文献标识码：AIn terface Desg n and Stability Anal ysis ofE lem entary Cell ular Auto mataGUO Juan WU D j ZHAO X ian- m ing(StateKey Laboratory of Rolling and Automation N ortheastern

3、U n iversty ShenyangL iaonng 110004 Ch ina) ABSTRACT : The visualization model and interface of elementary cellular automatawith all transition ruleswerede veloped and he application progran 1b r detem n ing he stability of one dmensional cellular automdion was desgned n th is paper Evo lution type

4、and per iodwere obtained from m odd d irectly Based on th is the evolution process and the stability w ith variant num ber of cells random n itia I configurations d ifferent transition rules and varied boundary conditions were analyzed respectvey It was shown that the nim ber of cells m, the initial

5、 configuration he trans- tion rule and the boundary cond ition had great influence on evolution type and period. And itw as concluded that he research prov i des an easyand v is ble computers mu lation method for com plexity suidy of cellu lar autDmatorn andthen offers reference or verification for

6、complex theoretical derivationKEYWORDS: Ce llular automata Interface Stability Boundary condition第26卷第7期计算机仿真2009年7月第26卷第7期计算机仿真2009年7月1引言元胞自动 机1,2 ( Cellu larA utomata简称CA)是由大量 简单一致的元素，通过简单的局部规则，组成的时间、空间和 状态变量都离散的动力学系统。它最早由Von Neumann等 人于20世纪40年代末最先提出，SW olfram对其进行了详细 的研究3,并对元胞自动机的演化结果进行分类。在此基础上,许多

7、学者从理论的角度研究了不同规则时的元 胞自动机演化过程及其稳定性 分析。H. Lee Y. Kawahara研究了满足 线性60规则的一维元胞自动机 ；T. Sato讨论了 27规则非 线性元胞 自动机5 ； S Inokuchi分析了 156规则元胞自动 机6, B. M artin研究了 54规则元胞自动 机7,邓婷等研究了 232规则一维CA的行为8；江志松等研究了规则数为122收稿日期：2008- 05- 12 修回日期：2008- 07- 03)178 )出的初等元胞自 动机的复杂性910。从理论的角度推导元胞自动机的稳定性 是一个复杂的 过程,通常局限于 某一种特定的规贝U。为此，

8、本文从计算机 模拟的角度，以MATLAB为开发工具建立了所有规则下的 初等元胞自动 机稳定性判断模型,设计了相应的界面,并分 析了不同元胞 数m,不同初始状态值,不同规则数R及不同 边界条件下各规则元胞自动机的稳定性，为复杂的理论推导 过程提供参考及验证工具。2基本理论及概念元胞自动 机是一个空间、时间以及 状态都离散 化的动力 学系统，由元胞、元胞的状态、邻居及局部 规则四部分组 成。 一维元胞自动机中的元 胞呈线性排列，元胞的状态 只有两种 选择,或者为/ 00,代表元胞为/死0,或者为/ 10,代表元胞为ina AIL rislits iserved- httpz/?wwiArrcBlc

9、i,nc图1初等元胞自动机的界面/生0。其邻居通常以邻域半径r确定,距离一个元 胞r距离内的所有元胞 均被认为是该元胞的邻居，称为一个邻域。r =1的一维元胞自动机，是最简单的元胞自动机，又称为初等 元胞自动机。初等元胞自动机 的局部规则可表示为：S：1 = f(S： 1, Si, S：+1 )(1)式中，S：, s：+1分别表示第i个元胞t时刻,t+ 1时刻的状 态值；S：1, S：+1分别表示第i个元胞左侧邻居，第i个元胞右侧 邻居t时刻的状态值。f是邻域元胞 的状态转 换函数。式(1) 表元胞t+ 1时刻的状态只与其本身及其左右邻居 t时刻的状 态有关。 194-2012 China A

10、cademic Journal lkctronic PublishingAll rights reserves表1局部规则f的标识t111110101 100011 010 001000t+ 11654r3r2r10初等元胞自动机中，啊寸刻一个邻域的 排列方式有8种， 对应的t+ 1时刻，中心元胞的状态值分别记为 ror7,如表 1所示。丘r,分别取/ 00或者/ 10,对应的规则数R定义为：760R = 2 r, + 2 r6 + , 2 r0(2)由式(2)知，规则数R可取为0255之间的整数，共256 种。全局变换规则 D由局部规则f决定。若总的元胞数为m,则 对应的全局变换规则 DD(

11、S1, S2, , Sm) = (f( A S*),f(S1, S2, S3), , , f(&-1, 5,B)(3)式中，ABSii Q1,Si为第K 1 i m )个元胞的状 态值。(A B)称为边界条件。边界条件为周期型时，A = Q, B=S1；边界条件为对称型时，A = S1, B= Sm；边界条件为固定 值时，A = 0 B = 0 或者 A = 1, B = 1。3 模型的建立 31界面设计在设计初等元胞 自动机时采用一个 m行，n列的二维数 组State存储数据，m为元胞数，n为时间步。在M atlab的figure 窗口中把轴划分为 m n个方格，每个格子对应数组 State

12、的 一个元素。第i( 1 i m)个元胞在t( 1 t n)时间步的 状态用 State(i, t)来表示。元胞状态为/活0时，State( j t)=1,显示为黑色的 点；元胞状态为/死0时，State( , t) = 0不 显示。根据模型所要实现的功能，设计界面如图1所示。界面包括三个初始条件 输入框，一个弹出菜单框,两个 控制按钮及图形输岀区。用户根据需要，在输入框中输入元胞数m,需要计算的时间步n规则数R,通过弹岀菜单选择边 界条件。可供选择的边界条件有4种:周期型边界条件；对称 型边界条件；固定值都为0的边界条件；固定值都为1的边界 条件。点击/ Plo0按钮,运行程序,在M atl

13、ab工作空间输出计 算结果，同时，在左侧绘图区输岀计算得到的图形。点击/ Close0按钮关闭界面。3 2稳定性判断模型对所有初等元胞自动机进行研究表明，其演化结果可分 为4类:1最后消失；o趋于一个不随时间演化的定态；？趋 于周期结构；？演化为更为复杂的结构。为判定元胞自动 机演化结果的稳定性，设计两个变量：Type变量用于记录图 形演化的类型。T变量用于记录图形演化的周期。若图形 最后消失，则显示Type为/ D isappea0,周期T = 1若图形最 后为固定结构，不随时间步的变化而变 化,则Type为/ Immo b周期T = 1;若图形成周期性排 列,则Type显示为/ Per-

14、odi(0,同时输出周期To若图形最后形成更为复杂的结果, 则Type显示为/ CompleX0, T= 0。其判断模型的N- S流程 图如图2所示。4模拟结果分析4. 1元胞数m不同时的稳定性分析元胞数m值过小，演化图容易失真；m值过大，则需要增 加模拟的时间 步n以保证能形成稳定结构的 模型在给定时 间步内即达到稳定状态。图3以周期型边界 条件,规则数R = 9为例，显示了不同m, n值时的演化图。观察知，图3a, 3c, 3d 中演化图均未 达到稳定，Type= -Complex。而图3b即显示 为T = 50的周期循环。即m, n值的合理选择对演化结果的稳 定性有很大 的影响。后续模拟

15、如不做 特殊说明，即表明m = 5Q n = 100,且边界条件为周期型。4 2初始状态值不同时的稳定性分析元胞的初始状态值是随机产生的，不同的初始状态值产 生不同的演化 结果。图4给出了规则数 R= 109时得到的演 化图。在随机产 生的初始状态值下，图4a 4b, 4c分别形成 周期为18 24和40的演化图，图4d在给定的时间步内，未达 到稳定结构。表明初始 状态值的选择，对元胞自动机的稳定 性有很大的影响。4 3 不同规则数R时的稳定性分析图5给出了规则数分另U为18 80 224 232时的演 化图。 观察知，图5a表现为较为复杂的结构；图5b表现为周期结)179)憾机中*人皓兄11

16、,捕果保存也敷组皿悅的梟】刊U J M *K.雷 -huM 1 !.h riH t* ml -X* *.!I- I - 3 _-l nh.hulrf- .4 H F H H dLh . HI- i. Jnu- J-! H- .if .s .rib M.- k- I h - -1 du a Adm A; 0r 罗 -J- IE fc-sr JFJJ Li 耳上P1 w羽尊33%巴r.w审 I-! .H- ! h.: I HL- I l.J; 可也-.=工話耳.:也|!:铲,.=禺3!:3构；图5C中元胞趋向 于消 失;图5d表现为固定结构。不同 的规则数产生不 同的构形,根据其演化模式的不同，可

17、将其 应用于模拟计算的各个方面。44不同边界条件下的稳定性分析图6显示了规则数为6时四种边界条件下的演化图。 在周期性边界条件下,图6a形成周期性排列，显示Type = -Periodic , T = 50;在对称性边界条件下，图形最终消失， Type= - D sappear, T= 1在固定值为/ 00的边界条件下，图 形演化为不随时间步变化的定态，Type= - Immoble , T = 1;）；”.180 ）_ * .品繼L址）R-224（d R-I12图5不同规则数的演化图在固定值为/ 10的边界条件下，图形呈周期性排列，Type = -Periodic.,但周期T= 4充分表明了

18、边界条件对初等元胞 自动机的稳定性产生的巨大影响。5结论1）本文开发了所有 规则下的初等元胞自动机的稳定性 判断模型及可 视化界面，用户根据需要，通过界面输入元胞 数m,时间步n规则数R,选择边界条件，即可直接观察演化 结果。2）在此基础上，设计了用于判断初等元胞自动 机稳定性 的应用程序，可自动对演化结果进行分类，并显示周期。同 时,分析了不同元胞数 m,不同初始状态，不同规则数 R以及 不同边界条件 对其稳定性的影响。结果表明，以上参数均对 初等元胞自动机的演化 类型,演化周期产生较大影响。充分 说明了元胞自动机的复杂性。3）本文从模拟的角度出发，为元胞自动机的复杂性研究:bins 丨1

19、窈|1客亡 All fights I eserved,hf thnk i. n e6 规则数M期P图- 邂*3心!;04玄宏龙,;,-r(.R= 6的演化图w ith linear ru le 60 J. Bu lletin of n Ibrmatics and Cybernetics 1992 (25): 22- 27.5 T Sato On behaviorsof cellularautomataw ith rule 27 J. Kyushu JMath 1996, (50): 133- 1526 S Inokuch. On b ehaviors of cellu ter automata

20、 with ru le 156 J.Bu lleti n of In fioimations and Cybernetics 1998 30(1): 121- 1317 B M artin A group interpretation of particles generated by one- d-im ensonal cellu ter autm atonwolfram. s rule 54 J. International Journal ofM odern Physics C, 2000,11( 1):101- 123.8 邓婷，等.232规则元胞自动机的稳定性J.广西科学，2003,

21、 10(4): 244 - 2489 江志松.122号初等元胞自动机的复杂性分析J.科学通报，2000, ( 18).10 江志松.122号元胞自动机的演化语言复杂性J.华东理工大学学报(自然科学版),2006, (4).)181)提供了一个简单的、的理论推导提供参考可视的计算机仿真工具。同时可为复杂 及验证。作者简介郭 娟（1981-）,女（汉族）,湖北省仙桃市人，东 北大学博士研究生，主要研究方向 是利用元 胞自动 机方法模拟组织演变 ；)181)参考文献：1 Von Neumann Theory of self- reproducing auton ataM . U rbana :Un

22、iversity of Illi no is Press 1966.2 D罗伯.计算材料学M .化学工业出版社,2002.3 SWolfran. Theory and A pplication of Cellular Au bmataM .Singapore W orld Scientific 19864 H Lee 丫 Kawahara On dynan ical behaviors of cellular automata吴 迪（1952-）,男（汉族）,辽宁绥中人，东北大学教授，博士生导师，从事型钢轧制理论与工艺研究,在孔型设计、计算机模拟与仿真、辅助孔型设计方面有专长，获省 级科技进步

23、奖 2项，发表论文60余篇，出版专著2部；赵宪明（1965-）,男（汉族）,辽宁桓仁人，东北大学教授，主要从事 钢铁材料组织性能预报、型钢理论、ANSYS模拟等方面的研究。)181)181)(上接第177页)参考文献：1 丫 W Liu, FM oses A sequential response surfacem ehod and its application n he reliability analysis of aircraft structural system J. Structu ral Safey 1994, 16 39- 46.2 V Baye, G I Schueller

24、 Discussion on A new look at the response su rface approach for reliability J. Struciu ralS alfety 1994, 16: 227 -2343 阎宏生，胡云昌，牛勇.基于神经网络响应面的结构可靠性分析方法研究J.海洋工程，2002, 20( 2): 1- 64 J D eng D S Gu, X B L i ZQ Yue. Structural reliability analysis for m pli cit perfom a nee un cti on s usi ng artificial n

25、 eural n etwork J. Structu ral Safey 2005, 27( 1): 25- 485 张义民，张雷.基于神经网络的结构可靠性优化设计J.应 用力学学报,2005 21 (1): 49- 54.6 L Schueren a ns D V Gemert Ben efit of Qi nes and n eural net works in simulation based structural reliability analysis J. Struc tu ral Safety, 2005 27(3): 246- 261.7 陈建英，张建仁.神经网络与响应面法相结

26、合分析既有混凝土桥梁的可靠性J.长沙理工大学学报(自然科学版)，2004, 1(3 4): 14.8 邓建，朱合华.基于神经网络的岩土工程结 构随机有 限元分析J.同济大学学报,2002, 30（3）: 269- 271.9徐军，张利民，郑颖人.基于数值模 拟和BP网络的可靠度计算方法J.岩石力学与工程学报，2003, 22（3）: 396.10吕震宙，杨子政.基于神经网络 的可靠 性分析新方法J.机械强度，2006 28（5）: 699 702作者简介尹婷婷（1983-）,女（汉族）,安徽人，西北工业大 学06级硕士研究生，主要研究方向为工程力学；高行山（1964-）,男（汉族）,陕西人博士 ,教授, 工程力学系主任,主要从事工程 力学、微/纳机电系 统力学、工程结构优化设计方面的研究工作；张 娟（1973 -）,女（汉族），陕西人，博士，副教授，主要研究方向 为航天器动力学与控制；赵玉龙（1982-）,男（汉族）,甘肃人，西北工 业大学06级硕士研究 生,主要研究方向为工程力学。)181)181) 1994-2() 12 Chitia Academic Journal lUecrronic Public HIP)181)